程序設計與算法

目錄

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題，填空題，原題如下：

輸