程序設(shè)計與算法

程序設(shè)計與算法

目錄

1.結(jié)構(gòu)體綜合訓(xùn)練4

2.擲骰子游戲7

3.n級臺階問題9

4.單位分?jǐn)?shù)求解11

5.位平方和12

6.讓我怎能過大年13

7.回文素數(shù)15

8.數(shù)獨(dú)游戲16

9.基于鏈表的學(xué)生信息管理21

10.派遣敢死隊25

II.勾股定理28

12.數(shù)字排列30

13.調(diào)和級數(shù)32

14.數(shù)單詞的個數(shù)33

15.循環(huán)移動35

16.函數(shù)和字符串排列37

17.圍圈數(shù)數(shù)問題41

18.指針與字符串拍序42

19.xAx=1044

20.子集和問題45

21.結(jié)點(diǎn)選擇48

22.最短路49

23.安慰奶牛50

24.逆序?qū)?1

25.操作格子53

26.關(guān)聯(lián)矩陣55

27.Torry的困惑58

28.最小乘積59

29.時間復(fù)雜度和空間復(fù)雜度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.循環(huán)小數(shù)83

41.直角三角形的邊85

42.617485

43.匪警請撥11088

44.低碳生活大獎賽92

45.石子合并問題95

46.租用游艇問題95

47.數(shù)字三角形96

48.用數(shù)組實現(xiàn)大數(shù)加法96

50.符號三角形問題100

51.批處理作業(yè)調(diào)度問題103

52.魔方矩陣105

53.螺旋矩陣106

54.39級臺階107

55.李白打酒108

56.二分法求方程的根114

57.驗證哥德巴赫猜想115

58.用數(shù)字出圖形116

59.最優(yōu)裝載問題117

60.活動安排問題121

61.最大k乘積問題123

62.獨(dú)立任務(wù)最優(yōu)調(diào)度124

63.判斷數(shù)字是多少位數(shù),正向反向輸出127

64.C語言實現(xiàn)萬年歷程序128

65.0-1背包問題動態(tài)規(guī)劃法129

66.最長公共子序列131

67.最大子段和問題133

68.矩陣連乘問題136

69.最大公約數(shù)和最小公倍數(shù)140

70.乘積是平方數(shù)141

71.最大公約數(shù)之和143

72.數(shù)字和與倍數(shù)144

73.大數(shù)的階乘145

74.指向函數(shù)的指針146

75.數(shù)組操作146

76.字符串排序148

77.轉(zhuǎn)圈數(shù)數(shù)淘汰149

78.十六進(jìn)制轉(zhuǎn)換為十進(jìn)制150

79.遞歸逆向輸出字符串151

80.統(tǒng)計最長的單詞152

81.數(shù)的插入排序153

82.統(tǒng)計個位數(shù)字相同的數(shù)的個數(shù)155

83.哥德巴赫猜想155

84.數(shù)字游戲157

85.大小之差158

86.求滿足條件的回文數(shù)字161

87.13年藍(lán)橋杯校內(nèi)選拔賽B組試題163

88.數(shù)組循環(huán)輸出168

89.螺旋矩陣168

90.數(shù)的進(jìn)制轉(zhuǎn)換170

91.求滿足如下條件的五位數(shù)字171

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

93.花朵數(shù)問題173

94.無限循環(huán)小數(shù)173

95.角谷猜想174

96.運(yùn)動員打靶問題175

97.直角三角形的邊問題176

98.輸出互不重復(fù)的三位偶數(shù)177

99.判斷幾位數(shù)，正序和逆序輸出178

IOO.getcharVSscanf179

101.最大子段和問題181

102.整數(shù)因子分解問題184

103.標(biāo)準(zhǔn)二維表問題185

104.集合劃分問題185

105.排列的字典序問題185

106.有重復(fù)元素的排列問題186

107.半數(shù)單集問題186

108.眾數(shù)問題186

109.字典序問題187

110.金幣陣列問題190

111.最大間隙問題193

1.結(jié)構(gòu)體綜合訓(xùn)練

有10個學(xué)生，每個學(xué)生的數(shù)據(jù)包括學(xué)號、姓名、3門課的成績，編寫如下函數(shù):

①輸入10個學(xué)生的基本信息(Input)；

②求出每個學(xué)生的平均分(Average)；

③求出最高分的學(xué)生信息(High_Score)；

