C语言编程之换硬币

淩亂°似流年 2023-06-22 05:30 34阅读 0赞

### 现在有这样一道题。假设给你一分硬币，两分硬币，五分硬币共60枚。需要将它们兑换成100分的硬币，可以怎么换？ ###

而我们可以列出如下关系式  
**假设x,y,z分别为一分，两分，五分硬币则:**  
**x+y+z=60**  
**x+2y+5z=100**  
对于这道题我们应该不太陌生，而我们最常见的应该是用三重循环来解决问题，又因为其为三重循环则需要三个未知数：  
代码如下：

#include<stdio.h>
    int main(void)
    {
        
     int coin1,coin2,coin5;
     for(coin1=0;coin1<=60;coin1++)//一分硬币可以等于硬币总数最大值，不超过100分 
      for(coin2=0;coin2<=50;coin2++)//两分五分硬币数目最大不应超过钱数/其面额 
       for(coin5=0;coin5<=20;coin5++)//减少循环次数，降低其时间复杂度
       {
        
        if(coin1+coin2+coin5==60&&1*coin1+2*coin2+5*coin5==100)
        printf("一分硬币%d枚，两分硬币%d枚，五分硬币%d枚\n",coin1,coin2,coin5);
       } 
     return 0;
    }

而这也是暴力解法，三重循环则会使其时间复杂度为O(n3)，我们应降低其循环次数  
若用二重循环，则需要两个未知数，我们只需将以上关系式消去一个未知数，当然消去哪个都可以，(我消去的是x)在我们利用了加减消元法之后可以得到以下关系式：  
**y+4z=40**  
**最后再利用x=60-y-z,得到x即可**  
代码如下：

#include<stdio.h>
    int main(void)
    {
        
     int coin1,coin2,coin5;
     for(coin2=0;coin2<=50;coin2++)
       for(coin5=0;coin5<=20;coin5++)//减少循环次数，降低其时间复杂度
       {
        
        if(coin2+4*coin5==40)
        {
        
         coin1=60-coin2-coin5;
         printf("一分硬币%d枚，两分硬币%d枚，五分硬币%d枚\n",coin1,coin2,coin5);
        }
       } 
     return 0;
    }

而最后的优化就是时间复杂度最低的一重循环了，所以我们应想办法将其变为一个未知数代替的关系式，而这需要我们找寻其隐含的条件。  
我们可以将y,z变为关于x的关系式，即：  
由y+4z=40,x+y+z=60得  
**z=1/3(x-20)**  
**y=1/3(200-4x)**  
**而且y,z必须大于等于0则有20<=x<=50**  
梳理完毕，代码如下：

#include<stdio.h>
    int main(void)
    {
        
     int coin1,coin2,coin5;
     for(coin1=20;coin1<=50;coin1++)
          {
        
           coin5=(coin1-20)/3;
           coin2=(200-4*coin1)/3;
       if(coin1+coin2+coin5==60)
         printf("一分硬币%d枚，两分硬币%d枚，五分硬币%d枚\n",coin1,coin2,coin5);           
        }
     return 0;
    }

这就是换硬币循环的逐步优化了，总而言之就是几重循环需要几个未知数，最后只需寻找其潜在关系。这需要我们努力思考，fighting!