题目一
煤球数目
有一堆煤球，堆成三角棱锥形。具体：
第一层放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\n",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\n",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\n",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("\n");
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("\n");
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\n",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\n",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\n",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\n",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\n", 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
请严格按要求输出，不要画蛇添足地打印类似：“请您输入...” 的多余内容。
所有代码放在同一个源文件中，调试通过后，拷贝提交该源码。
注意: main函数需要返回0
注意: 只使用ANSI C/ANSI C++ 标准，不要调用依赖于编译环境或操作系统的特殊函数。
注意: 所有依赖的函数必须明确地在源文件中 #include <xxx>， 不能通过工程设置而省略常用头文件。
提交时，注意选择所期望的编译器类型。
解析：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\n",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
请严格按要求输出，不要画蛇添足地打印类似：“请您输入...” 的多余内容。
所有代码放在同一个源文件中，调试通过后，拷贝提交该源码。
注意: main函数需要返回0
注意: 只使用ANSI C/ANSI C++ 标准，不要调用依赖于编译环境或操作系统的特殊函数。
注意: 所有依赖的函数必须明确地在源文件中 #include <xxx>， 不能通过工程设置而省略常用头文件。
提交时，注意选择所期望的编译器类型。
解析：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 }