1.青蛙跳台阶，一共n阶，可以一次跳一阶或两阶，一共多少种跳法。
def sumWays(n):
if n==0 or n==1:
return 1
else:
return(sumWays(n-1)+sumWays(n-2))
if __name__ == '__main__':
for x in range(1,10):
print(sumWays(x))
result:
weehaaMBA:Downloads huangyong$ python3 h1.py
1
2
3
5
8
13
21
34
55
这应该是最简单的递归了。
递归，先列出n=1,2,3的前三种情况，便于分析。
2.当上题中可以跳1～n阶时
f(1)=1
f(2)=2=f(1)+f(0)
f(3)=f(2)+f(1)+f(0)=4
可以推出 f(n)=2*f(n-1)
def sumWays(n):
if n==0 or n==1:
return 1
else:
return 2*sumWays(n-1)
if __name__ == '__main__':
for x in range(1,10):
print(sumWays(x))
result:
weehaaMBA:Downloads huangyong$ python3 h1.py
1
2
4
8
16
32
64
128
256
硬币兑换，给定一些面值的硬币和一个具体钱数，问少能用几个硬币兑换。例如给定硬币面值coins=[1,2,5] amount=11，return 3（5+5+1）02:coins=[2] amount =3，return -1.
非递归解法：
# coins = [1,2,5]
# amount = 11
# n1 = amount//coins[2]
# n2 = (amount%coins[2])//coins[1]
# n3 = (amount%coins[2]%coins[1])//1
# print(n1+n2+n3)
# 换硬币
def exchangeCoins(coins,amount):
res = 0
if len(coins)==0 or amount<coins[0]:
return -1
for i,s in enumerate(coins):
res += amount//coins[-1-i]
amount = amount%coins[-1-i]
if amount != 0:
return -1
return res
if __name__ == '__main__':
print(exchangeCoins([1,2,5],14))
