Board logo

标题: [出题]批处理趣味数学之平分水的问题 [打印本页]

作者: HAT     时间: 2008-8-25 17:18    标题: [出题]批处理趣味数学之平分水的问题

有一个8升的瓶子装满水,还有一个5升的空瓶子和一个3升的空瓶子。要求将水分成两个4升,请用批处理给出解决方案。

应观众需求,先把我的结果给大家看看:



答案见9楼

[ Last edited by HAT on 2009-2-3 at 05:43 ]
作者: pusofalse     时间: 2008-8-25 17:35
没明白什么意思。感觉只是8/2就可以了。
那两个空瓶子在这题里有何作用吗。
作者: bat-zw     时间: 2008-8-25 17:42
hat兄这个用批来做是不是太难了啊,下面给出倒水过程,初始状态为8 0 0
8 0 0
3 5 0
3 2 3
6 2 0
6 0 2
1 5 2
1 4 3
4 4
作者: HAT     时间: 2008-8-25 17:43    标题: Re 2楼

题目中除了三个瓶子和8升水,什么都没有,瓶子不会做除法吧,呵呵。你准备把两个4升的水分别装在什么地方呢?
作者: pusofalse     时间: 2008-8-25 17:47
明白了。
--------------------
类似汉诺塔,不知我理解的对否。

[ Last edited by pusofalse on 2008-8-25 at 05:53 PM ]
作者: BC     时间: 2008-8-25 20:14
如何用批写啊?
作者: lxmxn     时间: 2008-8-25 20:39
呵呵,面试官考我的时候也是出的这个,不过条件有点不大一样——3L和5L的两个杯子和足够的水。
作者: HAT     时间: 2008-8-26 09:43
昨天群里有朋友问,我自己有没有这个题目的解。
既然是出题,当然有啦^_^
先把结果贴到顶楼给大家看看
作者: HAT     时间: 2008-8-27 13:46
没有人贴代码,我先抛个砖。
CODE:  [Copy to clipboard]
@echo off
setlocal EnableDelayedExpansion
set x=8
set y=5
set z=3
echo Your containers: %x%   %y%   %z%
echo.
set a=%x%
set b=0
set c=0
set n=0
:water1
if %a% neq %b% (
  set /a n+=1
  if %b% equ 0 (
    set /a a-=y
    set /a b=y
  ) else (
    if %c% equ %z% (
      set /a a+=z
      set c=0
    ) else (
      set /a t=z-c
      if %b% gtr !t! (
        set /a b-=t
        set /a c=z
      ) else (
        set /a c+=b
        set b=0
      )
    )
  )
  echo Solution1 step%n%: %a%--^>%b%--^>%c%
  goto :water1
)
echo Solution1 step%n%: %a%--^>%b%--^>%c%
echo.
echo Your containers: %x%   %z%   %y%
echo.
set a=%x%
set b=0
set c=0
set n=0
:water2
if %a% neq %b% (
  set /a n+=1
  if %c% equ 0 (
    set /a a-=z
    set /a c=z
  ) else (
    if %b% equ %y% (
      set /a a+=y
      set b=0
    ) else (
      set /a t=y-b
      if %c% gtr !t! (
        set /a c-=t
        set /a b=y
      ) else (
        set /a b+=c
        set c=0
      )
    )
  )
  echo Solution2 step%n%: %a%--^>%c%--^>%b%
  goto :water2
)
echo Solution2 step%n%: %a%--^>%c%--^>%b%

作者: BC     时间: 2008-8-27 13:50
很复杂的计算过程...
作者: 523066680     时间: 2008-12-17 17:07
-------水平分问题---------

首先, HAT 版主直接贴代码而没有对其主干思路进行分析,应当扣5分.
其次,我认为这是道好题,我有加15分的权限,加15-5=10分.
----------- 执行者:中国DOS联盟 银牌会员:523066680 ------------

