【练习-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 编辑 ]

pusofalse

Joseph loop
我打算直接复制我的上来，却发现没保存。
给新人如何~

more

不知道这样是否正确?

@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 "str=%%c %%d %%a %%b"&goto :again) else (echo %%b&pause&exit)
)COPY

pusofalse

楼上的朋友可再深入一下。
n个人报数，从编号为z的人开始数，数到m的人退出，求最后的是原来的几号。
nzm为用户输入的数字。

more

@echo off
Setlocal Enabledelayedexpansion
:begin
cls&set "str="&set "var="&set "n=0"&set "m=0"
set /p men=请输入人数:
set /p bgn=请输入开始的编号:
set /a "nn=%bgn%-1"
set /p num=请输入循环数:
for /l %%a in (%bgn% 1 %men%) do (call set "str=%%str%% %%a")
for /l %%a in (1 1 %nn%) do (call set "str=%%str%% %%a")
if "%num%"=="1" (
   for %%a in (%str%) do (set "res=%%a")
   echo.&echo 最后剩下: !res!&echo.&pause&goto :begin
)
:again
for %%i in (%str%) do (
   set /a "m+=1"
   if "!m!"=="%num%" (set "%%i="&set "m=0") else (set "%%i=!m!")
)
for %%b in (%str%) do (if defined %%b (set "var=!var! %%b"))
for %%c in (%var%) do (set /a "n+=1")
if "%n%"=="1" (echo.&echo 最后剩下: %var%&echo.&pause&goto :begin)
set "n=0"&set "str=%var%"&set "var="&goto :againCOPY

ieutk

这里面也有类似的题目

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) do set "str= %%a !str!"
 
:main
set "ie=0"
for %%a in (%str%) do set /a ie+=1
if %ie% neq 1 (
        for %%a in (%str%) do (
                set /a num+=1
                if !num! equ 3 (
                        set "num=0"
                        set "str=!str: %%a =!
                    )
            )
        goto main
    )
echo %str%
pauseCOPY

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>nulCOPY

　　可能大家会说这里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
进行一行判断，当然在总人数和退出数不大的情况下是没有问题的，当数量提
上去以后，这个判断循环数将是可观的，效率自会大打折扣。

pusofalse

ieutk 版主的代码够简洁，只是有个缺点，人数多了便OVER了，貌似变量所能支持的最大数是8186个字符。

[ 本帖最后由 pusofalse 于 2008-8-1 22:26 编辑 ]

pusofalse

for /f "tokens=1-31" %%a in (a.txt) do echo %%a....%%z
%%z之后要用什么表示？~

ieutk

26个都不够用呀

terse

第一个有字符限制  第二个没字符限制 效率给限制了

@echo off&setlocal enabledelayedexpansion
set/a n=29,q=3,z=1
for /l %%i in (%z% 1 !n!) do (
    set/a m+=1,t=m%%q
    if !t! neq 0 set str=!str! %%i
)
set/a z-=1
for /l %%i in (!z! -1 1) do set str=%%i !str!
call :lp "!str!"
echo 最后剩下的是原来的 !str! 号
pause&exit
:lp
set p=&set "str="
for %%i in (%~1) do (
    set/a m+=1,t=m%%q
    if !t! neq 0 set str=!str! %%i&set/a p+=1
)
if !p! gtr 1 call:lp "!str!"COPY

修改 :  当从最后一位 开始循环出错

@echo off&setlocal enabledelayedexpansion
set/a n=29,s=29,q=3
if %n% equ %s% set p=1
:lp
for /l %%i in (!s! 1 !n!) do (
    if not defined %%i (
    set/a m+=1,t=m%%q
    if !t! equ 0 (set %%i=%%i)else set/a str=%%i,p+=1,n=%%i,s=1
)
)
if !p! gtr 1 set p=&goto lp
echo 最后剩下的是原来的 !str! 号
pauseCOPY

[ 本帖最后由 terse 于 2008-8-5 20:59 编辑 ]

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>nulCOPY

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

lhjoanna

借鉴了高级语言中链表的数据结构，构造环链表(只定义了创建和删除两个函数)。
没有针对顶楼的题目，算法根据更一般的Joseph描述：编号为1,2...,n的n个人按顺时针方向围坐一圈，每人持有一个密码(正整数)。一开始任选一个正整数作为开始报数值m,从第一个人开始按顺时针方向自1开始顺序报数，报到m时停止。报m的人出列，将他的密码作为新的m值，从他在顺时针方向的下一个人开始重新报数，如此循环，直至所有人出列。

 @echo off&setlocal enabledelayedexpansion
:begin
set /p "person_number=请输入人数："
set /p "begin_number=请输入开始报数值："
call :create
set /a cur=0,deleted=0,num=begin_number
set /p=出列顺序：<nul
for /l %%i in (1 1 !person_number!) do (
     call :delete !cur! !num!
     set /p= !deleted!<nul
)
pause>nul&echo.&echo.
goto begin
 
:create
set /p "passwords=请输入这!person_number!个人的密码："
set /a n=1
for %%i in (!passwords!) do set /a .!n!_code=%%i,.!n!_next=n+1,n+=1
set .!person_number!_next=1
set .0_next=1
goto :eof
 
:delete
set cur=%~1
for /l %%i in (2 1 %~2) do call set cur=%%.!cur!_next%%
set /a deleted=.!cur!_next
set /a .!cur!_next=.!deleted!_next
call set num=%%.!deleted!_code%%
goto :eofCOPY

没有对输入的数据检查，测试时注意查看有没有输错。

leaparde

从1到x报数，凡报到x的人退出。
报到数的号我这里用0代替，然后继续从1开始报数，周而复始，计算所有号的和，当和为0时，那么最后一个被替代的号码就是要找的人了。当数字过大的时候运行的好慢，请高手改进。

@echo off&setlocal enabledelayedexpansion&color 0a
title Number
echo 题目：有n个人围成一圈，顺序排号。从第一个人开始报数（从1到x报数），凡报到x的人退出圈子，问最后留下的是原来第几号的那位。
echo.
set /p var=请输入人数：
set /p var1=请输入报的数（x）：
echo.
set t=%time%
echo 十个人的序号为：
for /l %%i in (1,1,%var%) do set /a a%%i=%%i&set /p=%%i <nul
echo.
set /a m=0
:loop
set /a sum=0,n+=1,x+=1
if %x% gtr %var1% set /a x=1
:a
if %n% gtr %var% set /a n=1
if !a%n%! equ 0 set /a n+=1&goto a
if %x% equ %var1% (
   set s=!a%n%!
   set /a a%n%=0
)
for /l %%i in (1,1,%var%) do set /a sum+=!a%%i!
if %sum% neq 0 goto loop
echo.
echo 最后留下的人的号码是：%s%号
echo.
echo 程序开始时间：%t%
echo 程序结束时间：%time% 
pause>nulCOPY