旺旺网 - Powered by Discuz! Board

标题: [求助] 请教一道奥数题 [打印本页]

作者: wikky 时间: 2009-1-23 19:35 标题: 请教一道奥数题

[题目]把写有1、2、3、……、25的25张卡片按顺序叠齐，写有1的卡片放在最上面，进行这样的操作：把第一张卡片放到最下面，把第二张卡片扔掉；再把第一张卡片放到最下面，把第二张卡片扔掉……如此反复多次操作。
请问：当剩下最后一张卡片时，卡片上写的是几？
我用一次一次圈去“扔掉的卡片”上的数字的方法，得出“19”。
答案也确实是19。可是——
答案所用的方法，我不理解。特请教大师！

答案的步骤—— 25-16=9
            2X9+1=19。

我的疑惑是：  1、  为何用25-16？
               2、  为何又 X 2 ，再 +1 呢？

[ 本帖最后由 wikky 于 2009-1-23 19:38 编辑 ].

作者: 波妞 时间: 2009-1-23 21:12

16是2的四次方.

作者: 波妞 时间: 2009-1-23 21:15

第二部不明白，但我算过如果张数是33的话
答题步骤就是33-32=1,1*2+1=3,32是2的五次方.

作者: 波妞 时间: 2009-1-23 21:18

总之张数减去最接近的2的多次方的差，然后乘以2加上1
100张就是100-64=36,36*2+1=73, 64是2的六次方

[ 本帖最后由波妞于 2009-1-23 21:20 编辑 ].

作者: smartwxc 时间: 2009-1-24 09:09

本题是典型的约瑟夫问题，杀2留1（每次舍去2的倍数，但留除2余1的）。
Flavius Josephus 是公元一世纪的一个著名的历史学家。据传说，如果Josephus没有他的数学才能的话，也许他根本不会出名就死去（活不到他出名）。
在犹太人和古罗马人战争期间，他是陷入罗马人陷阱的41个犹太反抗者之一。反抗者宁死不做俘虏，他们决定围成一个圆圈，且环绕圆圈进行，杀死所有第三个剩下的人，直到没有一个人剩下。但是Josephus和一个未被告发的同谋者感到自杀是愚蠢的行为，所以他快速计算出在此恶性循环中他和他的朋友该站的地方。（即，最后剩下他们两个人未被杀死）Josephus要他的朋友先假装遵从，他將朋友与自己安排在第16個与第31個位置，于是逃过了这场死亡游戏。

解法
約瑟夫问题可用代数分析來求解，将这个问题扩大好了，假设现在您与m个朋友不幸参与了这个游戏，您要如何保护您的朋友？只要画两个圆圈就可以让自己与朋友免于死亡游戏，这两个圆内圈是排列顺序，而外圈是自杀顺序，如下图所示：(无法贴图抱歉）
使用程式来求解的话，只要将阵列当作环状来处理就可以了，在陈列中由计数1开始，每找到三的倍数区就填入一个计数，直接计数來求解的話，只要将阵列当作环状来处理就可以了，在阵列中由計数1开始，每找到三个无资料区就填入一个計数，直而計数达41为止，然后将阵列由索引1开始列出，就可以得知每个位置的自杀顺序，这就是約瑟夫排列，41个人报数3的約瑟夫排列如下所示：
14 36 1 38 15 2 24 30 3 16 34 4 25 17 5 40 31 6 18 26 7 37 19 8 35 27 9 20 32 10 41 21 11 28 39 12 22 33 13 29 23
由上可知，最后一个自杀的是在第31个位置，而倒数第二个自杀的要排在第16个位置，之前的人都死光了，所以他们也就不知道約瑟夫与他的朋友并没有遵守游戏规则了。
常见题详解例举：
例1：把1～999这999个自然数按顺时针的方向依次排列在一个圆圈上（如下图）。从1开始按顺时针的方向，保留1，擦去2；保留3，擦去4……这样每隔一个数擦去一个数，转圈擦下去。问：最后剩下一个数时，剩下的是哪个数？
解：如果有2^n个数，那么转一圈擦去一半，剩下2^n-1个数，起始数还是1；再转一圈擦去剩下的一半，又剩下2^n-2个数，起始数还是1……转了n圈后，就剩下一个数是1。
如果有2^n+d（d＜2n）个数，那么当擦去d个数时，剩下2^n个数，此时的第一个数是最后将剩下的数。因为擦去的第d个数是2d，所以2d+1就是最后剩下的整数。999=29+487，最后剩下的一个数是487×2+1=975。
例2：1000个学生坐成一圈，依次编号为1，2，3，…，1000。现在进行1，2报数：1号学生报1后立即离开，2号学生报2并留下，3号学生报1后立即离开，4号学生报2并留下……学生们依次交替报1或2，凡报1的学生立即离开，报2的学生留下，如此进行下去，直到最后还剩下一个人。问：这个学生的编号是几号？
解：这个问题与上面这题非常相似，只不过本例是报1的离开报2的留下，而上题相当于报1的留下报2的离开，由上题的结果可以推出本例的答案。本例中编号为1的学生离开后还剩999人，此时，如果原来报2的全部改报1并留下，原来报1的全部改报2并离开，那么，问题就与上面这题完全一样了。因为剩下999人时，第1人是2号，所以最后剩下的人的号码应比上题大1，是975＋1=976（号）。
为了加深理解，我们重新解这道题。
解：如果有2^n个人，那么报完第1圈后，剩下的是2的倍数号；报完第2圈后，剩下的是2^2的倍数号……报完第n圈后，剩下的是2^n的倍数号，此时，只剩下一人，是2^n号。
如果有（2^n＋d）（1≤d＜2n）人，那么当有d人退出圈子后还剩下2^n人。因为下一个该退出去的是（2d＋1）号，所以此时的第（2d＋1）号相当于2^n人时的第1号，而2d号相当于2^n人时的第2^n号，所以最后剩下的是第2d号。由1000=29＋488知，最后剩下的学生的编号是488×2=976（号）。.

作者: wikky 时间: 2009-1-24 10:48 标题: 回复 4#波妞的帖子

感谢大师!
类似的题我会解了,谢谢!

作者: wikky 时间: 2009-1-24 10:50 标题: 回复 5#smartwxc 的帖子

感谢大师!
从理论上帮我释疑解惑,非常感谢!

我已下载了,春节期间消化消化。.

作者: greenjyz 时间: 2009-1-24 15:01 标题: 回复 5#smartwxc 的帖子

妙哉！收藏了！.

作者: wikky 时间: 2009-1-24 20:56 标题: 回复 5#smartwxc 的帖子

今天反复学习了您的讲解,收益很大。
现在“取1舍1 ”的题目，如您最后列举的2个例子，我已经理解了。用代数的方法“减去最接近的2的多次方的差，然后乘以2加上1”可以解出来。

可是——

《約瑟夫问题》是“取2舍1”。我单独用一次一次圈去“舍1”的方法，得出“第16”和“第31”分别是最后2个“幸存者”。
但：如果不是41人，而是410人、999人中“取2舍1”，怎么算呢？
有没有代数的式子可以迅速地解出来呢？
类似地，如果是999人中“取3舍1”、“取4舍1”、或者“取3舍2”呢？

欢迎光临旺旺网 (http://ww123.net/)