[已解决]Python：每日一题 310

zltzlt

今天的题目：

给定两个整数 n 和 k，将整数 n 分成 k 份（分成的所有整数加起来等于 n），且每份不能为 0（不考虑顺序），求有多少种不同的分法。

示例 1：

输入：n = 7，k = 3
输出：4
解释：四种分法为：1 1 5、1 2 4、1 3 3、2 2 3（1 1 5、1 5 1、5 1 1 被认为是相同的分法）。

欢迎大家一起答题！

最佳答案

月排行榜 / 总排行榜

Croper

2020-1-19 22:59:44

不用递归的：

1. def func310(n,k):
   
2.     if (k==1): return 1
   
3.     n-=k-1
   
4.     l=[1]*n
   
5.     for i in range(k-2):
   
6.         l=[sum(l[j::i+2]) for j in range(n)]
   
7.     return sum(l[::k])

复制代码

跳转到最佳答案楼层

Croper

先来个递归的

1. def func310(n,k):
   
2.     d={}
   
3.     def func(n,k):
   
4.         if (k==1):
   
5.             return 1
   
6.         if (not (n,k) in d.keys()):
   
7.             ret=0
   
8.             imax=n//k+1
   
9.             for i in range(imax):
   
10.                 ret+=func(n-k*i,k-1)
    
11.                 d[(n,k)]=ret
    
12.         return d[(n,k)]
    
13.     return func(n-k,k)

复制代码

冬雪雪冬

没有好的思路，先写个笨的方法。

1. import itertools as it
   
2. def func(n, k):
   
3.     x = [range(1, n // 2  + 1) for i in range(k - 1)]
   
4.     y = it.product(*x)
   
5.     z = [list(i) + [n - sum(i)] for i in y if sum(i) < n]
   
6.     return len(set(map(lambda x: tuple(sorted(x)), z)))

复制代码

Croper

不用递归的：

1. def func310(n,k):
   
2.     if (k==1): return 1
   
3.     n-=k-1
   
4.     l=[1]*n
   
5.     for i in range(k-2):
   
6.         l=[sum(l[j::i+2]) for j in range(n)]
   
7.     return sum(l[::k])

复制代码

阴阳神万物主

默默擦干地板。

1. def solve(n,k):
   
2.     num = [1 for i in range(k-1)]+[n-k+1]
   
3.     res = 1
   
4.     i = 1
   
5.     while i < k:
   
6.         d = (num[i]-num[i-1])//2
   
7.         #print('调试',i,d,num,res)
   
8.         if d:
   
9.             res += d
   
10.             num[i-1] += d
    
11.             num[i] -= d
    
12.             i = 1
    
13.             continue
    
14.         i += 1
    
15.     return res
    
16. if __name__ == '__main__':
    
17.     print('示例1 输出：',solve(7,3))

复制代码

fan1993423

Croper 发表于 2020-1-19 22:39
先来个递归的

不太清楚原理

cool8517189

请问考虑负数吗？另外分成的k份整数是否可以为负？谢谢！

zltzlt

cool8517189 发表于 2020-1-20 02:40
请问考虑负数吗？另外分成的k份整数是否可以为负？谢谢！

不可以

阴阳神万物主

cool8517189 发表于 2020-1-20 02:40
请问考虑负数吗？另外分成的k份整数是否可以为负？谢谢！

要是考虑负数的话，无论输入什么，只要返回一个正无穷就好了呀。

godfishs

1. def fun310(n,k,begin = 1):
   
2.     if k == 1:
   
3.         return 1
   
4.     else:
   
5.         re = 0
   
6.         for i in range(begin,(n//k)+1):
   
7.             re += fun310(n-i,k-1,i)
   
8.         return re
   
9.         
   
10. if __name__ == '__main__':
    
11.     print(fun310(7,3))

复制代码

TJBEST

很惭愧，不是递归我写不出，但是k太大就超过了迭代次数。我再试试能不能把程序换成非迭代的等价程序。

1. def fun310(n,k):
   
2.     def inner(p,premax,k):
   
3.         if k > 2:
   
4.             tempmax = p // k
   
5.             for i in range(premax,(tempmax + 1)):
   
6.                 inner(p-i,i,k-1)
   
7.         else:
   
8.             tempmax = p//2
   
9.             count = tempmax - premax + 1
   
10.             res[0] = res[0] + count
    
11.     p = n - k
    
12.     if k == 0 or p < 0:
    
13.         return 0
    
14.     if k == 1:
    
15.         return 1
    
16.     res = [0]#统计
    
17.     inner(p,0,k)
    
18.     return res[0]

复制代码

zltzlt

冬雪雪冬 发表于 2020-1-19 22:50
没有好的思路，先写个笨的方法。

输入 n = 100，k = 5 超时。

zltzlt

阴阳神万物主 发表于 2020-1-19 23:08
默默擦干地板。

解答错误

输入：n = 20，k = 4
输出：22
预期结果：64

776667

1. from itertools import product
   
2. 
   
3. def fun310(n,k):
   
4.     result = []
   
5.     list_n = [i for i in range(1,n+1)]
   
6.     list_x = [sorted(i) for i in product(list_n,repeat=k) if sum(i) == n]
   
7.     for i in list_x:
   
8.         if i not in result:
   
9.             result.append(i)
   
10.     return len(result)

复制代码

Croper

所以我那个不用递归的花了多久呢？

zltzlt

Croper 发表于 2020-1-20 12:59
所以我那个不用递归的花了多久呢？

大概 70 ms

kinkon

Croper 发表于 2020-1-19 22:59
不用递归的：

大佬，能不能解释下代码，被绕晕了，求教

TJBEST

楼主 我写在 11楼

Croper

kinkon 发表于 2020-1-20 14:19
大佬，能不能解释下代码，被绕晕了，求教

动态规划。

首先，这道题不妨考虑为每份最小为0，但整数其实是n-k。这两者是完全等价的。那么以下均用n代替n-k，且认为每份最小为0.

其次，既然有序数列，不妨认为其从大到小排列。

然后，如果不要求分完，考虑把n分为k组，剩余m个的情况，此时的分法数目为f(m，k).
显然，k=1时，f(0，k)到f(n，k)均为1.

k不等于1时，如果最后一个值为i，那么前面的值都大于等于i。所以此时的分法数量为f(m+i*k,k-1)
考虑i最小为0，最大为(n-m)//k;
所以状态转移方程为
f(m,k)=f(m,k-1)+f(m+1*k,k-1)+f(m+2*k,k-1)+...+f(m+(n-m)//k*k,k-1)
        =sum(f(j,k-1) for j in range(m,n,k))
然后化简一下，把f()弄成列表，就是答案了

kinkon

Croper 发表于 2020-1-20 15:24
动态规划。

首先，这道题不妨考虑为每份最小为0，但整数其实是n-k。这两者是完全等价的。那么以下均 ...

感谢大佬回答，我再细细品味下