④輸出每個學(xué)生的信息(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.擲骰子游戲

編寫函數(shù)模擬擲骰子的游戲(兩個骰子)。第一次擲的時候，如果點(diǎn)數(shù)之和為7

或“則獲勝；如果點(diǎn)數(shù)之和為2、3或12則落?。黄渌闆r下的點(diǎn)數(shù)之和稱為

“目標(biāo)”，游戲繼續(xù)。在后續(xù)的投擲中，如果玩家再次擲出“目標(biāo)”點(diǎn)數(shù)則獲

勝，擲出7則落敗，其他情況都忽略，游戲繼續(xù)進(jìn)行。每局游戲結(jié)束時，程序

詢問用戶是否再玩一次，如果用戶輸入的回答不是y或Y,程序會顯示勝敗的次

數(shù)然后終止。

參考代碼如下：

#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級)出發(fā)，首先連續(xù)的上臺階，上到不超過第n級

的某一個位置后再連續(xù)的下臺階，直到回到地面。若每次上下臺階只允許走1

級或2級，請問可能的上下臺階的方案數(shù)是多少？

特別地，在0級站著不動也算一種方案。

【數(shù)據(jù)格式】

輸入一行包含兩個正整數(shù)n和m0

輸出一個整數(shù)，表示n級臺階有多少種合法的走樓梯方案，答案對m取余。

例如：輸入：

210007

程序應(yīng)該輸出

6

【樣例說明1】

共有6種方案(其中+表示上臺階，-表示下臺階)：

(1)原地不動

⑵+1-1

(3)+2-2

(4)+2-1-1

(5)+1+1-2

(6)+1+1-1-1

再例如，輸入：

314

程序應(yīng)該輸出：

1

【樣例說明2]

共有15種方案，對14取余后得1。

【數(shù)據(jù)規(guī)?！?/p>

對于30%的數(shù)據(jù)，n<=10000；

對于100%的數(shù)據(jù)，n<=10*17,m<=2*10^9o

資源約定：

峰值內(nèi)存消耗(含虛擬機(jī))<256M

CPU消耗<1000ms

分析：問題本質(zhì)是一個斐波拉契數(shù)列問題，加上組合的相關(guān)知識，可以按如下思

路得到相應(yīng)的答案。

11235813

當(dāng)n=2時，即要從第0個臺階走到第2個臺階，共有如下的走法：

1+1*1+2*2=6

其中第一個1對應(yīng)原地不動的情況，第二個1*1代表上一個臺階的方法數(shù)，乘下

一個臺階的方法數(shù)。2*2代表上兩個臺階的方法數(shù)乘下兩個臺階的方法數(shù)

類似，如果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.單位分?jǐn)?shù)求解

形如：1/a的分?jǐn)?shù)稱為單位分?jǐn)?shù)。

可以把1分解為若干個互不相同的單位分?jǐn)?shù)之和。

例如：

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項時的所有不同分解法。

【數(shù)據(jù)格式要求】

輸入一個整數(shù)n,表示要分解為n項(n<12)

輸出分解后的單位分?jǐn)?shù)項，中間用一個空格分開。

每種分解法占用一行，行間的順序按照分母從小到大排序。

例如，

輸入：

4

程序應(yīng)該輸出：

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

程序應(yīng)該輸出：

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

資源約定：

峰值內(nèi)存消耗（含虛擬機(jī)）<256M

CPU消耗<2000ms

請嚴(yán)格按要求輸出，不要畫蛇添足地打印類似：“請您輸入...”的多余內(nèi)容。

所有代碼放在同一個源文件中，調(diào)試通過后，拷貝提交該源碼。

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

注意：主類的名字必須是：Main,否則按無效代碼處理。

5.位平方和

把一個整數(shù)的每個數(shù)位都平方后求和，又得到一個整數(shù)，我們稱這個整數(shù)為：

位平方和。

對新得到的整數(shù)仍然可以繼續(xù)這一運(yùn)算過程。比如，給定整數(shù)為4,則一系列的

運(yùn)算結(jié)果為：

16,37,58,89

本題的要求是，已知一個整數(shù)x,求第n步的運(yùn)算結(jié)果。

【數(shù)據(jù)格式要求】

輸入，兩個整數(shù)xn,中間以空格分開。表示求x的第n步位平方和。其中，

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

輸出，一個整數(shù)，表示所求結(jié)果。

例如，

輸入：

43

則程序應(yīng)該輸出：

58

再例如，

輸入：

131410

則程序應(yīng)該輸出：

20

資源約定：

峰值內(nèi)存消耗(含虛擬機(jī))<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.讓我怎能過大年

有如下的加法算式。其中每個漢字代表一個數(shù)字。

(如存在對齊問題，可參見【圖l.png】)

年

大年

過大年

能過大年

怎能過大年

我怎能過大年

+讓我怎能過大年

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

請?zhí)顚憽白屛以跄苓^大年”所代表的整數(shù)。

所有數(shù)字連在一起，中間不要空格。例如：”3125697“。當(dāng)然，這個不是正確的

答案。

注意：只填寫一個整數(shù)，不要填寫任何多余的內(nèi)容。

