问题求解 入门.

Presentation on theme: "问题求解 入门."— Presentation transcript:

1 问题求解 入门

2 问题求解 入门 1. 【NOIP1998】某班有50名学生，每位学生发一张调查卡，上写a, b, c三本书的书名，将读过的书打√，结果统计数字如下：只读a者8人；只读b者4人；只读c者3人；全部读过的有2人；读过a，b两本书的有4人；读过a，c两本书的有2人；读过b，c两本书的有3人。 读过a的人数是 人； 一本书也没读过的人数是 人。 12 30 8

3 问题求解 入门 2. 【NOIP1999】根据 Nocomachns 定理，任何一个正整数n的立方一定可以表示成n个连续的奇数的和。例如： 13 = 1 23 = 3 + 5 33 = 43 = 在这里，若将每一个式中的最小奇数称为X，那么当给出n之后，请写出X与n的关系表达式。 【分析】可以通过观察，n的平方正好是右侧加法式子的中位数，这个值正好和最小奇数差了 n-1 。 X=n2-n+1

4 问题求解 入门 4. 【NOIP2002】如下图,有一个无穷大的的栈S,在栈的右边排列着1,2,3,4,5共五个车厢。其中每个车厢可以向左行走,也可以进入栈S让后面的车厢通过。现已知第一个到达出口的是3号车厢，请写出所有可能的到达出口的车厢排列总数(不必给出每种排列)。 【分析】因为第一个到达出口的是3号车厢，所以可以肯定，1号车厢在栈底，2号车厢在栈顶，之后所有的可能序列有9种，分别是 2145 、2154 、2415 、2451 、2541 、4215 、4251 、4521 、5421。

5 【分析】这是一个可重复排列的问题，求解方法为 (4+3)! / 4! / 3! = 35
问题求解 入门 5. 【NOIP2002】将N个红球和M个黄球排成一行。例如:N=2,M=3可得到以下6种排法: 红红黄黄黄 红黄红黄黄 红黄黄红黄 黄红红黄黄 黄红黄红黄 黄黄黄红红 问题:当N=4，M=3时有多少种不同排法? 【分析】这是一个可重复排列的问题，求解方法为 (4+3)! / 4! / 3! = 35

6 3. 【NOIP2000】已知，按中序遍历二叉树的结果为：abc 问：有多少种不同形态的二叉树可以得到这一遍历结果，并画出这些二叉树。
问题求解 入门 3. 【NOIP2000】已知，按中序遍历二叉树的结果为：abc 问：有多少种不同形态的二叉树可以得到这一遍历结果，并画出这些二叉树。 共五种。

7 问题求解 入门 6. 【NOIP2004】75名儿童到游乐场去玩。他们可以骑旋转木马，坐滑行铁道，乘宇宙飞船。已知其中20人这三种东西都玩过，55人至少玩过其中的两种。若每样乘坐一次的费用是5元，游乐场总共收入700，可知有 名儿童没有玩过其中任何一种。 10 【分析】集合的交并补。 3种东西都玩过的共用去：3*5*20=300(元)， 只玩过两种东西共用去：2*5*(55-20)=350(元)， 那么：只玩过一种东西的人数为：( )/5=10(人)， 所以：什么也没有玩的人数为 =10(人)。

8 问题求解 入门 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 |

9 谢谢

10