两道代码填空,三道编程大题
1 2 3 4 5 | 组合数(8分) 自首数(15分) 猜算式(16分) 魔方(28分) 最小距离(33分) |
组合数
从4个人中选2个人参加活动,一共有6种选法。
从n个人中选m个人参加活动,一共有多少种选法?下面的函数实现了这个功能。
请仔细分析代码,填写缺少的部分(下划线部分)。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 | #include <stdio.h> int f(int n, int m) { if(m>n) return 0; if(m==0) return 1; return f(n-1,m-1) + f(n-1,m); } int main(int argc, char *argv[]) { int m, n; scanf("%d%d", &n, &m); printf("%d\n", f(n, m)); return 0; } |
自首数
如果一个自然数的平方数的尾部仍然为该自然数本身,则称其为自守数。
例如:
5 x 5 = 25
76 x 76 = 5776
625 x 625 = 390625
下面代码的目的是寻找出2千万以内的所有自守数。
注意,2千万的平方已经超出了整数表达的最大范围,所以该程序使用了一个巧妙的方案。
如果我们仔细观察乘法的计算过程,就会发现实际上对乘积的尾数有贡献的环节,从而不用真正计算出整个乘积。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 | #include <stdio.h> int main(int argc, char *argv[]) { int n, n2, k, m; for(n=1; n<20 * 1000 * 1000; n++) { n2 = n; m = 0; for(;;) { if(n2==0) { printf("%d\n", n); break; } k = n2 % 10; // 从末尾开始,取出乘数的每位数字 m += k * n; // 累计乘积 if(m%10 != k) break; m = m / 10; // 舍去累计乘积的末位 n2 = n2/10; } } return 0; } |
猜算式
看下面的算式: □□ x □□ = □□ x □□□
它表示:两个两位数相乘等于一个两位数乘以一个三位数。
如果没有限定条件,这样的例子很多。
但目前的限定是:这9个方块,表示1~9的9个数字,不包含0。
该算式中1至9的每个数字出现且只出现一次!
比如:
46 x 79 = 23 x 158
54 x 69 = 27 x 138
54 x 93 = 27 x 186
.....
请编程,输出所有可能的情况!
注意:左边的两个乘数交换算同一方案,不要重复输出!
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 | #include <stdio.h> int is_ok(a, b, c, d) { int i, j, v[10]; for (i=1; i<10; i++) v[i]=0; v[a/10]=1; v[a%10]=1; v[b/10]=1; v[b%10]=1; v[c/10]=1; v[c%10]=1; v[d/100]=1; v[d%10]=1; v[d/10%10]=1; for (i=1; i<10; i++) if (v[i]==0) return 0; return 1; } int main(int argc, char *argv[]) { int i, j, k; for (i=10; i<100; i++) for (j=i+1; j<100; j++) for (k=10; k<100; k++) if ( i*j % k ==0 && is_ok(i, j, k, i*j/k )) printf("%dx%d=%d*%d\n", i, j, k, i*j/k); return 0; } |
魔方
最小距离