第一章 程序设计入门.

Presentation on theme: "第一章 程序设计入门."— Presentation transcript:

1 第一章 程序设计入门

2 1.1 算数表达式 计算 1+ 2 3 5−0.1 输出保留8位小数的实数 换行符 整数先“变”为浮点数，然后浮点数-浮点数=浮点数
计算 −0.1 输出保留8位小数的实数 %0.2f 保留2位小数的float型 %d int型 %lf double型 %s 字符串 # include <stdio.h> int main() { printf(“%.8f\n”, * sqrt(3) / ( )); return 0; } include <math.h> 换行符 整数先“变”为浮点数，然后浮点数-浮点数=浮点数 直接结束 System(“pause”) 按任意键退出 竞赛中不要让程序“按任意键退出”

3 1.2 变量及其输入 计算圆柱体表面积 s = πr2+2πrh 样例输入： 3.5 9 样例输出： Area = 274.889
# include <stdio.h> int main() { const double pi = acos(-1.0); double r, h, s1, s2, s; scanf(“%lf%lf”, &r, &h); s1 = pi * r * r; s2 = 2 * pi * r * h; s = s1 * s2; printf(“Area = %.3f\n”, s); return 0; } include <math.h> 读取double型变量到r和h

4 1.3 顺序结构程序设计 三位数反转 样例输入： 127 读取int型变量到r和h 样例输出： 721 n对10取余 n除以10后取余
# include <stdio.h> int main() { int m, n; double r, h, s1, s2, s; scanf(“%d”, &n); printf(“%d%d%d\n”, n % 10, n / 10 % 10, n / 100); return 0; } n对10取余 n除以10后取余

5 1.4 分支结构程序设计 Is this solution correct? What if the input is 1 1 1？
三整数排序 样例输入： 样例输出： # include <stdio.h> int main() { int a, b, c; scanf(“%d%d%d”, &a, &b, &c); if(a <= b && b <= c) printf(“%d %d %d\n”, a, b, c); if(a <= c && c <= b) printf(“%d %d %d\n”, a, c, b); if(b <= a && a <= c) printf(“%d %d %d\n”, b, a, c); if(b <= c && c <= a) printf(“%d %d %d\n”, b, c, a); if(c <= b && b <= a) printf(“%d %d %d\n”, c, b, a); return 0; } # include <stdio.h> int main() { int a, b, c; scanf(“%d%d%d”, &a, &b, &c); if(a < b && b < c) printf(“%d %d %d\n”, a, b, c); if(a < c && c < b) printf(“%d %d %d\n”, a, c, b); if(b < a && a < c) printf(“%d %d %d\n”, b, a, c); if(b < c && c < a) printf(“%d %d %d\n”, b, c, a); if(c < b && b < a) printf(“%d %d %d\n”, c, b, a); return 0; } No! Is this solution correct? What if the input is 1 1 1？

6 1.5 注解与习题 实验A1： 表达式11111*11111的值是多少？5个1改成6个1呢？9个1呢？
实验A2：把实验A1中的所有数换成浮点数，结果如何？ 实验A3：表达式sqrt(-10)的值是多少？尝试用各种方式输出 实验A4：表达式1.0/0.0、0.0/0.0的值是多少？ 实验A5：表达式1/0的值是多少？

7 第二章 循环结构程序设计

8 2.1 for 循环 输出所有形如aabb的4位完全平方数（即前两位数字相等，后两位数字也相等）。 没有判断语句，x调整后直接进入循环
for(;;)死循环，若不采取措施（如break），将永远不结束 # include <stdio.h> int main() { 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”, n); } return 0; continue 跳回for循环的开始，执行调整语句并判断循环条件（即直接进入下一次循环） break 直接跳出循环

9 2.2 while循环和do-while循环 对于任意大于1的自然数，若n为奇数，则将n变为3n+1，否则变为n的一半。经过若干次这样的变换，一定会使n变为1。例如，3->10->5->16->8->4->2->1 输入n，输出变换的次数。n <= 109。 样例输入： 3 样例输出： 7 # include <stdio.h> int main() { int n2, count = 0; scanf(“%d\”, &n2); long long n = n2; while(n > 1) if(n % 2 == 1) n = n * 3 + 1; else n /= 2; count++; } printf(“%d\n”, count); return 0; # include <stdio.h> int main() { int n, count = 0; scanf(“%d\”, &n); while(n > 1) if(n % 2 == 1) n = n * 3 + 1; else n /= 2; count++; } printf(“%d\n”, count); return 0; n /= 2 n = n / 2 n *= 2 n = n * 2 有bug！当输入 时答案为1，显然这是一个合法输入，<=109 n = n*3+1 时乘法溢出，int [-231, 231-1] 使用数据类型long long来解决

10 2.3 循环的代价 阶乘之和。计算S = 1! + 2! + 3! + …… +n!的末6位（不含前导0）。n<=106。n!表示前n个正整数之积。 样例输入： 10 样例输出： 37913 程序运行时间大致和n的平方成正比，n = 106时大致需要近5个小时才能完成。 从40开始，答案始终不变。因为25!末尾有6个0，所以从第5项开始，后面的所有项都不会影响和的末6位数字。n>25时可直接输出结果。

