理工软件工程考研-c语言程序设计c2012-d11continue

编码风格第2

页注意花括号的位置缩进应该是四个空格for、while

等语句和括号间要有空格,;等后要有空格或换行运算符的前后应有空格函数名后的括号无空格if、for、while

后必须使用花括号要在适当的位置添加空行函数要加return编码风格第3

页#include

<stdio.h>int

main(){ int

i,

n

=

0;for

(

i

=0;

i

<

10;

++i)

{if

(

n%

2

==

0

)

{n

=n

+i;}

else

{n

=n

-

i;}}printf("%d\n",

n);return

0;}}#include

<stdio.h>int

main(){ int

i,

n

=

0;for

(

i

=

0;

i

<

10;

++i

){

if

(

n

%

2

==0

){

n

=n

+i;}else{

n

=n

-

i;}printf("%d\n",

n);return

0;}纠错纠错的六个阶段：这不可能。我机器上就没事。不应该呀。为什么会出现这种问题？噢，我明白了。以前怎么就没问题？第4

页查找错误物理学家、工程师和程序员三人驾驶着一辆汽车行驶在山上。下山时，忽然刹车失灵，汽车无法控制地向下冲向一个悬崖，但是很幸运的是在这个悬崖的前面有一些小树让他们的汽车停了下来。三人惊魂未定地从车里爬了出来。应该建立一个模型况下失灵的情物理学家说，“我觉得来模拟在下山过程中刹车片在高形”。工程师说，“我车的后备厢有个扳手，要不我们把车拆开看看到底是什么原因”。程序员说，“为什么

不找个相同的车，再来一次以重现这个问题呢？”第5

页程序设计的一般步骤第6

页明确问题的性质，分析题意数值问题/非数值问题建立问题的描述模型数学模型/过程模型设计/确定算法数学问题：数值分析非数学问题：数据结构/算法分析与设计一般方法：穷举/递推/递归/分治/回溯/……编程调试分析运行结果数值问题：要发就发第7

页问题“1898─要发就发”。今年是2012年，现将不超过2012的所有素数从小到大排成第一行，第二行上的每个数都等于它“右肩”上的素数与“左肩”上的素数之差。请编程求出：第二行数中是否存在这样的若干个连续的整数，它们的和恰好是1898？假如存在的话，又有几种这样的情况？第一行：2

3

5

7

11

13...1979

1987

1993第二行：1

2

2

4

2.....8

6百例34:要发就发第8

页问题分析假设第1行的素数为n[i]（i=0,1,2,3,…），第2行的差值为m[j]：m[j]

=

n[j+1]

-

n[j]则第2行从k

开始连续j

个数的和为：SUM

=

m[k]

+

m[k+1]

+

m[k+2]

+

...

+

m[k+j-1]=(n[k+1]-n[k])+(n[k+2]-n[k+1])+(n[k+3]-n[k+2])+

…

+(n[k+j]-n[k+j-1])=

n[k+j]

-n[k]原题变为：在不超过2011的素数中，是否存在这样两个素数，它们的差恰好是1898。若存在，则第二行中必有所需整数序列，其和恰为1898。百例34:要发就发第9

页算法设计将小于2011的所有素数保存在一维数组number中；采用穷举法寻找：n[k+j]-n[k]=1898假设下标j和i（0<i<j<=素数的个数n）：①对于任一number[j]，令i=0；②判断number[j]-number[i]>1898？如果成立，则：i=i+1，重复②；如果不成立，则进入③；③如果number[j]-number[i]＝＝1898？如果成立，则输入结果；否则，j=j-1，进入④；④如果number[j]＜1898？如果成立，则算法结束；否则，进入①重复算法。百例34:要发就发第10

页算法设计1.将小于2011的所有素数保存在一维数组number中；假设一个判断素数的函数：int

fflag(int

i)：当整数i为素数的时候，函数的返回值为1，如果整数i不是素数，函数的返回值为0。for

(

j=0,

i=3;

i<=2011;

i+=2

)if

(

fflag(i)==1

)number[j++]

=

i;退出循环时，找的到素数的数量为：j

个。最后一个有效元素保存在下标j-1的位置上。百例34:要发就发第11

页2.采用穷举法寻找：n[k+j]-n[k]=1898假设下标j

和i（0<i<j<=素数的个数n）：①对于任一number[j]，令i=0；②判断number[j]-number[i]>1898？如果成立，则：i=i+1，重复②；如果不成立，则进入③；③如果number[j]-number[i]＝＝

1898？如果成立，则输入结果；否则，j=j-1，进入④；④如果number[j]＜1898？如果成立，则算法结束；否则，进入①重复算法。for

(

j--;

number[j]>1898;

j--

){}for(i=0;

number[j]-number[i]>1898;

i++)

；if

(

number[j]-number[i]==1898

)printf("....",

......);百例34:要发就发程序与程序注释#include<stdio.h>#include<math.h>#define NUM

320int

number[NUM];

/*存放小于2011的全部奇素数*/main(

)row:\n");/*求出全部素数*/{

int

i,

j,

count=0;printf

("There

are

sequences

infor

(

j=0,

i=3;

i<=2011;

i+=2)if

(

fflag(i)

)

number[j++]=i;for

(

j--;

number[j]>1898;

j--)

{/*开始搜索*/for

(

i=0;

number[j]-number[i]>1898;

i++)

；if

(number[j]-number[i]==1898)/*差满足条件输出*/printf("(%d).%3d,...,%d\n",++count,number[i],number[j]);}}第12

页百例34:要发就发第13

页程序与程序注释int

fflag(

int

i

){ int

j;

if

(i==2)return(1);if

(

i<=1

||

i%2==0

)return(0); /*

if

no,

return

0

*/for

(

j=3;

j<=(int)sqrt((double)i);

j+=2

)if

(

!(i%j)

)return(0);return(1); /*

if

yes,

return

1

*/}百例34:要发就发程序2与程序注释#include

<stdio.h>#include

<math.h>main(

){

int

i,j,

count=0;printf("There

are

sequences

inrow:\n");for

(

i=3;

i <=2011;

i+=2

)if

(

fflag(i)

&&

fflag(i )

)printf("The

result

%d..%d

is

1898.\n",i,

i);}第14

页小结：编程的步骤明确问题的性质，分析题意数值问题建立问题的描述模型进行数学分析，推导出数学公式设计/确定算法基本思想：穷举法采用逐步求精的步骤逐步，推导出整个算法确定数据结构：数组采用伪语言描述算法逐步细化产生程序编程调试分析运行结果第15

页算法设计:北理工的恶龙最近，北理工出现了一只恶龙，它长着很多头，而且还会吐火，它将会把北理工烧成废墟，于是，校长召集全校所有勇士杀死这只恶龙。要杀死这只龙，必须把它所有的头都砍掉，每个勇士只能砍一个龙头，龙的每个头大小都不一样，一个勇士只有在身高不小于龙头的直径的情况下才能砍下它。而且勇士们要求，砍

下一个龙头必须得到和自己身高厘米数一样的学分。校长想花最少的学分数杀死恶龙，于是找到你寻求帮助。第16

页算法设计:北理工的恶龙第17

页输入第一行龙头数n,勇士人数m（1<=n,

m<=100）接下来n

行，每行包含一个整数，表示龙头的直径接下来m

行，每行包含一个整数，表示勇士的身高输出如果勇士们能完成任务，输出校长需要花的最小费用；否则输出“bit

isdoomed!”输入样例12

354784输出样例111输入样例22

15510输出样例2bit

isdoomed!算法设计:北理工的恶龙基本思路首先找出人工方式应该如何进行处理，设计算法模拟人工的过程。算法设计读入龙头数

n

和勇士m读入n

个龙头数据存入数组dragon

中读入m

个勇士数据存入数组

cavalier

中对数组dragon

中的n

个数据从小到大进行排序对数组cavalier

中的m

个数据从小到大进行排序进行处理7.输出结果void

input(

int

a[

],

int

n

)void

sort(

int

a[

],

int

n

)第18

页算法设计:北理工的恶龙第19

页算法设计读入龙头数

n

和勇士m读入n

个龙头数据存入数组dragon

中读入m

个勇士数据存入数组

cavalier

中对数组dragon

中的n

个数据从小到大进行排序对数组cavalier

中的m

个数据从小到大进行排序#define

M100int

cavalier[M],

dragon[M],

n,

m;scanf("%d%d",

&n,

&m);input(

dragon,

n

);input(

cavalier,

m

);sort(

dragon,

n

);sort(

cavalier,

m

);算法设计:北理工的恶龙第20

页“处理”部分的算法设计龙头下标j=0，勇士下标

i=0当i<m

且j<n

时，进入3

进行尝试，否则结束。判断第i

个勇士的身高

>=第j

个龙头直径吗？

若成立，则表示第

i

个勇士可以砍下第

j

个龙头，记录身高，找下一个勇士和下一个龙头（i++,j++）转2。若不成立，试探下一个勇士（i++），转2。for

(

i=j=0;

i<m

&&j<n;

){}j++;if

(

cavalier[i]

>=

dragon[j]

){

result

+=

cavalier[i];

i++;}else

i++;算法设计:北理工的恶龙/*记录学分*/程序主体void

main

(){

int

n,

m,

i,

j;

long

result=0;scanf("%d%d",

&n,

&m);input(

dragon,

n);

input(

cavalier,

m);sort(

dragon,

n

);

sort(

cavalier,

m

);for

(i=j=0;i<m

&&

j<n;)

/*进行试探*/{

if

(

cavalier[i]

>=

dragon[j]

)i++;

j++;{

result

+=

cavalier[i];}else

i++;}if

(

j==n

)elseprintf("%ld\n",

result

);printf("bit

is

doomed!\n");第21

页}贪心法算法设计:腾腾与朋友用一副不含大小王的

牌进行

。：每人发

k张牌，各自看完各自的牌后，把牌面朝下放成一行，腾腾的牌从左到右

为

1…

k，朋友的牌对面放好，即腾腾的第

i

张牌和朋友的第

i

张牌相对，最后把

翻过来，得分规则如下：如果腾腾的第i张牌比朋友的大，腾腾得一分。如果朋友的第i张牌比腾腾的大，朋友得一分。牌的大小先由牌的数值决定：2<3<..<9<T<J<Q<K<A；如果数值相等的话，由花色决定：C(梅花)<D(方片)<S(黑桃)<H(红桃)这本应是由运气决定胜负的，但是腾腾在牌的背面做了标记，也就是，在牌还没有翻过来时腾腾就已经知道朋友的牌是什么了。你的任务是，给出两个人的牌，计算出腾腾最多可以得多少分。第22

页算法设计:输入第一行是一个整数

m，表示每个的牌数，m<=26;第二行和第三行分别为朋友和腾腾的牌：每张牌由两个字符组成，第一个表示大小，第二个表示花色。每张牌之间由空格隔开。输出输出腾腾最多可以得多少分。输入样例132H

3H

4H2D

3D

4D期望的输出12输入样例238C

8S

9S3C

2D

7H期望的输出20输入样例346S

JD

AC

8DKH

2D

6D

3C期望的输出31第23

页算法设计:基本思路首先找出人工方式腾腾应该如何进行应对。设计算法模拟人工的过程。基本算法贪心法。算法关键如何在计算机中表示52张不同的牌？不同的表示方法在处理中的难度不同！编码牌面数值2～9,T,J,Q,K,A

对应：20,30,40,...,140花色C、D、S、H对应：1,2,3,4◆

任意一张牌

牌面数值+花色值第24

页算法设计:程序思路char

str[10];int

poker[2][26];存输入的一张原始牌2维数组，保存转换后数据下标为0的行存朋友的牌，为1的行存腾腾的牌基本函数void

sort(int

a[],int

m)

从小到大排序对一张牌进行编码int

n_poker

(char

*

str

)算法设计读入m读入2*m

个牌面数据，进行转换后存入数组对第0行进行排序对第1行进行排序5.进行处理sort(

poker[

0

], m

)sort(

poker[

1

],m

)第25

页6.输出结果算法设计:main函数void

main(

void

){ char

str[10];int

poker[2][26];int

n,

m,

i,

j,

count;scanf("%d",

&m);for(i=0;

i<2;

i++)

/*输入两人手中的牌*/for(j=0;j<m;

j++){ scanf(“%s”,

str

); /*

读入一张牌

*/poker[i][j]

=

n_poker(

str

);

/*

转换

*/}第26

页算法设计:main函数sort

(

poker[0],

m

);sort

(

poker[1],

m

);for

(

count=i=j=0;

i<m

&&

j<m;

){ if

(

poker[0][i]

<

poker[1][j]

){ count

++;i

++; j

++;}else

j++;}printf(

"%d\n",

count

);}例poker第27

页算法设计:main函数int

n_poker

(

char

*

str

){ intnum;if

(

*str

>=

'2'

&&

*str

<=

'9'

)num

=

(*str

-

'0'

)*

10;else

if

(

*str

=='T'

)num

=100;else

if

(

*str

=='J'

)num

=110;else

if

(

*str

=='Q'

)num

=

120;else

if

(

*str

==

'K'

)num

=

130;else

num

=

140;正确的方法：将数字字符转换为数值'0'不好的办法：48第28

页算法设计:main函数int

n_poker

(char

*

str

){……switch

(

*(str+1)

){ case

'C':case

'D':case

'S':default:num

+=

1;break;num

+=

2;break;num

+=

3;break;num+=4;}return

num;}例poker第29

页例7-7：

有10张3分邮票和10张5分邮票，用这些邮票中的一张或若干

得到多少种不同的邮资？问题分析与算法设计计算不同张数和面值的邮票组成的邮资公式：s=

3*i

+

5*j其中i

为3分邮票的张数，j

为5分邮票的张数按题目要求，3分的邮票可以取i

(0~10)张，5分的邮票可以取

j

(0~10)张。采用穷举法进行组合，求出这些不同面值、不同张数的邮票组合后的邮资。关键：要记录已经组合好的面值。如：3张5分的邮票和5张3分的邮票是同一面值，只能算一种组合。数组应用实例-邮票组合/百例72共78页第30

页inta[100];void

main(

){ int

i,

j,

k,

sum,

count=0;for

(

i=0;

i<=10;

i++

)

for

(

j=0;

j<=10;

j++

){ sum

=

i*3

+

j*5;for(

k=0;

k<count;

k++)if

(

sum

==

a[k]

)break;if

(

k==count

&&sum!=0

){ a[k]

=

sum;count++;}}printf("%d

kinds:",

count);for

(

k=0;

k<count;

k++)printf("%4d

",

a[k]);}数组应用举例-邮票组合例C7_7共78页第31

页百例47:计算分数的精确值第32

页问题使用数组精确计算M/N(0<M<N<=100)的值。如果M/N是无限循环小数，则计算并输出它的第一循环节，同时要求输出循环节的起止位置（小数位的序号）。百例47:计算分数的精确值问题分析与算法设计将商存放在数组中，数组的每个元素存放1位十进制数，即商的第1位存放在第1个元素的第2位存放在第2个元素中……，这样使用数组来表示一个高精度的计算结果。进行除法运算时模拟人工操作：每次求出商的一位后将余数乘以10，再计算商的下1位。当某次计算后的余数为0时，表示M/N为有限不循环小数；当某次计算后的余数与前面的某个余数相同时，则M/N为无限循环小数，从该余数第1次出现后所求得的各位就是小数的循环节。第33

页第34

页百例47:计算分数的精确值程序与程序注释int

re[101],qu[101];

/*re:余数qu:商的每一位*/main

(

){ int

m,

n,

i,

j;scanf("%d/%d",&m,&n);

/*输入被除数和除数*/printf("%d/%d

it's

accuracy

value

is:

0.",

m,

n);for

(i=1;i<=100;i++){

/*

i:商的位数*/re[m]=i;

/*

m:余数，re[m]:该余数对应的商的位数*/m

*=10;

/*余数扩大10倍*/qu[i]=m/n;

/*商*/m=m%n;

/*求余数*/if(m==0){ /*余数为0则表示是有限小数*/for(j=1;j<=i;j++)printf("%d",qu[j]);

/*输出商*/break;

/*退出循环*//*若余数面已经出现过*/}if

(re[m]!=0

){for

(

j=1;

j<=i;

j++)printf("%d",

qu[j]);/*输出循环小数*/printf

("\n\tand

it

is

from

%d\n",

re[m]);printf

("\tdigit

to

%d

digit

after.\n",

i);break;/*循环节*//*退出*/}}}非数值问题:魔术师的猜牌术问题魔术师利用一副牌中的13张黑桃，预先将它们排好后迭在一起，牌面朝下。对观众说：我不看牌，只数数就可以猜到每张牌是什么，我大声数数， 听，不信？

就看。魔术师将最上面的那张牌数为1，把它翻过来正好是黑桃A，将黑桃A放在桌子上，然后按顺序从上到下数手中的余牌，第二次数1、2，将第一张牌放在这迭牌的下面，将第二张牌翻过来，正好是黑桃2，也将它放在桌子上。第三次数1、2、3，将前面两张依次放在这迭牌的下面，再翻第三张牌正好是黑桃3。这样依次进行将13张牌全翻出来，准确无误。问魔术师手中的牌原始次序是怎样按排的？第35

页百例69:魔术师的猜牌术问题分析与算法设计人工倒推：在桌子上放13个空盒子排成一圈，从1开始顺序，将黑桃A放入1号盒子中，从下一个空盒子开始对空的盒子计数，当数到第二个空盒子时，将黑桃2

放入空盒子中，然后再从下一个空盒子开始对空盒子计数，顺序放入3、4、5…，直到放入全部13张牌。注意在计数时要跳过非空的盒子，只对空盒子计数。最后牌在盒子中的顺序，就是魔术师手中原来牌的顺序。第36

页百例69:魔术师的猜牌术A23456178910111213第37

页百例69:魔术师的猜牌术第38

页程序说明与注释int

a[14];main(

){int

i,n,j=1;

/*

j:数组(盒子)下标，初始时为1号元素

*/printf("The

original

order

of

cards

is:

");/*

i:要放入盒子中的牌的序号

*//*

n:空盒计数器*/for

(

i=1;

i<=13;

i++){n=1;do

{if

(j>13)

j=1;if(

a[j])

j++;/*

j超过最后一个元素则指向1号元素*//*跳过非空的盒子，不计数

*/else{if(n==i

)a[j]=i;/*若数到第i个空，则放入*/j++;n++;

/*对空盒计数，下标指向下1个盒子

*/}}while

(n<=i);

/*控制空盒计数为i

*//*输出牌的排列顺序*/}for

(i=1;

i<=13;

i++)printf("%d

",a[i]);}3-1.

输入一行字符，将其中的每个字符从小到大排列后输出。#include

<stdio.h>main

()/*冒泡法排序*/{ char

string

[100],

t;int

i,

j,

n;gets(

string

);n

=

strlen

(

string

);for

(

i=0;

i<n;

i++

)for

(

j=0;

j

<

n-1-i;

j++

)if

(

string[j]

>

string[j+1]

){t

=string[j];

string[j]

=

string[j+1];string[j+1]

=

t;}编程实例-字符排序puts(string

);}第39

页3-3.输入五个单词，请将它们按从小到大的顺序排列后输出。#include

<stdio.h>main

(){ char

str

[5][20],

t[20];int

i,

j,

n;printf

("Enter

string:\n");for

(i=0;i<5;i++)

/*循环输入5个字符串*/gets(str[i]);for

(

i=0;

i<5;

i++

)for

(j=0;

j

<

5-1-i;

j++

)if

(

strcmp(

str[j],

str[j+1])

>

0

){

strcpy

(

t, str[j]

);strcpy

(

str[j],

str[j+1]);strcpy

(

str[j+1],

t);}printf("Result:\n");编程实例-单词排序for

(i=0;

i<5;

i++

)puts

(str[i]

);}第40

页3-14.输入字符串，删除串中重复字符。如：输入字符串：abacaeedabcdcd

；则输出：abcedmain(){char

str1[80],

str2[80]; int

i,

j,

n;printf

("Enter

string:");gets

(

str1

);n

=0;for

(

i=0;

str1[i]!='\0';

i++)

{for

(j=0;j<n

&&

str1[i]!=str2[j];j++);if

(j

==

n) /*不重复，则拷贝*/str2

[

n++

]

=

str1

[

i

];}str2[n]='\0';printf("Result:");puts

(

str2

);}编程实例-串处理第41

页3-16.

输入一行字符串，将其反序后再输出。main

(){

char

str[80],

c;int

i,

j,

n;printf

("Enter

string:");gets

(

str

);n=strlen(str);for(

i=0,j=n-1;

i<j;i++,j--

){

c =

str[i];str[i]

=

str[j];str[j]

=

c;}printf("Result:");puts

(

str

);}编程实例-串反序第42

页3-21.输入两个已经按从小到大顺序排列好的字符串，编写一个合并两个字符串的函数，使合并后的字符串，仍然是从小到大排列。main

(){

charstr1[80],

str2[80],

str[80];int

i,j,

n;printf

("Enter

string1:");printf

("Enter

string2:");gets

(

str1

);gets

(str2);n

=0;for

(

i=0,j=0;

str1[i]!='\0'

&&

str2[j]!='\0';

)if

(

str1[i]

<

str2[j]

) str[n++]

=

str1[i++];elsewhile

(

str1[i]!='\0'

)while

(

str2[j]!='\0'

)str[n++]

=

str2[j++];str[n++]

=

str1[i++];str[n++]

=str2[j++];str[n]='\0';printf("Result:");p