Board logo

标题: 【练习-005】批处理解约瑟夫环应用题 [打印本页]

作者: batman    时间: 2008-7-30 15:42     标题: 【练习-005】批处理解约瑟夫环应用题


题目:
  有二十九个女生(分别用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    时间: 2008-7-30 19:58

Joseph loop
我打算直接复制我的上来,却发现没保存。
给新人如何~
作者: more    时间: 2008-7-30 20:25

不知道这样是否正确?
  1. @echo off
  2. 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"
  3. :again
  4. for /f "tokens=1,2,4*" %%a in ("%str%") do (
  5.    if not "%%c"=="" (set "str=%%c %%d %%a %%b"&goto :again) else (echo %%b&pause&exit)
  6. )
复制代码

作者: pusofalse    时间: 2008-7-30 21:34

楼上的朋友可再深入一下。
n个人报数,从编号为z的人开始数,数到m的人退出,求最后的是原来的几号。
nzm为用户输入的数字。
作者: more    时间: 2008-7-31 12:28     标题: 头都要炸了

  1. @echo off
  2. Setlocal Enabledelayedexpansion
  3. :begin
  4. cls&set "str="&set "var="&set "n=0"&set "m=0"
  5. set /p men=请输入人数:
  6. set /p bgn=请输入开始的编号:
  7. set /a "nn=%bgn%-1"
  8. set /p num=请输入循环数:
  9. for /l %%a in (%bgn% 1 %men%) do (call set "str=%%str%% %%a")
  10. for /l %%a in (1 1 %nn%) do (call set "str=%%str%% %%a")
  11. if "%num%"=="1" (
  12.    for %%a in (%str%) do (set "res=%%a")
  13.    echo.&echo 最后剩下: !res!&echo.&pause&goto :begin
  14. )
  15. :again
  16. for %%i in (%str%) do (
  17.    set /a "m+=1"
  18.    if "!m!"=="%num%" (set "%%i="&set "m=0") else (set "%%i=!m!")
  19. )
  20. for %%b in (%str%) do (if defined %%b (set "var=!var! %%b"))
  21. for %%c in (%var%) do (set /a "n+=1")
  22. if "%n%"=="1" (echo.&echo 最后剩下: %var%&echo.&pause&goto :begin)
  23. set "n=0"&set "str=%var%"&set "var="&goto :again
复制代码

作者: ieutk    时间: 2008-8-1 02:37

这里面也有类似的题目

http://bbs.bathome.net/viewthread.php?tid=850&extra=page%3D1
  1. @echo off
  2. setlocal enabledelayedexpansion
  3. for /l %%a in (12 -1 1) do set "str= %%a !str!"
  4. for /l %%a in (29 -1 13) do set "str= %%a !str!"
  5. :main
  6. set "ie=0"
  7. for %%a in (%str%) do set /a ie+=1
  8. if %ie% neq 1 (
  9.         for %%a in (%str%) do (
  10.                 set /a num+=1
  11.                 if !num! equ 3 (
  12.                         set "num=0"
  13.                         set "str=!str: %%a =!
  14.                     )
  15.             )
  16.         goto main
  17.     )
  18. echo %str%
  19. pause
复制代码

作者: batman    时间: 2008-8-1 08:08

原帖由 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的,
运行以下的代码就会明白:
  1. @echo off
  2. for /l %%i in (1,1,32) do call,set str=%%str%% a
  3. for /f "tokens=31" %%i in ("%str%") do echo %%i
  4. for /f "tokens=32" %%i in ("%str%") do echo %%i
  5. pause>nul
复制代码

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

原帖由 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    时间: 2008-8-1 10:58

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

[ 本帖最后由 pusofalse 于 2008-8-1 22:26 编辑 ]
作者: pusofalse    时间: 2008-8-2 05:28

for /f "tokens=1-31" %%a in (a.txt) do echo %%a....%%z
%%z之后要用什么表示?~
作者: ieutk    时间: 2008-8-2 07:54

26个都不够用呀
作者: terse    时间: 2008-8-5 20:28

第一个有字符限制  第二个没字符限制 效率给限制了
  1. @echo off&setlocal enabledelayedexpansion
  2. set/a n=29,q=3,z=1
  3. for /l %%i in (%z% 1 !n!) do (
  4.     set/a m+=1,t=m%%q
  5.     if !t! neq 0 set str=!str! %%i
  6. )
  7. set/a z-=1
  8. for /l %%i in (!z! -1 1) do set str=%%i !str!
  9. call :lp "!str!"
  10. echo 最后剩下的是原来的 !str! 号
  11. pause&exit
  12. :lp
  13. set p=&set "str="
  14. for %%i in (%~1) do (
  15.     set/a m+=1,t=m%%q
  16.     if !t! neq 0 set str=!str! %%i&set/a p+=1
  17. )
  18. if !p! gtr 1 call:lp "!str!"
复制代码

修改 :  当从最后一位 开始循环出错
  1. @echo off&setlocal enabledelayedexpansion
  2. set/a n=29,s=29,q=3
  3. if %n% equ %s% set p=1
  4. :lp
  5. for /l %%i in (!s! 1 !n!) do (
  6.     if not defined %%i (
  7.     set/a m+=1,t=m%%q
  8.     if !t! equ 0 (set %%i=%%i)else set/a str=%%i,p+=1,n=%%i,s=1
  9. )
  10. )
  11. if !p! gtr 1 set p=&goto lp
  12. echo 最后剩下的是原来的 !str! 号
  13. pause
复制代码

[ 本帖最后由 terse 于 2008-8-5 20:59 编辑 ]
作者: batman    时间: 2009-4-17 09:57

今天翻旧贴无意中无看到了此题,才知道本人当时并未给出自己的解,现解答如下,
这是道经典的题目,大家都可以来练练手:
  1. @echo off&setlocal enabledelayedexpansion
  2. for /l %%a in (13,1,29) do set "str=!str! #%%a#"
  3. for /l %%a in (1,1,12) do set "str=!str! #%%a#"
  4. :lp
  5. for %%a in (!str!) do (
  6.      set /a n+=1
  7.      if !n! equ 3 set "str=!str: %%a=!"&set /a n=0
  8. )
  9. for /f "tokens=2" %%a in ("%str%") do if "%%a" neq "" goto lp
  10. echo 最后剩下的是%str:#=%号&pause>nul
复制代码

[ 本帖最后由 batman 于 2009-4-17 11:00 编辑 ]
作者: lhjoanna    时间: 2009-4-17 12:22

借鉴了高级语言中链表的数据结构,构造环链表(只定义了创建和删除两个函数)。
没有针对顶楼的题目,算法根据更一般的Joseph描述:编号为1,2...,n的n个人按顺时针方向围坐一圈,每人持有一个密码(正整数)。一开始任选一个正整数作为开始报数值m,从第一个人开始按顺时针方向自1开始顺序报数,报到m时停止。报m的人出列,将他的密码作为新的m值,从他在顺时针方向的下一个人开始重新报数,如此循环,直至所有人出列。
  1. @echo off&setlocal enabledelayedexpansion
  2. :begin
  3. set /p "person_number=请输入人数:"
  4. set /p "begin_number=请输入开始报数值:"
  5. call :create
  6. set /a cur=0,deleted=0,num=begin_number
  7. set /p=出列顺序:<nul
  8. for /l %%i in (1 1 !person_number!) do (
  9.      call :delete !cur! !num!
  10.      set /p= !deleted!<nul
  11. )
  12. pause>nul&echo.&echo.
  13. goto begin
  14. :create
  15. set /p "passwords=请输入这!person_number!个人的密码:"
  16. set /a n=1
  17. for %%i in (!passwords!) do set /a .!n!_code=%%i,.!n!_next=n+1,n+=1
  18. set .!person_number!_next=1
  19. set .0_next=1
  20. goto :eof
  21. :delete
  22. set cur=%~1
  23. for /l %%i in (2 1 %~2) do call set cur=%%.!cur!_next%%
  24. set /a deleted=.!cur!_next
  25. set /a .!cur!_next=.!deleted!_next
  26. call set num=%%.!deleted!_code%%
  27. goto :eof
复制代码
没有对输入的数据检查,测试时注意查看有没有输错。
作者: leaparde    时间: 2009-4-17 13:43

从1到x报数,凡报到x的人退出。
报到数的号我这里用0代替,然后继续从1开始报数,周而复始,计算所有号的和,当和为0时,那么最后一个被替代的号码就是要找的人了。当数字过大的时候运行的好慢,请高手改进。
  1. @echo off&setlocal enabledelayedexpansion&color 0a
  2. title Number
  3. echo 题目:有n个人围成一圈,顺序排号。从第一个人开始报数(从1到x报数),凡报到x的人退出圈子,问最后留下的是原来第几号的那位。
  4. echo.
  5. set /p var=请输入人数:
  6. set /p var1=请输入报的数(x):
  7. echo.
  8. set t=%time%
  9. echo 十个人的序号为:
  10. for /l %%i in (1,1,%var%) do set /a a%%i=%%i&set /p=%%i <nul
  11. echo.
  12. set /a m=0
  13. :loop
  14. set /a sum=0,n+=1,x+=1
  15. if %x% gtr %var1% set /a x=1
  16. :a
  17. if %n% gtr %var% set /a n=1
  18. if !a%n%! equ 0 set /a n+=1&goto a
  19. if %x% equ %var1% (
  20.    set s=!a%n%!
  21.    set /a a%n%=0
  22. )
  23. for /l %%i in (1,1,%var%) do set /a sum+=!a%%i!
  24. if %sum% neq 0 goto loop
  25. echo.
  26. echo 最后留下的人的号码是:%s%号
  27. echo.
  28. echo 程序开始时间:%t%
  29. echo 程序结束时间:%time%
  30. pause>nul
复制代码

作者: netbenton    时间: 2009-4-28 13:51

其实此题不用去考虑从第几个人开始,可视为全部从一开始,到最后再转换就可以了,如:
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 就可以了。
应该有公式,大家解解看。
作者: netbenton    时间: 2009-4-28 21:42

公式没找到,先搞个可以处理m和n输入的。
  1. @echo off&setlocal enabledelayedexpansion
  2. :lp
  3. set str=
  4. set in=
  5. (set /p in=输入总人数:
  6. set /p m=从第几个开始:
  7. if "!in!"=="%in%" goto :eof
  8. for /l %%a in (1,1,!in!) do (call set str=!str!%%a ))
  9. set str= !str!
  10. set n=
  11. :rep
  12. for %%a in (!str!) do (set/a n+=1
  13.         if !n! equ 3 (set str=!str: %%a = !&set n=0)
  14. )
  15. echo "!str!"
  16. if " !str: =! " neq "!str!" goto :rep
  17. set/a l=(m+!str!+in-1)%%in,1/l>nul||set/a l=in
  18. echo 共有%in%人一起游戏,从第%m%个开始,最后剩下第%l%个
  19. goto :lp
复制代码

作者: inittab    时间: 2009-4-28 22:17

呵呵,没有比下面更简单了吧, 是倒推出来的公式,但确实这个问题很难理解。
是借用前辈的分析结果。证验结果正确。
  1. @echo off
  2. set /p n= 参加游戏人数:
  3. set /p k=从几号开始:
  4. set /p m=报数:
  5. set s=0
  6. for /l %%a in (2,1,%n%) do set /a s=(s+m)%%%%a
  7. set /a x=(s+k)%%n
  8. if %x% equ 0 (set x=%n%)
  9. echo 最后剩下是:%x%
复制代码

[ 本帖最后由 inittab 于 2009-4-29 08:21 编辑 ]
作者: netbenton    时间: 2009-4-29 07:39

楼上厉害,我想了半天,都找不到公式所在,
不知以前有没有这个公式的。

还有点小问题,就是出现结果为0的错误,
为0时其实是x=n,稍加处理一下就可以了。
经典,加分!
作者: inittab    时间: 2009-4-29 08:23

谢谢,确实没考虑到x=n情况. 已修正.
作者: qixiaobin0715    时间: 2021-3-17 09:25

练练手:
  1. @echo off
  2. set /a x=13,y=29,z=3,m=0,n=0
  3. setlocal enabledelayedexpansion
  4. :o
  5. for /l %%a in (!x!,1,!y!) do (
  6.     if not defined #%%a (
  7.         set /a m+=1
  8.         set /a l=m%%z
  9.         if !l!==0 (
  10.             set #%%a=false
  11.             set /a n+=1
  12.             if !n! == !y! echo %%a&goto :p
  13.         )
  14.     )
  15. )
  16. if !n! lss !y! set x=1&goto :o
  17. :p
  18. pause
  19. goto :eof
复制代码

作者: lengmoke    时间: 2021-11-14 16:31

  1. @echo off
  2. setlocal enabledelayedexpansion
  3. set start=13
  4. set "numbers= "
  5. for /l %%i in (1,1,30) do (
  6.     if !start! equ 31 ( set /a start=1 )
  7.     set numbers=!numbers!!start!
  8.     set /a start+=1
  9. )
  10. set /a n=1
  11. :loop
  12. if "%numbers:~4%" neq "" (
  13.     for %%i in (%numbers%) do (
  14.         if "!n!" equ "3" ( set "numbers=!numbers: %%i = !" & set /a n=1 )
  15.         set /a n+=1
  16.     )
  17.     goto :loop
  18. )
  19. echo %numbers: =%
复制代码





欢迎光临 批处理之家 (http://bbs.bathome.net/) Powered by Discuz! 7.2