(汗,过了把给版主加分的瘾,没加满不介意吧.)

以下内容编辑:523066680
blog:   http://hi.baidu.com/523066680

先给出自己的代码,一些说明已在代码中出现.
CODE:  [Copy to clipboard]
@echo off &setlocal enabledelayedexpansion
title code by hi.baidu.com/523066680
mode con cols=85 lines=25
set /a a=8,b=5,c=3,ah=8,bh=0,ch=0,fo=-1
set ab=ab
echo,容器容量分别为 a-8 b-5 c-3  单位-升
echo,
echo,初状态 a=%ah% b=%bh% c=%ch%   
:for
set /a fo+=1,fo2=fo+1,p=fo%%2
if %p% equ 0 (set "no1=a") else (set "no1=b")
set "no2=!ab:%no1%=!"

if !%no2%h! equ 0 (
    if !%no1%h! leq !%no2%! (
            set /a %no2%h=%no1%h,%no1%h=0
    ) else (
            set /a %no2%h=%no2%,%no1%h=%no1%h-%no2%
    )
set "say= %no1% 大于 4 ,但 %no2% 没有水,比 c 优先从 %no1% 获取水.(否则可能走回头路)"
goto :next
)

if !%no1%h! gtr 4 (
    set /a "%no1%h-=c-ch,ch=c"
    set "say= %no1% 大于 4 ,往 c 倒."
    goto :next
)

if !%no1%h! lss 4 (
   if %ch% equ 0 (
           set /a ch+=%no1%h,cc-=%no1%h,%no1%h=0
           set "say= %no1% 小于 4 ,但 c 没有水,又要改变现状,故 %no1% 往 c 倒"
   ) else (
           set /a m=%no1%h+ch-%no1%
           if !m! leq 0 (set /a m=0)
           set /a %no1%h=%no1%h+ch-m,ch=0+m
           set "say= %no1% 小于 4 , c 往 %no1% 倒."
   )
)
:next
echo,                    %say%
echo,step%fo2%   %ah%   %bh%   %ch%
if !%no1%h! neq 4 (goto :for)
if !%no2%h! neq 4 (goto :for)
echo,
echo,到这里就 a=%ah% b=%bh% c=%ch% 啦
echo, &echo,按任意键退出 &pause>nul
这里是啰嗦部分:

    一般做此题时,拿起笔,然后漫无目地"把水倒来倒去"总能变成4 4 0 做得出,却说不出理由.
    但这样做题仍然是有意义的--用来推导逻辑的做题方式.

以下是对思路的推导(有些勉强吧,但用代码实现是可以的了):

    首先,要使两个杯都装着 4 升 的水,这两个杯必须是 8升 5升 的杯子,现假定杯子及容量分别为
a-8  b-5  c-3 所以解题过程必须有"使 a b 的水趋向于 4 升"的趋势.于是规定主要思路:

    分别对a  b 进行判断,若其大于4 则倒出水,小于4 则倒入水 直到4 4为止.显然c是中间者,所以大部分时候
的倒水过程都是 c 参与的.

    于是我尝试: 轮流判断a b与4的关系
                其>4 则往 c 倒水,小于4 则从c 获得水 
    发现,做题过程如果不遵守潜在的"规则" 总会走回头路,水往外倒,水往回倒,周而复始.
    于是继续看答案,试图尽量 逻辑的描述每一步的变化,尽量 合理的解释每一步"为何这么做",
