小学五年级信息学奥赛教材

《小学五年级信息学奥赛教材》由会员分享，可在线阅读，更多相关《小学五年级信息学奥赛教材（43页珍藏版）》请在装配图网上搜索。

1、第1课 结构流程图学习目标1、进一步掌握流程图的概念与意义，会用流程图的方式表达算法的顺序及过程。2、会用三种逻辑结构来进行流程图的设计开始输入A、B、C、x0、y0z1=Ax0+By0+Cz2=A2+B2 输出d结束一、算法的三种重要结构是：（1）顺序结构：描述的是最简单的算法结构，语句与语句之间，框与框之间是按从上到下的顺序进行的。（2）条件分支结构：它是依据指定条件选择执行不同指令的控制结构。（3）循环结构：根据指定条件决定是否重复执行一条或多条指令的控制结构。其中有两种类型的循环：直到型（Until型）循环：如图（1），先执行A框，再判断给定的条件P是否为“假”。若P为“假”，则再执行

2、A框，如此反复，直到为“真”为止。当型（While型）循环：如图（2）当给定的条件P成立时（“真”），反复执行A框操作，直到条件P为“假”时才停止循环。二、三种结构流程图练习下列三个问题，应分别用哪种逻辑结构给出流程图？1、已知点和直线l：Ax+By+C=0，写出求点P到直线l的距离d的流程图。2、写出求一元二次方程的根的流程图。3、已知n个正数排成一行如下：，其中下脚码表示n个数的排列位置。这一行数满足条件：，画出计算第n项的程序框图。三、知识运用例1 设y为年份，按照历法的规定，如果y为闰年，那么或者y能被4整除不能被100整除，或者y能被400整除。对于给定的年份y，要确定索是否为闰年，

3、如何设计算法，画出其流程图。例2 一个三位数，各位数字互不相同，十位数字比个位、百位数字之和还要大，且十位数字、百位数字不是素数。设计一种算法，找出所有符合条件的三位数，要求画出流程图。结束开始输出i是是是是是否否否否开始否100|y?是输出y非闰年输出y是闰年是4|y?否i输入y否400|y?是例3 已知算法：（1）指出其功能（用算式表示），（2）将该算法用流程图来描述之。S1 输入X；S2 若X0，执行S3；否则，执行S6；S3 ；S4 输出Y；S5 结束；S6 若X=0，执行S7；否则执行S10；S7 ；S8 输出Y；S9 结束；S10 ；S11 输出Y；S12 结束。结束开始输入x输出

4、y输出y输出y解：这是一个输入x的值，求y值的函数的算法。其中其流程图如下。小结1画出一个计算值的一个算法的程序框图。2写出计算的算法的程序框图。3画出任给一个有两位小数的实数，对末位用“四舍五入法”，求精确到一位小数的程序框图。第2课 进制转换学习目标1、学习10进制转2进制的方法；2、学习10进制数转换为8、16进制数一、进制数转换为2进制数给你一个十进制，比如：6，如果将它转换成二进制数呢？10进制数转换成二进制数，这是一个连续除2的过程：把要转换的数，除以2，得到商和余数，将商继续除以2，直到商为0。最后将所有余数倒序排列，得到数就是转换结果。听起来有些糊涂？我们结合例子来说明。比如要

5、转换6为二进制数。“把要转换的数，除以2，得到商和余数”。那么：要转换的数是6， 6 2，得到商是3，余数是0。 （不要告诉我你不会计算63！）“将商继续除以2,直到商为0”现在商是3，还不是0，所以继续除以2。那就： 3 2, 得到商是1,余数是1。“将商继续除以2，直到商为0”现在商是1，还不是0，所以继续除以2。那就： 1 2, 得到商是0，余数是1 （拿笔纸算一下，12是不是商0余1!）“将商继续除以2，直到商为0最后将所有余数倒序排列”好极！现在商已经是0。我们三次计算依次得到余数分别是：0、1、1，将所有余数倒序排列，那就是：110了！6转换成二进制，结果是110。把上面的一段改成

