北京大学计算概论课件ch14-c语言编程应用

第十四讲：

C语言编程应用北京大学

信息科学技术学院2013年12月二维数组

回形遍历#include“stdio.h”#defineROW100#defineCOL100intmain(){ introw,col,matrix[ROW][COL]; inti,j; scanf(“%d%d”,&row,&col); for(i=0;i<row;i++){ for(j=0;j<col;j++){ scanf(“%d”,&(matrix[i][j])); } } return0;}在这里继续插入代码01020304052223242506353637260734413827083340392809323130291000212019181716151413121101234501234560102030405222324250635363726073441382708334039280932313029100021201918171615141312110123450123456a…cdze……xowv…p列的下限xx_col列的上限sx_col行的下限xx_row行的上限sx_rowa…cdze……xowv…p列的下限xx_col列的上限sx_col行的下限xx_row行的上限sx_row

请一位同学

在黑板上写下程序：按照图中的顺序输出圈上的元素（从左上角开始）for(j=xx_col;j<sx_col;j++){ printf(“%d\n”,matrix[xx_row][j]);}for(i=xx_row;i<sx_row;i++){ printf(“%d\n”,matrix[i][sx_col]);}for(j=sx_col;j>xx_col;j--){ printf(“%d\n”,matrix[sx_row][j]);}for(i=sx_row;i>xx_row;i--){ printf(“%d\n”,matrix[i][xx_col]);}列的下限xx_col列的上限sx_col行的下限xx_row行的上限sx_row红圈蓝圈绿圈060515142423row=7col=6列的下限xx_col列的上限sx_col行的下限xx_row行的上限sx_row红圈蓝圈绿圈0row-10col-11row-21col-22row-32col-3row=7col=6#include“stdio.h”#defineROW100#defineCOL100intmain(){ introw,col,matrix[ROW][COL]; intxx_row,sx_row,xx_col,sx_col; inti,j; scanf(“%d%d”,&row,&col); for(i=0;i<row;i++){ for(j=0;j<col;j++){ scanf(“%d”,&(matrix[i][j])); } } return0;}在这里继续插入代码#include“stdio.h”#defineROW100#defineCOL100intmain(){ introw,col,matrix[ROW][COL]; intxx_row,sx_row,xx_col,sx_col; inti,j; scanf(“%d%d”,&row,&col); for(i=0;i<row;i++){ for(j=0;j<col;j++){ scanf(“%d”,&(matrix[i][j])); } } return0;}在这里继续插入代码

xx_row =________;

sx_row =________;

xx_col =________;

sx_col =________;while((xx_row____

sx_row)&&(xx_row____

sx_row)){

xx_row________;

sx_row________;

xx_col

________;

sx_col

________;}#include“stdio.h”#defineROW100#defineCOL100intmain(){ introw,col,matrix[ROW][COL]; intxx_row,sx_row,xx_col,sx_col; inti,j; scanf(“%d%d”,&row,&col); for(i=0;i<row;i++){ for(j=0;j<col;j++){ scanf(“%d”,&(matrix[i][j])); } } return0;}在这里继续插入代码

xx_row =________;

sx_row =________;

xx_col =________;

sx_col =________;while((xx_row____

sx_row)&&(xx_row____

sx_row)){

xx_row________;

sx_row________;

xx_col

________;

sx_col

________;}0row-10col-1<<++++----测试数据之一76000102030405212223242506203536372607193441382708183340392809173231302910161514131211✔测试数据之二4400010203111213041015140509080706✔测试数据之三38000102030405060717181920212223081615141312111009✗181920212223测试数据之四830001021718031619

041520

051421

061322

071223

08111009✗怎样才能输出缺失的这一行或列呢？请课后思考问题2：

跳绳游戏关键信息：计算1分钟内跳了多少下绳；1秒钟跳1次；跳坏后，3秒钟后才能又开始跳；输入、输出

示例=60–3*3=60–1*3=60–4*3=60–4*3=47=60–0*3输入：0

