蓝桥杯-代码填空之四
最后更新于：2022-04-01 14:53:29
身份证校验—神秘三位数—生日相同概率—四方定理—因数分解—组合数
①身份证校验
如果让你设计个程序，用什么变量保存身份证号码呢？长整数可以吗？不可以！
因为有人的身份证最后一位是"X"
实际上，除了最后一位的X，不会出现其它字母！
身份证号码18位 = 17位 + 校验码
校验码的计算过程：
例如：身份证前17位 = ABCDEFGHIJKLMNOPQ
A~Q 每位数字乘以权值求和（每位数字和它对应的“权”相乘后累加）
17位对应的权值分别是：
7 9 10 5 8 4 2 1 6 3 7 9 10 5 8 4 2
求出的总和再对11求模
然后按下表映射：
余数 0 1 2 3 4 5 6 7 8 9 10
校验码： 1 0 X 9 8 7 6 5 4 3 2
~~~
char verifyCode(char* s)
{
static int weight[] = {7,9,10,5,8,4,2,1,6,3,7,9,10,5,8,4,2};
static char map[] = {'1','0','X','9','8','7','6','5','4','3','2'};
int sum = 0;
for(int i=0; i<17; i++)
{
sum += (______________) * weight[i]; // 填空
}
return map[____________]; // 填空
}
~~~
题目中已经清楚说明，要做什么了，分成两步，第一步求权值，求权值的总和，然后对11求模，
根据余数进行相应映射，唯一注意一点就是，进来的字符肯定不是整型，需要减去48(即‘0’).
答案：s[i] - '0' sum % 11
②神秘的三位数
有这样一个3位数，组成它的3个数字阶乘之和正好等于它本身。即：abc = a! + b! + c!
下面的程序用于搜索这样的3位数。
~~~
int JC[] = {1,1,2,6,24,120,720,5040,40320,362880};
int i;
for(i=100; i<1000; i++)
{
int sum = 0;
int x = i;
while(__________)
{
sum += JC[x%10];
x /= 10;
}
if(i==sum) printf("%d\n", i);
}
~~~
题意很清晰，解法也明了，用JC数组存0！~9！，判断符不符合条件，肯定要一位数一位数取出来，
那就像判断水仙花数一样，%10再/10的循环。
答案：x>0
③生日相同的概率
生活中人们往往靠直觉来进行粗略的判断，但有的时候直觉往往很不可靠。比如：如果你们班有30名同学，那么出现同一天生日的概率有多大呢？你可能不相信，这个概率高达70%左右。
以下的程序就是用计算机随机模拟，再统计结果。
~~~
#define N 30
......
int a[N];
srand( time( NULL ) );
int n = 0;
for(int k=0; k<10000; k++)
{
for(int i=0; i<N; i++)
a[i] = rand() % 365;
bool tag = false; // 假设没有相同
for(i=1; i<N; i++)
{
for(int j=0; j<i; j++)
{
if(a[i]==a[j])
{
tag = true;
break;
}
}
_____________________;
}
if(tag) n++;
}
printf("%f\n", 1.0 * n / 10000 * 100);
~~~
30个人，同一天生日概率高达70%，( ⊙o⊙ )哇！
言归正传，解题。这道题，其实我没怎么大看，就看到当tag为true时，n++，但是当tag为true时候，虽然break，里面有两层for，于是乎，恍然大悟鸟。。。有时候解题并非要全弄懂他的方法，比赛时间有限啊= 。=
答案： if(tag)break;
④四方定理
数论中有著名的四方定理：所有自然数至多只要用四个数的平方和就可以表示。
我们可以通过计算机验证其在有限范围的正确性。
对于大数，简单的循环嵌套是不适宜的。下面的代码给出了一种分解方案。
~~~
int f(int n, int a[], int idx)
{
if(______________) return 1; // 填空1
if(idx==4) return 0;
for(int i=(int)sqrt(n); i>=1; i--)
{
a[idx] = i;
if(_______________________) return 1; // 填空2
}
return 0;
}
int main(int argc, char* argv[])
{
for(;;)
{
int number;
printf("输入整数(1~10亿)：");
scanf("%d",&number);
int a[] = {0,0,0,0};
int r = f(number, a, 0);
printf("%d: %d %d %d %d\n", r, a[0], a[1], a[2], a[3]);
}
return 0;
}
~~~
大体一看代码结构，就知道，得，又是一道递归题目，递归方法，也不难理解，就是，原来数减去一个数的平方，再接着找，找的范围，也不用我们想，题目给了。递归结束条件，出了Idx肯定是n了，当n为0，代表找到了，不多说了，return 1。递归结束条件定是定了，可是，还有一个return 1，怎么办啊？
其实不难，仔细一想就明白了，for循环在找i,找到以后，肯定要向下递归下去，那肯定是要执行f函数了，执行f函数会返回值的，一个return0，一个return1，什么时候return1呢？必然就是当它返回1时，不断return1,回到主函数。
答案：n==0 f(n-i*i, a, idx+1) == 1
⑤因数分解
因数分解是十分基本的数学运算，应用广泛。下面的程序对整数n(n>1)进行因数分解。
比如，n=60, 则输出：2 2 3 5。请补充缺失的部分。
~~~
void f(int n)
{
for(int i=2; i<n/2; i++)
{
____________________
{
printf("%d ", i);
n = n / i;
}
}
if(n>1) printf("%d\n", n);
}
~~~
因数分解，简单吧？刚学语言的时候，肯定做过这种题目，蓝桥杯出的代码填空，对于我们大部分做过的题目，一般就会让我们来优化一下或者简洁一下代码，不可能，填我们原来做的时候的代码。
这道题，显然也是，你会发现i是一直在++的，例子中也出现了，有可能有两个2的情况。怎么回事呢？
我以前做用的是两个for，然后，找到以后i--，使得i再次为原值，进行判断。
除了for循环就剩下while了，所以咯，答案一跃而出啊。
答案：while(n%i==0)
⑥组合数
从4个人中选2个人参加活动，一共有6种选法。
从n个人中选m个人参加活动，一共有多少种选法？下面的函数实现了这个功能。
~~~
// n 个元素中任取 m 个元素，有多少种取法
int f(int n, int m)
{
if(m>n) return 0;
if(m==0) _______________;
return f(n-1,m-1) + _____________;
}
~~~
就是排列组合的问题嘛，4个人选2个，就是C四二。
n个人选m个就是Cnm
当m==0？ C30==C33==1咯，所以return 1
第二个空如果想不起来，你不妨看一下判断条件，出现m>n return 0，输入的内容不会有m>n的情况吧？
所以只能是，我们递归的时候出现啦。
答案： return 1 f(n-1,m)