【练习-055】批处理根据输入数求出cmd范围内最大次方数

batman

出题目的：
    1、加深大家对cmd数值处理极限值的认识
    2、考察大家的正、反计算能力
加分原则：
    满分10分，视情形加分以思路为重
解题要求：
    代码简洁、效率高，产生临时文件应该是不存在的事
题目如下：
    要求编写一批处理，实现当用户输入正整数（不考虑负数）时，分别用正算和反算法计算出此数在cmd最大极限内可运算次方数。
示例如下：

Batcher

正算和反算法分别指什么？

batman

正算：乘
反算：除

neorobin

@echo off&setlocal enabledelayedexpansion
(set/p=初始化中, 请稍等...<nul)&(call :initRoots)
echo.&echo cmd 下最大正整数 2147483647 (2^^31-1) 的各次方根整数部分(次数2--30):
(for /l %%a in (2,1,30) do set /p=!root%%a!,<nul) & (echo  )
:loop
set/p i=请输入正整数:
if %i% lss 1 goto loop
if %i% equ 1 echo 1的任意次方=1&goto loop
set /a exp=1
for /l %%a in (2,1,30) do if %i% leq !root%%a! set /a exp+=1
echo %i%的%exp%次方接近于cmd最大值.
goto loop

:initRoots 初始化 cmd 下最大正整数 2147483647 (2^31-1) 的各次方根(次数2--30)
for /l %%a in (2,1,30) do (call :searchRoot root%%a 2 50000 %%a)& set /p=^>^><nul
exit /b

:checkOverflow overflow x y rem 检测 x^y 是否溢出
(set tc=%2)&(set te=%3)
:next
if !te! gtr 1 set /a "t0=tc,tc*=%2,t1=tc/ %2,te-=1"
if !t0! neq !t1! (set %1=yes)&(exit /b)
if !t0! geq !tc! (set %1=yes)&(exit /b)
if !tc! leq 0 (set %1=yes)&(exit /b) else if !te! leq 1 (set %1=no)&(exit /b) else goto next
exit /b

:searchRoot root lower upper time
set /a "ll=%2,uu=%3"
:schNext
set /a t=(ll+uu)/2
if !t! equ !ll! set /a "%1=t" & exit /b
call :checkOverflow ofl !t! %4
if /i "!ofl!"=="yes" (set /a "uu=t") else (set /a "ll=t")
goto schNext
exit /b
复制代码

[ 本帖最后由 neorobin 于 2009-12-19 03:42 编辑 ]

batman

个人指出存在以下三点问题（好的就不说了）：

1、cmd处理的最大值应在代码中计算出来，不能直接给出。

2、题中要求的是分别用正算、反算两种方法，楼上好像就用了正算法。

3、代码写得过于复杂，易读性不好。

neorobin

4 楼代码除了次数 30, 其它并未直接或间接实质性利用 最大正整数 值, 该数仅是 echo 的内容 未起计算作用.
下面代码彻底不利用已知的 最大正整数 值, 反算我就不做了, 呵呵, 至于复杂, 嗯是有些.

@echo off&setlocal enabledelayedexpansion
set t=1
:searchMaxInt
set /a "t<<=1"
if !t! leq 0 ((set /a "t>>=1,maxInt=t-1+t")& echo cmd 下最大正整数为:!maxInt!) else goto searchMaxInt

(set/p=初始化中, 请稍等...<nul)&(call :initRoots)
echo.&echo cmd 下最大正整数 !maxInt! 的各次方根整数部分(整数部分≥2)(次数2--!expMax!):
(for /l %%a in (2,1,!expMax!) do set /p=!root%%a!,<nul) & (echo  )
:loop
set/p i=请输入正整数:
if %i% lss 1 goto loop
if %i% equ 1 echo 1的任意次方=1&goto loop
set /a exp=1
for /l %%a in (2,1,!expMax!) do if %i% leq !root%%a! set /a exp+=1
echo %i%的%exp%次方接近于cmd最大值.
goto loop