输出：600秒60秒y秒在y秒时，小朋友停止了跳绳60下输入：3122345

输出：510秒60秒12下12秒15秒12下26秒23下29秒23下45下51秒54秒45下y秒在y秒时，小朋友停止了跳绳51=60–3*3输入：117

输出：570秒60秒17秒17下20秒17下y秒在y秒时，小朋友停止了跳绳57=60–1*3输入：410203040

输出：480秒60秒10秒10下13秒10下23秒20下26秒20下36秒30下39秒30下49秒40下52秒40下y秒在y秒时，小朋友停止了跳绳48=60–4*3输入：51020304058

输出：480秒60秒10秒10下13秒10下23秒20下26秒20下36秒30下39秒30下49秒40下52秒40下70秒58下75秒58下48=60–4*3输入：6102030404760

输出：600秒60秒10秒10下13秒10下23秒20下26秒20下36秒30下39秒30下49秒40下52秒40下59秒47下62秒47下75秒60下78秒60下47问题分析0秒60秒Case160秒Case2请同学们课后思考如何编写这个程序例题：合法C标识符

例题：合法C标识符

问题描述给定n个不包含空白符的字符串，请判断它们是否是C语言合法的标识符号（注：这些字符串一定不是C语言的关键字）。关于输入第一行为整数n，其后n行每行一个字符串，字符串中不包含任何空白字符，且长度不大于20。关于输出对应于每个字符串，如果它是C语言的合法标识符，则输出yes，否则输出no

。例题：合法C标识符