11 2.4 算法竞赛中的输入输出框架 Is this solution correct? 返回成功输入的变量个数 n != 0 时继续以下操作
数据统计。输入一些整数，求出它们的最小值、最大值和平均值（保留3位小数）。输入保证这些数都是不超过1000的整数。 输入包含多组数据，每组数据第一行是整数个数n，第二行是n个整数。N=0为输入结束标记，程序应当忽略这组数据。相邻两组数据之间应输出一个空行 # define INF int main() { int x, n = 0, min = INF, max = -INF, s = 0, kase = 0; while(scanf(“%d”, &n) == 1 && n) int s = 0; for(int i = 0; i < n; i++){ scanf(“%d”, &x); s += x; if(x < min) min = x; if(x > max) max = x; } if(kase) printf(“\n”); printf(“Case %d: %d %d %.3f\n”, ++kase, min, max, (double)s/n); return 0; include <stdio.h> 样例输入： 8 4 样例输出： Case 1： Case 2： 返回成功输入的变量个数 n != 0 时继续以下操作 Is this solution correct? No! min和max没有“重置”，仍然是上个数据结束后的值！

12 2.5 作业

13 第三章 数组和字符串

14 3.1 数组 开灯问题。有n盏灯，编号为1~n。第1个人把所有灯打开，第2个人按下所有编号为2的倍数的开关（这些灯将被关掉），第3个人按下所有编号为3的倍数的开关（其中关掉的灯将被打开，开着的灯将被关闭），以此类推。一共有k个人，问最后又哪些灯开合？输入n和k，输出开着的灯的编号。k<=n<=1000。 # include <string.h> #define maxn 1010 int a[maxn] int main() { int n, k, first = 1; memset(a, 0, sizeof(a)); scanf(“%d%d”, &n, &k); for(int i = 1; i < = k; i++) for(int j = 1; j < = n; j++) if(j % i == 0) a[j] = !a[j]; for(int i = 1; i < = n; i++) if(a[i]){ if(first) first = 0; else printf(“ ”); printf(“%d”, i); } printf(“\n”); return 0; include <stdio.h> 标志变量，表示当前要输出的变量是否为第一个， 第一个前不应有空格 清零数组a

15 3.2 字符数组 sprintf 输出到字符串 strchr 在一个字符串中查找单个字符
竖式问题。找出所有形如abc*de（三位数乘以两位数）的算是，使得在完整的竖式中，所有的数字都属于一个特定的数字集合。输入数字集合（相邻数字之间没有空格），输出所有竖式。每个竖式前应有编号，之后应有一个空行。最后输出解的总数。具体格式见阳历输出（为了便于观察，竖式中的空格改用小数点显示，但缩写程序中应该输出空格，而非小数点。 # include <string.h> int main() { int count = 0; char s[20], buf[99]; scanf(“%s”, s); for(int abc = 111; abc < = 999; abc++) for(int de = 11; de < = 99; de++) int x = abc * (de % 10), y = abc * (de / 10), z = abc * de; sprintf(buf, “%d%d%d%d%d”, abc, de, x, y, z); int ok = 1; for(int i = 0; i < strlen(buf); i++) if(strchr(s, buf[i]) == NULL) ok = 0; if(ok) printf(“<%d>\n”, ++count); printf(“%5d\nX%4d\n-----\n%5d\n%4d\n-----\n%5d\n\n”, abc, de, x, y, z); } printf(“The number of solutions = %d\n”, count); return 0; include <stdio.h> 样例输入： 2357 样例输出： <1> ..775 X..33 ----- .2325 2325. 25575 The number of solutions = 1 sprintf 输出到字符串 strchr 在一个字符串中查找单个字符

16 3.3 竞赛题目选讲 回文词。输入一个字符串，判断它是否为回文串以及镜像串。输入字符串保证不含数字0。
所谓回文串，就是反转以后和原串相同，如abba和madam。 所谓镜像串，就是左右镜像之后和原串相同，如2S和3AIAE。注意，并不是每个字符在镜像之后都能得到一个合法字符。在本体中，每个字符的镜像如图所示

17 3.3 竞赛题目选讲 镜像字符 自定义函数，返回ch的镜像字符 判断是否为字母 样例输入： NOTAPALINDROME
# include <string.h> const char* rev = “A 3 HIL JM O 2TUVWXY51SE Z 8 ” const char* msg[] = {“not a palindrome”, “a regular palindrome”, “a mirrored string”, “a mirrored palindrome”}; char r(char ch){ if(isalpha(ch)) return rev[ch – ‘A’]; return rev[ch – ‘0’ + 25]; } int main() { char s[30]; scanf(“%s”, s); while(scanf(“%s”, s) == 1){ int len = strlen(s); int p = 1, m = 1; for(int i = 0; i < (len + 1) / 2; i++) if(s[i] != s[len-1-i]) p = 0; //不是回文串 if(r(s[i]) != s[len-1-i]) m = 0; //不是镜像串 printf(“%s – is %s.\n\n”, s, msg[m * 2 + p]); return 0; include <stdio.h> include <ctype.h> # 样例输入： NOTAPALINDROME ISAPALINILAPASI 2A3MEAS ATOYOTA 样例输出： NOTAPALINDROME – is not a palindrome. ISAPALINILAPASI – is a regular palindarome. 2A3MEAS– is a mirrored string. ATOYOTA – is a mirrored palindrome. 自定义函数，返回ch的镜像字符 判断是否为字母

18 3.5 作业