6、用表格来表示，则为： 被除数计算过程商余数66/23033/21111/201（在计算机中，用 / 来表示） 如果是在考试时，我们要画这样表还是有点费时间，所更常见的换算过程是使用下图的连除： 二、10进制数转换为8、16进制数非常开心，10进制数转换成8进制的方法，和转换为2进制的方法类似，惟一变化：除数由2变成8。来看一个例子，如何将十进制数120转换成八进制数。用表格表示： 被除数计算过程商余数120120/81501515/81711/801120转换为8进制，结果为：170。非常非常开心，10进制数转换成16进制的方法，和转换为2进制的方法类似，惟一变化：除数由2变成16。同样是12

7、0，转换成16进制则为： 被除数计算过程商余数120120/167877/1607120转换为16进制，结果为：78。小结10进制转换成2进制、10进制、16进制的方法。第3课 字符串函数学习目标记忆字符串函数一、函数 语法 功能 1、Len Len(string|varname) 返回字符串内字符的数目，或是存储一变量所需的字节数。 2、Trim Trim(string) 将字符串前后的空格去掉 3、Ltrim Ltrim(string) 将字符串前面的空格去掉 4、Rtrim Rtrim(string) 将字符串后面的空格去掉 5、Mid Mid(string,start,length)

8、从string字符串的start字符开始取得length长度的字符串，如果省略第三个参数表示从start字符开始到字符串结尾的字符串 6、Left Left(string,length) 从string字符串的左边取得length长度的字符串 7、Right Right(string,length) 从string字符串的右边取得length长度的字符串 8、LCase LCase(string) 将string字符串里的所有大写字母转化为小写字母 9、UCase UCase(string) 将string字符串里的所有大写字母转化为大写字母 10、StrComp StrComp(string

9、1,string2，compare) 返回string1字符串与string2字符串的比较结果，如果两个字符串相同，则返回0，如果小于则返回-1，如果大于则返回1 11、InStr InStr(string1,string2,compare) 返回string1字符串在string2字符串中第一次出现的位置 Split Split(string1,delimiter,count,start) 将字符串根据delimiter拆分成一维数组，其中delimiter用于标识子字符串界限。如果省略，使用空格()作为分隔符。count返回的子字符串数目，-1指示返回所有子字符串。start为1执行文本比

10、较；如果为0或者省略执行二进制比较。 12、Replace Replace(expression,find,replacewith,compare,count,start) 返回字符串，其中指定数目的某子字符串(find)被替换为另一个子字符串(replacewith)。 小结字符串函数的应用。第4课 二维数组学习目标学习二维数组的概念 一、生活情景事实要开始变得复杂。 生活中，有很多事物，仅仅用一维数组，将无法恰当地被表示。还是说学生成绩管理吧。一个班级30个学员，你把他们编成1到30号，这很好。但现在有两个班级要管理怎么办？人家每个班级都自有自的编号，比如一班学生编是130；二班的学生也是

11、130。你说，不行，要进行计算机管理，你们两班学员的编号要混在一起，从1号编到60号。 另外一种情况，仍然只有一个班级30人。但这回他们站到了操场，他们要做广播体操，排成5行6列。这时所有老师都不管学员的编号了，老师会这样喊：“第2排第4个同学，就说你啦！踢错脚了！”。假设我们的校长大人要坐在校长室里，通过一个装有监视器的电脑查看全校学员做广播体操，这时，我们也需要一个多维数组。 二、二维数组基本语法语法：定义一个二维数组。 数据类型 数组名第二维大小第一维大小; 举例： int arr56; /注意，以分号结束。 这就是操场上那个“5行6列的学生阵”。当然，哪个是行哪个列凭你的习惯。如果数人