例子输入6GUE9NF1IccGB8nd97F3RKPEGX9R;TWyYcpiefZIko1s}zy9XBgsapOF36Lv5BYPeLPJ3vV`2[h例子输出yesyesnonoyesno#include<stdio.h>#defineMAX20/*最大标识符长度*/intmain(){inti,j,n;/*循环相关变量*/chars[MAX+1];/*定义字符数组*/scanf("%d",&n);/*读入待检查标识符的个数n*/for(i=0;i<n;i++){/*循环n次*/scanf("%s",s);/*读入一个待检查标识符字符串*/for(j=0;s[j];j++){/*遍历字符串中的每个字符*/if(!((s[j]=='_')||/*下划线“_”*/(s[j]>='A'&&s[j]<='Z')||/*大写字母*/(s[j]>='a'&&s[j]<='z')||/*小写字母*/(s[j]>='0'&&s[j]<='9'&&j>0)))

/*非首字符数字*/break;/*遇到任何非法字符中断循环*/

}

printf(s[j]?"no\n","yes\n");/*s[j]:break中断循环*/

}return0;}例题：首字母大写例题：首字母大写问题描述对一个字符串中的所有单词，如果单词的首字母不是大写字母，则把单词的首字母变成大写字母。在字符串中，单词之间通过空白符分隔，空白符包括：空格('')、制表符('\t')、回车符('\r')、换行符('\n’)。关于输入输入一行：待处理的字符串（长度小于80）。关于输出输出一行：转换后的字符串。提示由于输入字符串中有空格，因此应该用gets函数把一行字符串读入到字符数组s中。可用printf("%s\n",s)输出字符串s。例题：首字母大写例子输入ifso,youalreadyhaveagoogleaccount.youcansigninontheright.

例子输出IfSo,YouAlreadyHaveAGoogleAccount.YouCanSignInOnTheRight.

#include<stdio.h>#defineMAX80/*最大字符串长度*/intmain(){chars[MAX+1];/*字符数组*/inti;/*循环变量*/gets(s);/*读入一行字符串*/for(i=0;s[i];i++){/*遍历每个字符*//*判断s[i]是否为单词首字母，因为存在“布尔表达式短路”

规则，所以先判断i==0是安全的*/if(i==0||s[i-1]==''||s[i-1]=='\t'){if(s[i]>='a'

&&s[i]<='z'){/*首字母小写？

*/s[i]=s[i]-'a'+'A';/*把小写字符转换为大写*/}}}puts(s);/*输出转换后的字符串*/

return0;}例题：密码翻译例题：密码翻译问题描述在情报传递过程中，为了防止情报被截获，往往需要对情报用一定的方式加密，简单的加密算法虽然不足以完全避免情报被破译，但仍然能防止情报被轻易的识别。我们给出一种最简的加密方法，对给定的一个字符串，把其中从a~y，A~Y的字母用其后继字母替代，把z和Z用a和A替代，则可得到一个简单的加密字符串。关于输入第一行是字符串的数目n，（也用gets(s)读取字符串，再用

n

=atoi(s)获得整数数值）。其余n行每行一个字符串，用gets(s)方式读取这一行字符串。每个字符串长度小于80个字符。关于输出输出每行字符串的加密字符串。例题：密码翻译例子输入1Hello!Howareyou!例子输出Ifmmp!Ipxbsfzpv!#include<stdio.h>#include<string.h>#include<stdlib.h>#defineMAX80/*最大字符串长度*/intmain(){charstr[MAX+1];/*字符数组*/intn,i,j,len;/*循环相关变量*/

gets(str);/*读取第一个整数的字符串形式*/n=atoi(str);/*把字符串转换为整数值*/

for(i=0;i<n;i++){/*循环n次*/gets(str);/*每次读取一行待加密字符串*/.../*密码翻译，见下页*/puts(str);/*输出加密后的字符串*/}

return0;}len=strlen(str);/*求字符串的长度*/for(j=0;j<len;j++){/*用字符串长度控制遍历每个字符*/

if((str[j]>='a'

&&str[j]<='y')||

(str[j]>='A'

&&str[j]<='Y')){

str[j]=str[j]+1;/*把这些字符替换为其后继字符*/}elseif(str[j]=='z'){

str[j]='a';/*把z替换为a*/

}

elseif(str[j]=='Z'){

str[j]='A';/*把Z替换为A*/

}}例题：数制转换

例题：数制转换问题描述求任意两个不同进制非负整数的转换（二进制～三十六进制），所给整数在int所能表达的范围之内。不同进制的表示符号为（0，1，…，9，a，b，…，z）或者（0，1，…，9，A，B，…，Z）。关于输入输入只有一行，包含三个整数a、n、b。a表示其后的n是a进制整数，b表示欲将a进制整数n转换成b进制整数。a和b本身都是十进制整数，2≤a，b≤36

关于输出输出包含一行，该行有一个整数为转换后的b进制数。输出时字母符号全部用大写表示，即（0，1，…，9，A，B，…，Z）。例题：数制转换例子输入15Aab37

例子输出210306#include<stdio.h>#defineMAX80/*long型整数的任何进制数的长度都不比它大*/intmain(){

/*字符到数值的映射表，初始化为全0，待后面程序赋值*/inta2i[128]={0};

/*数值到字符的映射表，用字符串的形式初始化数组*/chari2a[]="0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ";

charin[MAX],out[MAX]="0";inti,from,to,len=0;longnum=0;

/*初始化a2i表*/for(i='0';i<='9';i++){a2i[i]=i-'0';}for(i='A';i<='Z';i++){a2i[i]=i-'A'+10;}for(i='a';i<='z';i++){a2i[i]=i-'a'+10;

}

/*按照指定的进制将数字读入，并放在变量num中*/scanf("%d%s%d",&from,in,&to);for(i=0;in[i]!='\0';i++){num=num*from+a2i[in[i]];}

/*数字已经在

num中，现在按照指定的进制输出它*/len=(num==0)?1:0;while(num>0){out[len++]=i2a[num%to];num/=to;}

/*逆序输出，高位下标大，但要先输出

*/

for(i=len-1;i>=0;i--){printf("%c",out[i]);}

return0;}例题：文字排版例题：文字排版问题描述给一段英文短文，单词之间以空格分隔（单词包括其前后紧邻的标点符号）。请按照每行不超过80个字符，每个单词居于同一行上的原则对短文进行排版，在同一行的单词之间以一个空格分隔，行首和行尾都没有空格。关于输入第一行是一个整数，表示英文短文中单词的数目。其后是n个以空格分隔的英文单词（单词包括其前后紧邻的标点符号，且每个单词长度都不大于40个字母）。关于输出排版后的多行文本，每行文本字符数最多80个字符，单词之间以一个空格分隔，每行文本首尾都没有空格。例题：文字排版例子输入84Oneswelteringday,Iwasscoopingicecreamintoconesandtoldmyfourchildrentheycould"buy"aconefrommeforahug.Almostimmediately,thekidslineduptomaketheirpurchases.Thethreeyoungesteachgavemeaquickhug,grabbedtheirconesandracedbackoutside.Butwhenmyteenagesonattheendofthelinefinallygothisturnto"buy"hisicecream,hegavemetwohugs."Keepthechanges,"hesaidwithasmile.例子输出Oneswelteringday,Iwasscoopingicecreamintoconesandtoldmyfourchildrentheycould"buy"aconefrommeforahug.Almostimmediately,thekidslineduptomaketheirpurchases.Thethreeyoungesteachgavemeaquickhug,grabbedtheirconesandracedbackoutside.Butwhenmyteenagesonattheendofthelinefinallygothisturnto"buy"hisicecream,hegavemetwohugs."Keepthechanges,"hesaidwithasmile.

例题：文字排版,I

OneendLINE...,I

wasOneendLINEend...,I

wasOneendLINE...例题：文字排版,IwasbeiOneng,I

wasOneendLINE...endLINEend,IwasOneLINEbeingend.........#include<stdio.h>#include<string.h>

#defineMAX40/*最大单词长度*/#defineLINE80/*一行的宽度*/

intmain(){inti,n,len;/*循环相关变量*/intend=0;/*下一个单词（或空格）输出的位置*/charword[MAX+1];/*单词字符数组*/

scanf("%d",&n);/*读入单词数目n*/for(i=0;i<n;i++){/*循环n次*/scanf("%s",word);/*每次读入一个单词*/

...

/*确定如何输出，见下一页

*/

}

return0;}for(i=0;i<n;i++){/*循环n次*/scanf(“%s”,word);/*每次读入一个单词*/len=strlen(word);/*求得单词字符串的长度*//*在当前行上，再输出一个单词（包括前面的空格）后是否超限*/if(end+len+1>LINE){printf("\n");/*超出LINE个字符限制时，换行*/end=0;/*下一个单词输出的位置归0*/}elseif(i>0){/*第一个单词前不加空格*/printf("");/*其余单词前要加空格*/end++;/*更新到下一个单词输出的位置*/}printf("%s",word);/*输出单词*/end+=len;/*更新到下一个空格输出的位置*/}55函数示例：假币问题问题描述

赛利有12枚银币。其中有11枚真币和1枚假币。假币看起来和真币没有区别，但是重量不同。赛利不知道假币比真币轻还是重。于是他向朋友借了一架天平。赛利希望称三次就能找出假币并且确定假币是轻是重。例如：如果赛利用天平称两枚硬币，发现天平平衡，说明两枚都是真的。如果赛利用一枚真币与另一枚银币比较，发现它比真币轻或重，说明它是假币。经过精心安排每次的称量，赛利保证在称三次后一定能够确定假币。

任务

编写一个程序，根据三次称量的结果，确定哪一个是假币，并指出其轻重。

56输入输入有三行，每行表示一次称量的结果。赛利事先将银币标号为A-L。每次称量的结果用三个以空格隔开的字符串表示：天平左边放置的硬币

天平右边放置的硬币

平衡状态其中平衡状态用“up”，“down”

或“even”

表示，分别为右端高、右端低和平衡。天平左右的硬币数总是相等的。函数示例：假币问题57输出输出哪一个标号的银币是假币，并说明它比真币轻还是重。

函数示例：假币问题58输入样例ABCDEFGHevenABCIEFJKupABIJEFGHeven

输出样例K是假币，它比较轻。函数示例：假币问题59算法思路

依次假设A-L是假币并且轻，再依次假设A-L是假币并且重，检查每次假设是否与称得的结果矛盾，如果矛盾，则假设不成立，否则假设成立。60假币问题定义全局变量存储称量结果charleft[3][7],right[3][7],result[3][5];数组下标3和7代表什么，为什么？61假币问题总体构想——

逐一试探法对于每一枚硬币isLight?Yes.输出，No.isHeavy?Yes.输出62假币问题：利用函数来解决问题#include<stdio.h>charleft[3][7],right[3][7],result[3][5];//全局变量，在各个函数中都可以使用voidmain(){scanf(“%s%s%s”,left[0],right[0],result[0]);scanf(“%s%s%s”,left[1],right[1],result[1]);scanf(“%s%s%s”,left[2],right[2],result[2]);for(charc=‘A’;c<=‘L’;c++){if(isLight(c)){printf("%c是假币，它比较轻。\n",c);break;}elseif(isHeavy(c)){printf(“%c是假币，它比较重。\n",c);break;}}}63intisLight(charx)//假设银币x是轻假币，看输入的条件是否满足{inti;for(i=0;i<3;i++)//判断3个条件是否矛盾

{switch(result[i][0]){case‘u’://右边轻，假币应该在右边

if(!

inRight(i,x))return0;break;case‘e’://两边相等，假币应该不在称上

if(inRight(i,x)||inLeft(i,x))return0;break;case‘d’://右边重，假币应该在左边

if(!

inLeft(i,x))return0;break;}}return1;}64intisHeavy(charx)//假设银币x是重假币，看输入的条件是否满足{inti;for(i=0;i<3;i++)//判断3个条件是否矛盾

{switch(result[i][0]){case‘u’://右边轻，假币应该在左边

if(!inLeft(i,x))return0;break;case‘e’://两边相等，假币应该不在称上面

if(inRight(i,x)||inLeft(i,x))return0;break;case‘d’://右边重，假币应该在右边

if(!

inRight(i,x))return0;break;}}return1;}65intinLeft(inti,charx)//判断x是否在第i次称量时天平的左边{intj;for(j=0;j<strlen(left[i]);j++){if(left[i][j]==x)return1;}return0;}intinRight(inti,charx)//判断x是否在第i次称量时天平的左边{intj;for(j=0;j<strlen(right[i]);j++){if(right[i][j]==x)return1;}return0;}66分治思想

对于简单问题，我们可以用一段较短的代码来获得问题的解。但实际中很多问题都是比较复杂的，简短的代码是无法解决问题的。这时，就需要我们将一个复杂问题分解成若干个简单问题，并逐一求解；然后再把几个简单问题的解综合起来，得到整个复杂问题的解。——这就是分而治之的思想。在C语言中，我们可以利用函数来实现分治思想。如前面的假币问题，我们就是利用5个函数来解决问题的：main()、isLight()、isHeavy()、inLeft()、inRight()例题：约瑟夫问题描述 约瑟夫问题：有ｎ只猴子，按顺时针方向围成一圈选大王（编号从１到ｎ），从第１号开始报数，一直数到ｍ，数到ｍ的猴子退出圈外，剩下的猴子再接着从1开始报数。就这样，直到圈内只剩下一只猴子时，这个猴子就是猴王，编程求输入ｎ，ｍ后，输出最后猴王的编号。 关于输入

每行是用空格分开的两个整数，第一个是n,第二个是m(0<m,n<=300)。最后一行是“00”关于输出

对于每行输入数据（最后一行除外)，输出数据也是一行，即最后猴王的编号。按部就班的解决问题用数组记录猴子的编号，通过在数组上依次删除报数到m的猴子的编号，直到数组中只剩下一个猴子的编号，即为所求。抽象每次删除操作的：删除从第k个位置后面第m个位置的猴子编号（需要循环遍历数组），删除后数组的大小减1。5个猴子数到3的实例123451231245123245123241234#include

<stdio.h>intremove_next(inta[],intn,intm,intk);intmain(){

inta[300];

intm,n,i,k;scanf("%d%d",&n,&m);

while(n!=