[新手上路]批处理新手入门导读[视频教程]批处理基础视频教程[视频教程]VBS基础视频教程[批处理精品]批处理版照片整理器
[批处理精品]纯批处理备份&还原驱动[批处理精品]CMD命令50条不能说的秘密[在线下载]第三方命令行工具[在线帮助]VBScript / JScript 在线参考
返回列表 发帖

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

本帖最后由 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)
        程序输出该整数的所有划分。
------------------------------------------------------------
答案在三楼
1

评分人数

    • hanyeguxing: 感谢给帖子标题标注[已解决]字样PB + 2

术业有专攻,楼主是专攻排列组合的吧,呵呵。。。
***共同提高***

TOP

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

TOP

本帖最后由 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
复制代码
1

评分人数

寒夜孤星:在没有说明的情况下,本人所有代码均运行在 XP SP3 下 (有问题请发贴,QQ临时会话已关闭)

TOP

一个递归算法 =.=

TOP

本帖最后由 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进行树形递归
寒夜孤星:在没有说明的情况下,本人所有代码均运行在 XP SP3 下 (有问题请发贴,QQ临时会话已关闭)

TOP

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

TOP

返回列表