12、头时，喜欢一列一列地数，那你也可以当成它是“5列6行”台湾人好像有这怪僻我们还是把它看成5行6列吧。 现在： 第一排第一个学员是哪个？答：arr00； 第二排第三个学员是？答：arr12； 也不并不困难，对不？惟一别扭的其实还是那个老问题：现实上很多东西都是从1开始计数，而在C里，总是要从0开始计数。 接下来，校长说，第一排的全体做得很好啊，他们的广播体操得分全部加上5分！程序如何写？答： for(int col=0; col6; col+) arr0col += 5; 对了，这里我没有用 i 来作循环的增量，而是用col。因为col在英语里表示“列”，这样更直观对不？下面要用到行，则用row

13、。 广播操做到“跳跃运动”了，校长大人在办公室蹦了两下，感觉自已青春依旧，大为开心，决定给所有学员都加1分，程序如何写？答： for(int row = 0; row 5; row+) for(int col = 0; col 6; col+) arrrowcol += 1; 看明白了吗？在二维数组，要确定一个元素，必须使用两个下标。 另外，这个例子也演示了如何遍历一个二维数组：使用双层循环。第一层循环让row 从 0到 4, 用于遍历每一行；col从0到5，遍历每一行中的每一列。 (遍历：访问某一集合中的每一个元素的过程) 大家把这两个程序都实际试一试. 三、二维数组初始化一维数组可以定义时

14、初始化： int arr = 0,1,2,3,4; 二维数组也可以： int arr56 = 0, 1, 2, 3, 4, 5, 10,11,12,13,14,15, 20,21,22,23,24,25, 30,31,32,33,34,35, 40,41,42,43,44,45, ; /注意，同样以分号结束 初始化二维数组使用了两层,内层初始化第一维，每个内层之间用逗号分隔。 例二：我们可以把这个数组通过双层循环输出： for(int row = 0; row 5; row+) for(int col = 0; col 6; col+) cout arrrowcol endl; 这段代码会把二

15、维数组arr中的所有元素（5*6=30个），一行一个地，一古脑地输出，并不适于我们了解它的二维结构。我们在输出上做些修饰： for(int row = 0; row 5; row+) cout 第 row + 1 行: for(int col = 0; col 6; col+) cout arrrowcol ,; /同一行的元素用逗号分开 cout endl; /换行 试验这两段代码，对比输出结果，明白二维数组中各元素次序。下面是完整程序中，后一段代码的输出： 小结二维数的应用及初始化过程。第5课 打鱼还是晒网 学习目标1、学习MOD的用法2、学习模拟算法的应用一、问题情景中国有句俗语叫“三天

16、打鱼两天晒网”。某人从1990年1月1日起开始“三天打鱼两天晒网”，问这个人在以后的某一天中是“打鱼”还是“晒网”。二、问题分析与算法设计 根据题意可以将解题过程分为三步：1)计算从1990年1月1日开始至指定日期共有多少天；2)由于“打鱼”和“晒网”的周期为5天，所以将计算出的天数用5去除；3)根据余数判断他是在“打鱼”还是在“晒网”； 若 余数为1，2，3，则他是在“打鱼” 否则 是在“晒网” 在这三步中，关键是第一步。求从1990年1月1日至指定日期有多少天，要判断经历年份中是否有闰年，二月为29天，平年为28天。闰年的方法可以用伪语句描述如下： 如果 (年能被4除尽 且 不能被100除

17、尽)或 能被400除尽) 则 该年是闰年； 否则 不是闰年。 C语言中判断能否整除可以使用求余运算(即求模)三、程序与程序注释intdays(struct date day);struct date int year; int month; int day;void main() struct date today,term; int yearday,year,day; printf(Enter year/month/day:); scanf(%d%d%d,&today.year,&today.month,&today.day); /*输入日期*/ term.month=12; /*设置变量的

18、初始值：月*/ term.day=31; /*设置变量的初始值：日*/ for(yearday=0,year=1990;year0&day4) printf(he was fishing at that day.n); /*打印结果*/ else printf(He was sleeping at that day.n);intdays(struct date day) static int day_tab213= 0,31,28,31,30,31,30,31,31,30,31,30,31, /*平均每月的天数*/ 0,31,29,31,30,31,30,31,31,30,31,30,31,

