## 历届试题 大臣的旅费   时间限制：1.0s   内存限制：256.0MB       问题描述 很久以前，T王国空前繁荣。为了更好地管理国家，王国修建了大量的快速路，用于连接首都和王国内的各大城市。 为节省经费，T国的大臣们经过思考，制定了一套优秀的修建方案，使得任何一个大城市都能从首都直接或者通过其他大城市间接到达。同时，如果不重复经过大城市，从首都到达每个大城市的方案都是唯一的。 J是T国重要大臣，他巡查于各大城市之间，体察民情。所以，从一个城市马不停蹄地到另一个城市成了J最常做的事情。他有一个钱袋，用于存放往来城市间的路费。 聪明的J发现，如果不在某个城市停下来修整，在连续行进过程中，他所花的路费与他已走过的距离有关，在走第x千米到第x+1千米这一千米中（x是整数），他花费的路费是x+10这么多。也就是说走1千米花费11，走2千米要花费23。 J大臣想知道：他从某一个城市出发，中间不休息，到达另一个城市，所有可能花费的路费中最多是多少呢？ 输入格式 输入的第一行包含一个整数n，表示包括首都在内的T王国的城市数 城市从1开始依次编号，1号城市为首都。 接下来n-1行，描述T国的高速路（T国的高速路一定是n-1条） 每行三个整数Pi, Qi, Di，表示城市Pi和城市Qi之间有一条高速路，长度为Di千米。 输出格式 输出一个整数，表示大臣J最多花费的路费是多少。 样例输入1 5 1 2 2 1 3 1 2 4 5 2 5 4 样例输出1 135 输出格式 大臣J从城市4到城市5要花费135的路费。 这道题，如果不看提示，感觉像是图论题（有点忒明显了）， 但是，提示说是 深度优先遍历，恩，于是DFS做了。 打表存某点到某点的距离，不能到达则为-1. 这样DFS做 75分。。 YM用Floyed做也是75分。。。 最后一组数据据说是10000左右， DFS打表是存不下这么大数组，超空间了。 等回头用别的方法试试，之前测试过一个JAVA程序，是可以过的，测试数据应该就没有问题了。 我的DFS（75分） ~~~ /******************** ********************* * Author:Tree * *From :http://blog.csdn.net/lttree * * Title : 大臣的旅费 * *Source: 蓝桥杯 历届试题 * * Hint : 深度优先遍历 * ********************* ********************/ #include <iostream> #include <string.h> using namespace std; int n,val,Map[1001][1001]; bool vis[1001][1001]; void dfs(int i,int v) { int j; for( j=1;j<=n;++j ) { if( Map[i][j]==-1 || vis[i][j] ) continue; vis[i][j]=vis[j][i]=1; dfs( j,v+Map[i][j] ); vis[i][j]=vis[j][i]=0; } val= v>val?v:val; } int find_max( void ) { int i,Max; Max=-1; for(i=1;i<=n;++i) { memset(vis,0,sizeof(vis)); val=-1; dfs(i,0); Max= val>Max?val:Max; } return Max; } int main() { int i,p,q,d,num,sum; while( cin>>n ) { memset(Map,-1,sizeof(Map)); for(i=1;i<n;++i) { cin>>p>>q>>d; Map[p][q]=d; Map[q][p]=d; } num=find_max(); if( num&1 ) sum= (num+1)*(num/2)+(num+1)/2; else sum=(num*num+num)/2; cout<<sum+num*10<<endl; } return 0; } ~~~ 那个100分能过的 JAVA代码（非本人所写） ~~~ import java.util.*; public class Main { public static void main(String args[]){ Scanner scan=new Scanner (System.in); int n=scan.nextInt(); QiDian[] QiDians=new QiDian[n]; for(int i=0;i<n;i++){ QiDians[i]=new QiDian(i,new ArrayList<ZhongDian>()); } int tem1=0; int tem2=0; int quanzhong=0; for(int i=0;i<n-1;i++){ tem1=scan.nextInt(); tem2=scan.nextInt(); quanzhong=scan.nextInt(); QiDians[tem1-1].list.add(new ZhongDian(quanzhong,QiDians[tem2-1])); QiDians[tem2-1].list.add(new ZhongDian(quanzhong,QiDians[tem1-1])); } int[] data=search(QiDians[0],null); int[] data2=search(QiDians[data[1]],null); int sum=0; for(int i=1;i<=data2[0];i++){ sum+=i+10; } System.out.println(sum); } public static int[] search(QiDian q,QiDian p){ int[] data=new int[]{0,q.index}; for(int i=0;i<q.list.size();i++){ if(q.list.get(i).qidian.equals(p)==false){ int [] data2=search(q.list.get(i).qidian,q); int tem=q.list.get(i).quanzhong+data2[0]; if(tem>data[0]){ data[0]=tem; data[1]=data2[1]; } } } return data; } } class QiDian{ int index; ArrayList<ZhongDian> list=new ArrayList<ZhongDian>(); public QiDian(int index, ArrayList<ZhongDian> list) { super(); this.index = index; this.list = list; } } class ZhongDian{ int quanzhong; QiDian qidian; public ZhongDian(int quanzhong, QiDian qidian) { super(); this.quanzhong = quanzhong; this.qidian = qidian; } } ~~~

## 排座位 要安排：3个A国人，3个B国人，3个C国人坐成一排。 要求不能使连续的3个人是同一个国籍。 求所有不同方案的总数？ 这道题，一看就排列组合的题目。。。据说给学校讲概率论老师做，老师纯手算， 费了好大劲。。。好吧，学计算机的当然不能浪费电脑的速度啦。。。 纯暴力破解吧！ 我想法就是把三个国家A,B,C用数字1，2,3来表示， 刚开始我想就是用1,2,3来循环做，如果碰到相连的三个国家，就可以continue，选下一个数字代表的国家。 结果发现，计算出来的只有5000多种和答案28万多种，差好多。。。 后来，经过小帅点播提醒，发现，国家要用九个的情况，并不能直接就让后面的不能选。 我原来的想法代码（错的）： ~~~ #include <iostream> using namespace std; // A,B,C用数字1,2,3代替 // arr 记录9个人状态，sum记录种类数 int arr[10],sum; // num下标记录每个数字总数是否到3 int num[4]={0,0,0,0}; void find(int n) { if(n==10) { int j; for(j=1;j<=9;++j) cout<<arr[j]<<" "; cout<<endl; ++sum; return; } int i,k; for(i=1;i<=3;++i) { if(n<3) { if(num[i]==3) continue; arr[n]=i; ++num[i]; find(n+1); --num[i]; } if(arr[n-1]==arr[n-2] && arr[n-1]==i) continue; if(num[i]==3) continue; arr[n]=i; ++num[i]; find(n+1); --num[i]; } } int main() { sum=0; find(1); cout<<sum<<endl; return 0; } ~~~ 正确的代码： ~~~ #include <iostream> using namespace std; // arr为排列方式数组 int arr[11],sum; // num为九个国家，前三个为A国设置为1，中间三个B国，设置为2，后面三个C国，设置为3 int num[11]; // a数组来表示，相应下标国家是否被选 int a[11]; void find(int n) { // 人数大于4是，查找是否有连着三个相同的 if(n>=4) { for(int i=1;i<=n-3;i++) if(arr[i]==arr[i+1]&&arr[i+1]==arr[i+2]) return ; } // n大于9，表示有一种排列可行 if(n>=10) { sum++; return ; } // 九次循环 for(int i=1;i<=9;i++) { if(num[i]==0) continue; num[i]=0; arr[n]=a[i]; find(n+1); num[i]=1; } } int main() { sum=0; // 赋初值1，表示都没有被选过 for(int i=1;i<=9;i++) num[i]=1; a[1]=a[2]=a[3]=1;a[4]=a[5]=a[6]=2;a[7]=a[8]=a[9]=3; find(1); cout<<sum<<endl; return 0; } ~~~

