赞
踩
给定三个正整数m,n,s问从1到m这m个数里面取n个不同的数,使它们和是s,有多少种取法
输入
多组数据
输入的第一行是整数t,表示有t组数据
此后有t行,每行是一组数据
每组数据就是三个正整数,m,n, s ( n <= 10,s <= 20)
输出
对每组数据,输出答案
样例输入
5 13 4 20 12 5 18 1 1 1 1 2 1 119 3 20
样例输出
22 3 1 0 24
提示
用函数ways(m,n,s)表示 从1到m这m个数里面取n个不同的数,使它们和是s的取法总数
显然,必须取m个数,不能不取(除非m == 0)
1) 考虑如果 m > s, 问题可以等价于什么?
2) 对于m<= s的情况,把所有的取法分成两类:
第一类: 取m。则取m后,剩下的问题变成什么?
第二类: 不取m,那么剩下的问题变成什么?
3) 注意边界条件(即递归终止条件,即不需要递归的条件)
边界条件一般是 n,m,s = 0, = 1 之类的情况。
初探递归的心得:先做一步,然后想象极端条件,写出边界的情况
- def ways(a,b,c):
- if a > c:
- return ways(c, b, c)
- if b == 0 and c == 0:
- return 1
- elif a == 0 or c == 0:
- return 0
- else:
- return ways(a-1,b-1,c-a)+ways(a-1,b,c)
-
- n=int(input())
- t=''
- for i in range(n):
- s=input().split()
- m,n,s=int(s[0]),int(s[1]),int(s[2])
- t=t+str(ways(m, n, s))+'\n'
- print(t)
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。