用python實(shí)現(xiàn)整數(shù)劃分（遞歸）

rencoxf4ever

題目如下：
整數(shù)的分劃問題。
如，對于正整數(shù)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
現(xiàn)在的問題是，對于給定的正整數(shù)n,編寫算法打印所有劃分。
用戶從鍵盤輸入 n （范圍1~10）
程序輸出該整數(shù)的所有劃分。


小弟是自學(xué)編程的菜鳥 昨天看到這個(gè)東西自己想出了遞歸的算法 但是發(fā)現(xiàn)自己對語言的掌控能力太差 編了好幾次都不成功 希望大神有空看看

我找到一個(gè)類似我的遞歸算法的程序 但是這個(gè)程序明顯混亂了 大家可以參考下http://www.itqun.net/content-detail/227063.html

我已經(jīng)嘗試了一天了 實(shí)在是弄不出來 求靠大神了 最好能講一講您對算法怎么用語言實(shí)現(xiàn)的理解

iamkey9

這個(gè)？
http://72891.cn/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)

復(fù)制代碼