程序设计与算法

程序设计与算法

目录

1.结构体综合训练4

2.掷骰子游戏7

3.n级台阶问题9

4.单位分数求解11

5.位平方和12

6.让我怎能过大年13

7.回文素数15

8.数独游戏16

9.基于链表的学生信息管理21

10.派遣敢死队25

II.勾股定理28

12.数字排列30

13.调和级数32

14.数单词的个数33

15.循环移动35

16.函数和字符串排列37

17.围圈数数问题41

18.指针与字符串拍序42

19.xAx=1044

20.子集和问题45

21.结点选择48

22.最短路49

23.安慰奶牛50

24.逆序对51

25.操作格子53

26.关联矩阵55

27.Torry的困惑58

28.最小乘积59

29.时间复杂度和空间复杂度61

30.删除零元素62

31.暴力搜索解0-1背包问题64

32.杨辉三角形66

33.布线问题67

34.0-1背包问题之分支限界法71

35.装载问题之分支限界法75

36.排列的字典序问题78

37.身份证号码验证78

38.信用卡号验证81

39.软件比赛83

40.循环小数83

41.直角三角形的边85

42.617485

43.匪警请拨11088

44.低碳生活大奖赛92

45.石子合并问题95

46.租用游艇问题95

47.数字三角形96

48.用数组实现大数加法96

50.符号三角形问题100

51.批处理作业调度问题103

52.魔方矩阵105

53.螺旋矩阵106

54.39级台阶107

55.李白打酒108

56.二分法求方程的根114

57.验证哥德巴赫猜想115

58.用数字出图形116

59.最优装载问题117

60.活动安排问题121

61.最大k乘积问题123

62.独立任务最优调度124

63.判断数字是多少位数,正向反向输出127

64.C语言实现万年历程序128

65.0-1背包问题动态规划法129

66.最长公共子序列131

67.最大子段和问题133

68.矩阵连乘问题136

69.最大公约数和最小公倍数140

70.乘积是平方数141

71.最大公约数之和143

72.数字和与倍数144

73.大数的阶乘145

74.指向函数的指针146

75.数组操作146

76.字符串排序148

77.转圈数数淘汰149

78.十六进制转换为十进制150

79.递归逆向输出字符串151

80.统计最长的单词152

81.数的插入排序153

82.统计个位数字相同的数的个数155

83.哥德巴赫猜想155

84.数字游戏157

85.大小之差158

86.求满足条件的回文数字161

87.13年蓝桥杯校内选拔赛B组试题163

88.数组循环输出168

89.螺旋矩阵168

90.数的进制转换170

91.求满足如下条件的五位数字171

92.用二分法求方程2x3-4x2+3x-6=0在（-10,10）之间的根172

93.花朵数问题173

94.无限循环小数173

95.角谷猜想174

96.运动员打靶问题175

97.直角三角形的边问题176

98.输出互不重复的三位偶数177

99.判断几位数，正序和逆序输出178

IOO.getcharVSscanf179

101.最大子段和问题181

102.整数因子分解问题184

103.标准二维表问题185

104.集合划分问题185

105.排列的字典序问题185

106.有重复元素的排列问题186

107.半数单集问题186

108.众数问题186

109.字典序问题187

110.金币阵列问题190

111.最大间隙问题193

1.结构体综合训练

有10个学生，每个学生的数据包括学号、姓名、3门课的成绩，编写如下函数:

①输入10个学生的基本信息(Input)；

②求出每个学生的平均分(Average)；

③求出最高分的学生信息(High_Score)；

④输出每个学生的信息(Output)；

⑤按平均分从高到低的顺序排序(Sort)o

参考代码如下：

#incIude<stdio.h>

#include<math.h>

structStudent{

intnum;

charname[10];

intscore[3];

fIoataverage;

}；

intinput(structStudentperson[],intn)