8 0 0       a > 4  但b = 0 , 比 c 优先,故往 b 倒.
3 5 0       b > 4 往 c 倒
3 2 3       a < 4 从 c 获得水
6 2 0       b < 4 但 c 没有水供给,避免下一步"往回走",但又必需改变现状,所以只能 b 往 c 倒水.
6 0 2       a > 4 本应往 c 倒 但 b = 0 --优先倒给 b
1 5 2       b > 4 往 c 倒
1 4 3       a < 4 从 c 获得水
4 4  0       a = 4 b = 4 结束
-------------------------------
以上步骤遵循: 轮流对a b 判断 然后水的交换一般是与c之间的.(像这样a c , b c , a c , b c ...)

    第一步就出现了"特别的情况",一般的a>4 应往c 倒水,但此时倒给b 我给出这样的解释:

                       b=0 应比c优先获得水,因为每一步的目的都是为了是 a 或 b 接近于4

    第4步,b<4 却倒水给c  因c=0 , b 没法从 c 获得水,而从a获得的话,则走了"回头路".
    所以特殊情况特殊对待,必须改变现状, b 倒水给 c

    接下来的按 之前的"优先"规定执行操作,如没有别的特殊情况,就可以完成了.

这样强制地假设"解题的方法",暂时也可以用批处理解答了,不过我觉这挺勉强的.

希望知道的人士慷慨的分享正解!在下感激不尽!

尤其是HAT,贴了代码不做解释.
虽然可以通过那段代码理解,可以分析出每一步的操作,但是为什么这么操做?实在琢磨不透.

所以热切希望 HAT版主 能够给出代码的主体思路.在下再次感激不尽!
作者: HAT     时间: 2008-12-17 17:24    标题: Re 11楼

如果我直接给出了思路,很多人(包括你)的思维可能就会受到束缚,也许大家就看不到你在11楼的精彩讲解了^_^
作者: 523066680     时间: 2008-12-17 17:30
(版主说精彩也~ 继续努力  追赶willsort时代的精神 从我做起!)
可惜版主的帖子沉了很久哦 我在精华帖2008翻到了
另外,发现楼上很多人都不认为这道题可能用批处理解呢

[ Last edited by 523066680 on 2008-12-17 at 17:31 ]
作者: HAT     时间: 2008-12-17 17:32    标题: Re 13楼

可能主要是思路问题吧,如果我一开始就在顶楼说出思路,相信批处理室能写出这个代码人成千上万。
作者: 523066680     时间: 2009-2-2 12:36    标题: 【挑战】题目升级

群里slore有找了升级的题目
    a.  10 7 3 的杯子 有10 0 0  要分成 5 5 0
    b.  16 9 7 的杯子 有16 0 0  要分成 8 8 0
     
     现在回来看我11楼的解 真勉强……

现在给题目升级,谁能给出针对这三道题,思路上通用的代码?
作者: slore     时间: 2009-2-2 13:11
=.=

HAT的就能……
作者: 523066680     时间: 2009-2-2 13:37
啊  我才知道。。。。。

     现在强烈想要知道那个原理……

[ Last edited by 523066680 on 2009-2-2 at 13:39 ]
作者: slore     时间: 2009-2-2 13:46
而且可以得到一个关系:
有2n水,
2n,n+1,n-1的空水杯,
2n杯子装满2n水。。要求最后
2n杯子里面n水,n+1杯子里面n水。

移动步骤次数最少为:2n-1


所以这种问题有无限个。。。
n=10
20,11,9
作者: 523066680     时间: 2009-2-3 17:45
顶贴 加分。。。 另外 +2 -2 的也有  像 10 7 3 的杯子组合
                        但是恰好这个例子+1 -1 不行 像10 6 4
作者: netbenton     时间: 2009-2-26 12:28    标题: 我不懂得算,只只知道猜

::呵呵,也蒙出了不少倒水方法。

@echo off
set/a b_8=8,b_5=0,b_3=0,#sa800=1
set #bb%random%35=35
set #bb%random%38=38
set #bb%random%53=53
set #bb%random%58=58
set #bb%random%83=83
set #bb%random%85=85


echo     动作    结果:a(8) b(5) c(3)
:头
for /f "tokens=2 delims==" %%a in ('set #bb') do call :sub %%a
set ran=34
if defined ok goto :end
goto :头