微生物增殖—除去次方数—古堡算式—奇怪的比赛—欧拉与鸡蛋 ①微生物增殖 假设有两种微生物 X 和 Y X出生后每隔3分钟分裂一次（数目加倍），Y出生后每隔2分钟分裂一次（数目加倍）。 一个新出生的X，半分钟之后吃掉1个Y，并且，从此开始，每隔1分钟吃1个Y。 现在已知有新出生的 X=10, Y=89，求60分钟后Y的数目。 如果X=10，Y=90 呢？ 本题的要求就是写出这两种初始条件下，60分钟后Y的数目。 题目的结果令你震惊吗？这不是简单的数字游戏！真实的生物圈有着同样脆弱的性质！也许因为你消灭的那只 Y 就是最终导致 Y 种群灭绝的最后一根稻草！ 一道数学题哈，这道题，有个小技巧，因为有需要算0.5分钟的，很麻烦，所以不如都X2，总共为120， 每隔0.5分钟即为每隔1。 这样，这道题可以分析为： X每隔6分裂一次，Y每隔4分裂一次。 新生X每隔1吃Y，此后每隔2吃Y。 求120后，Y的数目。 肯定不能拿手算啦。。好累的o(╯□╰)o， 可以仔细分析一下题目，可以用一个for循环模拟时间的增长， 那么就可以对4,6取模来判定X、Y的分裂时间。 最关键就是X什么时候吃Y，或许刚开始考虑的时候，你觉得要分新生X与以前的X， 可是，你仔细看就会发现不然，Y每隔4才分裂一次，而新生的X与老X吃Y时间是重合的。 所以，只要是奇数个时间段（以120为总和的时间段）就会吃Y。 可以画一个时间轴来更清晰的表示出来：  我们可以很清晰的看出，红蓝点会重合，也就是新生的X与以前的X吃Y的时间段是重合的，所以，就可以通过 判断是否为奇数断点来吃Y。 代码： ~~~ #include <iostream> using namespace std; int main() { int time; int x=10,y=89; // 第二次把Y改成90就可以了 for(time=1;time<=120;++time) { if(time%2==1) y-=x; if(time%4==0) y+=y; if(time%6==0) x+=x; if(y<0) {y=0;break;} } cout<<y<<endl; return 0; } ~~~ ②除去次方数 自然数的平方数是：1 4 9 16 25 … 自然数的立方数是：1 8 27 64 125 … 自然数的4次方数是：1 16 81256 … … 这些数字都可以称为次方数。 1~10000中，去掉所有的次方数，还剩下多少个数字？ 这题完全可以用筛法求素数的方式来计算哟， 就是注意一下，最大到多少次方，2的几次方大于10000呢？ 众所周知，2^10=1024 -> 2^14>10000 代码： ~~~ #include <iostream> #include <cmath> #include <string.h> using namespace std; bool no[10001]; int main() { int i,j,k; int num,sum; memset(no,0,sizeof(no)); // j为次方数 for(j=2;j<=14;++j) { // i为底数 i=1; k=pow(i++,j); while(k<10001) { no[k]=1; k=pow(i++,j); } } // 查找 sum=0; for(i=1;i<10001;++i) if(no[i]==0) ++sum; cout<<sum<<endl; return 0; } ~~~ ③古堡算式 福尔摩斯到某古堡探险，看到门上写着一个奇怪的算式：    ABCDE * ? = EDCBA    他对华生说：“ABCDE应该代表不同的数字，问号也代表某个数字！”    华生：“我猜也是！”    于是，两人沉默了好久，还是没有算出合适的结果来。    请你利用计算机的优势，找到破解的答案。    把 ABCDE 所代表的数字写出来。 一个五位数，乘以一个数得到另一个五位数，而且各位数字是相反的。 从题目中可以提取出的信息： ①相乘前后均为一个五位数 ②这五位数各位数字没有相同的 ③乘的是一个1~9的数字（准确的说是0~9，但是乘以0直接滤了） 我的做法： 设置一个变量Num从10000开始循环到100000，然后乘以1~9后的数传到函数，与原来num判断。 因为是结果填空题，所以就没有怎么优化，判断五个数各不相等，我也只是让第一个数不与后面的数相等。 这样就已经可以筛选的剩下一个了。。。 代码： ~~~ #include <iostream> #include <string.h> using namespace std; int n[5]; void show(int num) { int i,temp; temp=num; for(i=0;i<5;++i) { if(num%10!=n[i]) return; num/=10; } if(n[0]==n[1] || n[0]==n[2] || n[0]==n[3] || n[0]==n[4]) return; cout<<temp<<endl; } int main() { int num,i,k,no; for(num=10000;num<100000;++num) { for(k=1;k<10;++k) { memset(n,0,sizeof(n)); no=k*num; if(no>100000) continue; for(i=4;i>=0;--i) { n[i]=no%10; no/=10; } show(num); } } return 0; } ~~~ ④奇怪的比赛 某电视台举办了低碳生活大奖赛。题目的计分规则相当奇怪： 每位选手需要回答10个问题（其编号为1到10），越后面越有难度。答对的，当前分数翻倍；答错了则扣掉与题号相同的分数（选手必须回答问题，不回答按错误处理）。 每位选手都有一个起步的分数为10分。 某获胜选手最终得分刚好是100分，如果不让你看比赛过程，你能推断出他（她）哪个题目答对了，哪个题目答错了吗？ 如果把答对的记为1，答错的记为0，则10个题目的回答情况可以用仅含有1和0的串来表示。例如：0010110011就是可能的情况。 你的任务是算出所有可能情况。每个答案占一行。 多个答案顺序不重要。 这道题，可以暴力的。。。用10个变量，for循环。。。 我用的是模拟二进制加法，一直往最后一位加1，再判断各位，如果有等于2的就进位。 一直到下标为0的内容为1，则退出。。 对了，还要注意，题目中讲的是，如果答对该题目，当前拥有的分数翻倍，而不是得到当前题号X2的分数。 代码： ~~~ #include <iostream> using namespace std; int main() { int que[11]={0,0,0,0,0,0,0,0,0,0,0}; int i,j,sum; // 最高位不为1则循环下去 while(que[0]!=1) { // 最低位+1 ++que[10]; // 模拟二进制加法 for(j=10;j>0;--j) if(que[j]==2) { ++que[j-1]; que[j]=0; } // 初始sum为10，并算总分 sum=10; for(j=1;j<11;++j) if(que[j]==1) sum=sum+sum; else sum=sum-j; // 如果最后总分为100，则输出 if(sum==100) { for(j=1;j<11;++j) cout<<que[j]; cout<<endl; } } return 0; } ~~~ ⑤欧拉与鸡蛋 大数学家欧拉在集市上遇到了本村的两个农妇，每人跨着个空篮子。她们和欧拉打招呼说两人刚刚卖完了所有的鸡蛋。 欧拉随便问：“卖了多少鸡蛋呢？” 不料一个说：“我们两人自己卖自己的，一共卖了150个鸡蛋，虽然我们卖的鸡蛋有多有少，但刚好得了同样的钱数。你猜猜看！” 欧拉猜不出。 另一个补充道：“如果我按她那样的价格卖，可以得到32元；如果她按我的价格卖，可以得到24.5元”。 欧拉想了想，说出了正确答案。 我们不是数学家，懒得列出公式来分析。但计算机可以“暴力破解”，就是把所有可能情况都试验一遍，撞上为止！ 请写出每人鸡蛋的数目（顺序不限），用逗号隔开。 一道解一元二次方程的题目，设一个人以a元价格卖了x个鸡蛋，另一个人以b元价格卖了y个鸡蛋。 据题目分析： x+y=150 ax=by bx=32 ay=24.5 就是解这个方程，用笔算的话。。我觉得听麻烦的，还是暴力快点。。。 还要注意一点就是，后面两个也可以是： ax=32 by=24.5 所以，应该有2*n(n为答案个数）的答案。 因为没有确定谁卖了多少个。 代码： ~~~ #include <iostream> using namespace std; int main() { int x,y; for(x=1;x<=150;++x) { y=150-x; if(32*y*y==24.5*x*x) cout<<x<<" "<<y<<endl; if(32*x*x==24.5*y*y) cout<<x<<" "<<y<<endl; } return 0; } ~~~ 蓝桥杯结果填空题，注意一下几点，手算快于机算，就用手算，但是如果用机算，手也不要闲着，多划拉几下。 不要注重代码的优化，因为它只要结果，代码再漂亮人家也看不见，这时间可以用在后面编程大题上。 多注意题目给的线索，一般每个线索都能用上。