19、; int i,lp; lp=day.year%4=0&day.year%100!=0|day.year%400=0; /*判定year为闰年还是平年，lp=0为平年，非0为闰年*/ for(i=1;iday.month;i+) /*计算本年中自1月1日起的天数*/ day.day+=day_tablpi; return day.day;*运行结果 Enter year/month/day:1991 10 25 He was fishing at day. Enter year/month/day:1992 10 25 He was sleeping at day. Enter year/mo

20、nth/day:1993 10 25 He was sleeping at day.小结打印出任意年份的日历的程序设计。第6课 抓交通肇事犯 学习目标逻辑判断的语言描述。一、问题情景一辆卡车违反交通规则，撞人后逃跑。现场有三人目击事件，但都没有记住车号，只记下车号的一些特征。甲说：牌照的前两位数字是相同的；乙说：牌照的后两位数字是相同的，但与前两位不同； 丙是数学家，他说：四位的车号刚好是一个整数的平方。请根据以上线索求出车号。二、问题分析与算法设计 按照题目的要求造出一个前两位数相同、后两位数相同且相互间又不同的整数，然后判断该整数是否是另一个整数的平方。三、程序与程序注释void main

21、() int i,j,k,c; for(i=1;i=9;i+) /*i:车号前二位的取值*/ for(j=0;j=9;j+) /*j:车号后二位的取值*/ if(i!=j) /*判断二位数字是否相异*/ k=i*1000+i*100+j*10+j; /*计算出可能的整数*/ for(c=31;c*ck;c+); /*判断该数是否为另一整数的平方*/ if(c*c=k) printf(Lorry-No. is %d.n,k); /*若是，打印结果*/ *运行结果 Lorry _No.is 7744小结逻辑判断与循环语句的应用。第7课 该存多少钱 学习目标递推法的应用和语言描述。一、问题情景假设银

22、行一年整存零取的月息为0.63%。现在某人手中有一笔钱，他打算在今后的五年中的年底取出1000元，到第五年时刚好取完，请算出他存钱时应存入多少。二、问题分析与算法设计 分析存钱和取钱的过程，可以采用倒推的方法。若第五年年底连本带息要取1000元，则要先求出第五年年初银行存款的钱数： 第五年初存款=1000/(1+12*0.0063)依次类推可以求出第四年、第三年.的年初银行存款的钱数： 第四年年初存款=(第五年年初存款+1000)/(1+12*0.0063) 第三年年初存款=(第四年年初存款+1000)/(1+12*0.0063) 第二年年初存款=(第三年年初存款+1000)/(1+12*0.

23、0063) 第一年年初存款=(第二年年初存款+1000)/(1+12*0.0063)通过以上过程就可以很容易地求出第一年年初要存入多少钱。三、程序与程序注释#includevoid main()int i;float total=0;for(i=0;i5;i+) /*i 为年数，取值为04年*/total=(total+1000)/(1+0.0063*12); /*累计算出年初存款数额，第五次的计算 结果即为题解*/printf(He must save %.2f at first.n,total);*运行结果 He must save 4039.44 at first小结1、递推算法的语言描

