《第七次上机总结》由会员分享，可在线阅读，更多相关《第七次上机总结（32页珍藏版）》请在金锄头文库上搜索。
1、第七次上机总结2012年11月26日第七次上机题目Exercise 7.1：约瑟夫环退出顺序Exercise 7.2：对于输入的任意unsigned int整数，输出其位的翻转Exercise 7.3：随机置换Exercise 7.1：约瑟夫环退出顺序通常来说，我们可以通过两种方式实现一个环：数组、数组链数组：利用额外变量存储数组长度，整数 i 记录当前位置，对 i 进行取模运算即可模拟一个环（具有12个刻度的闹钟、以及时针）数组链：对于一个数组，其数组元素存储下一个数组元素的对应下标。而环中人退出也有两种实现方式：标记、删除对于数组模拟的环而言，采用标记的方式更好对于数组链模拟的环而言，采用
2、移动的方式更恰当其他方式：数组存储剩下的人，每次都从0开始计数。出队一次，对数组元素重新排列一次#include#define NMAX 100int main() int aNMAX = 0; int n, m; int i = 0, j = 0, k; scanf(%d%d, &n, &m); while (j n) k = 0; while (k m) if (ai = 0) k+; if (k = m) printf(%d , i); ai = 1; if (i = n - 1) i = 0; else i+; j+; return 0;题1此段代码的功能是i自增，但其值不能不应大于等
3、于n。利用取摸运算即可i = (i + 1) % n。i, j的初始化与循环有关，故这里可将while语句修改为for语句：for (j = 0; j n; j+)在循环计数方面，for语句较while语句更为清晰。#includeint main() int i, j, k; int n, m, s101 = 0; scanf(%d %d, &n, &m); j = k = 0; for(i = 0; k n; i = (i + 1) % n) if(si = 0) if(j = m - 1) si = 1; printf(%d , i); +k; j = (j + 1) % m; retu
4、rn 0;判断逻辑过于臃肿，不易理解。两份工作正常，但不是太好的代码示例题1#include main() int n, m, k; int i, j; char a1000 = 0; scanf(%d%d, &n, &m); k = -1; for (i = 0; i n; i+) for (j = 0; j m; j+) do k = (k + 1) % n; while (ak); ak = 1; /j出列 printf(%d , k); return 0;思路：标记已经出列的人。外层循环表示需要n个人出列。#include int main() int i, n, m; char fl
5、ag1000; scanf(%d%d, &n, &m); for (i = 0; i n;+i) flagi = 1; int p = -1; for (i = 0; i n;+i) int total = 0; while (total m) p = (p + 1) % n; total += flagp; flagp = 0; printf(%d , p); return 0;题1#include main() int n, m, a1000, b1000, k; int i; scanf(%d %d, &n, &m); for (i = 1; i = n; i+) ai = i-1; w
6、hile (n != 0) k = m % n; if (k = 0) k = n; printf(%d , ak); for (i = k+1; i = n; i+) bi-k = ai; for (i = 1; i = k-1; i+) bn-k+i = ai; n-; for (i = 1; i = n; i+) ai = bi; return 0;思路：不断让编号为k = m % n的人出队。随后对a中的元素循环右移k位，以实现圈中人的重新编号（方框中的代码）。在每一轮循环开始的时候，a0总是第一个要数数的那个人。题1#include main() int n, m, p; int p
7、eople100; int i; scanf(%d %d, &n, &m); for(i = 0; i 0) p = (p - 1 + m) % n; printf(%d , peoplep); for(i = p + 1; i = n; +i) peoplei-1 = peoplei; n-; printf(n); return 0;思路：通过数组前移，不断将不再报数的人覆盖掉。最后n为0时，表示已经无人在圈中。显然，本题思路与上页解法大体相同，不过这里没有额外的内存开销。题1#include main() int i, j; int n, m, k; int p1000; scanf(%d
8、%d, &n, &m); for (i = 0; i n-1; i+) pi = i+1; pn-1 = 0; k = 0; for (i = 0, k = 0; i n; i+) for (j = 1; j m-1; j+) k = pk; printf(%d , pk); pk = ppk; k = pk; return 0;利用链表实现约瑟夫环想象在这个出环游戏中，每个人都用手拉着下一个人的手。pi存储的就是他的下一个人的编号。Exercise 7.2：位翻转直接对x进行操作：将第一位与最后位交换，第二位与倒数第二位交换，执行16轮。或者：取x最低位，x右移，然后将最低位放置于x最高位；
9、执行32轮。或者：取数x的最低位，加到临时变量t的最低位；执行完之后x右移、t左移；执行32轮。其中t初值为0，x为要处理的数。递归方式，只需5次操作题2#include unsigned move(unsigned x, int n) return (n 0) ? x -n;main () unsigned a, b, t; scanf(%u, &a); b = 0; for (int i = 0; i 32; i+) t = a & move(1, i); b|= move(t, 31-2*i); printf(%u, b); return 0;#include main() const
10、W = 32; unsigned m, n, t; scanf(%u, &m); n = 0; for (int i = 0; i W; i+) t = m & (1 i) (W - i - 1); printf(%un, n); return 0;参考教材P187，此处W默认为int。关键字const的作用是为读你代码的人传达有用信息。合理地使用关键字const可以使编译器保护那些不希望被改变的参数，如果你后续代码中改变了这个变量的值，那么代码将无法通过编译。显然，这样可以减少bug的出现。题2#include #include main() int i, j; unsigned int n
11、, m, k; scanf(%u, &n); m = 0; for (i = 0; i 32; i+) m = 1; printf(%un, m); return 0;#include main() unsigned n, m; int bitlength, i; scanf(%u, &n); bitlength = sizeof(n) * 8; m = 0; for (i = 0; i bitlength; i+) m = (m = 1; printf(%u, m); return 0;题2#include main() unsigned x; scanf(%u, &x); x = (x&0
12、xAAAAAAAA)1 | (x&0x55555555)2 | (x&0x33333333)4 | (x&0x0F0F0F0F)8 | (x&0x00FF00FF)16| (x&0x0000FFFF)16; printf(%u, x); return 0;Exercise 7.3：随机置换思路1：生成一个随机数，将其与之前所有数进行比较数组存储结果，循环比较数组存储标志，散列发直接映射思路2：利用数组存储0n-1，然后随机乱序，将乱序结果顺序输出思路3：按一定规则将n!种排列与1n!一一对应，随机生成1, n!中的一个数，输出对应排列main() int n, k, r, num1000; s
13、rand(time(0); scanf(%d, &n); for (k = 0; k n;) r = rand() % n; if (check(r, num, k) printf(%d , r); numk+ = r; printf(n); return 0;题3朴素解法，对每次生成的随机数，都通过check函数判断这个数之前有没有生成过。#include #include #include int check( int r, int* num, int k) for (int i = 0; i k; +i) if (r = numi) return 0; return 1;题3#inclu
14、de #include #include main() int n, i, s; int a100 = 0; scanf(%d, &n); srand(time(NULL); s = 0; while (s n) i = rand() % n; if (ai = 0) printf(%d , i); ai = 1; s+; return 0;co虽然利用标志数组能快速的判断一个数是否已经出现过，但程序还是比较慢，因为越到后面就a中未标志的元素就越少。while (ai) i = (i + 1) % n;printf(%d , i);ai = 1;s+;常见写法为srand(unsigned)t
15、ime(NULL);其中的强制转换不一定是必须的，因为函数传参的时候会自动转换。NULL是一个定义在stdio.h中的宏，是空指针的意思，其值为0。题3：补充在VC 6.0中，以下代码会有编译错误#include #include int main()int* p = NULL;srand(p);错误为：cannot convert parameter 1 from int * to unsigned int。即不能将srand函数的第一个实参从int *转换为unsigned int。所以为了避免编译错误，上页中的代码还是写为srand(unsigned)time(NULL);较为安全。题3
16、#include #include #include main() int i, n, q, num1000; srand(time(0); scanf(%d, &n); for (i = 0; i 0) q = rand() % n; printf(%d , numq); for (i = q; i n-1; i+) numi = numi+1; n-; return 0;沿用解约瑟夫环的思路，不断随机出队一个数。每次输出一个数之后就“删除”这个数（通过向前移动一位覆盖已输出的数）。题3 for (i = n - 1; i; i-) m = rand() % i; temp = numi;
17、numi = numm; numm = temp; for (i = 0; i n; i+) printf(%d , numi); printf(n); return 0;#include #include #include main() int n, m, i, temp; int num1000; scanf(%d, &n); srand(time(0); for (i = 0; i b+c，那么这一定是一个合法三角形。而在上述条件下，有a=c，那么这一定是一个等边三角形；有b=c，这一定是一个等腰三角形；有a*a = b*b + c*c，则是一个直角三角形。由于一个合法的三角形可能是属于
18、多种三角形类型，因此可以使用组合的方式来记录三角形的类型。常见的方式是用二进制位来记录。题1：题目分析显然，判断一个三角形的流程如下1.读入三条边2.处理三条边3.判断三角形类型4.根据结果输出对应结果其中第2步主要涉及两个数的交换，可以编写函数实现之，第3两步显然应该从主函数中剥离，独立构成一个函数显然，判断三角形类型的函数judge的返回值需要认真设计题1int main() int a, b, c; char flag; scanf(%d%d%d, &a, &b, &c); if (a b) s, &b); if (a c) s, &c); flag = judge(a, b, c);
19、if (flag & 1) printf(illegal ); else if (flag & 2) printf(isosceles ); if (flag & 4) printf(equilateral ); if (flag & 8) printf(right ); if (flag = 0) printf(normal ); printf(triangle.n); return 0;#include void s* a, int* b) int t = *a; *a = *b; *b = t;char judge(int a, int b, int c) char type = 0;
20、/用位记录信息 if (a = b + c) type |= 1; if (b = c) type |= 1 2; if (a = c) type |= 1 4; if (a*a = b*b + c*c) type |= 1 8; return type;Exercise 8.2：计算多项式的值正如提示所言，本题和进制转换本质上是相通的我们也可以事先计算x的各次幂，并存储计算结果，这样也能简化计算题2#include double power(int x, int y) double r = 1; for(int i = 0; i y; +i) r *= x; return r;main()
21、int coefficient8 = 15, 11, 9, 1, 3, 6, 5, 7; int exponent8 = 1, 2, 4, 5, 11, 12, 13, 16; double sum = 0, t; int x; scanf(%d, &x); for(int i = 0; i 8; +i) t = power(x, exponenti); sum += t * coefficienti; printf(%.2fn, sum); return 0;double power(int x, int y) switch (y) case 0: return 1; case 1: ret
22、urn 2; default: double m = power(x, y/2); if (y % 2 = 0) return m*m; else return m*m*x; 或题2#include main() int c8 = 15, 11, 9, 1, 3, 6, 5, 7; int e8 = 1, 2, 4, 5, 11, 12, 13, 16; double sum, x; int i, j; scanf(%lf, &x); sum = c7; for (i = 6; i = 0; i-) for (j = ei; j ei+1; j+) sum *= x; sum += ci; s
23、um *= x; printf(%.2f, sum); return 0;题2#include #include int main() double c8 = 15, 11, 9, 1, 3, 6, 5, 7; int e8 = 1, 2, 4, 5, 11, 12, 13, 16; double f8; int x; scanf(%d, &x); double t = 1; for (int i = 0, j = 0; i = e7; i+) if (i = ej) fj+ = t; t *= x; t = 0; for (i = 0; i = 7; +i) t += ci * fi; pr
24、intf(%.02fn, t); return 0;这里假设了指数项是递增有序的，即最后一项值最大。Exercise 8.3：输出杨辉三角最直接的解法是利用组合数的定义计算输出或者利用条件“任意一项为其上方两项之和”，简化计算。采用二维数组存储所有的结果采用一个数组记录所在行的结果，输出之后将其处理为下一行的结果可以等处理之后再输出也可以一边处理一遍输出题3main() int m, n; for (m = 0; m 10; +m) for (n = 0; n = m; +n) printf(%d , combinations(m, n); printf(n); return 0;#inclu
25、de #include int factorial(int a) int sum = 1; while (a 0) sum *= a-; return sum;int combinations(int m, int n) int t1 = factorial(m); int t2 = factorial(n)*factorial(m-n); return t1 / t2;题3#include main() int f200200 = 1; for (int i = 1; i = 10; +i) for (int j = 1;j = i; +j) printf(%d , fij = fi-1j-
26、1 + fi-1j); printf(n); return 0;题3#include main() int a10 = 1; int i, j; printf( 1n); for (i = 1; i 0; j-) aj = aj + aj-1; for (j = 0; j = i/2; j+) ai-j = aj; for (j = 0; j = i; j+) printf(%3d , aj); printf(n); return 0;利用杨辉三角的对称性。题3for(j = 1; j = i; j+) q = aj; aj = p + q; p = q; printf(%d , aj); printf(n);#includemain() int a100 = 0; int i, j; for(a0 = i = 1; i 10; i+) for(j = i-1; j; j-) printf(%3d, aj += aj-1); printf( 1n); return 0;为什么两个for循环外侧的printf语句要输出的内容不一样？
