Tips
- 学习算法最好的方法并不是编写程序，而是手算
- 千万不要图快——如果没有足够的时间来实践，那么学的快，忘的也快
- 手工模拟的方法重点在于：记录每条语句执行之后各个变量的值
- 黑盒测试：只考察解决问题的能力，而不关心采用了什么方法
- 伪代码：在实际应用中并不太拘泥于伪代码的格式，主要目的是描述算法梗概，避开细节，启发思路
- 尽量缩短变量的定义范围
- 变量在未赋值前是不确定的，特别的，它不一定等于 0
- Keep It Simple and Stupid 保持程序简单
0. 管道机制
作用：把不同的程序串联起来
例如：程序 aplusb 作用是读入两个整数a,b，返回 a+b 的值 程序 sqr 作用是读入一个整数 a，返回 a*a 的值
用管道机制表示为
echo 10 20 | ./aplusb | ./sqr- 格式
echo 传入参数 | ./接收函数 | ./接收函数 …
1. 精确数值
const double pi = acos(-1.0); //精确取 π 值
//输出所有形如aabb的完全平方数。注意：a 的范围是1 ~ 9，但 b可以是 0
//方法一：
for(int a=0; a<=9; a++)
{
for(int b=0; b<=9; b++)
{
int n = a*1100+b*11;
int m = floor(sqrt(n)+0.5);
if(m*m == n) printf(“%d\n”, n);
}
}
//floor函数只取整数位，小数位舍弃
//floor(x+0.5)为了四舍五入 不过这样小数部分0.5也会有误差
//因此不能写 if( sqrt(n) == floor(sqrt(n)) ) printf(“%d\n”,n);
//方法二：
for(int x=1; ;x++)
{
int n = x*x;
if (n < 1000) continue;
if (n > 9999) break;
int hi = n/100;
int lo = n%100;
if(hi/10 == hi%10 && lo/10 == lo%10) printf(“%d”,n);
}
2. 输入输出框架
每次输入输出用标准输入「键盘输入」输出「显示器输出」太过于繁琐 采用输入输出数据存放在文件中来避免这种繁琐
//输入一些整数，求出它们的最小值、最大值和平均值（保留3位小数）
//输入保证这些数都是不超过1000的整数
//方法一：重定向
#define LOCAL //注意：这里的宏定义即便没有赋值 也算定义了LOCAL
#include<stdio.h>
#define INF 1000000000
int main()
{
#ifdefin LOCAL
freopen("data.in","r",stdin);//从这里开始所有键盘的输入改用文件
freopen("data.out","w",stdout);//从这里开始所有键盘的输出改用文件
#endif
int x,n=0,min=INF,max=-INF,s=0;
while(scanf("%d",&x) == 1)
{
s += x;
if(x<min) min = x;
if(x>max) max = x;
//printf("x=%d, min=%d, max=%d\n", x, min, max);
n++;
}
printf("%d %d %.3f\n", min, max, (double)s/n);
return 0;
}
//方法二：fopen
#include<stdio.h>
#define INF 1000000000
int main()
{
FILE fin, fout;
fin = fopen("data.in","rb");//fopen方法较灵活
fout = fopen("data.out","wb");//fin = stdin 便能切换到标准输入
int x, n=0, min = INF, max = -INF, s=0;
while(fscanf(fin, "%d", &x) == 1)
{
s += x;
if(x < min) min = x;
if(x > max) max = x;
n++;
}
fprintf(fout, "%d %d %.3f\n", min, max, (double)s/n);
fclose(fin);
fclose(fout);
return 0;
}
3. 细节注意
C语言中 数据有不同的类型，因此 关系运算符 == 和 != 有严格的规定，必须同时考虑 数据类型 和 数值大小
4. 关于 段
段：二进制文件内 的区域，所有特定类型信息被保存在里面
4.1 在可执行文件中
- 正文段：存储指令
- 数据段：存储全局变量「已初始化的」
- BSS段：存储全局变量所需的空间「未初始化的」
4.2 在运行时
- 堆栈段：程序动态创建，保存函数调用关系 和 局部变量
- 因此栈溢出不一定是递归调用太多，也可能是局部变量太大
