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

wanting-for

1. def solve(A:int,k,num = 1):
   
2.     count = 0
   
3.     if k == 2:
   
4.         return A//2-num+1
   
5.     else:
   
6.         for i in range(num,A//2):
   
7.             if i * k > A:
   
8.                 break
   
9.             else:
   
10.                 count += solve(A-i,k-1,i)
    
11.     return count
    
12. print(solve(100,5))

复制代码

递归菜鸟用递归，真难受
还没想到不用递归有什么很好的办法

wanting-for

wanting-for 发表于 2020-1-20 15:53
递归菜鸟用递归，真难受
还没想到不用递归有什么很好的办法

我这程序有bug，如果是n=4,k=4,会输出0

sillybibibi

from itertools import product

def fun310(n,k):
    result = []
    list_n = [i for i in range(1,n+1)]
    list_x = [sorted(i) for i in product(list_n,repeat=k) if sum(i) == n]
    for i in list_x:
        if i not in result:
            result.append(i)
    return len(result)

fan1993423

wanting-for 发表于 2020-1-20 15:53
递归菜鸟用递归，真难受
还没想到不用递归有什么很好的办法

能说一下数学原理吗？为什么返回的A//2-num+1以及循环里为什么（num,A//2）

wanting-for

fan1993423 发表于 2020-1-20 23:42
能说一下数学原理吗？为什么返回的A//2-num+1以及循环里为什么（num,A//2）

1：每次比作两个数字，所以我假定前边的数字要比后边的小，而（num，A//2）的意思就是现在这个数字要比num大，而且要比后边的数字的总和小!
2：k ==2 时执行A//2-num+1，现在是两个数字，前边的比后边的小，例如现在A是7，共有两个数字，前边的数字只有1、2、3，这三种可能，即A//2-num+1就是前边的数字的个数，前边的数字的个数，正好间接反映了后边的个数，即现在return的就是在前边那些固定条件下所有的可能!
3：解释的比较绕口，可能会有些难以理解，你可以写一下在n=10，k=5的时候的所有的可能，不过写的顺序要前边小，后边大！
4.我是一个夜猫子

fan1993423

wanting-for 发表于 2020-1-21 00:53
1：每次比作两个数字，所以我假定前边的数字要比后边的小，而（num，A//2）的意思就是现在这个数字要比nu ...

好像懂了

wanting-for

fan1993423 发表于 2020-1-21 00:58
好像懂了

写一下，会理解的深一些

fan1993423

wanting-for 发表于 2020-1-21 01:01
写一下，会理解的深一些

思路我一看还是大体明白，对于(num,A//2)其实我的疑问是，你既然说要比后面数字小，比如7,那么后面数字4,5,6，但是range后面是取不到的，为什么不是A//2+1,而对于 A//2-num+1，这里为什么要多num和1，而至于if i*k>A这个判别式是怎么想的

wanting-for

fan1993423 发表于 2020-1-21 01:06
思路我一看还是大体明白，对于(num,A//2)其实我的疑问是，你既然说要比后面数字小，比如7,那么后面数字 ...

1：首先解释A//2-num+1：假定A=7，num=1！那么A//2就是3，而减num是为了确定num和A//2之间共有几个数字（包括num和A//2）即3-1+1 = 3！加num就是这个原因！
2：（num，A//2）和i*k>A是一起使用的，有一种情况就是当A=8，k=4，而有2,2,2,2，这是一种极限情况，这时候最前边的2就不能增加了，如果第一个数字为3，那么后边的数字是没法分配的，所以并不是单纯的小于那么简单，这里就是i*k>A这个判别式存在的原因，其实（num，A//2）这里换成（num，A//2+1）也是可以的，因为不合理的情况会经过判别式，然后退出！

fan1993423

wanting-for 发表于 2020-1-21 01:31
1：首先解释A//2-num+1：假定A=7，num=1！那么A//2就是3，而减num是为了确定num和A//2之间共有几个数字（ ...

完全懂了，谢谢

wanting-for

fan1993423 发表于 2020-1-21 14:58
完全懂了，谢谢

哈哈，谢谢咯

ouyunfu

1. def f310(n:int,k:int)->int:
   
2.     m=n-k
   
3.     def f(m,k,t):
   
4.         if k==1:
   
5.             return 1
   
6.         else:
   
7.             res=0
   
8.             for i in range(t,m//k+1):
   
9.                 res+=f(m-i,k-1,i)
   
10.             return res
    
11.     return f(m,k,0)
    
12. 
    
13. print(f310(20,4))

复制代码