找回密码
 欢迎注册
查看: 13800|回复: 8

[提问] 幸运儿

[复制链接]
发表于 2009-6-13 21:23:38 | 显示全部楼层 |阅读模式

马上注册,结交更多好友,享用更多功能,让你轻松玩转社区。

您需要 登录 才可以下载或查看,没有账号?欢迎注册

×
有学号为1--n的n个同学,依次排成一个圆,从1号开始进行1-2-3-1-2-3...循环报数,报到
3的同学出列,问:最后剩下的一个人是几号同学?

如果进行1-2-3-...-m-1-2-...-m-1-...循环报数,结果又如何?
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2009-6-17 18:15:54 | 显示全部楼层
约瑟夫环
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2009-6-17 18:24:44 | 显示全部楼层
Excel中列个自定义函数即可:
  1. Function winner(ByVal n As Long, Optional ByVal m As Long = 3) As Long
  2. Dim i As Long, w As Long
  3. For i = 2 To n
  4. w = (w + m) Mod i
  5. Next
  6. winner = w + 1
  7. End Function

  8. Sub Macro1()
  9. MsgBox winner(10000000, 3)
  10. End Sub
复制代码
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2009-6-18 11:30:22 | 显示全部楼层
考虑了该问题后,如果研究出列数构成的序列,则此问题可以看成对某个自然数序列做以某种变换,得到一个新的序列。若在此序列的基础之上,施加同样的变换,则又得到另一个新的序列,反复使用该变换,则可最终得到一个与原序列完全相同的序列。下面举一例说明(n =7,m=3) 。
1 2 3 4 5 6 7
3 6 2 7 5 1 4
2 1 6 4 5 3 7
6 3 1 7 5 2 4  
1 2 3 4 5 6 7
如果竖着看,即每一列则构成一个循环群(暂且就叫做群吧,因为我对这一概念不是很了解),它们分别是{5}  {4,7}  {1,3,2,6}
下面给出m=2到11的变换后的首序列,及该循环序列所构成的集合。
S(7,2)=(2,4,6,1,5,3,7)  {7}   {3,6}  {1,2,4}  但该序列的循环次数是6。
S(7,4)=(4,1,6,5,7,3,2)    {3,6}    {1,4,5,7,2}        但该序列的循环次数是10
S(7,5)=(5,3,2,4,7,1,6)    {4}   {2,3}    {1,5,7,6}
S(7,6)=(6,5,7,2,1,4,3)    {3,7}    {1,6,4,2,5}
S(7,7)=(7,1,3,6,2,4,5)     {3}  {4,6}  {1,7,5,2}
S(7,8)=(1,3,6,5,2,7,4)     {1}  {3,6,7,4,5,2}
S(7,9)=(2,5,3,4,1,6,7)     {3}  {4}  {6}  {7}   {1,2,5}
S(7,10)=(3,7,6,2,4,5,1)   {1,3,6,5,4,2,7}
S(7,11)=(4,2,3,7,5,1,6)    {2} {3} {5} {1,4,7,6}
由以上简单的分析可以看出,集合中的每一种组合都对应着数n的一种加法拆分法 。
希望编程爱好者编个程序对以上问题做出更深入的研究。不知对该问的研究可用在哪一方面上,加密,解密能用的着吗?
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2009-6-18 11:42:00 | 显示全部楼层
4# wsc810
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2009-6-18 11:44:10 | 显示全部楼层
你说的这个和上面的问题没啥关系吧。
每个置换都可以按你上面的去做,基元集合的元素形成不同的轨道,这是群论基础的内容
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2009-6-18 13:12:19 | 显示全部楼层
只找到递推公式
A(2)=2
A(k+1)=A(k)+3 或 A(k)+3-k(当A(k)+3大于k时)
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2009-6-19 16:52:47 | 显示全部楼层
本帖最后由 bolizhou 于 2009-6-19 17:03 编辑

3#楼的程序好,但剩下不会只有1人啊?另外一个人呢,号码是多少,怎么编?
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2009-6-19 21:55:14 | 显示全部楼层
Excel中列个自定义函数即可:Function winner(ByVal n As Long, Optional ByVal m As Long = 3) As Long
Dim i As Long, w As Long
For i = 2 To n
w = (w + m) Mod i
Next
winner = w + 1
End Function

Su ...
northwolves 发表于 2009-6-17 18:24

两人报数的约瑟夫环跟二进制有巧妙的联系,不知道多人报数的有没有类似的关系?
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
您需要登录后才可以回帖 登录 | 欢迎注册

本版积分规则

小黑屋|手机版|数学研发网 ( 苏ICP备07505100号 )

GMT+8, 2024-3-29 18:25 , Processed in 0.046848 second(s), 16 queries .

Powered by Discuz! X3.5

© 2001-2024 Discuz! Team.

快速回复 返回顶部 返回列表