标题: 【练习-055】批处理根据输入数求出cmd范围内最大次方数 [打印本页]
作者: batman 时间: 2009-12-18 23:21 标题: 【练习-055】批处理根据输入数求出cmd范围内最大次方数
出题目的:
1、加深大家对cmd数值处理极限值的认识
2、考察大家的正、反计算能力
加分原则:
满分10分,视情形加分以思路为重
解题要求:
代码简洁、效率高,产生临时文件应该是不存在的事
题目如下:
要求编写一批处理,实现当用户输入正整数(不考虑负数)时,分别用正算和反算法计算出此数在cmd最大极限内可运算次方数。
示例如下:
作者: Batcher 时间: 2009-12-18 23:29
正算和反算法分别指什么?
作者: batman 时间: 2009-12-18 23:33
正算:乘
反算:除
作者: neorobin 时间: 2009-12-19 00:48 标题: 回复 1楼 的帖子
- @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 时间: 2009-12-19 10:35 标题: 回复 4楼 的帖子
个人指出存在以下三点问题(好的就不说了):
1、cmd处理的最大值应在代码中计算出来,不能直接给出。
2、题中要求的是分别用正算、反算两种方法,楼上好像就用了正算法。
3、代码写得过于复杂,易读性不好。
作者: neorobin 时间: 2009-12-19 20:52 标题: 回复 5楼 的帖子
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 时间: 2009-12-19 21:15 标题: 回复 1楼 的帖子
请问楼主检测 溢出 有哪些好的方法
作者: qzwqzw 时间: 2011-3-13 14:10
下面这个例子既用了乘法又用了除法
应该是符合“分别用正算和反算法”的要求吧:)
楼上的算法难以理解
最多30次的循环
还用二分搜索之类的玩意嘛?
检测溢出可以用大小比较
但是这个不可靠
最可靠的还是先乘再除看是否还是原数
- @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 时间: 2011-3-13 15:31
正算法:- @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 时间: 2011-3-14 10:57
程序着实有心意
妙处自不多说
有新人自己体会
只提供几个意见查缺补漏
@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 时间: 2011-3-14 11:07
书接上回
31和2147483648两个常数是不能随意指定
那么如何在cmd下得到这两个常数值呢?
位数可以通过
set /a _d=<一个超级大数>
然后捕捉并分析其错误输出
最大值可以通过
set __d=<一个超级大数>
set /a _d=__d
作者: CrLf 时间: 2011-3-14 13:21
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 时间: 2011-3-14 14:04
嗯
想通了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 时间: 2011-3-14 14:16
将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 时间: 2011-3-14 16:27
楼上说的有点小问题,当时我之所以用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 编辑 ]
作者: CrLf 时间: 2011-3-14 16:30
set /a n*=num,"max+=((n-1)>>31)+1","test=1/n/(!max!-max)"||goto re
这句用到了很多技巧,可读性降低,不过却是高效计算的核心代码,可读性在我看来一向是要排在高效、简洁、避免临时文件这几点之后的。
[ 本帖最后由 zm900612 于 2011-3-14 18:32 编辑 ]
作者: CrLf 时间: 2011-3-14 16:41
忽然想到这正是判断n是否为2的倍数的最快办法:set /a "test=1/(1073741824*n)"||echo %n%为2的倍数
作者: qzwqzw 时间: 2011-3-14 17:29
没办法台式机网络有点问题,使用手机回复比较累,简短点吧。关于溢出我不多讲,你测试下100000试试,看跟我的代码是否结果一致。
作者: CrLf 时间: 2011-3-14 17:44
已测试,100000结果为1,呵呵,有test的存在是不可能多次溢出的
作者: qzwqzw 时间: 2011-3-14 17:48
请测试你的乘法算法
我这里结果是2
除法算法天生不存在溢出问题我是知道的
作者: qzwqzw 时间: 2011-3-14 17:55
台式机网络刚恢复
set /a "test=1/(1073741824*n)"||echo %n%的技巧值得借鉴
不过乘法比较消耗CPU
改成“字节与”更好些
set /a "m=1/(n&1)"||echo %n%是偶数
作者: CrLf 时间: 2011-3-14 18:15
巧妙,位运算还是用得太少,没第一时间想到这方向
测试了下正算法,真的有溢出...而且十分诡异,为什么set /a n=100000*100000结果是1410065408??溢出不是应该变成负数么?
作者: CrLf 时间: 2011-3-14 18:30
调试了一下,发现100000的溢出很奇怪,以下数据均为 【每次循环的n值 max值】:
请输入大于1的正整数:100000
100000 1
1410065408 2【100000*100000=1410065408???】
-1530494976 2
确切地说是大于46340(约等于极限值的开方)的数可能都有问题:
请输入大于1的正整数:46340
46340 1
2147395600 2
214822976 3【第三次循环时发生溢出,但是不转负】
-837484288 3
302580736 4
作者: qzwqzw 时间: 2011-3-14 20:04 标题: 标题
没什么可怪异的,计算机的数集就像个圆,一个数不断累加,就像在圆上行走,等加到正数最大值时,就走了个半圆,再走一步就是负数最大值,然后继续延负数轴向前,直到走回零点,就画了一个整圆。然后重新开始,周而复始。类似于道家的阳极生阴,阴极生阳理论。数学上的数集也有类似的特性。溢出为正数不过是在数集圆上走的更远,越过了负数所在的半圆,又回到正数圆而已。不知道这样说你明白了没有?
作者: CrLf 时间: 2011-3-14 20:59
不敢苟同,个人见解如下:
溢出导致由正转负我可以理解,因为2147483647在cmd中的二进制形态为01111111111111111111111111111111,而-1则是1111111111111111111111111111110,所以数值计算时超过2147483648的部分会被当成负数,根本原因就是首位由0转1,才会正负逆转。
但是要发生逆转,必须达到1000000000000000000000000000000000000的数量级,可是有什么正数能同时满足下列方程组呢?
{m+n=32
m+n+n>64}
作者: CrLf 时间: 2011-3-14 21:06
哦,我晕,之前糊涂了,这里用的不是加而是乘,如果是加法确实不存在连续两次溢出,乘法溢出的可能就很大了
作者: qzwqzw 时间: 2011-3-14 21:12
抱歉,方程组没看懂
只看到二进制的-1写错了
不知道这样写如何?
二进制 十进制
00...0 0
00...1 1
......
01...1 2147483647
10...0 -2147483648
......
11...1 -1
00...0 0
......
作者: CrLf 时间: 2011-3-14 21:31
再理论化地解释一下:
假设计算范围为8位二进制00000000~11111111,也就是0~128,或者说-64~63,此时:
加法溢出:
十进制:64+64=128
二进制:1000000+1000000=10000000
十进制:65+65=130
二进制:1000001+1000001=10000010
发生溢出,由于二进制倒数第八位为1,所以由正转负,在cmd中分别变为-128和-126
乘法溢出:
十进制:64*64=4096
二进制:1000000*1000000=1000000000000
十进制:65*65=4225
二进制:1000001*1000001=1000010000001
两个算式的结果都超过11111111,于是发生溢出,只获取最后八位,也就是00000000和10000001,换算为cmd中的十进制分别为0与-127
所以结论是,当数值在n*2*128~(n*2+1)*128-1范围内时为正,而在(n*2-1)*128-1~(n*2+1)*128范围内时为负,不知道有没有讲错,反正大概意思是这样。
乘法之所以会出现同一个数值乘某数后,正数溢出仍为正数是因为数值前后跨度超过256,于是溢出之后再溢出,负负得正。这在加法中是不可能出现的,我之前脑筋歪了,把乘法当加法去了
[ 本帖最后由 zm900612 于 2011-3-14 21:34 编辑 ]
作者: CrLf 时间: 2011-3-14 21:32
正如27楼所言,咱俩说的恰恰是同一个事
作者: qzwqzw 时间: 2011-3-14 22:10
嗯,看着理论尤其是数字算式就头大如斗
只看到8位二进制的可表示范围错了(不好意思)
不是"0~128,或者说-64~63"
而是“0~256,或者说-128~127”
作者: CrLf 时间: 2011-3-14 22:25
嗯,笔误,呵呵
作者: applba 时间: 2011-4-27 09:41
本帖最后由 applba 于 2011-4-28 23:45 编辑
给出个求极大值的捷径:
通过二进制移位来给2开方,一直开到溢出,溢出后其结果是负的,以此负值判断结束条件。- @echo off &setlocal enabledelayedexpansion
- for /l %%i in (1,1,256) do (
- set /a "_tmp=1<<%%i"
- if !_tmp! leq 0 (
- set /a "t2=%%i-1"
- set /a "max=((1<<!t2!)-1)+(1<<!t2!)"
- goto 2out
- )
- )
- :2out
- echo 2的!t2!次方最接近极大值!max!
- pause>nul
复制代码
我用for是和256是因为我还没有看到支持256bit数据类型的编程语言和操作系统……
当然你喜欢用goto也没什么问题的……
作者: applba 时间: 2011-4-27 10:02
本帖最后由 applba 于 2011-4-27 13:24 编辑
既然上面求了极大值,现在就不存在溢出问题了:- @echo off &setlocal enabledelayedexpansion
- :input
- cls
- set /p _n=请输入正整数:
- set /a n=!_n!&&if !n! lss 2 goto input
- set /a "varup=1,vardn=2147483647"
- for /l %%i in (1,1,30) do (
- set /a "varup=!varup!*!n!,vardn=!vardn!/!n!"
- set /a "var=!vardn!/!varup!"
- if !var! lss !n! (
- if !var! equ 0 (set /a "cnt=2*%%i-1" && goto out)
- set /a "cnt=2*%%i" && goto out
- )
- )
- :out
- echo !n!的!cnt!次方接近最大值!
- PAUSE&goto input
复制代码
思路也很简单,正反一起用,往中间碰撞……
作者: qzwqzw 时间: 2011-4-27 11:48
给出个求极大值的捷径:(此方法通用于所有二进制计算机)
通过二进制逻辑移位来给2开方,一直开到溢出,溢出后其结果是负的,以此负值判断结束条件。
@echo off &setlocal enabledelayedexpansion
for /l %%i in ...
applba 发表于 2011-4-27 09:41
求极值的方法很多
比如11楼的方法
如果非要用二进制移位,也可以这样@echo off &setlocal enabledelayedexpansion
for /l %%i in (1,1,256) do (
set /a "_tmp=1<<%%i"
if !_tmp! leq 0 (
set /a "t2=%%i-1"
set /a "max=_tmp-1"
goto 2out
)
)
:2out
echo 2的!t2!次方最接近极大值!max!
pause>nul
作者: qzwqzw 时间: 2011-4-27 11:57
思路也很简单,正反一起用,往中间碰撞……
applba 发表于 2011-4-27 10:02
正反同时碰撞的思路不错
可以看考虑修改一下以支持负整数(除-2以外与正整数相同)和超大数(结果是0)
作者: applba 时间: 2011-4-27 13:11
34# qzwqzw
汗,我把这个极值翻转居然给忘了………………
就是不知道这个通用性如何?
作者: applba 时间: 2011-4-27 13:32
本帖最后由 applba 于 2011-4-27 13:33 编辑
35# qzwqzw
请教 第八行和第九行合并(用逗号)表达式后,结果会异常,但是程序运行都正常的……
超级大数?在cmd.exe是输不进去的,你赋值的时候提示无效……
关于负数很好弄吧,只看正值就行了, for i=(0,2,30)就行了?
作者: qzwqzw 时间: 2011-4-27 17:48
请教 第八行和第九行合并(用逗号)表达式后,结果会异常,但是程序运行都正常的……
这个,你去掉set /a 后面的!试试
也就是说不使用变量延迟扩展
超级大数?在cmd.exe是输不进去的,你赋值的时候提示无效……
你是用什么处理输入数的
可以看一下我14楼的代码
它是支持超大数的
没理解你想说的意思
最好能有代码实现让我看看
作者: CrLf 时间: 2011-4-27 18:15
合并算式的时候要注意预处理,要不然变量并不一定会按照我们所想的顺序去拓展
set /a "varup=!varup!*!n!,vardn=!vardn!/!n!","var=vardn/varup"
作者: yjstone 时间: 2011-5-17 15:04
忽然想到这正是判断n是否为2的倍数的最快办法:set /a "test=1/(1073741824*n)"||echo %n%为2的倍数
zm900612 发表于 2011-3-14 16:41
搞错了吧,应该是判断n是否为4的倍数才对,不信试试下面的代码:- @echo off
- set n=2
- :loop
- set /a "test=1/(1073741824*n)" 2>nul||echo %n%
- set /a n+=2
- if %n% lss 100 goto:loop
- pause
复制代码
作者: CrLf 时间: 2011-5-17 15:18
嗯,忘了溢出后的-2147483648是合法的,不过也好办,改成:
set /a "test=1/(1073741824*2*n)"||echo %n%
作者: caruko 时间: 2011-5-17 17:52
看了半天,后面全部离题了。。。
所谓的“正算反算”应该是 nx=n*n 之后,再求 n <> nx/n 的循环次数。
一个数乘了以后如果溢出,那么反过来这个溢出数除了之后肯定不等于原来的数了。
作者: caruko 时间: 2011-5-17 18:26
代码放上- @echo off
- set /p in=请输入正整数:
- set /a inx=in
- for /l %%i in (1,1,100) do (
- 2>nul set /a ix=inx*in,"1/!(ix / inx - in)",inx=ix ||call :end %%i
- )
- :end
- echo %in%的%1次方接近于CMD最大值,值为%inx%。
- pause>nul&exit
复制代码
作者: caruko 时间: 2011-5-17 18:50
判断是否2的倍数,只要知道最后一个字节是0是1就可以了。
哪怕最直接的 % 2 ,求余数都比你那个复杂的计算要快。
作者: CrLf 时间: 2011-5-17 18:57
44# caruko
确实,当时思维绕弯了,21楼也指出了这个问题
作者: caruko 时间: 2011-5-17 20:38
本帖最后由 caruko 于 2011-5-17 20:47 编辑
才发现这道题是两年前的。。。
把我前面43#的代码做了精简。
去掉了CALL- @echo off
- set /p in=请输入整数:
- set /a inx=in,flag=1&for /l %%i in (1,1,30) do (
- 2>nul set /a 1/flag,cs=%%i,ix=inx*in,"1/!(ix / inx - in)",inx=ix ||set flag=0)
- echo %in%的%cs%次方接近于CMD最大值,值为%inx%。
- pause>nul
复制代码
作者: CrLf 时间: 2011-5-17 20:53
看了半天,后面全部离题了。。。
所谓的“正算反算”应该是 nx=n*n 之后,再求 n nx/n 的循环次数。
一个数乘了以后如果溢出,那么反过来这个溢出数除了之后肯定不等于原来的数了。
caruko 发表于 2011-5-17 17:52
这思路好
作者: qzwqzw 时间: 2011-5-17 21:22
46# caruko
与我8楼代码的思路没有什么本质区别
只是形式上由goto :loop换成了for
这与楼主所说的正算、反算其实不是一回事……
欢迎光临 批处理之家 (http://www.bathome.net/) |
Powered by Discuz! 7.2 |