身份证校验—神秘三位数—生日相同概率—四方定理—因数分解—组合数 ①身份证校验 如果让你设计个程序，用什么变量保存身份证号码呢？长整数可以吗？不可以！ 因为有人的身份证最后一位是"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)

## 翻硬币 问题描述 小明正在玩一个“翻硬币”的游戏。 桌上放着排成一排的若干硬币。我们用 * 表示正面，用 o 表示反面（是小写字母，不是零）。 比如，可能情形是：**oo***oooo 如果同时翻转左边的两个硬币，则变为：oooo***oooo 现在小明的问题是：如果已知了初始状态和要达到的目标状态，每次只能同时翻转相邻的两个硬币,那么对特定的局面，最少要翻动多少次呢？ 我们约定：把翻动相邻的两个硬币叫做一步操作，那么要求： 输入格式 两行等长的字符串，分别表示初始状态和要达到的目标状态。每行的长度<1000 输出格式 一个整数，表示最小操作步数。 样例输入1 ****** o**o** 样例输出1 5 样例输入2 *o**o***o*** *o***o**o*** 样例输出2 1 这道题啊，一道简单的贪心题目，两个字符串比较，如果发现不同，将当前和之后的翻到另一面，再继续寻找。 ~~~ #include <iostream> #include <string> using namespace std; string str1,str2; void fan(int n) { if(str1[n]=='*') str1[n]='o'; else if(str1[n]=='o') str1[n]='*'; if(str1[n+1]=='*') str1[n+1]='o'; else if(str1[n+1]=='o') str1[n+1]='*'; } int main() { int i,len,sum; while(cin>>str1>>str2) { sum=0; len=str1.length(); for(i=0;i<len;++i) if(str1[i]!=str2[i]) { ++sum; fan(i); } cout<<sum<<endl; } return 0; } ~~~