(

inti,j,k;

for(i=0;i<n;i++)

(

scanf('%cT,&person[i].num);

getchar();

gets(person[i].name);

for(j=0;j<3;j++)

，，，，

scanf(%dt&person[i].score[j]);

)

return0;

)

intoutput(structStudentperson[],intn)

inti,j,k;

printfC--\n〃）；

for(i=0;i<3;i++)

(

printf("%5d”,person[i].num);

printf(〃％1Os”,person[i].name);

for(j=0;j<3;j++)

printf(z，%5dz，,person[i].score[j]);

putchar('\n);

1

return0;

)

intaverage(structStudentperson[],intn)

t

inti,j,k=0;

floataverage,maxaverage=0.;

for(i=0;i<3;i++)

(

average=0.0;

for(j=0;j<3;j++)

average+=person[i].score[j];

person[i].average=average/3;

printf(〃％6.2f”,person[i].average);

if(average/3>maxaverage)

(

maxaverage=average/3;

k二i;

)

)

putchar('\n);

printf("thebeststudentis%s.\n，z,person[k].name);

return0;

]

intsort(structStudent*ps[],intn)

(

inti,j,k;

structStudent*temp;

for(i=0;i<n;i++)

k=i;

for(j=i+1;j<n;j++)

{

if(ps[j]->average>ps[k]->average)

k=j；

1

if(k!=i)

(

temp=ps[i];

ps[i]=ps[k];

ps[k]=temp;

1

}

for(i=0;i<n;i++)

(

printf(z，%5d%10s%6.2f\n，z,ps[i]->num,ps[i]->name,

ps[i]->average);

)

return0;

1

intmain()

(

structStudentstu[10];//&stu[0],&stu[1],&stu[2]stu,stu+1,

stu+2

structStudent*ps[10];//ps[0],ps[1],ps[2]

inti,j,k;

input(stu,10);

output(stu,10);

average(stu,10);

for(i=0;i<10;i++)

ps[i]=stu+i;

sort(ps,10);

return0;

}

2.掷骰子游戏

编写函数模拟掷骰子的游戏(两个骰子)。第一次掷的时候，如果点数之和为7

或“则获胜；如果点数之和为2、3或12则落败；其他情况下的点数之和称为

“目标”，游戏继续。在后续的投掷中，如果玩家再次掷出“目标”点数则获

胜，掷出7则落败，其他情况都忽略，游戏继续进行。每局游戏结束时，程序

询问用户是否再玩一次，如果用户输入的回答不是y或Y,程序会显示胜败的次

数然后终止。

参考代码如下：

#include<stdio.h>

#incIude<stdIib.h>

#include<time.h>

intmain()

(

intwinCount,IostCount;

intfirst,second;

inttarget;

charinput;

winCount=IostCount=0;

srand(time(0));

first=rand()%6+1;

second=rand()%6+1;

printf("%d%d\n〃，first,second);

target=first+second;

if(target==7||target==11)

(

printf(^youwin\n〃)；

winCount++;

1

eIse

if(target==2||target=3||target==12)

(

printf("youIost\n〃)；

lostCount++;

)

eIse

(

printf("proceedornot?");

input=getchar();

while(input=>Y1||input='y')

(

first=rand()%6+1;

second=rand()%6+1;

printf("%d%d\n”,first,second);

if(target==first+second){

printf("youwin\n");

winCount++;

)

eIse

if(first+second=7){

printf("youIost\n");

lostCount++;

}

printf("proceedornot?");

getchar();

input=getchar();

)

}

)

printf(〃win=%d,Iost=%d\n〃，winCount,IostCount);

return0;

)

3.n级台阶问题

有n级台阶。从地面(第0级)出发，首先连续的上台阶，上到不超过第n级

的某一个位置后再连续的下台阶，直到回到地面。若每次上下台阶只允许走1

级或2级，请问可能的上下台阶的方案数是多少？

特别地，在0级站着不动也算一种方案。

【数据格式】

输入一行包含两个正整数n和m0

输出一个整数，表示n级台阶有多少种合法的走楼梯方案，答案对m取余。

例如：输入：

210007

程序应该输出

6

【样例说明1】

共有6种方案(其中+表示上台阶，-表示下台阶)：

(1)原地不动

⑵+1-1

(3)+2-2

(4)+2-1-1

(5)+1+1-2

(6)+1+1-1-1

再例如，输入：

314

程序应该输出：

1

【样例说明2]

共有15种方案，对14取余后得1。

【数据规模】

对于30%的数据，n<=10000；

对于100%的数据，n<=10*17,m<=2*10^9o

资源约定：

峰值内存消耗(含虚拟机)<256M

CPU消耗<1000ms

分析：问题本质是一个斐波拉契数列问题，加上组合的相关知识，可以按如下思

路得到相应的答案。

11235813

当n=2时，即要从第0个台阶走到第2个台阶，共有如下的走法：

1+1*1+2*2=6

其中第一个1对应原地不动的情况，第二个1*1代表上一个台阶的方法数，乘下

一个台阶的方法数。2*2代表上两个台阶的方法数乘下两个台阶的方法数

类似，如果n=3,答案为：

1+1*1+2*2+3*3=2+4+9=15

参考代码如下：

#incIude<stdio.h>

intmain()

(

inti;

int*a;

intn,m,sum=0;

scanf("%d%d”,&n,&m);

a=newint[n+1];

for(i=0;i<n+1;i++)

a[i]=0;

a[0]=a[1]=1;

for(i=2;i<n+1;i++)

a[i]=a[i-1]+a[i-2];

for(i=1;i<n+1;i++)

sum+=a[i]*a[i];

printf(，z%d\n，z,(sum+1)%m);

return0;

}

4.单位分数求解

形如：1/a的分数称为单位分数。

可以把1分解为若干个互不相同的单位分数之和。

例如：

1=1/2+1/3+1/9+1/18

1=1/2+1/3+1/10+1/15

1=1/3+1/5+1/7+1/9+1/11+1/15+1/35+1/45+1/231

等等，类似这样的分解无穷无尽。

我们增加一个约束条件：最大的分母必须不超过30

请你求出分解为n项时的所有不同分解法。

【数据格式要求】

输入一个整数n,表示要分解为n项(n<12)

输出分解后的单位分数项，中间用一个空格分开。

每种分解法占用一行，行间的顺序按照分母从小到大排序。

例如，

输入：

4

程序应该输出：

1/21/31/81/24

1/21/31/91/18

1/21/31/101/15

1/21/41/51/20

1/21/41/61/12

再例如，

输入：

5

程序应该输出：

1/21/31/121/211/28

1/21/41/61/211/28

1/21/41/71/141/28

1/21/41/81/121/24

1/21/41/91/121/18

1/21/41/101/121/15

1/21/51/61/121/20

1/31/41/51/61/20

资源约定：

峰值内存消耗（含虚拟机）<256M

CPU消耗<2000ms

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

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

注意：不要使用package语句。不要使用jdk1.7及以上版本的特性。

注意：主类的名字必须是：Main,否则按无效代码处理。

5.位平方和

把一个整数的每个数位都平方后求和，又得到一个整数，我们称这个整数为：

位平方和。

对新得到的整数仍然可以继续这一运算过程。比如，给定整数为4,则一系列的

运算结果为：

16,37,58,89

本题的要求是，已知一个整数x,求第n步的运算结果。

【数据格式要求】

输入，两个整数xn,中间以空格分开。表示求x的第n步位平方和。其中，

x,y都大于0,且小于100000。

输出，一个整数，表示所求结果。

例如，

输入：

43

则程序应该输出：

58

再例如，

输入：

131410

则程序应该输出：

20

资源约定：

峰值内存消耗(含虚拟机)<256M

CPU消耗<1000ms

参考代码如下：

#include<stdio.h>

intmain()

(

intm,n;

inttemp,sum;

inti;

/，，，

scanf(%d%d,&m,&n);

for(i=0;i<n;i++)

(

sum=0;

whiIe(m){

sum=sum+(m%10)*(m%10);

m=m/10;

)

m=sum;

1

printf("%d\n",sum);

return0;

)

6.让我怎能过大年

有如下的加法算式。其中每个汉字代表一个数字。

(如存在对齐问题，可参见【图l.png】)

年

大年

过大年

能过大年

怎能过大年

我怎能过大年

+让我怎能过大年

A股b能AE能AE能Ak能Ah能AB能AE

请填写“让我怎能过大年”所代表的整数。

所有数字连在一起，中间不要空格。例如：”3125697“。当然，这个不是正确的

答案。

注意：只填写一个整数，不要填写任何多余的内容。

#incIude<stdio.h>

#incIude<math.h>

intmain()

(

〃让我怎能过大年

Iongi,sum,j,k;

for(i=1000000;i<10000000;i++)

(

j=(i/1000)%10;;

sum=0;

for(k=0;k<7;k++)

sum=sum*10+j;

〃能能能能能能能能

j=i；

k=1000000;

while(k)

(

j+=i%k;

k=k/10;

)

if(sum==j)

/，，，

printf(%ld\nIi);

1

return0;

)

7.回文素数

10301是个5位的素数。它有个特点，把数字倒过来还是它本身，具有这样特征

的素数，我们称之为：回文素数。

10501

10601

11311

这些都是5位的回文素数。

请你计算一下，像这样的5位数的回文素数，一共有多少个？

请填写这个表示个数的整数，注意不要写任何其它多余的内容，比如说明或解

释文字，也不要列出所有的回文素数。

#incIude<stdio.h>

#include<math.h>

intfIag1(intn)

(

inti;

for(i=2;i<sqrt(n);i++)

if(n%i=0)

return0;

return1;

)

intfIag2(intn)

(

intm=n;

inttemp=0;

while(m)

temp=temp*10+m%10;

m=m/10;

)

if(n-temp)

return1;

eIse

return0;

)

intmain()

(

inti,count=O;

for(i=10000;i<100000;i++)

(

if(fIag1(i)&&flag2(i))

count++;

)

printf("%d\n",count);

return0;

)

8.数独游戏

蓝桥杯校内选择赛第6题，原题如下：

你一定听说过“数独”游戏。

如下图所示，玩家需要根据9X9盘面上的已知数字，推理出所有剩余空格的数

字，并满足每一行、每一列、每一个同色九宫内的数字均含1-9,不重复。

数独的答案都是唯一的，所以，多个解也称为无解。

本图的数字据说是芬兰数学家花了3个月的时间设计出来的较难的题目。但对

会使用计算机编程的你来说，恐怕易如反掌了。

本题的要求就是输入数独题目，程序输出数独的唯一解。我们保证所有已知数

据的格式都是合法的，并且题目有唯一的解。

格式要求，输入9行，每行9个数字，。代表未知，其它数字为已知。

输出9行，每行9个数字表示数独的解。

例如：

输入（即图中题目）：

005300000

800000020

070010500

400005300

010070006

003200080

060500009

004000030

000009700

程序应该输出：

145327698

839654127

672918543

496185372

218473956

753296481

367542819

984761235

521839764

再例如，输入：

800000000

003600000

070090200

050007000

000045700

000100030

001000068

008500010

090000400

程序应该输出：

812753649

943682175

675491283

154237896

369845721

287169534

521974368

438526917

796318452

资源约定：

峰值内存消耗<256M

CPU消耗<2000ms

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

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

注意：main函数需要返回0

注意：只使用ANSIC/ANSIC++标准，不要调用依赖于编译环境或操作系统的

特殊函数。

注意：所有依赖的函数必须明确地在源文件中#include<xxx>,不能通过工程

设置而省略常用头文件。

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

利用回溯法，参考代码如下：

#incIude<stdio.h>

inta[9][9];

intplace(intx,inty)//二者分别是数组对应的行地址和列地址，取值为

0-8

(

intup,down,Ieft,right;

inti,j;

up=x/3*3;

down=up+3;

Ieft=y/3*3;

right=Ieft+3;

〃以下分三种情况判断是否在x,y对应的位置放这个数，如果不可以放,

返回0,如果可以放，返回1,会进一步迭代

for(i=0;i<9;i++){

if(a[x][y]==a[i][y]&&i!=x&&a[i][y]!=0)

return0;

)

for(i=0;i<9;i++){

if(a[x][y]==a[x][i]&&i!=y&&a[x][i]!=0)

return0;

1

for(i=up;i<down;i++)

for(j=left;j<right;j++)

if(i!=x||j!=y)

if(a[i][j]==a[x][y]&&a[i][j]!=0)

return0;

return1;

voidbacktrack(intt)

inti,j;

intx,y;

if(t-81)

printf("\n：

for(i=0;i<9;i++)

{

for(j=0;j<9;j++)

printfa[i][j]);

putchar('\n');

x=t/9;

y=t%9;//将这个转换为相应的数组行坐标和列坐标

if(a[x][y]!=0)

backtrack(t+1);

for(i=1;i<10;i++)

(

a[x][y]=i;

if(place(x,y)==1)

backtrack(t+1);

a[x][y]=0;

)

}

}

)

intmain()

(

charstr[9][9];

inti,j;

for(i=0;i<9;i++)

gets(str[i]);

for(i=0;i<9;i++)

for(j=0;j<9;j++)

a[i][j]=str[i][j]-'0';

backtrack(0);

return0;

)

9.基于链表的学生信息管理

供C语言的初学者熟悉链表以及结构体，仅供参考，不足之处，敬请谅解!

#incIude<stdio.h>

#incIude<stdIib.h>

#incIude<string.h>

structstuNode{

intnumber;

charname[20];

intage;

structstuNode*next;

);

structstuNode*newChain()

t

intn,i;

structstuNode*head,*cur,*temp;

printfCinputthenumberofstudents:z，);

scanf(〃％d〃，&n);

for(i=0;i<n;i++)

temp=(structstuNode*)maIIoc(sizeof(structstuNode));

if(temp!=NULL)

(

printfCinputthenumber:，z);

scanf(，z%d，z,&temp->number);

getchar();

printfCinputthename:，z);

gets(temp->name);

printfCinputtheage:〃)；

，，，，

scanf(%dl&temp->age);

temp->next=NULL;

if(i=0)

head二cur=temp;

eIse

{

cur->next=temp;

cur=cur->next;

}

)

}

returnhead;

)

intdisplay(structstuNode*head)

(

structstuNode*cur;

cur二head;

while(cur!=NULL)

(

printf(，z%5d\t%20s\t%d\n，z,cur->number,cur->name,cur->age);

cur=cur->next;

}

return0;

1

intsearch(structstuNode*head)

(

structstuNode*cur;

cur二head;

charname[20];

printfCinputthenameyouwanttosearch:z，);

getchar();

gets(name);

whiIe(cur!二NULL)

(

if(strcmp(cur->name,name)=0)

break;

cur=cur->next;

}

if(cur==NULL)

printf("nofound.\n〃)；

eIse

(

，z，，

printf(%5d\t%20s\t%d\nJcur->number,cur->name,cur->age);

)

return0;

1

structstuNode*deIe(structstuNode*head)

(

structstuNode*cur,*temp;

cur=head;

intnumber;

printfCinputthenumberuwanttodelete:");

scanf&number);

if(head->number==number)

(

head=head->next;

free(cur);

)

eIse{

while(cur->next!=NULL&&cur->next->number!=number)

cur=cur->next;

if(cur->next!=NULL){

temp=cur->next;

cur->next=temp->next;

free(temp);

)

I

returnhead;

}

intadd(structstuNode*head)

(

structstuNode*cur,*temp;

cur=head;

while(cur->next!=NULL)

cur=cur->next;

temp=(structstuNode*)maIIoc(sizeof(structstuNode));

if(temp!二NULL)

(

printfCinputthenumber:，z);

scanf(〃％cT,&temp->number);

getchar();

printfCinputthename:");

gets(temp->name);

printfCinputtheage:");

scanf(z，%d，z,&temp->age);

temp->next=NULL;

cur->next=temp;

)

return0;

1

intupdate(structstuNode*head)

(

structstuNode*cur;

intnumber;

cur=head;

printfCinputthenumberofthestudent:，z);

scanf("%cT,&number);

while(curJ=NULL&&cur->number!=number)

cur=cur->next;

if(cur!二NULL)

(

printfCinputthenameofthestudent:，z);

getchar();

gets(cur->name);

printfCinputtheageofthestudent:z，);

scanf("%d”,&cur->age);

)

return0;

)

intmain()

intseI;

structstuNode*head;

while(1)

printf(，z\n\t=======\n〃)；

printfC\t1newchain\n");

printf(，z\t2displaychain\n〃);

printf("\t3search\n，z);

printff\t4delete'n");

printfC\t5add\n，z);

printf(，z\t6updatechain\n");

printfC\t7quit\n，z);

printfC\tinputyourchoice:");

scanf(，z%d，z,&sel);

switch(sei)

(

case1:head=newChain();break;

case2:display(head);break;

case3:search(head);break;

case4:head=deIe(head);break;

case5:add(head);break;

case6:update(head);break;

case7:return0;

1

)

return0;

1

10.派遣敢死队

本题为蓝桥杯2014年校内选拔赛的第7题，原题如下：

G将军有一支训练有素的军队，这个军队除开G将军外，每名士兵都有一个

直接上级(可能是其他士兵，也可能是G将军)。现在G将军将接受一个特别

的任务，需要派遣一部分士兵（至少一个）组成一个敢死队，为了增加敢死队

队员的独立性，要求如果一名士兵在敢死队中，他的直接上级不能在敢死队中。

请问，G将军有多少种派出敢死队的方法。注意，G将军也可以作为一个士兵进

入敢死队。

输入格式

输入的第一行包含一个整数n,表示包括G将军在内的军队的人数。军队的士兵

从1至n编号，G将军编号为10

接下来n-1个数，分别表示编号为2,3n的士兵的直接上级编号，编号

i的士兵的直接上级的编号小于io

【输出格式】

输出一个整数，表示派出敢死队的方案数。由于数目可能很大，你只需要输出

这个数除10007的余数即可。

样例输入1

3

11

样例输出1

4

【样例说明】

这四种方式分别是：

1.选1;

2.选2；

3.选3；

4.选2,30

样例输入2

7

112233

样例输出2

40

数据规模与约定

对于20%的数据，nW20；

对于40%的数据，n/100；

对于100%的数据，1这n<100000o

资源约定：

峰值内存消耗<256M

CPU消耗<2000ms

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

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

注意：main函数需要返回0

注意：只使用ANSIC/ANSIC++标准，不要调用依赖于编译环境或操作系统的

特殊函数。

注意：所有依赖的函数必须明确地在源文件中#include<xxx>,不能通过工程

设置而省略常用头文件。

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

1、暴力搜索

#include“stdio.h"

#incIude“stdIib.h"

#include"math.h〃

intmain()

intn,*a,i,j,k,*b,flag;

intcount=0;

scanf(〃%cT,&n);

a二newint[n];

a[0]=0;//thegeneraI

for(i=1;i<n;i++)

scanfa+i);

for(i=1;i<pow(2,n);i++)

k=i;

b=newint[n];

for(j=0;j<n;j++)

(

b[j]=k%2;

k=k/2;

)

flag=1;

for(j=1;j<n;j++)

(

if(b[j]=1&&b[a[j]-1]=1)

(

flag=0;

break;

}

)

if(flag=1)

count=(count+1)%10007;

)

printf("%d\n",count);

return0;

)

2、回溯法

11.勾股定理

本题为蓝桥杯校内选拔赛第4题，原题如下：

勾股定理，西方称为毕达哥拉斯定理，它所对应的三角形现在称为：直角三

角形。

已知直角三角形的斜边是某个整数，并且要求另外两条边也必须是整数。

求满足这个条件的不同直角三角形的个数。

【数据格式】

输入一个整数n(0<n<10000000)表示直角三角形斜边的长度。

要求输出一个整数，表示满足条件的直角三角形个数。

例如，输入：

5

程序应该输出：

1

再例如，输入：

100

程序应该输出：

2

再例如，输入：

3

程序应该输出：

0

资源约定：

峰值内存消耗<256M

CPU消耗<1000ms

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

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

注意：main函数需要返回0

注意：只使用ANSIC/ANSIC++标准，不要调用依赖于编译环境或操作系统的

特殊函数。

注意：所有依赖的函数必须明确地在源文件中#include<xxx>,不能通过工程

设置而省略常用头文件。

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

#incIude<stdio.h>

#incIude<math.h>

intmain()

(

intn,i,j;

intcount=O;

scanf(〃％d〃，&n);

for(i=1;i<n;i++)

j=sqrt(n*n-i*i);

if(i*i+j*j==n*n)

count++;

)

printf("%cT,count/2);

return0;

1

12.数字排列

今有7对数字：两个1,两个2,两个3,...两个7,把它们排成一行。

要求，两个1间有1个其它数字，两个2间有2个其它数字，以此类推，两个7

之间有7个其它数字。如下就是一个符合要求的排列：

17126425374635

当然，如果把它倒过来，也是符合要求的。

请你找出另一种符合要求的排列法，并且这个排列法是以74开头的。

注意：只填写这个14位的整数，不能填写任何多余的内容，比如说明注释等。

74****4*7*******

利用回溯法求解，参考代码如下：

#incIude<stdio.h>

inta[8];

intpIace(intt);

intjudge0；

voidbacktrack(intt)

(

inti;

if(t==8)

(

if(a[7]==1&&a[4]==2&&judge()){

/*for(i=1;i<8;i++)

printfa[i]);

printf("\n");*/

intb[15]={0};

for(i=1;i<8;i++)

b[a[i]]=i;

b[a[i]+i+1]=i;

)

for(i=1;i<15;i++)

printfb[i]);

printfC\n，z);

)

)

eIse

(

for(i=1;i<14;i++)

(

a[t]=i;

if((t+i+1<=14)&&pIace(t))

backtrack(t+1);

)

)

intjudge()

(

intflag=1;

inti;

intb[15]={0};

for(i=1;i<8;i++)

(

b[a[i]]=i;

b[a[i]+i+1]=i;

)

for(i=1;i<15;i++)

(

if(b[i]==0)

(

fIag=0;

break;

)

)

returnflag;

)

intpIace(intt)

inti;

intflag=1;

for(i=1;i<t;i++)

(

if(a[t]==a[i]||a[t]==(a[i]+i+1))

(

flag=0;

break;

)

)

returnflag;

)

intmain()

backtrack(1);

return0;

)

答案为：

74151643752362

13.调和级数

本题为14年蓝桥杯校内选拔赛第2题，原题如下：

1/1+1/2+1/3+1/4+...在数学上称为调和级数。

它是发散的，也就是说，只要加上足够多的项，就可以得到任意大的数字。

但是，它发散的很慢：

前1项和达到1.0

前4项和才超过2.0

前83项的和才超过5.0

那么，请你计算一下，要加多少项，才能使得和达到或超过15.0呢？

请填写这个整数。

注意：只需要填写一个整数，不要填写任何多余的内容。比如说明文字。

本题的关键在于如何控制循环变量，如果用int类型，有可能超出其表示范围，

因此，可以采取long类型，如果该类型不够，采用float或double类型，参考

代码如下：

#incIude<stdio.h>

intmain()

(

Iongi=0;

doubIesum=0.0;

while(sum<15.0)

(

i=i+1.0;

sum+=1./i;

)

printfr%d\nz，,i);

return0;

)

14.数单词的个数

2014年蓝桥杯校内选拔赛第1题，填空题，原题如下：

输