第七届蓝桥杯个人赛省赛--C语言B组

题目一

煤球数目

有一堆煤球，堆成三角棱锥形。具体：
第一层放1个，
第二层3个（排列成三角形），
第三层6个（排列成三角形），
第四层10个（排列成三角形），
....
如果一共有100层，共有多少个煤球？

请填表示煤球总数目的数字。
注意：你提交的应该是一个整数，不要填写任何多余的内容或说明性文字。

答案：171700

解析：

方法一：数学方法

方法二：暴力循环

易知每一层的数目都是上一层煤球数加上这一层的层数，代码如下：

 1 #include<cstdio>
 2 #include<iostream>
 3 using namespace std;
 4 
 5 int main()
 6 {
 7     int i=0,sum=0,num=0;
 8     //sum是煤球总数，num是当前层煤球数
 9     for(i=1;i<=100;i++)
10     {
11         num+=i;
12         sum+=num;
13     }
14     printf("%d
",sum);
15     return 0;
16 }

题目二

生日蜡烛

某君从某年开始每年都举办一次生日party，并且每次都要吹熄与年龄相同根数的蜡烛。

现在算起来，他一共吹熄了236根蜡烛。

请问，他从多少岁开始过生日party的？

请填写他开始过生日party的年龄数。
注意：你提交的应该是一个整数，不要填写任何多余的内容或说明性文字。

答案：26

解析：

暴力枚举，代码如下：

 1 #include<cstdio>
 2 #include<iostream>
 3 using namespace std;
 4 
 5 int main()
 6 {
 7     int i,j,num;
 8     //设某君从i岁开始过生日，现在j岁
 9     //num是吹灭掉蜡烛数
10     for(i=0;i<200;i++)
11     {
12         for(j=0;j<200;j++)
13         {
14             num=(i+j)*(j-i+1)/2;
15             if(num==236)
16             {
17                 printf("%d
",i);
18                 break;
19             }
20         }
21     }
22     return 0;
23 }

题目三

凑算式

这个算式中A~I代表1~9的数字，不同的字母代表不同的数字。

比如：
6+8/3+952/714 就是一种解法，
5+3/1+972/486 是另一种解法。

这个算式一共有多少种解法？

注意：你提交应该是个整数，不要填写任何多余的内容或说明性文字。

答案：29

解析：

方法一：递归法/DFS法，请自行百度

方法二：暴力枚举，注意每个字母代表的数字都不一样。代码如下：

 1 #include<cstdio>
 2 #include<iostream>
 3 using namespace std;
 4 
 5 int main()
 6 {
 7     int a[9];//a[0]~a[8]代表A-I
 8     int sum=0;
 9     double num=0;
10     for(a[0]=1;a[0]<=9;a[0]++)
11     {
12         for(a[1]=1;a[1]<=9;a[1]++)
13         {
14             if(a[1]==a[0])
15                 continue;
16             for(a[2]=1;a[2]<=9;a[2]++)
17             {
18                 if(a[2]==a[1]||a[2]==a[0])
19                     continue;
20                 for(a[3]=1;a[3]<=9;a[3]++)
21                 {
22                     if(a[3]==a[2]||a[3]==a[1]||a[3]==a[0])
23                         continue;
24                     for(a[4]=1;a[4]<=9;a[4]++)
25                     {
26                         if(a[4]==a[3]||a[4]==a[2]||a[4]==a[1]||a[4]==a[0])
27                             continue;
28                         for(a[5]=1;a[5]<=9;a[5]++)
29                         {
30                             if(a[5]==a[4]||a[5]==a[3]||a[5]==a[2]||a[5]==a[1]||a[5]==a[0])
31                                 continue;
32                             for(a[6]=1;a[6]<=9;a[6]++)
33                             {
34                                 if(a[6]==a[5]||a[6]==a[4]||a[6]==a[3]||a[6]==a[2]||a[6]==a[1]||a[6]==a[0])
35                                     continue;
36                                 for(a[7]=1;a[7]<=9;a[7]++)
37                                 {
38                                     if(a[7]==a[6]||a[7]==a[5]||a[7]==a[4]||a[7]==a[3]||a[7]==a[2]||a[7]==a[1]||a[7]==a[0])
39                                         continue;
40                                     for(a[8]=1;a[8]<=9;a[8]++)
41                                     {
42                                         if(a[8]==a[7]||a[8]==a[6]||a[8]==a[5]||a[8]==a[4]||a[8]==a[3]||a[8]==a[2]||a[8]==a[1]||a[8]==a[0])
43                                             continue;
44                                         num=(double)a[0]+(double)a[1]/a[2]+(double)(a[3]*100+a[4]*10+a[5])/(a[6]*100+a[7]*10+a[8]);
45                                         if(num==10.0)
46                                         {
47                                             sum++;
48                                         }
49                                     }
50                                 }
51                             }
52                         }
53                     }
54                 }
55             }
56         }
57     }
58     printf("%d
",sum);
59     return 0;
60 }

题目四

快速排序

排序在各种场合经常被用到。
快速排序是十分常用的高效率的算法。

其思想是：先选一个“标尺”，
用它把整个队列过一遍筛子，
以保证：其左边的元素都不大于它，其右边的元素都不小于它。

这样，排序问题就被分割为两个子区间。
再分别对子区间排序就可以了。

下面的代码是一种实现，请分析并填写划线部分缺少的代码。

 1 #include <stdio.h>
 2 
 3 void swap(int a[], int i, int j)
 4 {
 5     int t = a[i];
 6     a[i] = a[j];
 7     a[j] = t;
 8 }
 9 
10 int partition(int a[], int p, int r)
11 {
12     int i = p;
13     int j = r + 1;
14     int x = a[p];
15     while(1){
16         while(i<r && a[++i]<x);
17         while(a[--j]>x);
18         if(i>=j) break;
19         swap(a,i,j);
20     }
21     ______________________;
22     return j;
23 }
24 
25 void quicksort(int a[], int p, int r)
26 {
27     if(p<r){
28         int q = partition(a,p,r);
29         quicksort(a,p,q-1);
30         quicksort(a,q+1,r);
31     }
32 }
33     
34 int main()
35 {
36     int i;
37     int a[] = {5,13,6,24,2,8,19,27,6,12,1,17};
38     int N = 12;
39     
40     quicksort(a, 0, N-1);
41     
42     for(i=0; i<N; i++) printf("%d ", a[i]);
43     printf("
");
44     
45     return 0;
46 }

注意：只填写缺少的内容，不要书写任何题面已有代码或说明性文字。

答案：swap(a,p,j)

可验证的完整代码如下：

 1 #include <stdio.h>
 2 
 3 void swap(int a[], int i, int j)
 4 {
 5     int t = a[i];
 6     a[i] = a[j];
 7     a[j] = t;
 8 }
 9 
10 int partition(int a[], int p, int r)
11 {
12     int i = p;
13     int j = r + 1;
14     int x = a[p];
15     while(1){
16         while(i<r && a[++i]<x);
17         while(a[--j]>x);
18         if(i>=j) break;
19         swap(a,i,j);
20     }
21     //______________________;
22     swap(a,p,j);
23     return j;
24 }
25 
26 void quicksort(int a[], int p, int r)
27 {
28     if(p<r){
29         int q = partition(a,p,r);
30         quicksort(a,p,q-1);
31         quicksort(a,q+1,r);
32     }
33 }
34     
35 int main()
36 {
37     int i;
38     int a[] = {5,13,6,24,2,8,19,27,6,12,1,17};
39     int N = 12;
40     
41     quicksort(a, 0, N-1);
42     
43     for(i=0; i<N; i++) printf("%d ", a[i]);
44     printf("
");
45     
46     return 0;
47 }

题目五

抽签

X星球要派出一个5人组成的观察团前往W星。
其中：
A国最多可以派出4人。
B国最多可以派出2人。
C国最多可以派出2人。
....

那么最终派往W星的观察团会有多少种国别的不同组合呢？

下面的程序解决了这个问题。
数组a[] 中既是每个国家可以派出的最多的名额。
程序执行结果为：
DEFFF
CEFFF
CDFFF
CDEFF
CCFFF
CCEFF
CCDFF
CCDEF
BEFFF
BDFFF
BDEFF
BCFFF
BCEFF
BCDFF
BCDEF
....
(以下省略，总共101行)

 1 #include <stdio.h>
 2 #define N 6
 3 #define M 5
 4 #define BUF 1024
 5 
 6 void f(int a[], int k, int m, char b[])
 7 {
 8     int i,j;
 9     
10     if(k==N){ 
11         b[M] = 0;
12         if(m==0) printf("%s
",b);
13         return;
14     }
15     
16     for(i=0; i<=a[k]; i++){
17         for(j=0; j<i; j++) b[M-m+j] = k+'A';
18         ______________________;  //填空位置
19     }
20 }
21 int main()
22 {    
23     int  a[N] = {4,2,2,1,1,3};
24     char b[BUF];
25     f(a,0,M,b);
26     return 0;
27 }

仔细阅读代码，填写划线部分缺少的内容。

注意：不要填写任何已有内容或说明性文字。

答案：f(a,k+1,m-i,b) 或者 f(a,k+1,m-j,b)

代码填空题完成后代入完整程序进行验证是最好的检验方法。

可验证的完整代码如下：

 1 #include <stdio.h>
 2 #define N 6
 3 #define M 5
 4 #define BUF 1024
 5 
 6 void f(int a[], int k, int m, char b[])
 7 {
 8     int i,j;
 9     
10     if(k==N){ 
11         b[M] = 0;
12         if(m==0) printf("%s
",b);
13         return;
14     }
15     
16     for(i=0; i<=a[k]; i++){
17         for(j=0; j<i; j++) b[M-m+j] = k+'A';
18         f(a,k+1,m-i,b) ;  //填空位置
19     }
20 }
21 int main()
22 {    
23     int  a[N] = {4,2,2,1,1,3};
24     char b[BUF];
25     f(a,0,M,b);
26     return 0;
27 }

题目六

方格填数

如下的10个格子

填入0~9的数字。要求：连续的两个数字不能相邻。
（左右、上下、对角都算相邻）

一共有多少种可能的填数方案？

请填写表示方案数目的整数。
注意：你提交的应该是一个整数，不要填写任何多余的内容或说明性文字。

答案：1580

解析：http://www.cnblogs.com/xiangguoguo/p/5339605.html

  1 #include<stdio.h>
  2 #include<stdlib.h>
  3 int count=0;
  4 int take[10],index=0;//记录当前已经填入的数字，用于填数字前判断是否已经使用，避免重复使用 
  5 int is_legal(int s[3][4])//判断是否满足要求：相邻位置数字不能相邻，就是两数字的差大于1.就是为什么s[0][0]、s[2][3]置为-2；
  6 {
  7     //这里的判断方法有点死板。假设每个位置都有上下左右和对角，只需要判断这些位置
  8     //是不是在数组中，在就进行比较，不在就说明没有。 
  9     for(int i=0;i<3;i++)
 10     {
 11         for(int j=0;j<4;j++)
 12         {
 13             if(j-1>=0)
 14             {
 15                 if(abs(s[i][j]-s[i][j-1])==1)
 16                 {
 17                     return 0;
 18                 }
 19             }
 20             if(j+1<4)
 21             {
 22                 if(abs(s[i][j]-s[i][j+1])==1)
 23                 {
 24                     return 0;
 25                 }
 26             }
 27             if(i+1<3)
 28             {
 29                 if(abs(s[i][j]-s[i+1][j])==1)
 30                 {
 31                     return 0;
 32                 }
 33             }
 34             if(j-1>=0&&i+1<3)
 35             {
 36                 if(abs(s[i][j]-s[i+1][j-1])==1)
 37                 {
 38                     return 0;
 39                 }
 40             }
 41             if(j+1<4&&i+1<3)
 42             {
 43                 if(abs(s[i][j]-s[i+1][j+1])==1)
 44                 {
 45                     return 0;
 46                 }
 47             }
 48             if(i-1>=0&&j+1<4)
 49             {
 50                 if(abs(s[i][j]-s[i-1][j+1])==1)
 51                 {
 52                     return 0;
 53                 }
 54             }
 55             if(i-1>=0)
 56             {
 57                 if(abs(s[i][j]-s[i-1][j])==1)
 58                 {
 59                     return 0;
 60                 }
 61             }
 62             if(j-1>=0&&i-1>=0)
 63             {
 64                 if(abs(s[i][j]-s[i-1][j-1])==1)
 65                 {
 66                     return 0;
 67                 }
 68             }
 69         }
 70     } 
 71     return 1;
 72 }
 73 void fun(int s[3][4],int a,int b)
 74 {
 75     int i;
 76     if(a==2&&b==3)//表示当前已经填满了表格，需要进行判断看是否满足要求 
 77     {
 78         if(is_legal(s))
 79         {
 80             count++;
 81         }
 82     }
 83     else//继续填写 
 84     {
 85         for(i=0;i<=9;i++)
 86         {
 87             int j;
 88             for(j=0;j<index;j++)//填写的数字必须是没有用过的 
 89             {
 90                 if(i==take[j])
 91                 {
 92                     break;
 93                 }
 94             }
 95             if(j==index)
 96             {
 97                 s[a][b]=i;
 98                 take[index++]=i;
 99                 if(b<3)//表示当前行还没填完 
100                 {
101                     fun(s,a,b+1);
102                 }
103                 else//当前行填完就从下一行开始 
104                 {
105                     if(a<2)//判断当前行是否是最后一行 
106                     {
107                         fun(s,a+1,0);
108                     }
109                 }
110                 index--;//在一次填满结束后，当前位置的数字换为其他可以填写的数字
111                         //所以当前使用的数字需要出去。 
112             }
113         } 
114     }
115 }
116 int main()
117 {
118     int s[3][4];
119     s[0][0]=-2;
120     s[2][3]=-2;
121     //左上角和右下角没有，为了方便判断把数值设为-2（小于-1大于10均可） 
122     fun(s,0,1);
123     printf("%d
",count);
124     return 0;
125 }

题目七

剪邮票

如【图1.jpg】, 有12张连在一起的12生肖的邮票。
现在你要从中剪下5张来，要求必须是连着的。
（仅仅连接一个角不算相连）
比如，【图2.jpg】，【图3.jpg】中，粉红色所示部分就是合格的剪取。

请你计算，一共有多少种不同的剪取方法。

请填写表示方案数目的整数。
注意：你提交的应该是一个整数，不要填写任何多余的内容或说明性文字。

答案：116

解析：http://www.cnblogs.com/program-ccc/p/5321243.html

 1 #include<cstdio>
 2 #include<cstring>
 3 using namespace std;
 4 int a[3][4]={
 5     {0,1,2,3},
 6     {4,5,6,7},
 7     {8,9,10,11}};//为了方便，均执行-1操作
 8 int vec[15];
 9 int res;
10 int dx[4]={1,0,-1,0};
11 int dy[4]={0,1,0,-1};
12 int vis[5][5];
13 bool Include(int x)
14 {
15     for(int i=0;i<5;i++)
16         if(vec[i]==x)    return true;
17     return false;
18 }
19 void Connect(int y,int x)
20 {
21     for(int i=0;i<4;i++)
22     {
23         int ny=dy[i]+y;
24         int nx=dx[i]+x;
25         if(0<=ny&&ny<3&&0<=nx&&nx<4&&!vis[ny][nx]&&Include(a[ny][nx]))
26         {
27                 vis[ny][nx]=1;
28                 Connect(ny,nx);
29         }
30     }
31 }
32 void dfs(int i,int j)
33 {
34     if(i==12)
35     {
36         if(j==5)
37         {
38             memset(vis,0,sizeof(vis));
39             int y=vec[0]/4,x=vec[0]%4;
40             vis[y][x]=1;
41             Connect(y,x);
42             int mark=0;
43             for(int k=0;k<j;k++)
44             {
45                 y=vec[k]/4;
46                 x=vec[k]%4;
47                 if(vis[y][x]==1)        
48                     mark++;
49             }
50             if(mark==5)    res++;
51         }
52         return ;
53     }
54     vec[j]=*(a[0]+i);
55     dfs(i+1,j+1);
56     vec[j]=0;
57     dfs(i+1,j);
58 }
59 
60 int main()
61 {
62     res=0;
63     dfs(0,0);
64     printf("%d
",res);
65     return 0;
66 }

题目八

四平方和

四平方和定理，又称为拉格朗日定理：
每个正整数都可以表示为至多4个正整数的平方和。
如果把0包括进去，就正好可以表示为4个数的平方和。

比如：
5 = 0^2 + 0^2 + 1^2 + 2^2
7 = 1^2 + 1^2 + 1^2 + 2^2
（^符号表示乘方的意思）

对于一个给定的正整数，可能存在多种平方和的表示法。
要求你对4个数排序：
0 <= a <= b <= c <= d
并对所有的可能表示法按 a,b,c,d 为联合主键升序排列，最后输出第一个表示法

程序输入为一个正整数N (N<5000000)
要求输出4个非负整数，按从小到大排序，中间用空格分开

例如，输入：
5
则程序应该输出：
0 0 1 2

再例如，输入：
12
则程序应该输出：
0 2 2 2

再例如，输入：
773535
则程序应该输出：
1 1 267 838

资源约定：
峰值内存消耗 < 256M
CPU消耗 < 3000ms

请严格按要求输出，不要画蛇添足地打印类似：“请您输入...” 的多余内容。

所有代码放在同一个源文件中，调试通过后，拷贝提交该源码。

注意: main函数需要返回0
注意: 只使用ANSI C/ANSI C++ 标准，不要调用依赖于编译环境或操作系统的特殊函数。
注意: 所有依赖的函数必须明确地在源文件中 #include <xxx>，不能通过工程设置而省略常用头文件。

提交时，注意选择所期望的编译器类型。

解析：http://blog.csdn.net/luoluozlb/article/details/51339287

 1 #include <stdio.h>
 2 #include <math.h>
 3 
 4 int main()
 5 {
 6     int a, b, c, n, flag = 0;
 7     double maxN, d;
 8     scanf("%d", &n);
 9     maxN = sqrt((double)n);
10 
11     for(a = 0; a <= maxN; a ++){
12         for(b = a; b <= maxN; b ++){
13             for(c = b; c <= maxN; c ++){
14                 d = sqrt((double)(n - a*a - b*b - c*c));
15                 if(d == (int)d){
16                     printf("%d %d %d %d
", a, b, c, (int)d);
17                     flag = 1;
18                     break;
19                 }
20             }
21             if(flag)
22                 break;
23         }
24         if(flag)
25             break;
26     }
27     return 0;
28 }

题目九

交换瓶子

有N个瓶子，编号 1 ~ N，放在架子上。

比如有5个瓶子：
2 1 3 5 4

要求每次拿起2个瓶子，交换它们的位置。
经过若干次后，使得瓶子的序号为：
1 2 3 4 5

对于这么简单的情况，显然，至少需要交换2次就可以复位。

如果瓶子更多呢？你可以通过编程来解决。

输入格式为两行：
第一行: 一个正整数N（N<10000）, 表示瓶子的数目
第二行：N个正整数，用空格分开，表示瓶子目前的排列情况。

输出数据为一行一个正整数，表示至少交换多少次，才能完成排序。

例如，输入：
5
3 1 2 5 4

程序应该输出：
3

再例如，输入：
5
5 4 3 2 1

程序应该输出：
2

资源约定：
峰值内存消耗 < 256M
CPU消耗 < 1000ms

请严格按要求输出，不要画蛇添足地打印类似：“请您输入...” 的多余内容。

所有代码放在同一个源文件中，调试通过后，拷贝提交该源码。

提交时，注意选择所期望的编译器类型。

解析：http://blog.csdn.net/luoluozlb/article/details/51339307

 1 #include <stdio.h>
 2 #include <math.h>
 3 
 4 int main()
 5 {
 6     int arr[10010];        //记录第i个瓶子编号为多少
 7     int flag[10010];    //记录编号为i的瓶子在哪儿
 8     int ans = 0;
 9     int n,i;
10     scanf("%d",&n);
11 
12     for(i = 1 ; i <= n ; i ++)
13         scanf("%d",&arr[i]);
14         
15     for(i = 1 ; i <= n ; i ++ )
16         flag[arr[i]] = i;
17     
18     for(i = 1 ; i <= n ; i ++)
19     {
20         if( i != arr[i] )
21         {
22             int x = arr[i];
23             arr[i] ^= arr[flag[i]] ^= arr[i] ^= arr[flag[i]];
24             flag[i] ^= flag[x] ^= flag[i] ^= flag[x];
25             ans ++;
26         }  
27     }
28     
29     printf("%d
",ans);
30     return 0;
31 }

题目十

最大比例

X星球的某个大奖赛设了M级奖励。每个级别的奖金是一个正整数。
并且，相邻的两个级别间的比例是个固定值。
也就是说：所有级别的奖金数构成了一个等比数列。比如：
16,24,36,54
其等比值为：3/2

现在，我们随机调查了一些获奖者的奖金数。
请你据此推算可能的最大的等比值。

输入格式：
第一行为数字 N (0<N<100)，表示接下的一行包含N个正整数
第二行N个正整数Xi(Xi<1 000 000 000 000)，用空格分开。每个整数表示调查到的某人的奖金数额

要求输出：
一个形如A/B的分数，要求A、B互质。表示可能的最大比例系数

测试数据保证了输入格式正确，并且最大比例是存在的。

例如，输入：
3
1250 200 32

程序应该输出：
25/4

再例如，输入：
4
3125 32 32 200

程序应该输出：
5/2

再例如，输入：
3
549755813888 524288 2

程序应该输出：
4/1

资源约定：
峰值内存消耗 < 256M
CPU消耗 < 3000ms

请严格按要求输出，不要画蛇添足地打印类似：“请您输入...” 的多余内容。

所有代码放在同一个源文件中，调试通过后，拷贝提交该源码。

提交时，注意选择所期望的编译器类型。

解析：http://www.aichengxu.com/cyvyan/6607933.htm

 1 #include <iostream>
 2 #include <algorithm>
 3 #include <cstring>
 4 using namespace std;
 5 
 6 long long int a[100],p1[100],p2[100];
 7 
 8 long long int gcd(long long int a,long long int b)
 9 {
10     long long int t;
11     while(t=a%b)
12     {
13         a=b;
14         b=t;
15     }
16     return b;
17 }
18 
19 int main()
20 {
21     int n;
22     cin>>n;
23 
24     memset(a,0,sizeof(a));
25     for(int i=0; i<n; i++)
26     {
27         cin>>a[i];
28     }
29     sort(a,a+n);//从小到大排序
30     int k=1;
31     for(int i=1; i<n; i++)//去掉重复的数字
32     {
33         if(a[i]!=a[i-1])
34             a[k++]=a[i];
35     }
36     n=k;
37     if(n==1)//如果只剩下一个数字，则公比为1/1
38     {
39         cout<<"1/1"<<endl;
40         return 0;
41     }
42     else if(n==2)//如果剩下两个数字，则公比为两者的商，利用最大公约数求商
43     {
44         long long int g=gcd(a[n-1],a[n-2]);
45         cout<<a[n-1]/g<<"/"<<a[n-2]/g<<endl;
46     }
47     else if(n>2)
48     {
49         k=0;
50         long long int g,g1,g2;
51         for(int i=1; i<n; i++)//分别求出后一项与前一项的比值
52         {
53             g=gcd(a[i],a[i-1]);
54             p1[k]=a[i]/g;
55             p2[k]=a[i-1]/g;
56             k++;
57         }
58         double t=999999;
59         long long int t1,t2,tt1,tt2;
60 
61         for(int i=0; i<k; i++)//遍历每一个比值，用大的除以小的，找出最小的公比
62             for(int j=i+1; j<k; j++)
63             {
64 
65                 if(p1[i]*p2[j]>p1[j]*p2[i])
66                 {
67                     t1=p1[i]/p1[j];
68                     t2=p2[i]/p2[j];
69                 }
70                 else if(p1[i]*p2[j]<p1[j]*p2[i])
71                 {
72                     t1=p1[j]/p1[i];
73                     t2=p2[j]/p2[i];
74                 }
75                 else if(p1[i]*p2[j]==p1[j]*p2[i])
76                 {
77                     t1=p1[i];
78                     t2=p2[i];
79                 }
80                 if(1.0*t1/t2<t)
81                 {
82                     t=1.0*t1/t2;
83                     tt1=t1;
84                     tt2=t2;
85                 }
86             }
87         g=gcd(tt1,tt2);
88         cout<<tt1/g<<"/"<<tt2/g<<endl;
89     }
90 
91     return 0;
92 }