批处理之家 - Powered by Discuz! Board

标题: 【练习-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

不知道这样是否正确?

@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)
)
复制代码

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

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

作者: more 时间: 2008-7-31 12:28 标题: 头都要炸了

@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 :again
复制代码

作者: 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) 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
复制代码

作者: 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的，
运行以下的代码就会明白：

@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 时间: 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

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

@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!"
复制代码

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

@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
复制代码

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

作者: batman 时间: 2009-4-17 09:57

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

@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 编辑 ]

作者: lhjoanna 时间: 2009-4-17 12:22

借鉴了高级语言中链表的数据结构，构造环链表(只定义了创建和删除两个函数)。
没有针对顶楼的题目，算法根据更一般的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 :eof
复制代码

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

作者: leaparde 时间: 2009-4-17 13:43

从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>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输入的。

@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
复制代码

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

呵呵，没有比下面更简单了吧, 是倒推出来的公式，但确实这个问题很难理解。
是借用前辈的分析结果。证验结果正确。

@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%
复制代码

[ 本帖最后由 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

练练手：

@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
复制代码

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

@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: =%
复制代码

欢迎光临批处理之家 (http://bbs.bathome.net/)