Board logo

标题: 【练习-051】批处理求数值n为哪些连续自然数的和 [打印本页]

作者: pusofalse    时间: 2009-8-28 20:58     标题: 【练习-051】批处理求数值n为哪些连续自然数的和

用户输入任意整数值n (n<2^32),计算n为哪些连续自然数的和。
例如:
  1. 15 = 1 + 2 + 3 + 4 + 5
  2. 15 = 4 + 5 + 6
  3. 15 = 7 + 8
  4. 60 = 4 + 5 + 6 + 7 + 8 + 9 + 10 + 11
  5. 60 = 10 + 11 + 12 + 13 + 14
  6. 60 = 19 + 20 + 21
  7. 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
  8. 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
  9. 5050 = 243 + 244 + 245 + 246 + 247 + 248 + 249 + 250 + 251 + 252 + 253 + 254 + 255 + 256 + 257 + 258 + 259 + 260 + 261 + 262
  10. 5050 = 1008 + 1009 + 1010 + 1011 + 1012
  11. 5050 = 1261 + 1262 + 1263 + 1264
复制代码
将所有可能的组合正确输出如上。
作者: canyuexiaolang    时间: 2009-8-29 08:42

n (n<2^32)
" ^ "是什么意思
作者: more    时间: 2009-8-29 11:37

效率很低:
  1. @echo off
  2. :bgn
  3. Setlocal Enabledelayedexpansion
  4. set /p in=请输入:
  5. if not defined in goto :eof
  6. echo.
  7. set /a n=in-1,m=0
  8. :agn
  9. set /a m+=1,ans=0&set "ans_str="
  10. for /l %%a in (%m% 1 %n%) do (
  11.    set /a ans+=%%a
  12.    set "ans_str=!ans_str!%%a+"
  13.    if !ans! gtr %in% (
  14.       goto :agn
  15.    ) else (
  16.       if "!ans!"=="%in%" (
  17.          set ans_str=!ans_str:~,-1!
  18.          echo.!in!=!ans_str!&echo.
  19.          goto :agn
  20.       )
  21.    )
  22. )
  23. endlocal
  24. goto :bgn
复制代码

作者: 随风    时间: 2009-8-29 12:24

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

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

[ 本帖最后由 随风 于 2009-8-29 12:27 编辑 ]
作者: 基拉freedom    时间: 2009-8-29 13:01

  1. @echo off&setlocal enabledelayedexpansion
  2. set /p p=输入一个数字(大于0且小于2^32):
  3. set a=0
  4. :begin
  5. set ok=
  6. set /a a+=1
  7. if %a% gtr %p% goto over
  8. set b=%a%
  9. set d=%a%
  10. :do
  11. set /a b=b+1
  12. set /a d=d+b
  13. if %d% lss %p% goto :do
  14. if %d% equ %p%  (
  15. for /l %%i in (%a% 1 %b% ) do set ok=!ok!+%%i
  16. echo %p%=!ok:~1!
  17. echo.&goto begin
  18. )
  19. if %d% gtr %p% goto begin
  20. :over
  21. echo 完成了&pause>nul
复制代码
只有这个逐个算下去的思路  效率实在太低了
作者: 基拉freedom    时间: 2009-8-29 15:07

这么久了
没有人有效率更高的思路吗?我再想想
作者: zhouyongjun    时间: 2009-8-29 18:07

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

作者: zhouyongjun    时间: 2009-8-29 18:11

零也是自然数哦
作者: pusofalse    时间: 2009-8-29 18:21

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

[ 本帖最后由 pusofalse 于 2009-8-29 18:23 编辑 ]
作者: defanive    时间: 2009-8-29 19:25

这其实是个数学问题,(x+y)(x-y+1)/2=n,求出x与y的通解,并代入即可,不需要枚举。。。
作者: canyuexiaolang    时间: 2009-8-29 19:59

