【练习-005】批处理解约瑟夫环应用题

batman

题目：
　　有二十九个女生（分别用1－29号来称呼）围成一圈玩报数游戏，规则是这样的：从1开始数数，当数到3的这个人就退出游戏，而她后面的人接着从1数。。。如此一直到最后剩下一个人，现在知道最初是从13号女生开始的游戏，问最后剩下的会是第几号女生？
要求：
　　1　用批处理解答
　　2　代码简洁高效
　　3　代码通用且不生成临时文件
加分原则：
　　以思路为重（如思路独特，请简要说明）
　　完全符合要求的加10分
－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－
　　已有两套解决方案，见3楼more和6楼ieutk版主的代码，但个人认为这两套方案均不完美（见本人的跟贴评述），期
待完美方案的出现，大家加油了！！！

注：约瑟夫问题
　　约瑟夫问题是个有名的问题：N个人围成一圈，从第一个开始报数，第M个将被杀掉，最后剩下一个，其余人都将被杀掉。例如N=6，M=5，被杀掉的人的序号为5，4，6，2，3。最后剩下1号。





[ 本帖最后由 batman 于 2009-4-17 10:58 编辑 ]

batman

原帖由 more 于 2008-7-30 20:25 发表
不知道这样是否正确?@echo off
set "str=13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 1 2 3 4 5 6 7 8 9 10 11 12"
:again
for /f "tokens=1,2,4*" %%a in ("%str%") do (
   if not "%%c"=="" (set "s ...

　　思路是好的，但代码不通用，因为for /f "tokens=*" 是有个极限值tokens=31的，
运行以下的代码就会明白：

@echo off
for /l %%i in (1,1,32) do call,set str=%%str%% a
for /f "tokens=31" %%i in ("%str%") do echo %%i
for /f "tokens=32" %%i in ("%str%") do echo %%i
pause>nul
复制代码

　　可能大家会说这里tokens=1,2,4*是个循环，根本不涉及到最大tokens值的问题，
是的，本题是不会出现这个tokens最大值的问题，但如果将退出数增加到31以上呢？
如总人数为100，数到50的人退出，这样的代码将无法运行。
　　

batman

原帖由 ieutk 于 2008-8-1 02:37 发表
这里面也有类似的题目

http://bbs.bathome.net/viewthread.php?tid=850&extra=page%3D1@echo off
setlocal enabledelayedexpansion
for /l %%a in (12 -1 1) do set "str= %%a !str!"
for /l %%a in (29 -1 13) ...

　　代码已经够简洁了，但存在效率问题：每循环一次还要用for循环对变量str
进行一行判断，当然在总人数和退出数不大的情况下是没有问题的，当数量提
上去以后，这个判断循环数将是可观的，效率自会大打折扣。

batman

今天翻旧贴无意中无看到了此题，才知道本人当时并未给出自己的解，现解答如下，
这是道经典的题目，大家都可以来练练手：

@echo off&setlocal enabledelayedexpansion
for /l %%a in (13,1,29) do set "str=!str! #%%a#"
for /l %%a in (1,1,12) do set "str=!str! #%%a#"
:lp
for %%a in (!str!) do (
     set /a n+=1
     if !n! equ 3 set "str=!str: %%a=!"&set /a n=0
)
for /f "tokens=2" %%a in ("%str%") do if "%%a" neq "" goto lp
echo 最后剩下的是%str:#=%号&pause>nul
复制代码

[ 本帖最后由 batman 于 2009-4-17 11:00 编辑 ]