小学奥数题求解算法的综合分析以及一种简单的通解算法
2004-12-09 16:02:08 下载试卷 标签：分析
关于那道小学奥数题求解算法的综合分析以及一种简单的通解算法
这几天强坛上关于那道小学奥数题大家进行了比较热烈的讨论，目前出现了几种解法。这几种解法中，有的给出了错误的结果；有的只能在特殊的情况下成立；有的则过于复杂，不易于理解。尽管各有缺陷，这些算法却各有其合理之处。本帖子将对这几种算法进行综合分析，并提出一种新的解法。这种解法相对比较简单，整个求解过程简洁明了，所用知识没有超出小学范围，易于理解。
为了不了解情况的网友阅读方便，首先将原题论述如下：
100个人回答五道试题，有81人答对第一题，91人答对第二题，85人答对第三题，79人答对第四题，74人答对第五题，答对三道题或三道题以上的人算及格，那么，在这100人中，至少有（ ）人及格。
请说出算法！
下面首先对几种已有的算法作出分析。
算法一
目前的几种算法中，一种流行的能得出本题正确结果的解法是求出满足答错题总数的最大人数。其基本思想是，假设答对的都答对了所有题（本题中是5道），这样，最少的人数就能得到所要求的总分；假设错题的人只错了满足要求的最少题（本题中是3道），这样，需要最多的人才能凑够满足要求的错题总人次。用数学算法表述如下：
5n+2(100-n)=81+91+85+79+74 => n=70
这种算法的思路是比较好理解的，但是其破绽也是很容易找出来的。上面这个表达式中的右端项显然只用到了答题人数的总和，而不管其具体分布情况。这说明这种解法并没有用到题目所给的所有信息，其所求得的结果是“在答对题总人次为410 的情况下的最低及格人数” ，而不是题目所给出的具体分布情况下的结果。因此，尽管这道题的结果是正确的，但其求解过程并不完全正确，因为在别的情况下，这样求解就可能给出错误解。如在本题的条件下，求答对2道题的最少人数、答对1道题的最少人数就不对了。
这种算法虽然不完全正确，但却是很有意义的，它的求下限值的方法将成为本帖子给出的新算法的一个基础。
曾给出这种算法的网友有[布威寺方丈]、[姜悠]、[强国导弹分子]等等。
算法二
另一种算法是Wyling网友提出来的，其求解过程如下：
假设共有m道题(这里为5：m=5)，每道题错x(i)人次（i=1,…m）,总共错sum(x(1),…x(m))人次，再假设每人至少错n道题(这里n=3)不及格，求最多有多少人不及格算法如下：
1． 求出最大值x=max(x(1),…x(m)) 及对应的题号no;
2． 求出除错最多那道题外的错误人次total= sum(x(1),…x(m))-x;
3． y=(int) (total/(n-1)) ;
4． 如果x<=y,则最多不及格人数emax=(int)( sum(x(1),…x(m)) / n);否则，x(no)=y;重复上述步骤（从1开始）。
这种算法考虑了答题人数的具体分布情况，可以求出一般情况下的通解。但是，解法的第4步的判断条件可能会导致过早结束求解。[谷中蕉]网友对此进行了改进，采用第归的方式，这样第四步的判断直到n=1时才开始回溯，这保证了求解对整个分布的判断。
然而，这个算法中用到了较多的计算机编程中常用的知识，并且，为什么可以这样做，Wyling网友讲得不是非常清楚，理解起来是比较困难的。[谷中蕉]网友在他的改进算法中，加入了自己的理解：
“ 算法的基本思路是，先从m道题目中排除答错人数最多的那道，然后看看剩下的m-1道题目中，答错至少n-1道题目的最大人数是多少。
如果m-1道题目中至少答错n-1道题的最大人数小于被排除的那道题目的答错人数，说明这种分布下，m道题目中至少答错n道题的最大人数就是m-1道题中至少答错n-1道题以上的最大人数。
如果大于等于，因为不管分布的算法得出的是最高的不及格人数的上限，所以，这种分布可以使用数组求和然后除以n的方法求得答案。”
这段理解对于本帖子体出的新算法非常重要。
算法三
还有一种算法是[周命维新]网友给出来的。 他的方法是：
“至少n个人及格，就是算最多100-n个人不及格，每道题不及格的人数是：26、21、19、15、9，要凑出三道题答错才能不及格，尽量考虑人数最多，这样先采用26、21、19，然后去除19人，剩下的7、2人都是错两题，再和15、9组合，去除7人，还剩2人还可以组合出错三道题的，最后得到28人，这样n=100-28=72人。”
这种方法考虑了答题人数的分布情况，但没有得到正确的答案。这种算法的错误是，在确定了一个组合中最多人不及格以后，将这个最多人从已有的人群中扣除，然后利用剩下的人继续组合出最多人数来，这在逻辑上是不合理的。因为在扣除最多的答对题时，剩下的人将是可能剩下的人数中最少的。由这个最少的人数再进行组合，得到的最大已经不是真正的最大数目了。所以这种算法所求得的最大不及格人数偏少。
还有一些其他网友提出的算法，这里不再进行详细叙述了。
本帖子给出的新算法
算法一给出了已知答错总题情况下，最多答错n道题的求解方法；算法二则提出：由算法一计算的结果必须满足其下一层（即去除最多答错题的人数，答错n-1道题）答题人数的分布。并依次循环第归，使得整个答题数的分布都能得以满足。
算法二的思想进一步可以阐述为：如果下一层的最大可能人数比上一层的最大可能人数大，则说明下一层能容纳上一层的最大分布人数，否则最大可能人数最多只能达到下一层的最大可能人数。这一阐述可以得出以下求解思想：求解结果是所有分布层中最大可能人数的最小的那个。基于这一思想，我们可以得到一个非常简明的算法：
1、 求出第n, n-1,…,1所有可能分布层的最大可能人数Xn，……，X1。（所谓第n分布层表示m道题中答错n道题的最多人数，第n-1分布层是将m道题中去除最大答错题后，剩下的m-1道题中答错n-1道题的最多情况，其它以此类推）
2、 找出n个可能最大人数中最小的那个，作为求解结果。即：Max_n=Min(X1,…,Xn)
现在我们利用这种算法求解那道奥数题以及其它一些情况。
首先求解原题。每道题的答错人数为（次序不重要）：26，21，19，15，9
第3分布层：答错3道题的最多人数为：（26+21+19+15+9）/3=30
第2分布层：答错2道题的最多人数为：（21+19+15+9）/2=32
第1分布层：答错1道题的最多人数为：（19+15+9）/1=43
Max_3=Min(30, 32, 43)=30。因此答案为：100-30=70。
如果现在求至少有多少人答对2道题，则按以上算法，计算如下（除不断的取整）：
第4分布层：答错4道题的最多人数为：（26+21+19+15+9）/4=22
第3分布层：答错3道题的最多人数为：（21+19+15+9）/3=21
第2分布层：答错2道题的最多人数为：（19+15+9）/2=21
第1分布层：答错1道题的最多人数为：（15+9）/1=24
Max_4=Min(22, 21, 21，24)=21。因此答案为：100-21=79。而按照算法1 的结果是78。
至少有多少人答对1道题呢？
第5分布层：答错5道题的最多人数为：（26+21+19+15+9）/5=18
第4分布层：答错4道题的最多人数为：（21+19+15+9）/4=16
第3分布层：答错3道题的最多人数为：（19+15+9）/3=14
第2分布层：答错2道题的最多人数为：（15+9）/2=12
第1分布层：答错1道题的最多人数为：（9）/1=9
Max_5=Min(18, 16, 14，12，9)=9。因此答案为：100-9=91。而按照算法1 的结果是82。
现在用本算法求解[姜悠]网友给出的人数分布情况。他认为“计算就麻烦一点了”，但采用本算法是一点也不麻烦的。
[姜悠]网友的人数分布情况为：5道题中每道题的答对人数分布为：69 79 82 85 95。问至少有多少人及格。
求解。每道题的答错人数为（次序不重要）：31，21，18，15，5
第3分布层：答错3道题的最多人数为：（31+21+18+15+5）/3=30
第2分布层：答错2道题的最多人数为：（21+18+15+5）/2=29
第1分布层：答错1道题的最多人数为：（18+15+5）/1=38
Max_3=Min(30, 29, 38)=29。因此答案为：100-29=71。跟[姜悠]网友的结果一样。不过我不知道他计算和判断的具体过程是怎样的，我想肯定是比较麻烦吧。
对于一些极端的特殊情况，本算法也是适用的。如有4道题100个人全答对，10个人答对了第5道题的情况，至少有多少人及格？
求解。每道题的答错人数为（次序不重要）：0，0，0，0，90
第3分布层：答错3道题的最多人数为：（0+0+0+0+90/3=30
第2分布层：答错2道题的最多人数为：（0+0+0+0）/2=0
第1分布层：答错1道题的最多人数为：（0+0+0）/1=0
Max_3=Min(30, 0, 0)=0。因此答案为：100-0=100。即大家全部及格。
关注奥数网官方微信 数学资料、数学真题、更有全国教育资讯
微信搜索“奥数网”或扫描二维码即可添加