这练习压根不是新手练习嘛
不会不会不会不会
啊啊啊啊啊
什么时候才可以学好BAT啊
作者: 基拉freedom    时间: 2009-8-29 20:26

翻来了资料:
在一些小学奥数书上有这样一类题,比如:把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    时间: 2009-8-29 20:26

小学奥数..........................哎 ╮(╯▽╰)╭
这个比较容易看懂 关键是我数学没学好啊:
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    时间: 2009-8-29 20:55

以本人的理解,此题还是有点问题,有些数是不能分的,如4,8,16本人代码如下,请大家指证:
  1. @echo off&setlocal enabledelayedexpansion
  2. cd.>temp.txt
  3. set /p n=请输入要折分的数字:
  4. set /a x=n,y=n%%2
  5. for /l %%a in (1,1,10) do set /a x=(x+n/x)/2
  6. set /a x+=1,y=3-y
  7. for /l %%a in (%y%,1,%x%) do (
  8.     set /a a=%%a%%2,b=%%a/2,c=n%%%%a,d=n/%%a,min=1,max=0
  9.     if !a! neq 0 (
  10.        if !c! equ 0 set /a min=d-b,max=d+b
  11.        ) else (
  12.        if !c! neq 0 (
  13.           set /a e=2*n,e=e%%%%a
  14.           if !e! equ 0 set /a min=d-b+1,max=d+b
  15.        )
  16.     )
  17.     for /l %%b in (!min!,1,!max!) do set /p=%%b <nul>>temp.txt
  18.     if !max! neq 0 set flag=a&echo.>>temp.txt
  19. )
  20. if not defined flag echo 此数不可分>temp.txt
  21. start temp.txt
复制代码

[ 本帖最后由 batman 于 2009-8-29 21:21 编辑 ]
作者: defanive    时间: 2009-8-29 20:59

还是引用10L的话,是不需要枚举的,直接写出通解,然后代入判断通解是否整数即可。。。
作者: 基拉freedom    时间: 2009-8-29 21:09

想通了 就让我弱弱的讲下7L的思路吧:
set/a n+=1,x=2*s-n*n-n,y=2*n,mod=x%%y,a=x/y,m=(n*n+n)/2

(2a+n+1)n/2=s
2an+n^2+n=2s
2*s-n*n-n=2an(这个就是x)
然后 a=(2S-n^2-n)/2n(2n=y)
用mod=x%%y来判断2n与2an中 n与a是否一奇一偶 是 就输出
这个其实是一个变形

哇 数学真是伟大..................我要加油学数学........
作者: 基拉freedom    时间: 2009-8-29 21:29     标题: 回复 14楼 的帖子

2^n是不会有分解的
作者: batman    时间: 2009-8-29 21:37     标题: 回复 17楼 的帖子

并不仅是2的n次方不可分,如:28,44也是不可分的。。。
作者: 基拉freedom    时间: 2009-8-29 21:59     标题: 回复 18楼 的帖子

28 44是可分的
n*(2K+n+1)=28*2=56
取n=7 则2K+n+1=8 K=0
则从1开始加到7

n*(2K+n+1)=44*2=88
取n=2 2K+n+1=44 舍
取n=4 2K+n+1=22舍
取n=8 2K+n+1=11 k=1
从2开始加到9
作者: 523066680    时间: 2009-9-16 19:25

爽! 我发的部分没有了,那个人一定还记得我。
这下中了冤鬼缠身符,有得折腾……
作者: garyng    时间: 2011-8-20 18:55

回复 2# canyuexiaolang


^ 是次方的意思
2^2=2*2=4
2^30=2*2*2*2*2*2*2*2*2*2*2*2*2*2*2*2*2*2*2*2*2*2*2*2*2*2*2*2*2*2
n^m就是n自己乘自己m次~




欢迎光临 批处理之家 (http://bathome.net./) Powered by Discuz! 7.2