24、述；2、递推算法的生活实际应用。第8课 捕鱼和分鱼学习目标递推算法的语言描述一、问题描述 A、B、C、D、E五个人在某天夜里合伙去捕鱼，到第二天凌晨时都疲惫不堪，于是各自找地方睡觉。日上三杆，A第一个醒来，他将鱼分为五份，把多余的一条鱼扔掉，拿走自己的一份。B第二个醒来，也将鱼分为五份，把多余的一条鱼扔掉，保持走自己的一份。C、D、E依次醒来，也按同样的方法拿走鱼。问他们合伙至少捕了多少条鱼？二、问题分析与算法设计 根据题意，总计将所有的鱼进行了五次平均分配，每次分配时的策略是相同的，即扔掉一条鱼后剩下的鱼正好分成五份，然后拿走自己的一份，余下其它的四份。 假定鱼的总数为X，则X可以按照题目的

25、要求进行五次分配：X-1后可被5整除，余下的鱼为4*(X-1)、5。若X满足上述要求，则X就是题目的解。三、程序与程序注释void main() int n,i,x,flag=1; /*flag：控制标记*/ for(n=6;flag;n+) /*采用试探的方法。令试探值n逐步加大*/ for(x=n,i=1&flag;i=5;i+) if(x-1)%5=0) x=4*(x-1)/5; else flag=0; /*若不能分配则置标记falg=0退出分配过程*/ if(flag) break; /*若分配过程正常结束则找到结果退出试探的过程*/ else flag=1; /*否则继续试探下一个

26、数*/ printf(Total number of fish catched=%dn,n); /*输出结果*/*运行结果 Total number of fish catched = 3121小结程序采用试探法，试探的初值为6，每次试探的步长为1。这是过分保守的做法。可以在进一步分析题目的基础上修改此值，增大试探的步长值，以减少试探次数。第9课 出售金鱼 学习目标递推算法的语言描述一、问题描述 买卖提将养的一缸金鱼分五次出售系统上一次卖出全部的一半加二分之一条；第二次卖出余下的三分之一加三分之一条；第三次卖出余下的四分之一加四分之一条；第四次卖出余下的五分之一加五分之一条；最后卖出余下的11

27、条。问原来的鱼缸中共有几条金鱼？二、题目分析与算法设计 题目中所有的鱼是分五次出售的，每次卖出的策略相同；第j次卖剩下的(j+1)分之一再加1/(j+1)条。第五次将第四次余下的11条全卖了。 假定第j次鱼的总数为X，则第j次留下： x-(x+1)/(j+1)当第四次出售完毕时，应该剩下11条。若X满足上述要求，则X就是题目的解。 应当注意的是：(x+1)/(j+1)应满足整除条件。试探X的初值可以从23开始，试探的步长为2，因为X的值一定为奇数。三、程序说明与注释void main() int i,j,n=0,x; /*n为标志变量*/ for(i=23;n=0;i+=2) /*控制试探的步

28、长和过程*/ for(j=1,x=i;j=11;j+) /*完成出售四次的操作*/ if(x+1)%(j+1)=0) /*若满足整除条件则进行实际的出售操作*/ x-=(x+1)/(j+1); else x=0;break; /*否则停止计算过程*/ if(j=5&x=11) /*若第四次余下11条则满足题意*/ printf(There are %d fishes at first.n,i); /*输出结果*/n=1; /*控制退出试探过程*/*运行结果There are 59 fishes at first. 小结 日本著名数学游戏专家中村义作教授提出这样一个问题：父亲将2520个桔子分给

29、六个儿子。分完后父亲说：“老大将分给你的桔子的1/8给老二；老二拿到后连同原先的桔子分1/7给老三；老三拿到后连同原先的桔子分1/6给老四；老四拿到后连同原先的桔子分1/5给老五；老五拿到后连同原先的桔子分1/4给老六；老六拿到后连同原先的桔子分1/3给老大”。结果大家手中的桔子正好一样多。问六兄弟原来手中各有多少桔子？第10课 平分七筐鱼学习目标递推算法的语言描述一、问题描述甲、乙、丙三位鱼夫出海打鱼，他们随船带了21只箩筐。当晚返航时，他们发现有七筐装满了鱼，还有七筐装了半筐鱼，另外七筐则是空的，由于他们没有秤，只好通过目测认为七个满筐鱼的重量是相等的，7个半筐鱼的重量是相等的。在不将鱼倒