:initRoots 初始化 cmd 下最大正整数 !maxInt! 的各次方根(次数2--!expMax!)
for /l %%a in (2,1,256) do (call :searchRoot root%%a 1 !maxInt!/2 %%a)&(if !root%%a! lss 2 set /a expMax=%%a-1& exit /b)& set /p=^>^><nul
exit /b

:checkOverflow overflow x y rem 检测 x^y 是否溢出
(set tc=%2)&(set te=%3)
:next
if !te! gtr 1 set /a "t0=tc,tc*=%2,t1=tc/ %2,te-=1"
if !t0! neq !t1! (set %1=yes)&(exit /b)
if !t0! geq !tc! (set %1=yes)&(exit /b)
if !tc! leq 0 (set %1=yes)&(exit /b) else if !te! leq 1 (set %1=no)&(exit /b) else goto next
exit /b

:searchRoot root lower upper time 二分法搜索方根
set /a "ll=%2,uu=%3"
:schNext
set /a t=(ll+uu)/2
if !t! equ !ll! set /a "%1=t" & exit /b
call :checkOverflow ofl !t! %4
if /i "!ofl!"=="yes" (set /a "uu=t") else (set /a "ll=t")
goto schNext
exit /b
复制代码

[ 本帖最后由 neorobin 于 2009-12-19 23:51 编辑 ]

neorobin

请问楼主检测 溢出 有哪些好的方法

qzwqzw

下面这个例子既用了乘法又用了除法
应该是符合“分别用正算和反算法”的要求吧：）
楼上的算法难以理解
最多３０次的循环
还用二分搜索之类的玩意嘛？
检测溢出可以用大小比较
但是这个不可靠
最可靠的还是先乘再除看是否还是原数

@echo off&setlocal
:loop2
set /p num=请输入大于1的正整数：
echo.
set count=0
set temp=1
:loop
set /a count+=1
set /a temp1=temp
rem 为了避免set/a的对超大的溢出数自动纠错，直接引用原数，并屏蔽可能的错误输出
set /a temp*=%num% 2>nul
set /a temp2=temp/%num% 2>nul
if "%temp1%"=="%temp2%"	goto :loop
set /a count-=1
echo %num%的%count%次方接近于cmd的最大值。
echo.
goto :loop2
复制代码

CrLf

正算法：

@echo off&setlocal enabledelayedexpansion 2>nul 3>nul
set n=1
set /p num=请输入大于1的正整数：
for /l %%a in (1 1 31) do (
set /a n*=num,"max+=^!((n-1)>>31)","test=1/n+1/(!max!-max)"||goto re
)
:re
echo %max%
pause
复制代码

反算法：

@echo off&setlocal enabledelayedexpansion 2>nul 3>nul
set n=2147483648
set /p num=请输入大于1的正整数：
for /l %%a in (1 1 31) do (
set /a n/=num,"max+=^!((n-1)>>31)","test=1/n+1/(!max!-max)"||goto re
)
:re
echo %max%
pause
复制代码

二者联用的话和8楼思路差不多，也是通过比较两个变量大小来判断两种算法的图像相交于何处

qzwqzw

程序着实有心意
妙处自不多说
有新人自己体会
只提供几个意见查缺补漏

@echo off&setlocal enabledelayedexpansion 2>nul 3>nul

将 2>nul 3>nul的屏蔽错误用在这里确实有新意
不过别忘了程序执行完还要打扫战场的
否则别人在cmd下执行完后
看不到后续所有命令的错误输出时
都不知道该怪谁

31和2147483648两个常数的指定
有些想当然了
万一别人是在64位的cmd环境下呢？

