蓝桥杯-代码填空之三
最后更新于：2022-04-01 14:53:22
连续和的平方数—排列的个数—巧放棋子—取中间数字—去掉重复字母—日历天数之差
①连续和的平方数
1+3 = 4, 1+3+5 = 9, 1+3+5+7 = 16 它们的结果都是平方数。
这是偶然的巧合吗？下面代码验证对于累加至1000以内的情况都成立。
~~~
int n = 1;
for(int i=1; i<1000/2; i++)
{
n += 2 * i + 1;
int m = ______________;
if( m * m != n)
{
printf("加至%d 时不成立！\n", 2 * i + 1);
break;
}
}
~~~
连续和的平方数，我刚开始还在那找规律，发现 n最后加上的数字再加1 再除以2 所得到的数的平方就是最后那个平方数， 化简下来： (2*i+1+1)/2=i+1 然后突然发现我二了= 。=
答案：i+1
②排列的个数
计算3个A，2个B可以组成多少种排列的问题（如：AAABB, AABBA）是《组合数学》的研究领域。
但有些情况下，也可以利用计算机计算速度快的特点通过巧妙的推理来解决问题。
下列的程序计算了m个A，n个B可以组合成多少个不同排列的问题。
~~~
int f(int m, int n)
{
if(m==0 || n==0) return 1;
return _______________________;
}
~~~
这道题，一看就知道递归题目了，做了这么多代码填空题我也发现了，看见只给一个函数，最上面还有一些判断，return的，一般跑不了递归。在本上画一画，算一算，不难求出来。
答案： f(m-1,n)+f(m,n-1)
③巧放棋子
今有 6 x 6 的棋盘格。其中某些格子已经预先放好了棋子。
现在要再放上去一些，使得：每行每列都正好有3颗棋子。
我们希望推算出所有可能的放法。
初始数组中，“1”表示放有棋子，“0”表示空白。
~~~
int N = 0;
bool CheckStoneNum(int x[][6])
{
for(int k=0; k<6; k++)
{
int NumRow = 0;
int NumCol = 0;
for(int i=0; i<6; i++)
{
if(x[k][i]) NumRow++;
if(x[i][k]) NumCol++;
}
if(_____________________) return false; // 填空
}
return true;
}
int GetRowStoneNum(int x[][6], int r)
{
int sum = 0;
for(int i=0; i<6; i++) if(x[r][i]) sum++;
return sum;
}
int GetColStoneNum(int x[][6], int c)
{
int sum = 0;
for(int i=0; i<6; i++) if(x[i][c]) sum++;
return sum;
}
void show(int x[][6])
{
for(int i=0; i<6; i++)
{
for(int j=0; j<6; j++) printf("%2d", x[i][j]);
printf("\n");
}
printf("\n");
}
void f(int x[][6], int r, int c);
void GoNext(int x[][6], int r, int c)
{
if(c<6)
_______________________; // 填空
else
f(x, r+1, 0);
}
void f(int x[][6], int r, int c)
{
if(r==6)
{
if(CheckStoneNum(x))
{
N++;
show(x);
}
return;
}
if(______________) // 已经放有了棋子 // 填空
{
GoNext(x,r,c);
return;
}
int rr = GetRowStoneNum(x,r);
int cc = GetColStoneNum(x,c);
if(cc>=3) // 本列已满
GoNext(x,r,c);
else if(rr>=3) // 本行已满
f(x, r+1, 0);
else
{
x[r][c] = 1;
GoNext(x,r,c);
x[r][c] = 0;
if(!(3-rr >= 6-c || 3-cc >= 6-r)) // 本行或本列严重缺子，则本格不能空着！
GoNext(x,r,c);
}
}
int main(int argc, char* argv[])
{
int x[6][6] = {
{1,0,0,0,0,0},
{0,0,1,0,1,0},
{0,0,1,1,0,1},
{0,1,0,0,1,0},
{0,0,0,1,0,0},
{1,0,1,0,0,1}
};
f(x, 0, 0);
printf("%d\n", N);
return 0;
}
~~~
这道题代码不短，莫慌莫急，慢慢缕一缕就很好解决了，
先看最下面的空，后面还有注释： 本格有棋子，那还用想填什么吗？当然是当数组内数为1的时候啊。
再看倒数第二个，下面那个else是r+1,然后c归0，显然是换行操作，什么时候需要换行？肯定读到末尾了，
就是c>6的时候。
再看第一个，乍一看，真不懂，回程序找找哪里出现这个函数调用，发现调用这个函数，返回1的时候N自增，
就是棋子的数目增加一个了，那就简单了，肯定是判断该行，该列棋子是否都为3了。如果符合这个条件，就
可以放棋子，棋子总数++。
答案：
~~~
NumRow!=3 || NumCol!=3
f(x, r, c+1)
x[r][c] 或 x[r][c]==1
~~~
④取中间数字
假设a,b,c是3个互不相等的整数。下列代码取出它们中居中的数值，记录在m中。
其中的swap()函数可以交换两个变量的值。
~~~
if(a>b) swap(&a, &b);
if(b>c) swap(&b, &c);
______________________;
int m = b;
~~~
这题目，很容易理解吧，互不相等的整数，取中间那个，肯定三个数需要两两比较，
第一个if进行了a,b 比较，第二个if 进行 b,c比较，
第三个肯定也需要比较一次，是比较a,b呢还是b,c呢？
可以这样看:
如果a<b， 第一个If没有执行，b与c比较，b是b,c中小的那个，那么肯定需要再与a比较一次，要去中间的嘛。
如果a>b，第一个if执行，再将b,c比较，b依旧是较小的那个，b,c中较小的再与原来的b即现在的a比较，取中间。
上面的话，是不是很绕啊。。。
就是因为b,c比较在后，肯定无法与a,b中较大的数比较，所以要增设一个a,b比较。
实在不理解可以列几组数据来算一下。
答案： if(a>b) swap(&a,&b)
⑤去掉重复字母
给定一个串，例如“aabbbcddddkkkmmmmaakkkk”我们希望去掉连续的重复字母，
得出串：“abcdkmak”，下面代码实现了该功能，请完善之。
~~~
char* p = "aabbbcddddkkkmmmmaakkkk";
char buf[100];
char* q = p;
int i=0;
for(;*q;)
{
if(___________|| *q != *(q-1))
{
buf[i++] = *q;
}
q++;
}
buf[i] = '\0';
printf("%s\n", buf);
~~~
任务明确，代码完整， 将不重复的字符存到buf数组中，q指向p头部即a的位置， for循环第一第三条件空缺，判断q是否等于NULL， 什么情况下 会将指针q的内容赋值给buf呢？if已经写一半了，就是当当前指针指向的内容不等于之前指针指向的内容的时候，会赋值，这就有一个问题了，如果指针指向第一个位置，怎么办？所以空缺的地方显而易见了。
答案：p==q
⑥日历天数差
人类历史上出现了很多种历法。现行的公历即格里历由儒略历改革而来。它是目前较为精确和规则简明的一种历法，约3300年误差一日。因为闰年问题以及每个月的长度不等，仍然使得某些计算较为麻烦。
比如：求两个日期间差多少天。
下面的代码实现了求两个由公历表示的日期间差多少天的功能。
其计算原理是先求出每个日期距离1年1月1日的天数差值，再进一步做差即可。
请研读代码，填写缺失的部分。
~~~
struct MyDate
{
int year;
int month;
int day;
};
int GetAbsDays(MyDate x)
{
int i;
int month_day[] = {31,28,31,30,31,30,31,31,30,31,30,31};
int year = x.year-1; // 因为欲求距离1年1月1日的距离
int days = year * 365 + year/4 - year/100 + year/400;
if(x.year%4==0 && x.year%100!=0 || x.year%400==0) month_day[1]++;
for(i=0; i<______________; i++)
days += month_day[i];
days += x.day-1;
return days;
}
int GetDiffDays(MyDate a, MyDate b)
{
return GetAbsDays(b) - GetAbsDays(a);
}
int main(int argc, char* argv[])
{
MyDate a = {1842,5,18};
MyDate b = {2000,3,13};
int n = GetDiffDays(a,b);
printf("%d\n", n);
}
~~~
这道题无外乎求，某个日期到1年1月1日的时间，一看到计算年月日的，我就直接看空缺处了，for循环体内是
days+=month_day[i]，就是总天数加上该月份拥有的天数，那还用想吗？肯定填当前月份了，
但是假设日期是 2014年3月22日，月份肯定不能等于3，所以就是x.month-1咯
答案：x.month-1