[数值计算] [已解决]批处理怎样进行整数的分划？

yangfengoo

在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

术业有专攻，楼主是专攻排列组合的吧，呵呵。。。

yangfengoo

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

hanyeguxing

@echo off&title by Hanyeguxing QQ:515187266&set #1=1
:start
setlocal enabledelayedexpansion&set/pn=请输入 1 - 10 之间的自然数:
if %n%==1 goto:end
for /l %%a in (2,1,%n%) do (
    set a=!a!+1&set #%%a=%%a !a:~1!+1
    if %%a gtr 2 (
        set/a b=%%a-1,c=b-1&set #%%a=!#%%a! !b!+1
        for /l %%b in (2,1,!c!) do (
            set/a d=%%a-%%b
            for %%c in (!#%%b!) do for /f "tokens=1* delims=+" %%d in ("%%c") do if %%d leq !d! set #%%a=!#%%a! !d!+%%c
)))
:end
for %%a in (!#%n%!) do echo;%%a
pause&cls&endlocal&goto:start
复制代码

caruko

一个递归算法 =.=

hanyeguxing

1# yangfengoo

#1=1
#2=2 1+1
#3=3 1+1+1 2+1
#4=4 1+1+1+1 3+1 2+2 2+1+1
#5=5 1+1+1+1+1 4+1 3+2 3+1+1 2+1+1+1 2+2+1
#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 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 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

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