【练习-051】批处理求数值n为哪些连续自然数的和

pusofalse

用户输入任意整数值n (n<2^32)，计算n为哪些连续自然数的和。
例如：

15 = 1 + 2 + 3 + 4 + 5
15 = 4 + 5 + 6
15 = 7 + 8

60 = 4 + 5 + 6 + 7 + 8 + 9 + 10 + 11
60 = 10 + 11 + 12 + 13 + 14
60 = 19 + 20 + 21
 
5050 = 1 + 2 + 3 + 4 + 5 + 6 + 7 + 8 + 9 + 10 + 11 + 12 + 13 + 14 + 15 + 16 + 17 + 18 + 19 + 20 + 21 + 22 + 23 + 24 + 25 + 26 + 27 + 28 + 29 + 30 + 31 + 32 + 33 + 34 + 35 + 36 + 37 + 38 + 39 + 40 + 41 + 42 + 43 + 44 + 45 + 46 + 47 + 48 + 49 + 50 + 51 + 52 + 53 + 54 + 55 + 56 + 57 + 58 + 59 + 60 + 61 + 62 + 63 + 64 + 65 + 66 + 67 + 68 + 69 + 70 + 71 + 72 + 73 + 74 + 75 + 76 + 77 + 78 + 79 + 80 + 81 + 82 + 83 + 84 + 85 + 86 + 87 + 88 + 89 + 90 + 91 + 92 + 93 + 94 + 95 + 96 + 97 + 98 + 99 + 100
5050 = 190 + 191 + 192 + 193 + 194 + 195 + 196 + 197 + 198 + 199 + 200 + 201 + 202 + 203 + 204 + 205 + 206 + 207 + 208 + 209 + 210 + 211 + 212 + 213 + 214
5050 = 243 + 244 + 245 + 246 + 247 + 248 + 249 + 250 + 251 + 252 + 253 + 254 + 255 + 256 + 257 + 258 + 259 + 260 + 261 + 262
5050 = 1008 + 1009 + 1010 + 1011 + 1012
5050 = 1261 + 1262 + 1263 + 1264
复制代码

将所有可能的组合正确输出如上。

canyuexiaolang

n (n<2^32)
" ^ "是什么意思

more

效率很低:

@echo off
:bgn
Setlocal Enabledelayedexpansion
set /p in=请输入:
if not defined in goto :eof
echo.
set /a n=in-1,m=0
:agn
set /a m+=1,ans=0&set "ans_str="
for /l %%a in (%m% 1 %n%) do (
   set /a ans+=%%a
   set "ans_str=!ans_str!%%a+"
   if !ans! gtr %in% (
      goto :agn
   ) else (
      if "!ans!"=="%in%" (
         set ans_str=!ans_str:~,-1!
         echo.!in!=!ans_str!&echo.
         goto :agn
      )
   )
)
endlocal
goto :bgn
复制代码

随风

又一道挑战效率的题目，。

回复2楼
n (n<2^32)
表示n小于 2的32次方。即不超过cmd的最大数值范围。

[ 本帖最后由 随风 于 2009-8-29 12:27 编辑 ]

基拉freedom

@echo off&setlocal enabledelayedexpansion
set /p p=输入一个数字（大于0且小于2^32):
set a=0
:begin
set ok=
set /a a+=1
if %a% gtr %p% goto over
set b=%a%
set d=%a%
:do
set /a b=b+1
set /a d=d+b
if %d% lss %p% goto :do
if %d% equ %p%  (
for /l %%i in (%a% 1 %b% ) do set ok=!ok!+%%i
echo %p%=!ok:~1!
echo.&goto begin
)
if %d% gtr %p% goto begin
:over
echo 完成了&pause>nul
复制代码

只有这个逐个算下去的思路  效率实在太低了

基拉freedom

这么久了
没有人有效率更高的思路吗？我再想想

zhouyongjun

@echo off
:begin
cls&setlocal enabledelayedexpansion
set/p s=please input number:
set/a n=1
:loop
set/a n+=1,x=2*s-n*n-n,y=2*n,mod=x%%y,a=x/y,m=(n*n+n)/2
if %mod% equ 0 (
	for /l %%i in (1,1,%n%) do (
		set/a a+=1&set "str=!str!!a!+"
	)
	echo %s%^=!str:~,-1!&set "str="
)
if %m% gtr %s% (pause&endlocal&goto begin) else goto loop
复制代码

zhouyongjun

零也是自然数哦

pusofalse

我目前的解法也存在很大的效率问题，7楼的算法很经典，只有学习了！

[ 本帖最后由 pusofalse 于 2009-8-29 18:23 编辑 ]

defanive

这其实是个数学问题，(x+y)(x-y+1)/2=n，求出x与y的通解，并代入即可，不需要枚举。。。

canyuexiaolang

这练习压根不是新手练习嘛
不会不会不会不会
啊啊啊啊啊
什么时候才可以学好BAT啊

基拉freedom