#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.回文素數(shù)

10301是個5位的素數(shù)。它有個特點(diǎn)，把數(shù)字倒過來還是它本身，具有這樣特征

的素數(shù)，我們稱之為：回文素數(shù)。

10501

10601

11311

這些都是5位的回文素數(shù)。

請你計算一下，像這樣的5位數(shù)的回文素數(shù)，一共有多少個？

請?zhí)顚戇@個表示個數(shù)的整數(shù)，注意不要寫任何其它多余的內(nèi)容，比如說明或解

釋文字，也不要列出所有的回文素數(shù)。

#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.數(shù)獨(dú)游戲

藍(lán)橋杯校內(nèi)選擇賽第6題，原題如下：

你一定聽說過“數(shù)獨(dú)”游戲。

如下圖所示，玩家需要根據(jù)9X9盤面上的已知數(shù)字，推理出所有剩余空格的數(shù)

字，并滿足每一行、每一列、每一個同色九宮內(nèi)的數(shù)字均含1-9,不重復(fù)。

數(shù)獨(dú)的答案都是唯一的，所以，多個解也稱為無解。

本圖的數(shù)字據(jù)說是芬蘭數(shù)學(xué)家花了3個月的時間設(shè)計出來的較難的題目。但對

會使用計算機(jī)編程的你來說，恐怕易如反掌了。

本題的要求就是輸入數(shù)獨(dú)題目，程序輸出數(shù)獨(dú)的唯一解。我們保證所有已知數(shù)

據(jù)的格式都是合法的，并且題目有唯一的解。

格式要求，輸入9行，每行9個數(shù)字，。代表未知，其它數(shù)字為已知。

輸出9行，每行9個數(shù)字表示數(shù)獨(dú)的解。

例如：

輸入（即圖中題目）：

005300000

800000020

070010500

400005300

010070006

003200080

060500009

004000030

000009700

程序應(yīng)該輸出：

145327698

839654127

672918543

496185372

218473956

753296481

367542819

984761235

521839764

再例如，輸入：

800000000

003600000

070090200

050007000

000045700

000100030

001000068

008500010

090000400

程序應(yīng)該輸出：

812753649

943682175

675491283

154237896

369845721

287169534

521974368

438526917

796318452

資源約定：

峰值內(nèi)存消耗<256M

CPU消耗<2000ms

請嚴(yán)格按要求輸出，不要畫蛇添足地打印類似：“請您輸入的多余內(nèi)容。

所有代碼放在同一個源文件中，調(diào)試通過后，拷貝提交該源碼。

注意：main函數(shù)需要返回0

注意：只使用ANSIC/ANSIC++標(biāo)準(zhǔn)，不要調(diào)用依賴于編譯環(huán)境或操作系統(tǒng)的

特殊函數(shù)。

注意：所有依賴的函數(shù)必須明確地在源文件中#include<xxx>,不能通過工程

設(shè)置而省略常用頭文件。

提交時，注意選擇所期望的編譯器類型。

利用回溯法，參考代碼如下：

#incIude<stdio.h>

inta[9][9];

intplace(intx,inty)//二者分別是數(shù)組對應(yīng)的行地址和列地址，取值為

0-8