30、出来的前提下，怎样将鱼和筐平分为三份？二、问题分析与算法设计 根据题意可以知道：每个人应分得七个箩筐，其中有3.5筐鱼。采用一个3*3的数组a来表示三个人分到的东西。其中每个人对应数组a的一行，数组的第0列放分到的鱼的整筐数，数组的第1列放分到的半筐数，数组的第2列放分到的空筐数。由题目可以推出：数组的每行或每列的元素之和都为7； 对数组的行来说，满筐数加半筐数=3.5； 每个人所得的满筐数不能超过3筐； 每个人都必须至少有1 个半筐，且半筐数一定为奇数 对于找到的某种分鱼方案，三个人谁拿哪一份都是相同的，为了避免出现重复的分配方案，可以规定：第二个人的满筐数等于第一个人的满筐数；第二个人的半

31、筐数大于等于第一个人的半筐数。三、程序与程序注释int a33,count;void main() int i,j,k,m,n,flag; printf(It exists possible distribtion plans:n); for(i=0;i3*/ a00=i;for(j=i;j=7-i&j3*/a10=j;if(a20=7-j-a00)3)continue; /*第三个人满筐数不能3*/if(a20=前一个人，以排除重复情况*/for(k=1;k=5;k+=2) /*试探半筐a01的值，半筐数为奇数*/a01=k;for(m=1;m7-k;m+=2) /*试探 半筐a11的值，半

32、筐数为奇数*/a11=m;a21=7-k-m;for(flag=1,n=0;flag&n3;n+) /*判断每个人分到的鱼是 3.5筐，flag为满足题意的标记变量*/if(an0+an17&an0*2+an1=7)an2=7-an0-an1; /*计算应得到的空筐数量*/else flag=0; /*不符合题意则置标记为0*/if(flag)printf(No.%d Full basket Semi-basket Emptyn,+count);for(n=0;n3;n+)printf( fisher %c: %d %d %dn, A+n,an0,an1,an2);*运行结果It exists

33、 possible distribution plans: No.1 Full basket Semi-basket Empty fisher A: 1 5 1 fisher B: 3 1 3fisher C: 3 13 No.2Full basketSemi-basket Empty fisher A: 2 3 2 fisher B: 2 3 2 fisher C: 31 3小结 晏会上数学家出了一道难题：假定桌子上有三瓶啤酒，癣瓶子中的酒分给几个人喝，但喝各瓶酒的人数是不一样的。不过其中有一个人喝了每一瓶中的酒，且加起来刚好是一瓶，请问喝这三瓶酒的各有多少人？ (答案：喝三瓶酒的人数分别是

34、2人、3人和6人)第11课 要发就发学习目标数组的应用及语言描述一、问题描述 “1898-要发就发”。请将不超过1993的所有素数从小到大排成第一行，第二行上的每个素数都等于它右肩上的素数之差。编程求出：第二行数中是否存在这样的若干个连续的整数，它们的和恰好是1898？假好存在的话，又有几种这样的情况？ 第一行：2 3 5 7 11 13 17.1979 1987 1993 第二行：1 2 2 4 2 4.8 6二、问题分析与算法设计： 首先从数学上分析该问题： 假设第一行中的素数为n1、n2、n3.ni、.第二行中的差值为m1、m2、m3.mj.。其中mj为： mj=nj+1-nj。则第二行

35、连续N个数的和为： SUM=m1+m2+m3+.+mj =(n2-n1)+(n3-n2)+(n4-n3)+.+(nj+1-nj) =nj+1-n1由此题目就变成了：在不超过1993的所有素数中是否存在这样两个素数，它们的差恰好是1898。若存在，则第二行中必有所需整数序列，其和恰为1898，。 对等价问题的求解是比较简单的。 由分析可知，在素数序列中不必包含2，因为任意素数与2的差一定为奇数，所以不必考虑。三、程序与程序注释：int numberNUM; /*存放不超过1993的全部奇数*/int fflag(int i);void main() int i,j,count=0; printf

36、(there are follwing primes sequences in first row:n); for(j=0,i=3;i1898;j-)/*从最大的素数开始向1898搜索*/ for(i=0;numberj-numberi1898;i+); /*循环查找满足条件的素数*/ if(numberj-numberi=1898) /*若两个素数的差为1898，则输出*/ printf(%d).%3d,.,%dn,+count,numberi,numberj); int fflag(int i) int j; if(i=1) return 0; /*判断是否为素数*/ if(i=2) re

37、turn 1; if(!(i%2) return 0;/*if no, return 0*/ for(j=3;j=(int)(sqrt(double)i)+1);j+=2) if(!(i%j) return 0; return 1;*运行结果 There are follwing primes sequences in first row: (1).89,.,1987 (2).53,.,1951 (3). 3,.,1901小结 将1,2，3，,20这20个连续的自然数排成一圈，使任意两个相邻的自然数之和均为素数。第12课 猴子分桃学习目标递推算法的理解及语言描述一、问题描述五只猴子采得一堆桃子

38、，猴子彼此约定隔天早起后再分食。不过，就在半夜里，一只猴子偷偷起来，把桃子均分成五堆后，发现还多一个，它吃掉这桃子，并拿走了其中一堆。第二只猴子醒来，又把桃子均分成五堆后，还是多了一个，它也吃掉这个桃子，并拿走了其中一堆。第三只，第四只，第五只猴子都依次如此分食桃子。那么桃子数最少应该有几个呢？ s=s*5/4+1二、编程简析怎样编程呢？先要找一下第N只猴子和其面前桃子数的关系。如果从第1只开始往第5只找，不好找，但如果思路一变，从第N到第1去，可得出下面的推导式：第N只猴 第N只猴前桃子数目5 s5=x4 s4=s5*5/4+13 s3=s4*5/4+12 s2=s3*5/4+11 s1=s

39、2*5/4+1s1即为所求。上面的规律中只要将s1-s5的下标去掉：s=xs=s*5/4+1s=s*5/4+1s=s*5/4+1s=s*5/4+1所以可以用循环语句加以解决。综观程序的整体结构，最外是一个循环，因为循环次数不定，可以使用While循环，其结束条件则是找到第一个符合条件的数。为了做出上面while循环的结束条件，还需进一步分析上述规律的特点，要符合题目中的要求，s1-s4四个数必须全部为整数，这个可作为条件。三、源程序ClsX=6K=0Do S=xK=0For i=4 to 1 step -1S=s*5/4+1If int(s)=s then K=k+1End ifNext iX

40、=x+5Loop while k4Print s小结理解递推算法的结构美。第13课 谁是窃贼学习目标逻辑判断问题的语言描述及问题分析一、问题描述 公安人员审问四名窃贼嫌疑犯。已知，这四人当中仅有一名是窃贼，还知道这四人中每人要么是诚实的，要么总是说谎的。在回答公安人员的问题中： 甲说：“乙没有偷，是丁偷的。” 乙说：“我没有偷，是丙便的。” 丙说：“甲没有偷，是乙偷的。” 丁说：“我没有偷。” 请根据这四人的答话判断谁是盗窃者。二、问题分析与算法设计 假设A、B、C、D分别代表四个人，变量的值为1代表该人是窃贱。 由题目已知：四人中仅有一名是窃贱，且这四个人中的每个人要么说真话，要么说假话，而

41、由于甲、乙、丙三人都说了两句话：“X没偷，X偷了”，故不论该人是否说谎，他提到的两人中必有一人是小偷。故在列条件表达式时，可以不关心谁说谎，谁说实话。这样，可以列出下列条件表达式： 甲说：”乙没有偷，是丁偷的。” B+D=1 乙说：“我没有偷，是丙偷有。” B+C=1 丙说：“甲没有偷，是乙偷的。” A+B=1 丁说：“我没有偷。” A+B+C+D=1 其中丁只说了一句话，无法判定其真假，表达式反映了四人中仅有一名是窃贱的条件。三、程序与程序注释、 int i,j,a4; for(i=0;i4;i+) /*假定只有第i个人为窃贱*/ for(j=0;j4;j+) /*将第i个人设置为1表示窃贱

42、，其余为0*/ if(j=i)aj=1; else aj=0; if(a3+a1=1&a1+a2=1&a0+a1=1) /*判断条件是否成立*/ printf(The thief is ); /*成立*/ for(j=0;j=3;j+) /*输出计算结果*/ if(aj)printf(%c.,j+A); printf(n); *运行结果The thief is B. (乙为窃贱。)小结理解逻辑判断问题的语言描述的关键及枚举算法的应用。第14课 黑与白学习目标学习枚举算法在逻辑判断中的应用。一、问题描述 有A、B、C、D、E五人，每人额头上都帖了一张黑或白的纸。五人对坐，每人都可以看到其它人额头

43、上的纸的颜色。五人相互观察后， A说：“我看见有三人额头上帖的是白纸，一人额头上帖的是黑纸。” B说：“我看见其它四人额头上帖的都是黑纸。” C说：“我看见一人额头上帖的是白纸，其它三人额头上帖的是黑纸。” D说：“我看见四人额头上帖的都是白纸。” E什么也没说。 现在已知额头上帖黑纸的人说的都是谎话，额头帖白纸的人说的都是实话。问这五人谁的额头是帖白纸，谁的额头是帖黑纸？二、问题分析与算法设计 假如变量A、B、C、D、E表示每个人额头上所帖纸的颜色，0 代表是黑色，1 代表是白色。根据题目中A、B、C、D四人所说的话可以总结出下列关系： A说： a&b+c+d+e=3|!a&b+c+d+e!

44、=3 B说： b&a+c+d+e=0|!b&a+c+d+e!=0 C说： c&a+b+d+e=1|!c&a+b+d+e!=1 D说： d&a+b+c+e=4|!d&a+b+c+e!=4 穷举每个人额头所帖纸的颜色的所有可能的情况，代入上述表达式中进行推理运算，使上述表达式为“真”的情况就是正确的结果。三、程序与程序注释 int a,b,c,d,e; for(a=0;a=1;a+) /*黑色：0 白色：1*/ for(b=0;b=1;b+)/*穷举五个人额头帖纸的全部可能*/ for(c=0;c=1;c+) for(d=0;d=1;d+) for(e=0;e=1;e+) if(a&b+c+d+e

45、=3|!a&b+c+d+e!=3) &(b&a+c+d+e=0|!b&a+c+d+e!=0) &(c&a+b+d+e=1|!c&a+b+d+e!=1) &(d&a+b+c+e=4|!d&a+b+c+e!=4) printf(A is pasted a piece of %s paper on his forehead.n, a?white:black); printf(B is pasted a piece of %s paper on his forehead.n, b?white:black); printf(C is pasted a piece of %s paper on his f

46、orehead.n, c?white:black); printf(D is pasted a piece of %s paper on his forehead.n, d?white:black); printf(E is pasted a piece of %s paper on his forehead.n, e?white:black); *运行结果 A is pasted a paper of black paper on his forehead. (黑)B is pasted a paper of black paper on his forehead. (黑)C is pasted a paper ofwhite paper on his forehead. (白)D is pasted a paper of black paper on his forehead. (黑)E is pasted a paper ofwhite paper on his forehead. (白)小结体会枚举算法在逻辑判断中的应用。第15课 迷语博士的难题(1)学习目标学习枚举算法在逻辑判断中的应用。一、问题描述