max+=^!((n-1)>>31)
想来是用来判断n的正负性的
转换为0或1后加入max
但是感觉这用法有些多余
直接取%%a不是很省事吗？
只需要在最后再减个1就可以了
而且用除法的话
n可能会溢出为负值吗？
用乘法的话
也有可能直接溢出到正值

test=1/n+1/(!max!-max)
大概是用来判断n是否为0和max是否溢出的
||goto re是遇到错误时跳转
只是看不明白max
是如果未溢出就要跳转吗？
需要详解一下

另外程序没有对超大数进行处理
即如果用户输入的数直接溢出了该怎么办？

qzwqzw

书接上回
31和2147483648两个常数是不能随意指定
那么如何在cmd下得到这两个常数值呢？

位数可以通过
set /a _d=<一个超级大数>
然后捕捉并分析其错误输出

最大值可以通过
set __d=<一个超级大数>
set /a _d=__d

CrLf

max+=^!((n-1)>>31) 是用于判断n是否小等于0，为0不变，否则加1，直接获取%%a是要绕弯的，不过现在想想确实可以简化成max+=n>>31+1
test=1/n+1/(!max!-max)||goto re 用于进行两个if判断，满足n为0时或者新max变量大于旧max变量两条件之一时跳转到re

楼上方法二巧妙...
{
最大值可以通过
set __d=<一个超级大数>
set /a _d=__d
}

qzwqzw

嗯
想通了max的作用和变化了
因为1/n已经判断了n是否为0
所以^!((n-1)>>31)改为^!(n>>31)
只需要判断n是否小于0是可行的
或者将1/n去掉也可以

如果直接取%%a到max
则可以在test中判断n是否小于等于0
set /a max=%%a,"test=1/(^!((n-1)>>31))"

总体来说
是使用set/a的错误抛出
来实现了if的判断跳转

不过正如我在10楼所说
依靠乘方结果的正负性来判断是否溢出是不可靠的
比如100000的乘方结果是1410065408
直接溢出成正值就导致程序判断出错

qzwqzw

将8楼的代码整理了一下
逻辑上更清晰一些
使可读性更强
并且支持了绝对值大于1的负整数

@echo off&setlocal
:loop2
set /p num=请输入绝对值大于1的整数（可以是负数）：
echo.
set count=0
set temp=1
:loop
set /a temp1=temp
rem 为了避免set/a的对超大的溢出数自动纠错，直接引用原数，并屏蔽可能的错误输出
set /a temp*=%num% 2>nul
set /a temp2=temp/%num% 2>nul
rem 如果次方结果乘以整数n再除以整数n不再是原值，则认为乘方结果已接近溢出，跳出
if not "%temp1%"=="%temp2%"                                  goto :jump
if %count% gtr 1024 echo 程序溢出，请确认输入的整数是否正确&pause&goto :eof
set /a count+=1
goto :loop
:jump
echo %num%的%count%次方接近于cmd的最大值。
echo.
goto :loop2
复制代码

[ 本帖最后由 qzwqzw 于 2011-3-14 14:25 编辑 ]

CrLf

楼上说的有点小问题，当时我之所以用max+=^!((n-1)>>31)而不用^!(n>>31)是考虑到2的x次方数的n次方溢出为0的情况，这一点不可不防，所以特意设置一个-1来弥补，用max+=(n-1)>>31+1也可以，大家知道，嗯嗯...

至于溢出导致由正转负再转正，楼上可能没搞明白test的用途，"test=1/n+1/(!max!-max)"这句不仅仅是判断n是否为0，更重要的就是避免溢出被重复计算，!max!是在set /a之前被解释，而max是由set解释，所以!max!-max的效果就是（set前的max  -  当前的max），并借/来判断二者是否相同，相同则跳转。因为不可能存在一个数连续两次乘同样一个数都溢出的情况，所以还没有第二次溢出就已经跳转了。不过现在想想刻意简化成"test=1/n/(!max!-max)"可以

[ 本帖最后由 zm900612 于 2011-3-14 16:37 编辑 ]