一个算法修正:百钱买百鸡问题

问题是:
公元钱五世纪,我国古代数学家张丘建在《算经》一书中提出了“百鸡问题”:
鸡翁一值钱五,鸡母一值钱三,鸡雏三值钱一。百钱买百鸡,问鸡翁、鸡母、鸡雏各几何?

以下是 安全矩阵站长 fleshwound 的代码:

#include
using namespace std;

int main()
{
  int cocks, hens, chicks;
  cocks = 0;
  int times = 1;
  
  while(cocks <= 19)
  {
    hens = 0;
    while(hens <= 33)
    {
        chicks = 100 - cocks - hens;
        if(5*cocks + 3*hens + chicks/3 == 100
        && chicks%3 ==0 )        
          cout << "times = " << times++ << endl
              << "cocks = " << cocks   << " "
              << "hens = " << hens   << " "
              << "chicks= " << chicks << " "
              << endl;        
        
        hens = hens+1;
    }
    cocks = cocks+1;
  }
  
  getchar();
  return 0;
}


我回帖,进行一些修改:

#include

using namespace std;

int main(int argc,char** argv)
{
int cocks, hens, chicks;
cocks = 0;
int times = 1;

long N=atol(argv[1]);
int flags=atoi(argv[2]);
int cocksmax;
if(flags)
    cocksmax=(N-(N-N/5)/3)/5; //进行优化
else
    cocksmax=N/5; //不进行优化

while(cocks <= cocksmax)
{
  hens = 0;
  while(hens <= N/3)
  {
    chicks = N - cocks - hens;
    if(5*cocks + 3*hens + chicks/3 == N && chicks%3 ==0 ) times++;
/*       cout << "times = " << times++ << endl
        << "cocks = " << cocks   << " "
        << "hens = " << hens   << " "
        << "chicks= " << chicks << " "
        << endl;    
    */
    hens++;
  }
  cocks++;
}
    cout<<"times="<
return 0;
}


具体的想法是:

思路还没有理清,主要是想法是:

1、鸡翁一值钱五,100钱最多是20,但很多显然不可能达到100只的条件,所以这个值肯定要小于20
2、做个假设,如果购买了20只鸡翁,那么最有可能的是剩下的80只要用鸡雏填补,才能达到100只的条件,但此时又超出了100钱条件
3、在2的情况下,是否可以做如下假定:
  A、先从100里扣除80只鸡雏所用的钱数,然后再用此数计算购买鸡翁的最大数,即:(100-80/3)/5
    这样范围就从原来的100/5=20缩小到了15
  B、如A,当鸡翁缩小到15,80为鸡雏时,还剩下5只,而钱数则近空;
  C、所以推论,鸡翁的最大值是不会超出15的。


都是引用原先的发帖,没有做改动!
发到博客,以作记念与收藏!