用python实现整数划分（递归）

rencoxf4ever

题目如下：
整数的分划问题。
如，对于正整数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）
程序输出该整数的所有划分。


小弟是自学编程的菜鸟 昨天看到这个东西自己想出了递归的算法 但是发现自己对语言的掌控能力太差 编了好几次都不成功 希望大神有空看看

我找到一个类似我的递归算法的程序 但是这个程序明显混乱了 大家可以参考下http://www.itqun.net/content-detail/227063.html

我已经尝试了一天了 实在是弄不出来 求靠大神了 最好能讲一讲您对算法怎么用语言实现的理解

iamkey9

这个？
http://bbs.chinaunix.net/viewthr ... ;page=1#pid15459271

iix

就是背包吧。
http://www.itnosh.com/2010/07/Project_Euler_76.html

1. # -*- coding: utf-8 -*-
   
2. """
   
3. @author: neo
   
4. """
   
5. tem={}
   
6. def Pe76(v, n):
   
7.     global tem
   
8.     if 1>=n or v==2:
   
9.         if (v, n) not in tem:
   
10.             tem[(v, n)]=n/2+1
    
11.             return n/2+1
    
12.         else:
    
13.             return tem[(v, n)]
    
14.     elif v==1:
    
15.         if (v, n) not in tem:
    
16.             tem[(v, n)]=1
    
17.             return 1
    
18.         else:
    
19.             return tem[(v, n)]
    
20.     elif v>n:
    
21.         if (v, n) not in tem:
    
22.             tem[(v, n)]=Pe76(n-1, n)+1
    
23.             return Pe76(n-1, n)+1
    
24.         else:
    
25.             return tem[(v, n)]
    
26.     else:
    
27.         if (v, n) not in tem:
    
28.             temp=sum([Pe76(v-1, n-v*x) for x in xrange(n/v+1)])
    
29.             tem[(v, n)]=temp
    
30.             return temp
    
31.         else:
    
32.             return tem[(v, n)]
    
33. 
    
34. print Pe76(99, 100)

复制代码