(

intup,down,Ieft,right;

inti,j;

up=x/3*3;

down=up+3;

Ieft=y/3*3;

right=Ieft+3;

〃以下分三種情況判斷是否在x,y對應(yīng)的位置放這個數(shù)，如果不可以放,

返回0,如果可以放，返回1,會進(jìn)一步迭代

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;//將這個轉(zhuǎn)換為相應(yīng)的數(shù)組行坐標(biāo)和列坐標(biāo)

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.基于鏈表的學(xué)生信息管理

供C語言的初學(xué)者熟悉鏈表以及結(jié)構(gòu)體，僅供參考，不足之處，敬請諒解!

#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.派遣敢死隊

本題為藍(lán)橋杯2014年校內(nèi)選拔賽的第7題，原題如下：

G將軍有一支訓(xùn)練有素的軍隊，這個軍隊除開G將軍外，每名士兵都有一個

直接上級(可能是其他士兵，也可能是G將軍)?，F(xiàn)在G將軍將接受一個特別

的任務(wù)，需要派遣一部分士兵（至少一個）組成一個敢死隊，為了增加敢死隊

隊員的獨(dú)立性，要求如果一名士兵在敢死隊中，他的直接上級不能在敢死隊中。

請問，G將軍有多少種派出敢死隊的方法。注意，G將軍也可以作為一個士兵進(jìn)

入敢死隊。

輸入格式

輸入的第一行包含一個整數(shù)n,表示包括G將軍在內(nèi)的軍隊的人數(shù)。軍隊的士兵

從1至n編號，G將軍編號為10

接下來n-1個數(shù)，分別表示編號為2,3n的士兵的直接上級編號，編號

i的士兵的直接上級的編號小于io

【輸出格式】

輸出一個整數(shù)，表示派出敢死隊的方案數(shù)。由于數(shù)目可能很大，你只需要輸出

這個數(shù)除10007的余數(shù)即可。

樣例輸入1

3

11

樣例輸出1

4

【樣例說明】

這四種方式分別是：

1.選1;

2.選2；

3.選3；

4.選2,30

樣例輸入2

7

112233

樣例輸出2

40

數(shù)據(jù)規(guī)模與約定

對于20%的數(shù)據(jù)，nW20；

對于40%的數(shù)據(jù)，n/100；

對于100%的數(shù)據(jù)，1這n<100000o

資源約定：

峰值內(nèi)存消耗<256M

CPU消耗<2000ms

請嚴(yán)格按要求輸出，不要畫蛇添足地打印類似：“請您輸入的多余內(nèi)容。

所有代碼放在同一個源文件中，調(diào)試通過后，拷貝提交該源碼。

注意：main函數(shù)需要返回0

注意：只使用ANSIC/ANSIC++標(biāo)準(zhǔn)，不要調(diào)用依賴于編譯環(huán)境或操作系統(tǒng)的

特殊函數(shù)。

注意：所有依賴的函數(shù)必須明確地在源文件中#include<xxx>,不能通過工程

設(shè)置而省略常用頭文件。

提交時，注意選擇所期望的編譯器類型。

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.勾股定理

本題為藍(lán)橋杯校內(nèi)選拔賽第4題，原題如下：

勾股定理，西方稱為畢達(dá)哥拉斯定理，它所對應(yīng)的三角形現(xiàn)在稱為：直角三

角形。

已知直角三角形的斜邊是某個整數(shù)，并且要求另外兩條邊也必須是整數(shù)。

求滿足這個條件的不同直角三角形的個數(shù)。

【數(shù)據(jù)格式】

輸入一個整數(shù)n(0<n<10000000)表示直角三角形斜邊的長度。

要求輸出一個整數(shù)，表示滿足條件的直角三角形個數(shù)。

例如，輸入：

5

程序應(yīng)該輸出：

1

再例如，輸入：

100

程序應(yīng)該輸出：

2

再例如，輸入：

3

程序應(yīng)該輸出：

0

資源約定：

峰值內(nèi)存消耗<256M

CPU消耗<1000ms

請嚴(yán)格按要求輸出，不要畫蛇添足地打印類似：“請您輸入的多余內(nèi)容。

所有代碼放在同一個源文件中，調(diào)試通過后，拷貝提交該源碼。

注意：main函數(shù)需要返回0

注意：只使用ANSIC/ANSIC++標(biāo)準(zhǔn)，不要調(diào)用依賴于編譯環(huán)境或操作系統(tǒng)的

特殊函數(shù)。

注意：所有依賴的函數(shù)必須明確地在源文件中#include<xxx>,不能通過工程

設(shè)置而省略常用頭文件。

提交時，注意選擇所期望的編譯器類型。

#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.數(shù)字排列

今有7對數(shù)字：兩個1,兩個2,兩個3,...兩個7,把它們排成一行。

要求，兩個1間有1個其它數(shù)字，兩個2間有2個其它數(shù)字，以此類推，兩個7

之間有7個其它數(shù)字。如下就是一個符合要求的排列：

17126425374635

當(dāng)然，如果把它倒過來，也是符合要求的。

請你找出另一種符合要求的排列法，并且這個排列法是以74開頭的。

注意：只填寫這個14位的整數(shù)，不能填寫任何多余的內(nèi)容，比如說明注釋等。

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.調(diào)和級數(shù)

本題為14年藍(lán)橋杯校內(nèi)選拔賽第2題，原題如下：

1/1+1/2+1/3+1/4+...在數(shù)學(xué)上稱為調(diào)和級數(shù)。

它是發(fā)散的，也就是說，只要加上足夠多的項，就可以得到任意大的數(shù)字。

但是，它發(fā)散的很慢：

前1項和達(dá)到1.0

前4項和才超過2.0

前83項的和才超過5.0

那么，請你計算一下，要加多少項，才能使得和達(dá)到或超過15.0呢？

請?zhí)顚戇@個整數(shù)。

注意：只需要填寫一個整數(shù)，不要填寫任何多余的內(nèi)容。比如說明文字。

本題的關(guān)鍵在于如何控制循環(huán)變量，如果用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.數(shù)單詞的個數(shù)

2014年藍(lán)橋杯校內(nèi)選拔賽第1題，填空題，原題如下：

輸