Board logo

标题: [数值计算] [已解决]批处理怎样进行整数的分划？ [打印本页]
作者: yangfengoo    时间: 2011-5-1 20:01     标题: [已解决]批处理怎样进行整数的分划？

本帖最后由 yangfengoo 于 2011-5-3 13:56 编辑

在http://www.bathome.net/thread-12158-1-1.html
讨论中neorobin提出这个思路，刚好是我在做的另一个问题

如，对于正整数n=6，可以分划为：
        6
        5+1
        4+2, 4+1+1
        3+3, 3+2+1, 3+1+1+1
        2+2+2, 2+2+1+1, 2+1+1+1+1
        1+1+1+1+1+1+1
        现在的问题是，对于给定的正整数n,编写算法打印所有划分。
        用户从键盘输入 n （范围1~10）
        程序输出该整数的所有划分。
------------------------------------------------------------
答案在三楼
作者: batman    时间: 2011-5-1 21:33

术业有专攻，楼主是专攻排列组合的吧，呵呵。。。
作者: yangfengoo    时间: 2011-5-1 22:12

只是最近刚好看到这个问题。
前面的问题是由求N位数的水仙花数引导出来的。如果用一般的枚举求水仙花水效率有限，6位的以上的水仙花数得枚举几分钟才能完成，所以我想到先组合在计算。
作者: hanyeguxing    时间: 2011-5-2 12:47

本帖最后由 hanyeguxing 于 2011-5-2 22:38 编辑 
  1. @echo off&title by Hanyeguxing QQ:515187266&set #1=1

  2. :start

  3. setlocal enabledelayedexpansion&set/pn=请输入 1 - 10 之间的自然数:

  4. if %n%==1 goto:end

  5. for /l %%a in (2,1,%n%) do (

  6.     set a=!a!+1&set #%%a=%%a !a:~1!+1

  7.     if %%a gtr 2 (

  8.         set/a b=%%a-1,c=b-1&set #%%a=!#%%a! !b!+1

  9.         for /l %%b in (2,1,!c!) do (

  10.             set/a d=%%a-%%b

  11.             for %%c in (!#%%b!) do for /f "tokens=1* delims=+" %%d in ("%%c") do if %%d leq !d! set #%%a=!#%%a! !d!+%%c

  12. )))

  13. :end

  14. for %%a in (!#%n%!) do echo;%%a

  15. pause&cls&endlocal&goto:start
复制代码
作者: caruko    时间: 2011-5-2 21:24

一个递归算法 =.=
作者: hanyeguxing    时间: 2011-5-2 21:56

本帖最后由 hanyeguxing 于 2011-5-2 22:21 编辑

1# yangfengoo 
  1. #1=1

  2. #2=2 1+1

  3. #3=3 1+1+1 2+1

  4. #4=4 1+1+1+1 3+1 2+2 2+1+1

  5. #5=5 1+1+1+1+1 4+1 3+2 3+1+1 2+1+1+1 2+2+1

  6. #6=6 1+1+1+1+1+1 5+1 4+2 4+1+1 3+3 3+1+1+1 3+2+1 2+1+1+1+1 2+2+2 2+2+1+1

  7. #7=7 1+1+1+1+1+1+1 6+1 5+2 5+1+1 4+3 4+1+1+1 4+2+1 3+1+1+1+1 3+3+1 3+2+2 3+2+1+1 2+1+1+1+1+1 2+2+1+1+1 2+2+2+1

  8. #8=8 1+1+1+1+1+1+1+1 7+1 6+2 6+1+1 5+3 5+1+1+1 5+2+1 4+4 4+1+1+1+1 4+3+1 4+2+2 4+2+1+1 3+1+1+1+1+1 3+3+2 3+3+1+1 3+2+1+1+1 3+2+2+1 2+1+1+1+1+1+1 2+2+1+1+1+1 2+2+2+2 2+2+2+1+1
复制代码
看一下数列规则：
#1到#8即是变量名，也是被分解的数字。
规则：所有分解式必须从大到小排列，这样用以解决重复问题
当n=1时，直接#1=1
当n大于1时，前两列分别是n和n个1相加
当n大于2时，第三列是（n-1）+1
将前三列单独运算，以加快运算速度
当n大于3时，其他的列有一个特征，即分解为m1+m2，m1为2到n-2。而m2为#m2，即将m2做为一个分解数插入，并判断第一个数字是否大于m1，大于则过滤。
例如，n为5时，前三列分别是 5 1+1+1+1+1 4+1
然后分解为3+2和2+3
3+2时，扩展#2的分解2 1+1，获得3+2 3+1+1
2+3时，扩展#3的分解3 1+1+1 2+1，因为3大于2，过滤，获得2+1+1+1 2+2+1


所以，求n的分解式，就是对1到n进行树形递归。
作者: yangfengoo    时间: 2011-5-3 13:54

我最先也是想递归，但是逻辑思维差点，想不明白。
现在我想用for嵌套循环试试。类似上个帖子的思路



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