:sub
if defined ok goto :eof
set dz=%1
call :save
call :手ct%1
if %b_8%==0 call :read
if defined #sa%b_8%%b_5%%B_3% (call :read) else (set #sa%b_8%%b_5%%B_3%=1&echo.   %dz:~0,1%杯^=^>%dz:~1,1%杯        %b_8%   %b_5%    %b_3%)
if "%b_8%%b_5%%B_3%"=="440" set ok=1
goto :eof

:end
echo.任务完成
pause
goto :eof

:save
set/a s8=b_8,s5=b_5,s3=b_3
goto :eof

:read
set/a b_8=s8,b_5=s5,b_3=s3
goto :eof

:手ct85
set/a n=5-B_5
if %b_8% leq %n% set/a n=b_8
set/a b_5=b_5+n,b_8=b_8-n
goto :eof

:手ct83
set/a n=3-B_3
if %b_8% leq %n% set/a n=b_8
set/a b_3=b_3+n,b_8=b_8-n
goto :eof

:手ct53
set/a n=3-B_3
if %b_5% leq %n% set/a n=b_5
set/a b_3=b_3+n,b_5=b_5-n
goto :eof

:手ct58
set/a n=8-B_8
if %b_5% leq %n% set/a n=b_5
set/a b_8=b_8+n,b_5=b_5-n
goto :eof

:手ct35
set/a n=5-B_5
if %b_3% leq %n% set/a n=b_3
set/a b_5=b_5+n,b_3=b_3-n
goto :eof

:手ct38
set/a n=8-B_8
if %b_3% leq %n% set/a n=b_3
set/a b_8=b_8+n,b_3=b_3-n
goto :eof
作者: 523066680     时间: 2009-2-27 05:34
知道的都把原理说下哈~  我尤其想知道hat的那个原理~
作者: netbenton     时间: 2009-2-27 08:55
我的方法是每种可能都试做一次,错了再恢复,还有就是绝不走回头路和绝路(800,053),直到得到最后结果。
就好像现实中的设想:
a倒入b,结果可行吗?
不行!
不行就不倒,换种方法,a倒入c
...
作者: terse     时间: 2009-2-28 11:38
分出任意数
修正一处错误
CODE:  [Copy to clipboard]
@echo off&setlocal enabledelayedexpansion
set "Tab=        "这里替换为TAB键
set /p _n=输入你要分出的量:
set/a a=16,b=9,c=7,x=0,yb=a-b-c
if %yb% lss 0 (set/a y=a-b)else set/a y=c
echo;%Tab%%a% %Tab%%b%%Tab%%c%
echo.&echo.初始%Tab%%a%%Tab%0%Tab%0&echo.
set/a a1=a,a2=0,a3=0
call:next %b% %c% %y%
if %yb% lss 0 (set/a y=a-c)else set/a y=b
echo.&echo.初始%Tab%%a%%Tab%0%Tab%0&echo.
set/a a1=a,a2=0,a3=0,n=0
call:next %c% %b% %y%
pause&exit
:next
if %a1% equ %_n% (exit/b)else if %a2% equ %_n% (exit/b)else if %a3% equ %_n% exit/b
set/a n+=1
if %a2% equ 0 (
      if %a3% equ %2 echo 不能分出你要的量&pause&exit
      if %a3% geq %3 (set /a a2=%1-a3+%3) else set/a a2=%1
    ) else (
      if %a3% leq %3 (
      set/a a2-=%2-a3,a3=%2
      if !a2! leq 0 set /a a3+=a2,a2=0
    )
     if %a3% geq %3 set a3=0
)
set/a a1=a-a2-a3
echo 第%n%次%Tab%%a1% %Tab%%a2%%Tab%%a3%
goto next
[ Last edited by terse on 2009-3-1 at 03:04 ]




欢迎光临 中国DOS联盟论坛 (http://cndos.fam.cx/forum/) Powered by Discuz! 2.5