Python算法100例-2.11 换分币

`完整源代码项目地址，关注博主私信'源代码'后可获取`

1.问题描述
2.问题分析
3.算法设计
4.确定程序框架
5.完整的程序
6.运行结果

1．问题描述

将5元的人民币兑换成1元、5角和1角的硬币，共有多少种不同的兑换方法。

2．问题分析

根据该问题的描述，可将该问题抽象为一个不定方程。

设变量x、y和z分别代表兑换的1元、5角和1角的硬币所具有的钱数（角），则由题目的要求，可得到如下的方程：

x+y+z=50

其中，x为兑换的1元硬币钱数，其可能的取值为{0,10,20,30,40,50}；y为兑换的5角硬币钱数，其可能的取值为{0,5,10,15,20,25,30,35,40,45,50}；z为兑换的1角硬币钱数，其可能的取值为{0,1,…50}。

3．算法设计

在问题分析中，我们得到了一个不定方程，显然该不定方程会有多组解。根据题意可知x、y和z的可能取值，将它们所有可能取值的组合代入方程中，能使该方程成立的那些解即为该问题的解。

`为实现该功能，需要使用三个嵌套的for循环语句。`

4．确定程序框架

程序流程图如图所示。

在这里插入图片描述

5．完整的程序

根据上面的分析，编写程序如下：

%%time
# 换分币

if __name__=="__main__":
    # 变量x、y和z分别代表兑换的1元、5角和1角的硬币所具有的钱数（角）
    count = 0                                                               # 计数器
    print("可能的兑换方法如下：")
    # x 为兑换的1元硬币钱数，可能的取值为{0,10,20,30,40,50}
    for x in range(0, 50+1, 10):
        # y为5角硬币钱数，其取值为{0,5,10,15,20,25,30,35,40,45,50}
        for y in range(0, 50-x+1, 5):
            # z为1角硬币钱数，其取值为{0,1,...50}
            for z in range(0, 50-x-y+1, 1):
                if(x + y + z == 50):
                    count += 1
                    if count % 3 == 0:              # 每3列一行
                        print(count, end="   ")
                        print("10*%d+5*%d+1*%d \t" % (x // 10, y // 5, z))
                    else:
                        print(count, end=" ")
                        print("10*%d+5*%d+1*%d \t" % (x // 10, y // 5, z), end=" ")

可能的兑换方法如下：
1 10*0+5*0+1*50 	 2 10*0+5*1+1*45 	 3   10*0+5*2+1*40 	
4 10*0+5*3+1*35 	 5 10*0+5*4+1*30 	 6   10*0+5*5+1*25 	
7 10*0+5*6+1*20 	 8 10*0+5*7+1*15 	 9   10*0+5*8+1*10 	
10 10*0+5*9+1*5 	 11 10*0+5*10+1*0 	 12   10*1+5*0+1*40 	
13 10*1+5*1+1*35 	 14 10*1+5*2+1*30 	 15   10*1+5*3+1*25 	
16 10*1+5*4+1*20 	 17 10*1+5*5+1*15 	 18   10*1+5*6+1*10 	
19 10*1+5*7+1*5 	 20 10*1+5*8+1*0 	 21   10*2+5*0+1*30 	
22 10*2+5*1+1*25 	 23 10*2+5*2+1*20 	 24   10*2+5*3+1*15 	
25 10*2+5*4+1*10 	 26 10*2+5*5+1*5 	 27   10*2+5*6+1*0 	
28 10*3+5*0+1*20 	 29 10*3+5*1+1*15 	 30   10*3+5*2+1*10 	
31 10*3+5*3+1*5 	 32 10*3+5*4+1*0 	 33   10*4+5*0+1*10 	
34 10*4+5*1+1*5 	 35 10*4+5*2+1*0 	 36   10*5+5*0+1*0 	
CPU times: user 1.21 ms, sys: 65 µs, total: 1.27 ms
Wall time: 1.11 ms