蓝桥杯真题集锦2016.docx

《蓝桥杯真题集锦2016.docx》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、1.代码设计（满分5分）625这个数字很特别，625的平方等于，刚好其末3位是625本身。除了625，还有其它的3位数有这个特征吗？请编写程序，寻找所有这样的3位数：它的平方的末3位是这个数字本身。输出结果中，从小到大，每个找到的数字占一行。比如那个625就输出为：625代码:#includeusingnamespacestd;intshousan(intn){returnn%1000;//得到后三位}intmain(){for(inti=100;i<=999;i++){if(i==shousan(i*i))cout<

2、turn0;}运行结果：1.代码设计（满分11分）考虑方程式：a^3+b^3=c^3+d^3其中：“^”表示乘方。a、b、c、d是互不相同的小于30的正整数。这个方程有很多解。比如：a=1，b=12，c=9，d=10就是一个解。因为：1的立方加12的立方等于1729，而9的立方加10的立方也等于1729。当然，a=12，b=1，c=9，d=10显然也是解。如果不计abcd交换次序的情况，这算同一个解。你的任务是：找到所有小于30的不同的正整数解。把abcd按从小到大排列，用逗号分隔，每个解占用1行。比如，刚才的解输出为：1,9,10,12不同解间的顺序可以不考虑

3、。代码：#includeusingnamespacestd;#includeintmain(){inta,b,c,d;for(a=1;a<30;a++)for(b=a+1;b<30;b++)for(c=b+1;c<30;c++)for(d=c+1;d<30;d++){if(b*b*b+c*c*c==a*a*a+d*d*d)cout<

4、2+1,3+1+1+12+2+2,2+2+1+1,2+1+1+1+11+1+1+1+1+1+1现在的问题是，对于给定的正整数n,编写算法打印所有划分。用户从键盘输入n（范围1~10）程序输出该整数的所有划分。整数划分问题是算法中的一个经典命题之一，有关这个问题的讲述在讲解到递归时基本都将涉及。所谓整数划分，是指把一个正整数n写成如下形式：    n=m1+m2+...+mi;（其中mi为正整数，并且1<=mi<=n），则{m1,m2,...,mi}为n的一个划分。如果{m1,m2,...,mi}中的最大值不超过m，即max(m1,m2,...,mi)<=m，则称

5、它属于n的一个m划分。这里我们记n的m划分的个数为f(n,m);例如但n=4时，他有5个划分，{4},{3,1},{2,2},{2,1,1},{1,1,1,1};注意4=1+3和4=3+1被认为是同一个划分。该问题是求出n的所有划分个数，即f(n,n)。下面我们考虑求f(n,m)的方法;1.递归法：   根据n和m的关系，考虑以下几种情况：  (1)当n=1时，不论m的值为多少（m>0)，只有一种划分即{1};   (2)当m=1时，不论n的值为多少，只有一种划分即n个1，{1,1,1,...,1};   (3)当n=m时，根据划分中是否包含n，可以分为两种情况

6、：      (a)划分中包含n的情况，只有一个即{n}；      (b)划分中不包含n的情况，这时划分中最大的数字也一定比n小，即n的所有(n-1)划分。      因此f(n,n)=1+f(n,n-1);   (4)当nm时，根据划分中是否包含最大值m，可以分为两种情况：      (a)划分中包含m的情况，即{m,{x1,x2,...xi}},其中{x1,x2,...xi}的和为n-m，因此这情况下          为f(n-m,m)       (b)划分中不包含m的情况，

7、则划分中所有值都比m小，即n的(m-1)划分，个数为f(n,m-1);第五种情况中为划分中最大的整数不超过m，而不超过m则有两种情况，一种是划分中有m，此时剩下的则为n-m，那么相当于对n-m进行划分，并且划分中的最大整数不超过m；另一种情况为不包含m，那么最大整数位m-1，相当于对n进行划分，最大整数不超过m-1.      因此f(n,m)=f(n-m,m)+f(n,m-1);     综上所述：                            f(n,m)= 1;              (n=1orm=1)               f(n,m

8、)= f(n,n);