c程序实现一道简单的算法题

在别人博客看到这样一道题：

有足够的1分，2分，5分硬币，请问有多少种方法拼出1快

我的思路：从需要多少个硬币想起，如果全用5分的，需要20个
全用1分的，需要100个

就是说，不管有多少种方法，需要的硬币数最多100，最少20

设需要 5分硬币数量为x , 2分为y, 1分为z , 用整数i 从20到100循环，
x+y+z = i
5x+2y+z=100

这是三元一次方程，但是只有2个等式，不能解，所以，再嵌套一个循环， x 用j表示从0到20 循环，这样就可以解了，
转换为
x+y+z = i
5x+2y+z=100
1x+0y+0z=j

那么，问题就转换为，怎么用程序解三元一次方程，解三元一次方程网上有现成的例子

全部代码如下：

#include <stdio.h>
#include <stdlib.h>

void Calculate3yuan1ci(int a1,int b1,int c1,int d1,int a2,int b2,int c2,int d2 ,int a3,int b3,int c3,int d3,int *ret)
{
    long  d,e,f,g;
    float x,y,z;

    d=a1*b2*c3+b1*c2*a3+c1*a2*b3-c1*b2*a3-b1*a2*c3-a1*c2*b3;
    e=d1*b2*c3+b1*c2*d3+c1*d2*b3-c1*b2*d3-b1*d2*c3-d1*c2*b3;
    f=a1*d2*c3+d1*c2*a3+c1*a2*d3-c1*d2*a3-d1*a2*c3-a1*c2*d3;
    g=a1*b2*d3+b1*d2*a3+d1*a2*b3-d1*b2*a3-b1*a2*d3-a1*d2*b3;

    x=e/d;
    y=f/d;
    z=g/d;

    if((d==0)||(x<0)||(y<0)||(z<0))
     return;
    else {
     ret[0]=x;
     ret[1]=y;
     ret[2]=z;

    }

    //return NULL;
}

int main()
{
  int i,j;
  int iResult[3]={NULL};
    //int iResult[3];
    
  for(i=20;i<=100;i++)
  {
    for(j=0;j<=20;j++)
    {
      //*iResult=NULL;
      Calculate3yuan1ci(1,1,1,i,5,2,1,100,1,0,0,j,iResult);
      //Calculate3yuan1ci(1,1,1,i,5,2,1,100,1,0,0,j,iResult);
      if(iResult[0]==NULL)
        continue;
      else  {
        printf("yingbi= %d     5 fen = %d     2 fen = %d     1 fen = %d \n",i,iResult[0],iResult[1],iResult[2]);
        iResult[0]=NULL;
        iResult[1]=NULL;
        iResult[2] =NULL;
        break;

      }
    }

    
  }


  getchar();
  return 0;


}

解方程的函数来自 https://wenku.baidu.com/view/596bac0f6c85ec3a87c2c559.html

PS , 解决问题后再回头看原博主的答案，说实话没看懂，云山雾罩，不知所云：

[题目]有足够量的2分、5分、1分硬币，请问凑齐1元钱有多少种方法？

此题乍看上去，只会觉得完全无法入手，但是按照由简至繁的思路，我们可以先考虑极端简单的情况，假如把问题规模缩小成:有足够量的1分硬币，请问凑齐1分钱有多少种方法？毫无疑问，答案是1。

得到这一答案之后，我们可以略微扩大问题的规模：有足够量的1分硬币，凑齐2分钱有多少种方法？凑齐n分钱有多少种方法？答案仍然是1

接下来，我们可以从另一个角度来扩大问题，有足够量的1分硬币和2分硬币，凑齐n分钱有多少种方法？这时我们手里已经有了有足够量的1分硬币，凑齐任意多钱都只有1种方法，那么只用1分钱凑齐n-2分钱，有1种方法，只用1分钱凑齐n-4分钱，有1种方法，只用1分钱凑齐n-6分钱，有1种方法......

而凑齐这些n-2、n-4、n-6这些钱数，各自补上2分钱，会产生一种新的凑齐n分钱的方法，这些方法的总数+1，就是用1分硬币和2分硬币，凑齐n分钱的方法数了。

在面试时，立刻采用这种思路是一种非常有益的尝试，解决小规模问题可以让你更加熟悉问题，并且慢慢发现问题的特性，最重要的是给你的面试官正面的信号——立即动手分析问题比皱眉冥思苦想看起来好得多。

对于此题而言，我们可以很快发现问题的规模有两个维度：用a1-ak种硬币和凑齐n分钱，所以我们可以记做P(k,n)。当我们发现递归公式 P(k,n) = P(k-1,n - ak) + P(k-1,n - 2*ak) + P(k-1,n - 3*ak) ... ... 时，这个问题已经是迎刃而解了

通常由简至繁的思路，用来解决动态规划问题是非常有效的，当积累了一定量简单问题的解的时候，往往通向更高一层问题的答案已经摆在眼前了。

秒客网

c程序实现一道简单的算法题

相关文章