第3章问题求解入门篇.ppt

《第3章问题求解入门篇.ppt》由会员分享，可在线阅读，更多相关《第3章问题求解入门篇.ppt（10页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,问题求解 入门,问题求解 入门,1.【,NOIP1998,】,某班有,50,名学生，每位学生发一张调查卡，上写,a,b,c,三本书的书名，将读过的书打,，结果统计数字如下：只读,a,者,8,人；只读,b,者,4,人；只读,c,者,3,人；全部读过的有,2,人；读过,a,，,b,两本书的有,4,人；读过,a,，,c,两本书的有,2,人；读过,b,，,c,两本书的有,3,人。,读过,a,的人数是,人；,一本书也没读过的人数是,人。,8,30,12,问题求解 入门,2.【,NOIP1999,】,根据,Nocomach

2、ns,定理，任何一个正整数,n,的立方一定可以表示成,n,个连续的奇数的和。例如：,1,3,=1,2,3,=3+5,3,3,=7+9+11,4,3,=13+15+17+19,在这里，若将每一个式中的最小奇数称为,X,，那么当给出,n,之后，请写出,X,与,n,的关系表达式。,【,分析,】,可以通过观察，,n,的平方正好是右侧加法式子的中位数，这个值正好和最小奇数差了,n-1,。,X=n,2,-n+1,问题求解 入门,【,分析,】,因为第一个到达出口的是,3,号车厢，所以可以肯定，,1,号车厢在栈底，,2,号车厢在栈顶，之后所有的可能序列有,9,种，分别是,2145,、,2154,、,2415,

3、、,2451,、,2541,、,4215,、,4251,、,4521,、,5421,。,4.,【,NOIP2002,】,如下图,有一个无穷大的的栈,S,在栈的右边排列着,1,2,3,4,5,共五个车厢。其中每个车厢可以向左行走,也可以进入栈,S,让后面的车厢通过。现已知第一个到达出口的是,3,号车厢，请写出所有可能的到达出口的车厢排列总数,(,不必给出每种排列,),。,问题求解 入门,5.【,NOIP2002,】,将,N,个红球和,M,个黄球排成一行。例如,:N=2,M=3,可得到以下,10,种排法,:,红红黄黄黄 红黄红黄黄 红黄黄红黄 红黄黄黄红 黄红红黄黄,黄红黄红黄 黄黄黄红红 黄红黄

4、黄红,黄黄红红黄 黄黄红黄红,问题,:,当,N=4,，,M=3,时有多少种不同排法,?,【,分析,】,这是一个可重复排列的问题，求解方法为,(4+3)!/4!/3!=35,问题求解 入门,3,.,【,NOIP2000,】,已知，按中序遍历二叉树的结果为：,abc,问：有多少种不同形态的二叉树可以得到这一遍历结果，并画出这些二叉树。,共五种。,问题求解 入门,6.【,NOIP2004,】75,名儿童到游乐场去玩。他们可以骑旋转木马，坐滑行铁道，乘宇宙飞船。已知其中,20,人这三种东西都玩过，,55,人至少玩过其中的两种。若每样乘坐一次的费用是,5,元，游乐场总共收入,700,，可知有,名儿童没有

5、玩过其中任何一种。,【,分析,】,集合的交并补。,3,种东西都玩过的共用去：,3*5*20=300(,元,),，,只玩过两种东西共用去：,2*5*(55-20)=350(,元,),，,那么：只玩过一种东西的人数为：,(700-300-350)/5=10(,人,),，,所以：什么也没有玩的人数为,75-55-10=10(,人,),。,10,问题求解 入门,7.【,NOIP2005,普及组,】,将数组,32,74,25,53,28,43,86,47,中的元素按从小到大的顺序排列，每次可以交换任意两个元素，最少需要交换次。,25,|74,32,53,28,43,86,47,25,28,|32,53,74,43,86,47,25,28,32,|53,74,43,86,47,25,28,32,43,|74,53,86,47,25,28,32,43,47,|53,86,74,25,28,32,43,47,53,|86,74,25,28,32,43,47,53,74,|,86,25,28,32,43,47,53,74,86|,谢谢,