方阵旋转—取球概率—巧开平方 ①方阵旋转 对一个方阵转置，就是把原来的行号变列号，原来的列号变行号 例如，如下的方阵： 1  2  3  4 5  6  7  8 9 10 11 12 13 14 15 16 转置后变为： 1  5  9 13 2  6 10 14 3  7 11 15 4  8 12 16 但，如果是对该方阵顺时针旋转（不是转置），却是如下结果： 13  9  5  1 14 10  6  2 15 11  7  3 16 12  8  4 下面的代码实现的功能就是要把一个方阵顺时针旋转。 ~~~ void rotate(int* x, int rank) { int* y = (int*)malloc(___________________); // 填空 for(int i=0; i<rank * rank; i++) { y[_________________________] = x[i]; // 填空 } for(i=0; i<rank*rank; i++) { x[i] = y[i]; } free(y); } int main(int argc, char* argv[]) { int x[4][4] = {{1,2,3,4},{5,6,7,8},{9,10,11,12},{13,14,15,16}}; int rank = 4; rotate(&x[0][0], rank); for(int i=0; i<rank; i++) { for(int j=0; j<rank; j++) { printf("%4d", x[i][j]); } printf("\n"); } return 0; } ~~~ 这道题就是矩阵转置，只不过是顺时针的，看一遍代码，第二个for循环将x[i]=y[i] 然后把y给free掉，y肯定是中间变量，用来存正确的放置方法的，所以它的大小应该等同于X的大小。 那么第一个空肯定就是rank*rank呗，如果这样写提交，肯定一个大红叉叉在上面。Why？因为你开辟的空间，确定是 rank*rank吗？你心里把它默认为Int形式，可是代码不知道啊！所以还需要再乘一个4，作为int型的大小。如果更保险一些，你可以写成 sizeof（int）。 这个如果自己编一个程序没有乘4或者sizeof(int)，程序会给你报错的。（PS：malloc 需要头文件　malloc.h） 然后第二个空，开始我还纳闷他是怎么用一个i来进行二维数组的赋值？后来经好友提醒，顿时恍悟： 二维数组可以写成这样： 1 2 3 4 5 6 7 8  9 10 11 12 13 14 15 16 5可以用 1,0，同样也可以用长度 1*4+1啊。 所以懂了吧？就是一行的宽度有限个，当你输入的宽度大于该行的宽度，它会给你换下一行，继续找。 答案： sizeof(int) * rank * rank  或者 4 * rank * rank   (i%rank)*rank+(rank-(i/rank)-1)     ②取球概率 口袋中有5只红球，4只白球。随机从口袋中取出3个球，则取出1个红球2个白球的概率是多大？ 类似这样的数学问题，在计算的时候往往十分复杂。但如果通过计算机模拟这个过程，比如进行100000次取球模拟，统计一下指定情况出现的次数对计算机来说是方便且快速的。 ~~~ srand( (unsigned)time( NULL ) ); int n = 0; for(int i=0; i<100000; i++) { char x[] = {1, 1, 1, 1, 1, 2, 2, 2, 2}; int a = 0; // 取到的红球的数目 int b = 0; // 取到的白球的数目 for(int j=0; j<3; j++) { int k = rand() % (9-j); if(x[k]==1) a++; else b++; _______________________; } if(a==1 && b==2) n++; } printf("概率=%f\n", n/100000.0*100); ~~~ 题目很简单就是模拟取球，空格上填的第一遍看也能懂，就是怕取道的那个下标的球去掉，但怎么去除？ 赋0？赋0的话下次碰到会以else 让b++,显然不可以。 其实，题目中已经给了你隐藏的信息，题中每次rand()值对9-j取模而不是9，也就是说，第一次对9取余， 第二次对8取余，第三次对7取余，这样第一次所有球都是好球，第二次，最后一个球是费球，用不到， 第三次最后两个都是废球，也用不到。如此一来，我们完全可以把取到的球和最后的互换，这样取到的球， 可以扔到后面做废球，而后面的可以换到前面，继续来随机取球。 答案： x[k] = x[9-j-1] ③开平方 开平方 如果没有计算器，我们如何求2的平方根？ 可以先猜测一个数，比如1.5，然后用2除以这个数字。如果我们猜对了，则除法的结果必然与我们猜测的数字相同。我们猜测的越准确，除法的结果与猜测的数字就越接近。 根据这个原理，只要我们每次取猜测数和试除反馈数的中间值作为新的猜测数，肯定更接近答案！这种计算方法叫做“迭代法”。 下面的代码模拟了如何用手工的方法求2的平方根的过程。 ~~~ double n = 2; double a = 0; double b = n; while(fabs(a-b)>1E-15) { a = (a+b)/2; b = __________; } printf("%f\n", a); ~~~ 很短的代码，就是用迭代法求平方根，题目中给出了： 只要我们每次取猜测数和试除反馈数的中间值 作为新的猜测数，肯定接近答案。根据代码，我们也明白，a肯定是猜测数，b肯定是试除反馈数。（为什么？因为a=（a+b）/2， a是新的猜测数，新猜测数的产生，根据题意就明白了b肯定是试除反馈数），刚开始读题，我始终搞不懂什么叫试 除反馈数，b要怎么求呢？ 再仔细看看题目中的描述，b是 试除反馈数，反馈数不就是我们求的猜测数吗，于是乎，答案随之跃出。 答案：n/a

连续和的平方数—排列的个数—巧放棋子—取中间数字—去掉重复字母—日历天数之差 ①连续和的平方数 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

干支纪年法—歌赛新规则—红球多于白球的概率—交换变量—考拉兹猜想—利息计算 ①干支纪年法 在我国古代和近代，一直采用干支法纪年。它采用10天干和12地支配合，一个循环周期为60年。    10天干是：甲,乙,丙,丁,戊,己,庚,辛,壬,癸    12地支是：子,丑,寅,卯,辰,巳,午,未,申,酉,戌,亥 如果某年是甲子，下一年就是乙丑，再下是丙寅，......癸酉，甲戌，乙亥，丙子，.... 总之天干、地址都是循环使用，两两配对。   今年（2012）是壬辰年，1911年辛亥革命 下面的代码根据公历年份输出相应的干支法纪年。已知最近的甲子年是1984年。 ~~~ void f(int year) { char* x[] = {"甲","乙","丙","丁","戊","己","庚","辛","壬","癸"}; char* y[] = {"子","丑","寅","卯","辰","巳","午","未","申","酉","戌","亥"}; int n = year - 1984; while(n<0) n += 60; printf("%s%s\n", x[_______], y[_______]); } int main(int argc, char* argv[]) { f(1911); f(1970); f(2012); return 0; } ~~~ 这道题，最近的一个甲午年（就是对10或者12取模都为0）是1984年，就以它为标准，求模就可以了， 题目中也有对给出的年份小于1984年的处理（n+=60），这题难度，应该很小了。。。 答案：  n%10    n%12  ②歌赛新规 歌手大赛的评分规则一般是去掉一个最高分，去掉一个最低分，剩下的分数求平均。当评委较少的时候，如果我们只允许去掉一个分数，该如何设计规则呢？ 有人提出：应该去掉与其余的分数平均值相差最远的那个分数。即“最离群”的分数。 以下的程序用于实现这个功能。其中x存放所有评分，n表示数组中元素的个数。函数返回最“离群”的那个分数值。 ~~~ double score(double x[], int n) { int i,j; double dif = -1; double bad; for(i=0; i<n; i++) { double sum = 0; for(j=0; j<n; j++) { if(________) sum += x[j]; } double t = x[i] - sum / (n-1); if(t<0) t = -t; if(t>dif) { dif = t; bad = x[i]; printf("%d, %f\n", i, x[i]); } } return bad; } ~~~ 题目很简单，就是求最离群的数字，如果让我打代码，我猜可能是求最大和最小的，然后剩下的求平均，通过它们之间的差值来查找，这题目的做法，应该是，计算n-1个平均值，来比较，所以两层循环， 第一层，计算2~n的，第二层计算1,3~n。。。。所以if里应该是去除掉当前循环的i,对应的值再求和 答案：i!=j ③概率问题 某个袋子中有红球m个，白球n个。现在要从中取出x个球。那么红球数目多于白球的概率是多少呢？ 下面的代码解决了这个问题。其中的y表示红球至少出现的次数。 这与前文的问题是等价的。因为如果取30个球，要求红球数大于白球数，则等价于至少取出16个红球。 ~~~ /* m: 袋中红球的数目 n: 袋中白球的数目 x: 需要取出的数目 y: 红球至少出现的次数 */ double pro(int m, int n, int x, int y) { if(y>x) return 0; if(y==0) return 1; if(y>m) return 0; if(x-n>y) return 1; double p1 = _______________________; double p2 = _______________________; return (double)m/(m+n) * p1 + (double)n/(m+n) * p2; } ~~~ 刚开始，我以为要直接求出来p1,p2，但是后来一想，不对啊，代码填空题，只给了一个函数，没有给主函数那些，肯定是递归了，再加上题目中给了递归终止的条件，所以肯定是递归了。 知道了递归以后就很简单了：模拟拿球情况，要么拿了一个红球，要么拿了一个白球。 答案：pro(m-1,n,x-1,y-1)  pro(m,n-1,x-1,y)   ④交换变量 如果要把两个整型变量a、b的值交换，一般要采用一个中间变量做过渡， 但也可以在不借助任何其它变量的情况下完成。 a = _________; b = _________; a = _________; 这道题目，有很多种解法，我这里就给出两种吧，一个是用位运算—  ^ ^（异或）是将两边数都转换成2进制，然后异或， 第一种方法：a=a^b,b=a^b,a=a^b 第二种方法就是  a=a+b,b=a-b,a=a-b ⑤考拉兹猜想 “考拉兹猜想”（又称3n＋1猜想、角谷猜想、哈塞猜想、乌拉姆猜想或叙拉古猜想） 和“哥德巴赫猜想”一样目前还没有用数学方法证明其完全成立。在1930年，德国汉堡大学的学生考拉兹，曾经研究过这个猜想，因而得名。在1960年，日本人角谷静夫也研究过这个猜想。 该猜想的叙述十分简单：从任何一个正整数n出发，若是偶数就除以2，若是奇数就乘3再加1,如此继续下去，经过有限步骤，总能得到1。例如： 17－52－26－13－40－20－10－5－16－8－4－2－1 该猜想虽然没有完全证明，但用计算机验证有限范围的数字却十分容易。 ~~~ for(int n=2; n<=10000; n++) { int m = n; for(;;) { if(____________) m = m / 2; else m = m * 3 + 1; if( m == 1 ) { printf("%d ok! \n", n); break; } } }; ~~~ 这道题，额，看起来很高端大气上档次，猜想也很厉害的样子，但是空就有些。。。 根据题目所给，遇到偶数时  该数除以2，所以答案就是判断m是不是偶数： m%2==0 ⑥利息计算 小李年初在银行存款1千元（一年定期）。他计划每年年底取出100元救助失学儿童。 假设银行的存款利率不变，年利率为3%，年底利息自动计入本金。下面的代码计算5年后，该账户上有多少存款。 ~~~ double money = 1000; int n = 5; int i; for(i=0; i<n; i++) { money = _______________; money -= 100; } printf("%.2f\n", money); ~~~ 这道题啊，唉，每年年末，要把本金加上利息都算上再存进去，扣的钱就不需要减了，下面代码帮助你减了。 答案：money=money*1.03

N进制小数—车票找零方案计数—串的反转—串的轮换—大数分块乘法—二进制串转整数 ①N进制小数 将任意十进制正小数分别转换成2,3,4,5,6,7,8,9进制正小数，小数点后保留8位，并输出。例如：若十进制小数为0.795，则输出： 十进制正小数 0.795000 转换成 2 进制数为: 0.11001011 十进制正小数 0.795000 转换成 3 进制数为: 0.21011011 十进制正小数 0.795000 转换成 4 进制数为: 0.30232011 十进制正小数 0.795000 转换成 5 进制数为: 0.34414141 十进制正小数 0.795000 转换成 6 进制数为: 0.44341530 十进制正小数 0.795000 转换成 7 进制数为: 0.53645364 十进制正小数 0.795000 转换成 8 进制数为: 0.62702436 十进制正小数 0.795000 转换成 9 进制数为: 0.71348853 以下代码提供了这个功能。其中，dTestNo表示待转的十进制小数。iBase表示进制数。请填写缺失的部分。 ~~~ void fun(double dTestNo, int iBase) { int iT[8]; int iNo; printf("十进制正小数 %f 转换成 %d 进制数为: ",dTestNo, iBase); for(iNo=0;iNo<8;iNo++) { dTestNo *= iBase; iT[iNo] = ________________; if(___________________) dTestNo -= iT[iNo]; } printf("0."); for(iNo=0; iNo<8; iNo++) printf("%d", iT[iNo]); printf("\n"); } void main ( ) { double dTestNo= 0.795; int iBase; for(iBase=2;iBase<=9;iBase++) fun(dTestNo,iBase); printf("\n"); } ~~~ 这道题看到函数传进来的是一个小数和进制数， 题中建立一个大小为8的数组，再看看输出，就知道，是把每一个相应进制数存在数组中， 在本上算一算就发现，小数乘以相应进制，整数部分即为该进制第一个小数（这个是小数转换进制的基础知识）， 显然题目，也是这么做的，填空就不难了，第一个就是取整数部分，直接强制类型转换就可以， 第二个就是判断什么时候需要减去整数部分，前面是*=，原来的小数变化了，求下一个数，肯定要把整数部分清零， 所以就是，当数组内容不为0的时候，也可以说是大于0的时候。 答案：（答案不唯一，只要能满足要求即可） 空1：  (int)dTestNo    空2：  dTestNo>=1.0   ②车票找零方案计数 公交车票价为5角。假设每位乘客只持有两种币值的货币：5角、1元。 再假设持有5角的乘客有m人，持有1元的乘客有n人。由于特殊情况，开始的时候，售票员没有零钱可找。 我们想知道这m+n名乘客以什么样的顺序购票则可以顺利完成购票过程。 显然，m < n的时候，无论如何都不能完成，m >=n的时候，有些情况也不行。 比如，第一个购票的乘客就持有1元。 下面的程序计算出这m+n名乘客所有可能顺利完成购票的不同情况的组合数目。 注意：只关心5角和1元交替出现的次序的不同排列，持有同样币值的两名乘客交换位置并不算做一种新的情况来计数。 //m: 持有5角币的人数 //n: 持有1元币的人数 //返回：所有顺利完成购票过程的购票次序的种类数 ~~~ int f(int m, int n) { if(m < n) return 0; if(n==0) return 1; return _______________________; } ~~~ 这道题，一看函数类型int 还有终止条件，显然是递归， 递归的话就简单了，你是 return f(m-1,n-1)+1还是 return f(m-1,n)+f(m,n-1) 呢？ m-1，n-1就是 当前人数，先来一个五毛钱的，再来一个1元的， 那排序基本上就是 0.5  1   0.5   1显然方案不全， 所以就是m-1,n + m,n-1了， 答案： f(m-1, n) + f(m, n-1) ③反转串 我们把“cba”称为“abc”的反转串。 下面的代码可以把buf中的字符反转。其中n表示buf中待反转的串的长度。请补充缺少的代码。 ~~~ void reverse_str(char* buf, int n) { if(n<2) return; char tmp = buf[0]; buf[0] = buf[n-1]; buf[n-1] = tmp; _______________________________; } ~~~ 题目要求很简单，就是把串反转，看题干，也很明白它的做法， 就是取头尾，互换，下一步肯定是往里缩进一格，首位都缩进，肯定长度减少2了， 这样，接着把串和长度传下去就可以了，也是一个递归，因为传递的是指针，所以不需要返回值。 答案： reverse_str(buf+1,n-2) （答案不唯一） ④串的轮换 串“abcd”每个字符都向右移位，最右的移动到第一个字符的位置，就变为“dabc”。这称为对串进行位移=1的轮换。同理，“abcd”变为：“cdab”则称为位移=2的轮换。 下面的代码实现了对串s进行位移为n的轮换。请补全缺失的代码。 ~~~ void shift(char* s, int n) { char* p; char* q; int len = strlen(s); if(len==0) return; if(n<=0 || n>=len) return; char* s2 = (char*)malloc(_________); p = s; q = s2 + n % len; while(*p) { *q++ = *p++; if(q-s2>=len) { *q = ___________; q = s2; } } strcpy(s,s2); free(s2); } ~~~ 这道题，我是从下往上看的，看到最后有个 strcpy(s,s2) 和 free(s2)  就明白， 它的方法就是建立一个中间串s2，s2存储正确顺序，最后直接赋值给s， 过程，malloc肯定就是开辟s2的空间，开辟空间大小显然与s长度len有关， 后面p指针指向s头部，q指向中间串s2的相应位置，n%len 就是计算具体指向那个地方， 然后通过循环，当p!=NULL时，将p指向内容赋值给q指向内容，然后两者再往后移动， 这里要注意是先赋值再移动， 假如题目是  abcd 2，那么通过上述循环，s2串内容将是   空空ab  (空代表什么都没有） 那个if就是判断q是否指到了末尾，当指到末尾，就给q赋值为NULL， 将q指向s2头部，接着赋值。这样就达到了构建s2的目的。 简单的说，就是： p是从s头指向尾不变， 而q从s2中间位置向后移动，如果长度大于等于串长度，再指向s2头部， 以 abcd 2为例就是： p从指向a移动到d， q先指向c的位置，将a，b，赋值到s2串第3,4的位置，if成立，所以将后面第5个设置NULL， 指回s2头部，这是p指向的是c，到指到d下一个是空，所以循环跳出，s2串构建完成。 答案： len+1 0（指的是空，也可以写成NULL或者‘\0'或者（char）0 ⑤大数分块乘法   对于32位字长的机器，大约超过20亿，用int类型就无法表示了，我们可以选择int64类型， 但无论怎样扩展，固定的整数类型总是有表达的极限！如果对超级大整数进行精确运算呢？ 一个简单的办法是：仅仅使用现有类型，但是把大整数的运算化解为若干小整数的运算，即所谓：“分块法”。   如图  表示了分块乘法的原理。可以把大数分成多段（此处为2段）小数，然后用小数的多次运算组合表示一个大数。 可以根据int的承载能力规定小块的大小，比如要把int分成2段，则小块可取10000为上限值。 注意，小块在进行纵向累加后，需要进行进位校正。 以下代码示意了分块乘法的原理（乘数、被乘数都分为2段）。 ~~~ void bigmul(int x, int y, int r[]) { int base = 10000; int x2 = x / base; int x1 = x % base;  int y2 = y / base; int y1 = y % base;  int n1 = x1 * y1;  int n2 = x1 * y2; int n3 = x2 * y1; int n4 = x2 * y2; r[3] = n1 % base; r[2] = n1 / base + n2 % base + n3 % base; r[1] = ____________________________________________; // 填空 r[0] = n4 / base; r[1] += _______________________;  // 填空 r[2] = r[2] % base; r[0] += r[1] / base; r[1] = r[1] % base; } int main(int argc, char* argv[]) { int x[] = {0,0,0,0}; bigmul(87654321, 12345678, x); printf("%d%d%d%d\n", x[0],x[1],x[2],x[3]); return 0; } ~~~ 这题应该比较简单了，根据图很容易填上第一个空， 要注意它的r[3]、r[2]、r[1]、r[0]对应图中r4,r3,r2,r1， 第二个空，根据下面r0也可以照葫芦画瓢的填出来。 答案：（答案不唯一） n2 / base + n3 / base + n4 % base    r[2] / base                      ⑥二进制串转整数 下列代码把一个二进制的串转换为整数。请填写缺少的语句； ~~~ char* p = "1010110001100"; int n = 0; for(int i=0;i<strlen(p); i++) { n = __________________; } printf("%d\n", n); ~~~ 就是将2进制的串转换成10进制， 如果有cmath库函数，直接用个Pow, 这题好像没提供， 但是，不要忘了，将10进制转换2进制可以用while循环做： ~~~ i=0 while(num>2) { arr[i++]=num%2; num/=2; } ~~~ 这题完全可以逆着来。 还要注意一下，题目中的是字符，而不是数字。 答案： n * 2 + (p[i] - '0') 上述题目的答案都不是唯一的，当答案和标准答案不一样时，会将答案带入程序运行，通过运行结果来判断正误。

## 算法训练 最大最小公倍数   时间限制：1.0s   内存限制：256.0MB   问题描述 已知一个正整数N，问从1~N中任选出三个数，他们的最小公倍数最大可以为多少。 输入格式 输入一个正整数N。 输出格式 输出一个整数，表示你找到的最小公倍数。 样例输入 9 样例输出 504 数据规模与约定 1 <= N <= 106。 这道题，首先说明一下，公认的5,8,9,10四个测试数据有错误，详情看论坛。。。 还有，类型用long long， 题意很简单，就是求三个互质的数，何为互质？两两最大公约数为1， 而且，在所有两两互质的数中，肯定值越大乘积越大，因此，可以向这方面做。 但是，列出几个例子就会发现，这题目是有规律的： 例1： 1 2 3 4 5 6 （n为6） 例2： 1 2 3 4 5 6 7（n为7） 例3： 1 2 3 4 5 6 7 8 （n为8） 规律： ①. 当n为奇数时， n*n-1*n-2最大 ②. 当n为偶数时，有两个选择方案，要么选n-1*n-2*n-3 要么选n*n-1*n-3，这两个选择差就差在与3的余数关系， 这个优先策略很简单，尽量先选最大的，然后往下选，但是，如果你选了最大的以后，比如例1中，选了6，就 无法选择4也无法选择3，甚至2，所以，这种情况就不能去选择6，只能退一步选择n-1，再讨论 这样代码就出来了： ~~~ #include<iostream> using namespace std; int main() { long long n, number; cin>>n; if( n <= 2) { cout<<2; } else if(n % 2) { number = n * (n - 1) * (n - 2); cout<<number; } else { if( n % 3 == 0) { number = (n - 1) * (n - 2) * (n - 3) ; } else number = n * (n - 1) * (n - 3); cout<<number; } return 0; } ~~~

## 算法训练 区间k大数查询   时间限制：1.0s   内存限制：256.0MB   问题描述 给定一个序列，每次询问序列中第l个数到第r个数中第K大的数是哪个。 输入格式 第一行包含一个数n，表示序列长度。 第二行包含n个正整数，表示给定的序列。 第三个包含一个正整数m，表示询问个数。 接下来m行，每行三个数l,r,K，表示询问序列从左往右第l个数到第r个数中，从大往小第K大的数是哪个。序列元素从1开始标号。 输出格式 总共输出m行，每行一个数，表示询问的答案。 样例输入 5 1 2 3 4 5 2 1 5 2 2 3 2 样例输出 4 2 数据规模与约定 对于30%的数据，n,m<=100； 对于100%的数据，n,m<=1000； 保证k<=(r-l+1)，序列中的数<=106。 ~~~ // k 大数查询 #include <iostream> #include <algorithm> using namespace std; int arr[1001],brr[1001]; bool cmp(int a,int b) { return a>b; } int main() { int n,m; int l,r,k; int i,j; while(cin>>n) { for(i=0;i<n;++i) cin>>arr[i]; cin>>m; while(m--) { cin>>l>>r>>k; // 将相应的区间复制到另一个数组中，排序 for(j=l-1,i=0;j<r;++j,++i) brr[i]=arr[j]; sort(brr,brr+i,cmp); cout<<brr[k-1]<<endl; } } return 0; } ~~~

## 基础练习 数列排序   时间限制：1.0s   内存限制：512.0MB   问题描述 　　给定一个长度为n的数列，将这个数列按从小到大的顺序排列。1<=n<=200 输入格式 　　第一行为一个整数n。 　　第二行包含n个整数，为待排序的数，每个整数的绝对值小于10000。 输出格式 　　输出一行，按从小到大的顺序输出排序后的数列。 样例输入 5 8 3 6 4 9 样例输出 3 4 6 8 9 ~~~ // 数列排序 #include <iostream> #include <algorithm> using namespace std; int arr[100001]; int main() { int n,i; while(cin>>n) { for(i=0;i<n;++i) cin>>arr[i]; sort(arr,arr+n); for(i=0;i<n;++i) { if(i==n-1) cout<<arr[i]<<endl; else cout<<arr[i]<<" "; } } return 0; } ~~~

## 基础练习 十六进制转八进制   时间限制：1.0s   内存限制：512.0MB   问题描述 　　给定n个十六进制正整数，输出它们对应的八进制数。 输入格式 　　输入的第一行为一个正整数n （1<=n<=10）。 　　接下来n行，每行一个由0~9、大写字母A~F组成的字符串，表示要转换的十六进制正整数，每个十六进制数长度不超过100000。 输出格式 　　输出n行，每行为输入对应的八进制正整数。 注意 　　输入的十六进制数不会有前导0，比如012A。 　　输出的八进制数也不能有前导0。 样例输入 2 39 123ABC 样例输出 71 4435274 提示 　　先将十六进制数转换成某进制数，再由某进制数转换成八进制。 刚开始，犯得老毛病，就是先转换成了十进制，忘了题目中有一句话，每个十六进制数长度不超过100000，十万啊，大数问题了，用字符串吧。 这是错误的，我转换十进制再转换八进制的代码： ~~~ // 十六进制转八进制,WA #include <iostream> #include <string> #include <cmath> using namespace std; int arr[10000001]; // 记录八进制的数 int main() { string str; int n,m,i,num,j; cin>>n; while(n--) { cin>>str; m=str.length(); // 转换成十进制 num=0; for(i=m-1;i>=0;--i) { if(str[i]>='0'&&str[i]<='9') num+=pow(16,m-1-i)*(str[i]-'0'); else if(str[i]>='A'&&str[i]<='F') num+=pow(16,m-1-i)*(str[i]-'A'+10); } i=0; while(num/8!=0) { arr[i]=num%8; num/=8; ++i; } arr[i]=num; for(j=i;j>=0;--j) cout<<arr[j]; cout<<endl; } return 0; } ~~~ 这个是正确的，先转换二进制再转换八进制： // 修正位数，那里，因为转换成八进制，要将二进制三个一组分组，如果不能被三整除，会出错，所以 要修正位数，往前面填0，填0后要防止转换八进制后第一个为0，输出时判断一下。 // 十六进制转换8进制 AC ~~~ #include <iostream> #include <string> using namespace std; int arr[10000001]; int main() { int n,len_str,i,j; string str,str2; cin>>n; while(n--) { cin>>str; len_str=str.length(); str2=""; // 十六进制转换为二进制 for(i=0;i<len_str;++i) { switch(str[i]) { case '0':str2+="0000";break; case '1':str2+="0001";break; case '2':str2+="0010";break; case '3':str2+="0011";break; case '4':str2+="0100";break; case '5':str2+="0101";break; case '6':str2+="0110";break; case '7':str2+="0111";break; case '8':str2+="1000";break; case '9':str2+="1001";break; case 'A':str2+="1010";break; case 'B':str2+="1011";break; case 'C':str2+="1100";break; case 'D':str2+="1101";break; case 'E':str2+="1110";break; case 'F':str2+="1111";break; default:break; } } ~~~ // 修正位数，这里用十六进制的长度来对3取余，其实用2进制的 //长度也是一样的，因为1个16进制对应4个二进制，所以取余效果是相同的 ~~~ if(len_str%3==1)str2="00"+str2; else if(len_str%3==2)str2="0"+str2; len_str=str2.length(); // 二进制转换八进制 j=0; for(i=0;i<=len_str-2;i+=3) { arr[j]=(str2[i]-'0')*4+(str2[i+1]-'0')*2+(str2[i+2]-'0'); ++j; } for(i=0;i<j;++i) { if(i==0 && arr[i]==0)continue; cout<<arr[i]; } cout<<endl; } return 0; } ~~~

## 基础练习 十六进制转十进制   时间限制：1.0s   内存限制：512.0MB   问题描述 　　从键盘输入一个不超过8位的正的十六进制数字符串，将它转换为正的十进制数后输出。 　　注：十六进制数中的10~15分别用大写的英文字母A、B、C、D、E、F表示。 样例输入 FFFF 样例输出 65535 ~~~ // 十六进制转换十进制 #include <iostream> #include <string> #include <cmath> using namespace std; long long num; int main() { string str; int n,m,i; while(cin>>str) { m=str.length(); // 转换成十进制 num=0; for(i=m-1;i>=0;--i) { if(str[i]>='0'&&str[i]<='9') num+=pow(16,m-1-i)*(str[i]-'0'); else if(str[i]>='A'&&str[i]<='F') num+=pow(16,m-1-i)*(str[i]-'A'+10); } cout<<num<<endl; } return 0; } ~~~

## 基础练习 十进制转十六进制   时间限制：1.0s   内存限制：512.0MB   问题描述 　　十六进制数是在程序设计时经常要使用到的一种整数的表示方式。它有0,1,2,3,4,5,6,7,8,9,A,B,C,D,E,F共16个符号，分别表示十进制数的0至15。十六进制的计数方法是满16进1，所以十进制数16在十六进制中是10，而十进制的17在十六进制中是11，以此类推，十进制的30在十六进制中是1E。 　　给出一个非负整数，将它表示成十六进制的形式。 输入格式 　　输入包含一个非负整数a，表示要转换的数。0<=a<=2147483647 输出格式 　　输出这个整数的16进制表示 样例输入 30 样例输出 1E ~~~ // 十进制转换十六进制 #include <iostream> using namespace std; long long num,k; char arr[10000001]; int main() { int i; while(cin>>num) { i=0; while(num/16>0) { k=num%16; if( k>=0 && k<=9 ) arr[i]=char('0'+k); else if(k>=10 && k<=15) arr[i]=char('A'+k-10); num/=16; ++i; } k=num%16; if( k>=0 && k<=9 ) arr[i]=char('0'+k); else if(k>=10 && k<=15) arr[i]=char('A'+k-10); for(k=i;k>=0;--k) cout<<arr[k]; cout<<endl; } return 0; } ~~~

## 基础练习 特殊回文数   时间限制：1.0s   内存限制：512.0MB   问题描述 　　123321是一个非常特殊的数，它从左边读和从右边读是一样的。 　　输入一个正整数n， 编程求所有这样的五位和六位十进制数，满足各位数字之和等于n 。 输入格式 　　输入一行，包含一个正整数n。 输出格式 　　按从小到大的顺序输出满足条件的整数，每个整数占一行。 样例输入 52 样例输出 899998 989989 998899 数据规模和约定 　　1<=n<=54。 直观一点的，这个多加了一条剪枝，如果是五位数，在第一位数确定后 n-第一位数差不得大于 36，因为后面四位数最大为9999 所以不能大于36，其他几位数如是 ~~~ // 特殊回文数 #include <iostream> using namespace std; int n; int f[5],s[6]; bool judge(int ws,int no) { int i,sum=0; if(ws==5) { if(no==1) { if(n-f[0]>36 || n-f[0]<0) return 0; } else if(no==2) { for(i=0;i<no;++i) sum+=f[i]; if(n-sum>27 || n-sum<0) return 0; } else if(no==3) { for(i=0;i<no;++i) sum+=f[i]; if(n-sum>18 || n-sum<0) return 0; } else if(no==4) { if(f[3]!=f[1]) return 0; for(i=0;i<no;++i) sum+=f[i]; if(n-sum>9 || n-sum<0) return 0; } else { if(f[4]!=f[0]) return 0; for(i=0;i<no;++i) sum+=f[i]; if(sum!=n) return 0; } } else { if(no==1) { if(n-s[0]>45 || n-s[0]<0) return 0; } else if(no==2) { for(i=0;i<no;++i) sum+=s[i]; if(n-sum>36 || n-sum<0) return 0; } else if(no==3) { for(i=0;i<no;++i) sum+=s[i]; if(n-sum>27 || n-sum<0) return 0; } else if(no==4) { if(s[3]!=s[2]) return 0; for(i=0;i<no;++i) sum+=s[i]; if(n-sum>18 || n-sum<0) return 0; } else if(no==5) { if(s[4]!=s[1]) return 0; for(i=0;i<no;++i) sum+=s[i]; if(n-sum>9 || n-sum<0) return 0; } else { if(s[5]!=s[0]) return 0; for(i=0;i<no;++i) sum+=s[i]; if(sum!=n) return 0; } } } int main() { int i,j,k; while(cin>>n) { for(f[0]=1;f[0]<10;++f[0]) { if(!judge(5,1)) continue; for(f[1]=0;f[1]<10;++f[1]) { if(!judge(5,2)) continue; for(f[2]=0;f[2]<10;++f[2]) { if(!judge(5,3)) continue; for(f[3]=0;f[3]<10;++f[3]) { if(!judge(5,4)) continue; for(f[4]=0;f[4]<10;++f[4]) { if(!judge(5,5)) continue; for(i=0;i<5;++i) cout<<f[i]; cout<<endl; } } } } } for(s[0]=1;s[0]<10;++s[0]) { if(!judge(6,1)) continue; for(s[1]=0;s[1]<10;++s[1]) { if(!judge(6,2)) continue; for(s[2]=0;s[2]<10;++s[2]) { if(!judge(6,3)) continue; for(s[3]=0;s[3]<10;++s[3]) { if(!judge(6,4)) continue; for(s[4]=0;s[4]<10;++s[4]) { if(!judge(6,5)) continue; for(s[5]=0;s[5]<10;++s[5]) { if(!judge(6,6)) continue; for(i=0;i<6;++i) cout<<s[i]; cout<<endl; } } } } } } } return 0; } ~~~ 优化后的： ~~~ #include <iostream> using namespace std; int arr[7],i; bool isreturn(int num) { // 判断它是五位还是六位 if(i%2==0) { if(arr[0]==arr[4] && arr[1]==arr[3]) return 1; return 0; } else { if(arr[0]==arr[5] && arr[1]==arr[4] && arr[2]==arr[3]) return 1; return 0; } } bool isequal(int num,int n) { int s=0; // 数分别存储 i=0; while(num/10>0) { arr[i]=num%10; num/=10; s+=arr[i]; ++i; } arr[i]=num; s+=num; return n==s; } int main() { int num,n; while(cin>>n) { for(num=10000;num<1000000;++num) if(isequal(num,n)) if(isreturn(num)) cout<<num<<endl; } return 0; } ~~~

## 基础练习 回文数   时间限制：1.0s   内存限制：512.0MB   问题描述 　　1221是一个非常特殊的数，它从左边读和从右边读是一样的，编程求所有这样的四位十进制数。 输出格式 　　按从小到大的顺序输出满足条件的四位十进制数。 ~~~ //回文数 #include <iostream> using namespace std; int main() { int a,b,c,d; for(a=1;a<10;++a) { for(b=0;b<10;++b) { for(c=0;c<10;++c) { if(c!=b) continue; for(d=0;d<10;++d) { if(d!=a) continue; cout<<a<<b<<c<<d<<endl; } } } } return 0; } ~~~

## 基础练习 特殊的数字   时间限制：1.0s   内存限制：512.0MB   问题描述 　　153是一个非常特殊的数，它等于它的每位数字的立方和，即153=1*1*1+5*5*5+3*3*3。编程求所有满足这种条件的三位十进制数。 输出格式 　　按从小到大的顺序输出满足条件的三位十进制数，每个数占一行。 ~~~ // 特殊的数字 #include <iostream> using namespace std; int main() { int num,i,j,k; for(num=100;num<1000;++num) { i=num/100; k=num%10; j=(num-i*100-k)/10; if(num==i*i*i+j*j*j+k*k*k) cout<<num<<endl; } return 0; } ~~~

## 基础练习 杨辉三角形   时间限制：1.0s   内存限制：256.0MB   问题描述 杨辉三角形又称Pascal三角形，它的第i+1行是(a+b)i的展开式的系数。 　　 它的一个重要性质是：三角形中的每个数字等于它两肩上的数字相加。 　　 下面给出了杨辉三角形的前4行： 　　   1 　　  1 1 　　 1 2 1 　　 1 3 3 1 　　 给出n，输出它的前n行。 输入格式 输入包含一个数n。 输出格式 输出杨辉三角形的前n行。每一行从这一行的第一个数开始依次输出，中间使用一个空格分隔。请不要在前面输出多余的空格。 样例输入 4 样例输出 1 1 1 1 2 1 1 3 3 1 数据规模与约定 1 <= n <= 34。

## 基础练习 查找整数   时间限制：1.0s   内存限制：256.0MB   问题描述 给出一个包含n个整数的数列，问整数a在数列中的第一次出现是第几个。 输入格式 第一行包含一个整数n。 第二行包含n个非负整数，为给定的数列，数列中的每个数都不大于10000。 第三行包含一个整数a，为待查找的数。 输出格式 如果a在数列中出现了，输出它第一次出现的位置(位置从1开始编号)，否则输出-1。 样例输入 6 1 9 4 8 3 9 9 样例输出 2 数据规模与约定 1 <= n <= 1000。 ~~~ // 查找整数 #include <iostream> using namespace std; int arr[1005]; int main() { int n,i,num; bool isfind; while(cin>>n) { isfind=false; for(i=0;i<n;++i) cin>>arr[i]; cin>>num; for(i=0;i<n;++i) if(num==arr[i]) { isfind=true; cout<<i+1<<endl; break; } if(isfind==false) cout<<"-1"<<endl; } return 0; } ~~~