翻来了资料：
在一些小学奥数书上有这样一类题，比如：把2007分拆成若干个连续自然数之和，有哪几种拆法？
最好想的就是1003＋1004＝2007，其余的如何找？
假设2007拆成了以a为首项的k个连续自然数之和，即2007＝a＋（a＋1）＋（a＋2）＋……＋（a＋k－1），
即〔a＋（a＋k－1）〕×k/2＝2007
即k×（2a＋k－1）＝2007×2＝2×3×3×223＝4014
而k和（2a＋k－1）必为一奇一偶，（且k＜2a＋k－1）所以4014有几个大于1的奇约数，那么2007就有几种分拆方法。
4014的大于1的奇约数有3、9、223、669、2007共5个，即2007有5种拆成连续自然数之和的方法。
而2007的奇约数和4014的奇约数个数相同，所以2007的大于1的奇约数的个数就是2007拆成连续自然数之和的方法数。
2007＝3×3×223的大于1的奇约数有3、9、223、669、2007共5个。
4014＝3×1338，即k＝3，（2a＋k－1）＝1338，解出a＝668， 2007拆成以668为首项的3个连续自然数之和；
    ＝9×446， 即k＝9，（2a＋k－1）＝446， 解出a＝219， 2007拆成以219为首项的9个连续自然数之和；
    ＝223×18，即k＝18，（2a＋k－1）＝223，解出a＝103， 2007拆成以103为首项的18个连续自然数之和；
    ＝669×6， 即k＝6，（2a＋k－1）＝669， 解出a＝332， 2007拆成以332为首项的6个连续自然数之和；
    ＝2007×2，即k＝2，（2a＋k－1）＝2007，解出a＝1003，2007拆成以1003为首项的2个连续自然数之和；
下面是2007的具体的5种拆分：
2007＝668＋669＋670
2007＝219＋220＋221＋222＋223＋224＋225＋226＋227
2007＝103＋104＋105＋……＋118＋119＋120
2007＝332＋333＋334＋335＋336＋337
2007＝1003＋1004
结论：如果自然数n有几个大于1的奇约数，那么n就有几种方法拆成连续自然数之和。
推论：2的方幂拆不成连续自然数之和。

基拉freedom

小学奥数..........................哎 ╮(╯▽╰)╭
这个比较容易看懂 关键是我数学没学好啊：
450分拆成若干连续自然数的和，有8种方法。
149+150+151，111+112+113+114，88+89+90+91+92,
46+47+…+54,32+33+…+43,23+24+…+37,13+14+…+32,6+7+…+30

设k+1,k+2,...,k+n是n个连续的自然数，如果
(k+1)+...+(k+n)=(k+k+n+1)n/2=450
则((2k+n+1)n=900, 由(2k+n+1)>n,故得n<30且能被900整除.
可取n=2,3,4,5,6,9,10,12,15,20,25,
n=2,2k+n+1=450, 与2k+n+1是奇数矛盾。
n=3,2k+n+1=300,解得k=148,  149+150+151
n=4,2k+n+1=225,解得k=110,  111+112+113+114
n=5,2k+n+1=180,解得k=87,   88+89+90+91+92
n=6,2k+n+1=150, 与2k+n+1是奇数矛盾
n=9,2k+n+1=100,解得k=45,  46+47+48+49+50+51+52+53+54
n=10,2k+n+1=90, 与2k+n+1是奇数矛盾
n=12,2k+n+1=75,解得k=31,   32+33+...+43
n=15,2k+n+1=60,解得k=22,   23+24+25+...+37
n=20,2k+n+1=45,解得k=12,   13+14+…+32
n=25,2k+n+1=36,解得k=5,    6+7+…+30

[ 本帖最后由 基拉freedom 于 2009-8-29 20:32 编辑 ]

batman

以本人的理解，此题还是有点问题，有些数是不能分的，如4，8，16本人代码如下，请大家指证：

@echo off&setlocal enabledelayedexpansion
cd.>temp.txt
set /p n=请输入要折分的数字:
set /a x=n,y=n%%2
for /l %%a in (1,1,10) do set /a x=(x+n/x)/2
set /a x+=1,y=3-y
for /l %%a in (%y%,1,%x%) do (
    set /a a=%%a%%2,b=%%a/2,c=n%%%%a,d=n/%%a,min=1,max=0
    if !a! neq 0 (
       if !c! equ 0 set /a min=d-b,max=d+b
       ) else (
       if !c! neq 0 (
          set /a e=2*n,e=e%%%%a
          if !e! equ 0 set /a min=d-b+1,max=d+b
       )
    )
    for /l %%b in (!min!,1,!max!) do set /p=%%b <nul>>temp.txt
    if !max! neq 0 set flag=a&echo.>>temp.txt
)
if not defined flag echo 此数不可分>temp.txt
start temp.txt
复制代码

[ 本帖最后由 batman 于 2009-8-29 21:21 编辑 ]

defanive

还是引用10L的话，是不需要枚举的，直接写出通解，然后代入判断通解是否整数即可。。。