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

《小学五年级信息学奥赛教材.doc》由会员分享，可在线阅读，更多相关《小学五年级信息学奥赛教材.doc（44页珍藏版）》请在麦多课文档分享上搜索。

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

2、到为“真”为止。 当型（ While 型）循环： 如图（ 2）当给定的条件 P成立时（“真”），反复执行 A 框操作，直到条件 P 为“假”时才停止循环。 二、三种结构流程图练习 下列三个问题，应分别用哪种逻辑结构给出流程图？ 1、 已知点 )y,x(P 00 和直线 l： Ax+By+C=0，写出求点 P 到直线 l 的距离 d 的流程图。 2、 写出求一元二次方程 0cbxax 2 的根的流程图。 3、 已知 n 个正数排成一行如下： n1n321 a,a,a,a,a ，其中下脚码表示 n 个数的排列位置。这一行数满足条件： 1n2nn21 aaa,1a,1a )Nn,3n( ，画出计算第

3、 n 项的程序框图。 三 、知识运用 例 1 设 y 为年份，按照历法的规定，如果 y 为闰年，那么或者 y 能被 4 整除不能被 100整除，或者 y 能被 400 整除。对于给定的年份 y，要确定索是否为闰年，如何设计算法，画出其流程图。 例 2 一个三位数，各位数字互不相同，十位数字比个位、百位数字之和还要大，且十位数字、百位数字不是素数。设计一种算法，找 出所有符合条件的三位数，要求画出流程图。 开始 输入 A、 B、 C、 x0、 y0 z1=Ax0+By0+C z2=A2+B2 21z |z|d输出 d 结束 例 3 已知算法：（ 1）指出其功能（用算式表示），（ 2）将该算法用流

4、程图来描述之。 S1 输入 X； S2 若 X0 float total=0; for(i=0;i=11;j+) /*完成出售四次的操作 */ if(x+1)%(j+1)=0) /*若满足整除条件则进行实际的出售操作 */ x-=(x+1)/(j+1); else x=0;break; /*否则停止计算过程 */ if(j=5 /*输出结果 * / n=1; /*控制退出试探过程 */ *运行结果 There are 59 fishes at first. 小结 日本著名数学游戏专家中村义作教授提出这样一个问题：父亲将 2520 个桔子分给六个儿子。分完后父亲说： “老大将分给你的桔子的 1/

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

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

7、筐数等于第一个人的满筐数；第二个人的半筐数大于等于第一个人的半筐数。 三、 程序与程序注释 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;j3*/ a10=j; if(a20=7-j-a00)3)continue; /*第三个人满筐数不能 3*/ if(a20=前一个人，以排除重复情况 */ for(k=1;k1898;j-) /*从最大的素数开始向 1898 搜索 */ for(i=0;nu

8、mberj-numberi1898;i+); /*循环查找满足条件的素数 */ if(numberj-numberi=1898) /*若两个素数的差为 1898，则输出 */ printf(“(%d).%3d,.,%dn“,+count,numberi,numberj); int fflag(int i) int j; if(i4 Print s 小结 理解递推算法的结构美。 第 13 课 谁是窃贼 学习目标 逻辑判断问题的语言描述及问题分析 一、问题描述 公安人员审问四名窃贼嫌疑犯。已知，这四人当中仅有一名是窃贼，还知道这四人中每人要么是诚实的，要么总是说谎的。在回答公安人员的问题中： 甲说

9、： “乙没有偷，是丁偷的。 ” 乙说： “我没有偷，是丙便的。 ” 丙说： “甲没有偷，是乙偷的。 ” 丁说： “我没有偷。 ” 请根据这四人的答话判断谁是盗窃者。 二、 问题分析与算法设计 假设 A、 B、 C、 D 分别代表四个人，变量的值为 1 代表该人是窃贱。 由题目已知：四人中仅有一名是窃贱，且这四个人中的每个人要么说真话，要么说假话，而由于甲、乙、丙三人都说了两句话： “X没偷， X 偷了 ”，故不论该人是否说谎，他提到的两人中必有一人是小偷。故在列条件表达式时，可以不关心谁说谎，谁说实话。这样，可以列出下列条件表达式： 甲说： ”乙没有偷，是丁偷的。 ” B+D=1 乙说： “我

10、没 有偷，是丙偷有。 ” 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 表示窃贱，其余为 0*/ if(j=i)aj=1; else aj=0; if(a3+a1=1 /*成立 */ for(j=0;j=3;j+) /*输出计算结果 */ if(aj)printf(“%c.“,j+A

11、); printf(“n“); *运行结果 The thief is B. (乙为窃贱。 ) 小结 理解逻辑判断问题的语言描述的关键及枚举算法的应用。 第 14 课 黑与白 学习目标 学习枚举算法在逻辑判断中的应用。 一、问题描述 有 A、 B、 C、 D、 E 五人，每人额头上都帖了一张黑或白的纸 。五人对坐，每人都可以看到其它人额头上的纸的颜色。五人相互观察后， A 说： “我看见有三人额头上帖的是白纸，一人额头上帖的是黑纸。 ” B 说： “我看见其它四人额头上帖的都是黑纸。 ” C 说： “我看见一人额头上帖的是白纸，其它三人额头上帖的是黑纸。 ” D 说： “我看见四人额头上帖的都是

12、白纸。 ” E 什么也没说。 现在已知额头上帖黑纸的人说的都是谎话，额头帖白纸的人说的都是实话。问这五人谁的额头是帖白纸，谁的额头是帖黑纸？ 二、 问题分析与算法设计 假如变量 A、 B、 C、 D、 E 表示每个人额头上所帖纸的颜色， 0 代表是黑色， 1 代表是白色。根据题目中 A、 B、 C、 D 四人所说的话可以总结出下列关系： A 说： a 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 pr

13、intf(“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 forehead.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?

14、“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 of white paper on his forehead. (白 ) D is pasted a paper of black paper on his forehead. (黑 ) E is pasted a paper of white paper on his forehe

15、ad. (白 ) 小结 体会枚举算法在逻辑判断中的应用。 第 15 课 迷语博士的难题 (1) 学习目标 学习枚举算法在逻辑判断中的应用。 一、问题描述 诚实族和说谎族是来自两个荒岛的不同民族，诚实族的人永远说真话，而说谎族的人永远说假话。迷语博士是个聪明的人，他要来判断所遇到的人是来自哪个民族的。 迷语博士遇到三个人，知道他们可能是来自诚实族或说谎族的。为了调查这三个人是什么族的，博士分别问了他们的问题，这是他们的对话： 问第一个人： “你们是什么族？ ”，答： “我们之中有两个来自诚实族。 ”第二个人说： “不要胡说，我们三个人中只有一个是诚实族的。 ”第三个人听了第二个人的话后说： “对

16、，就 是只有一个诚实族的。 ” 请根据他的回答判断他们分别是哪个族的。 二、 问题分析与算法设计 假设这三个人分别为 A、 B、 C，若说谎其值为 0，若诚实，其值为 1。根据题目中三个人的话可分别列出： 第一个人： a for(a=0;a=1;a+) /*穷举每个人是说谎还是诚实的全部情况 */ for(b=0;b=1;b+) /*说谎： 0 诚实： 1*/ for(c=0;c=1;c+) if(a /*输出判断结果 */ printf(“B is a %s.n“,b?“honest“:“lier“); printf(“C is a %s.n“,c?“honest“:“lier“); *运行

17、结果 A is a lier (说谎族 ) B is a lier (说谎族 ) C is a lier (说谎族 ) 小结 迷语博士遇到四个人，知道他们可能是来自诚实族和说谎族的。为了调查这四个人是什么族的，博士照例进行询问： ”你们是 什么族的？ “ 第一人说： ”我们四人全都是说谎族的。 “ 第二人说： ”我们之中只有一人是说谎族的。 “ 第三人说： ”我们四人中有两个是说谎族的。 “ 第四人说： ”我是诚实族的。 “ 问自称是 “诚实族 ”的第四个人是否真是诚实族的？ (答案：第四个人是诚实族的。 ) 第 16 课 迷语博士的难题 (2) 学习目标 学习枚举算法在逻辑判断中的应用。 一

18、、问题描述 两面族是荒岛上的一个新民族，他们的特点是说话真一句假一句且真假交替。如果第一句为真，则第二句是假的；如果第一句为假 的，则第二句就是真的，但是第一句是真是假没有规律。 迷语博士遇到三个人，知道他们分别来自三个不同的民族：诚实族、说谎族和两面族。三人并肩站在博士前面。 博士问左边的人： “中间的人是什么族的？ ”，左边的人回答： “诚实族的 ”。 博士问中间的人： “你是什么族的？ ”，中间的人回答： “两面族的 ”。 博士问右边的人： “中间的人究竟是什么族的？ ”，右边的人回答： “说谎族的 ”。 请问：这三个人都是哪个民族的？ 二、 问题分析与算法设计 这个问题是两面族问题中最

19、基本的问题，它比前 面只有诚实族和说谎族的问题要复杂。解题时要使用变量将这三个民族分别表示出来。 令：变量 A=1 表示：左边的人是诚实族的 (用 C 语言表示为 A)； 变量 B=1 表示：中间的人是诚实族的 (用 C 语言表示为 B)； 变量 C=1 表示：右边的人是诚实族的 (用 C 语言表示为 C)； 变量 AA=1 表示：左边的人是两面族的 (用 C 语言表示为 AA)； 变量 BB=1 表示：中间的人是两面族的 (用 C 语言表示为 BB)； 变量 CC=1 表示：右边的人是两面族的 (用 C 语 言表示为 CC)； 则左边的人是说谎族可以表示为： A!=1 且 AA!=1 (不是

20、诚实族和两面族的人 ) 用 C 语言表示为： !A for(a=0;a=1;a+) /*穷举全部情况 */ for(b=0;b=1;b+) for(c=0;c=1;c+) for(aa=0;aa=1;aa+) for(bb=0;bb=1;bb+) for(cc=0;cc=1;cc+) if(a+aa!=2 printf(“The man stand on left is a %s.n“, bb?“double-dealer“:(b?“honest“:“lier“); printf(“The man stand on left is a %s.n“, cc?“double-dealer“:(c?

21、“honest“:“lier“); /*输出最终的推理结果 */ *运行结果 The man stand on left is a double-dealer. (左边的人是 两面族的 ) The man stand on center is a lier. (中间的人是说谎族的 ) The man stand on right is a honest. (右边的人是诚实族的 ) 小结 迷语博士遇到三个人，便问第一个人： “你是什么族的？ ”，回答： “诚实族的。 ”问第二个人： “你是什么族的？ ”，答： “说谎族的。 ”博士又问第二个人： “第一个人真的是诚实族的吗？ ”，答： “是的。

22、”问第三个人： “你是什么族的？ ”，答： “诚实族的。 ”博士又问第三个人： “第一个人是什么族的？ ”，答： “两面族的。 ” 请判断这个人到底是哪个民族的？ (答案：第一个人是诚实族的，第二个人是两面族的，第三人是说谎族。 ) 第 17 课 哪个大夫哪天值班 学习目标 学习枚举算法在逻辑判断中的应用。 一、问题描述 医院有 A、 B、 C、 D、 E、 F、 G 七位大夫，在一星期内 (星期一至星期天 )每人要轮流值班一天。现在已知： A 大夫比 C 大夫晚一天值班； D 大夫比 E 大夫晚二天值班； B 大夫比 G 大 夫早三天值班； F 大夫的值班日在 B 和 C 大夫的中间，且是星

23、期四； 请确定每天究竟是哪位大夫值班？ 二、 问题分析与算法设计 由题目可推出如下已知条件： *F 是星期四值班； *B 值班的日期在星期一至星期三，且三天后是 G 值班； *C 值班的日期在星期五至星期六，且一天后是 A 值班； *E 两天后是 D 值班； E 值班的日期只能在星期一至星期三； 在编程时用数组元素的下标 1 到 7 表示星期一到星期天，用数组元素的值分别表示 AF七 位大夫。 三、 程序与程序注释 int a8; char *day=“,“MONDAY“,“TUESDAY“,“WEDNESDAY“,“THURSDAYT“, “FRIDAY“,“SATUDAY“,“SUNDAY

24、“; /*建 立星期表 */ void main() int i,j,t; a4=6; /*星期四是 F 值班 */ for(i=1;i=3;i+) ai=2; /*假设 B 值班的日期 */ if(!ai+3) ai+3=7; /*若三天后无人值班则安排 G 值班 */ else ai=0;continue; /*否则 B 值班的日期不断对 */ for(t=1;t=3;t+) /*假设 E 值班的时间 */ if(!at) at=5; /*若当天无人值 班则安排 E 值班 */ else continue; if(!at+2) at+2=4; /*若 E 值班两天后无人值班则应为 D*/

25、else at=0;continue; /*否则 E 值班的日期不对 */ for(j=5;j7;j+) if(!aj) aj=3; /*若当天无人值班，则安排 C 值班 */ else continue; if(!aj+1) aj+1=1; /*C 之后一天无人值班则应当是 A 值班 */ else aj=0;continue; /*否则 A 值班日期不对 */ for(i=1;i=7;i+) /*安排完毕，输出结果 */ printf(“Doctor %c is on duty %s.n“,A+ai-1,dayi); exit(0); *运行结果 Doctor E is on duty M

26、ONDAY. (星期一： E) Doctor B is on duty TUESDAY. (星期二： B) Doctor D is on duty WEDNESDAY. (星期三： D) Doctor F is on duty THUESDAY. (星期四： F) Doctor G is on duty FRIDAY. (星期五： G) Doctor C is on duty SATURDAY. (星期六： C) Doctor A is on duty SUNDAY. (星期日： A) 小结 在本题的求解过程中，我们只考虑了一星期之内的情况，没有考虑跨周的情况。对于 “B大夫比 G 大夫早三天值班的 ”条件只是简单的认为是在同一周内早三天。若考虑跨周的情况就可能出现： B 大夫星期一值班，而 G 大夫是上周的星期五。同样，对 “F大夫的值班日在B 和 C 大夫的中间 ”这个条件，也可以扩展为： “只要 F 大夫的值班日在 B 和 C 大夫的中间