【练习-005】批处理解约瑟夫环应用题
[color=blue]题目：
有二十九个女生（分别用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号。
[/color]
[[i] 本帖最后由 batman 于 2009-4-17 10:58 编辑 [/i]] Joseph loop
我打算直接复制我的上来，却发现没保存。
给新人如何~ 不知道这样是否正确?[code]@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)
)[/code] 楼上的朋友可再深入一下。
n个人报数，从编号为z的人开始数，数到m的人退出，求最后的是原来的几号。
nzm为用户输入的数字。
头都要炸了
[code]@echo offSetlocal 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 :again[/code] 这里面也有类似的题目
[url=http://bbs.bathome.net/viewthread.php?tid=850&extra=page%3D1]http://bbs.bathome.net/viewthread.php?tid=850&extra=page%3D1[/url][code]@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%
pause[/code] [quote]原帖由 [i]more[/i] 于 2008-7-30 20:25 发表 [url=http://bbs.bathome.net/redirect.php?goto=findpost&pid=6129&ptid=1280][img]http://bbs.bathome.net/images/common/back.gif[/img][/url]
不知道这样是否正确?@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 ... [/quote]
思路是好的，但代码不通用，因为for /f "tokens=*" 是有个极限值tokens=31的，
运行以下的代码就会明白：
[code]
@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
[/code]
可能大家会说这里tokens=1,2,4*是个循环，根本不涉及到最大tokens值的问题，
是的，本题是不会出现这个tokens最大值的问题，但如果将退出数增加到31以上呢？
如总人数为100，数到50的人退出，这样的代码将无法运行。
[quote]原帖由 [i]ieutk[/i] 于 2008-8-1 02:37 发表 [url=http://bbs.bathome.net/redirect.php?goto=findpost&pid=6220&ptid=1280][img]http://bbs.bathome.net/images/common/back.gif[/img][/url]
这里面也有类似的题目
[url=http://bbs.bathome.net/viewthread.php?tid=850&extra=page%3D1@echo]http://bbs.bathome.net/viewthread.php?tid=850&extra=page%3D1@echo[/url] off
setlocal enabledelayedexpansion
for /l %%a in (12 -1 1) do set "str= %%a !str!"
for /l %%a in (29 -1 13) ... [/quote]
代码已经够简洁了，但存在效率问题：每循环一次还要用for循环对变量str
进行一行判断，当然在总人数和退出数不大的情况下是没有问题的，当数量提
上去以后，这个判断循环数将是可观的，效率自会大打折扣。 ieutk 版主的代码够简洁，只是有个缺点，人数多了便OVER了，貌似变量所能支持的最大数是8186个字符。
[[i] 本帖最后由 pusofalse 于 2008-8-1 22:26 编辑 [/i]] for /f "tokens=1-31" %%a in (a.txt) do echo %%a....%%z
%%z之后要用什么表示？~ 26个都不够用呀 第一个有字符限制 第二个没字符限制 效率给限制了[code]@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!"[/code]
修改 : 当从最后一位 开始循环出错
[code]@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! 号
pause[/code]
[[i] 本帖最后由 terse 于 2008-8-5 20:59 编辑 [/i]] 今天翻旧贴无意中无看到了此题，才知道本人当时并未给出自己的解，现解答如下，
这是道经典的题目，大家都可以来练练手：[code]@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[/code]
[[i] 本帖最后由 batman 于 2009-4-17 11:00 编辑 [/i]] 借鉴了高级语言中链表的数据结构，构造环链表(只定义了创建和删除两个函数)。
没有针对顶楼的题目，算法根据更一般的Joseph描述：编号为1,2...,n的n个人按顺时针方向围坐一圈，每人持有一个密码(正整数)。一开始任选一个正整数作为开始报数值m,从第一个人开始按顺时针方向自1开始顺序报数，报到m时停止。报m的人出列，将他的密码作为新的m值，从他在顺时针方向的下一个人开始重新报数，如此循环，直至所有人出列。[code] @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 :eof[/code]没有对输入的数据检查，测试时注意查看有没有输错。 从1到x报数，凡报到x的人退出。
报到数的号我这里用0代替，然后继续从1开始报数，周而复始，计算所有号的和，当和为0时，那么最后一个被替代的号码就是要找的人了。当数字过大的时候运行的好慢，请高手改进。[code]@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>nul[/code] 其实此题不用去考虑从第几个人开始，可视为全部从一开始，到最后再转换就可以了，如：
n=6 m=5 l=1
视为：n=6 xm=1 ,xl=3
5-1=4
3+4-6=1
也就是说：只要n确定后，xm=1, 则 xl 是有公式可求的。
最后：
只要给出n,必能求xl,再转换为 l 就可以了。
应该有公式，大家解解看。 公式没找到，先搞个可以处理m和n输入的。
[code]@echo off&setlocal enabledelayedexpansion
:lp
set str=
set in=
(set /p in=输入总人数：
set /p m=从第几个开始：
if "!in!"=="%in%" goto :eof
for /l %%a in (1,1,!in!) do (call set str=!str!%%a ))
set str= !str!
set n=
:rep
for %%a in (!str!) do (set/a n+=1
if !n! equ 3 (set str=!str: %%a = !&set n=0)
)
echo "!str!"
if " !str: =! " neq "!str!" goto :rep
set/a l=(m+!str!+in-1)%%in,1/l>nul||set/a l=in
echo 共有%in%人一起游戏，从第%m%个开始，最后剩下第%l%个
goto :lp[/code] 呵呵，没有比下面更简单了吧, 是倒推出来的公式，但确实这个问题很难理解。
是借用前辈的分析结果。证验结果正确。[code]@echo off
set /p n= 参加游戏人数:
set /p k=从几号开始：
set /p m=报数:
set s=0
for /l %%a in (2,1,%n%) do set /a s=(s+m)%%%%a
set /a x=(s+k)%%n
if %x% equ 0 (set x=%n%)
echo 最后剩下是:%x%[/code]
[[i] 本帖最后由 inittab 于 2009-4-29 08:21 编辑 [/i]] 楼上厉害，我想了半天，都找不到公式所在，
不知以前有没有这个公式的。
还有点小问题，就是出现结果为0的错误，
为0时其实是x=n，稍加处理一下就可以了。
经典，加分！ 谢谢,确实没考虑到x=n情况. 已修正. 练练手：[code]@echo off
set /a x=13,y=29,z=3,m=0,n=0
setlocal enabledelayedexpansion
:o
for /l %%a in (!x!,1,!y!) do (
if not defined #%%a (
set /a m+=1
set /a l=m%%z
if !l!==0 (
set #%%a=false
set /a n+=1
if !n! == !y! echo %%a&goto :p
)
)
)
if !n! lss !y! set x=1&goto :o
:p
pause
goto :eof[/code] [code]
@echo off
setlocal enabledelayedexpansion
set start=13
set "numbers= "
for /l %%i in (1,1,30) do (
if !start! equ 31 ( set /a start=1 )
set numbers=!numbers!!start!
set /a start+=1
)
set /a n=1
:loop
if "%numbers:~4%" neq "" (
for %%i in (%numbers%) do (
if "!n!" equ "3" ( set "numbers=!numbers: %%i = !" & set /a n=1 )
set /a n+=1
)
goto :loop
)
echo %numbers: =%
[/code]
页:
[1]