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 在运行时

• 堆栈段：程序动态创建，保存函数调用关系 和 局部变量
• 因此栈溢出不一定是递归调用太多，也可能是局部变量太大