python换硬币(理学院举办换硬币活动)

本文主要是介绍python换硬币(理学院举办换硬币活动)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

换硬币

时间限制: 1Sec 内存限制: 128MB

题目描述

理学院举办换硬币活动，假设有一个面值为N(1<=Ｎ<=10)的纸币，给定两种不同零钱：1元和2元，数目不限。如果把这张N元的纸币换成零钱，，一共有多少种不同的换法？
例如，面值为4的纸币一共有如下5种换法：
4=1+1+1+1
4=2+1+1
4=1+2+1
4=1+1+2
4=2+2
编程用递归的方法求解上述问题。

输入

只有一个数N，代表纸币面值

输出

输出一个数，代表所有不同的兑换方法的总数

样例输入

4

样例输出

5

解法1：模拟(暴力出奇迹)

N = int(input())
def dfs(N):if(N==0):return 1;count1 = 0count2 = 0if(N-1 >= 0):count1 = dfs(N - 1)if(N - 2 >= 0):count2 = dfs(N - 2)return count1 + count2
print(dfs(N))

解的答案是:[1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377]

我们发现规律,后一项的值等于前2项之和。
可以修改dfs()函数为:

def dfs(N):if N == 1:return 1if N == 2:return 2return dfs(N-1)+dfs(N-2)

解法2:带记忆的背包(效率提升)

N = int(input())
#data列表记录已经算出过的值，避免重复计算
data = [0]*1001
def dfs(N):#data为全局变量，记录下来修改过的data列表的值global dataif(data[N] != 0):return data[N]if(N == 1):return 1if(N == 2):return 2# 把算出来的值添加进data列表data[N] = dfs(N-1) + dfs(N-2)return dfs(N-1) + dfs(N-2)
print(dfs(N))

解法3:(动态规划—快到飞起)

状态转移方程:f(n) = f(n-1) + f(n-2)

N = int(input())
def dp(N):data = [0,1,2]for i in range(3,N + 1):data.append(data[i-1] + data[i-2])return data[N]
print(dp(N))

解法4:打表(oj得分神器，专治各种不服，时间复杂度O(1))

N = int(input())
data = [0, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946, 17711]
print(data[N])

这篇关于python换硬币(理学院举办换硬币活动)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---