简单记录

【转载】关于三元一次方程组程序优化问题

时间 ：2016-9-30  作者： thtomatic  分类： php笔记   评论: [ 0 ] 条  浏览: [ 1056 ] 次

如题：
 今有2匹马、3头牛和4只羊,它们各自的总价都不满10000文钱(古时的货币单位) 。如果2匹马加上1头牛,或者3 头牛加上1只羊,或者4只羊加上1匹马,那么它们各自的总 价都正好是10000文钱了。问：马、牛、羊的单价各是多少文钱？ 
一般思路：利用三层for循环配合if匹配出马，牛，羊的数量关系，主体思路如下：
 for（马=1，马<10000,马++）
{
     for(牛=1，牛<10000,牛++)
    {
          for（羊=1，羊<10000,羊++）
            {
                    if(条件1&&条件2&&条件3){        
                        输出 马，牛，羊；
            }
      }
}
但是要意识到一个问题：数据结构中提到：算法的执行时间与该算法基本操的重复执行的次数成正比。以上算法中，利用了三层for循环，程序复杂度为O（10000^3），显然计算机处理这些数据会增大运算量，并不是最优算法，故可将如上代码做优化：
 for（马=1，马<10000,马++）
{
     for(牛=1，牛<10000,牛++)
    {
          for（羊=1，羊<10000,羊++）
            {
                    if(条件1&&条件2&&条件3){        
                        输出 马，牛，羊；
            }
      }
}
以最内层for为基准，判断条件中找到，样与牛的数量关系表达式，那么在每次循环中牛+1的同时与其关联的表达式，羊也会顺次增加，依次类推，第二层循环中找到牛和马的数量关系，这样就可以利用马的循环+1，依次定位出牛、羊每次增加的个数，对于此题。共有每只马的价格不大于5000，那么我们得到的程序和结果如下：
#include "iostream"

int main()
{
int a=1, b=1, c=1;
for(a=1;a<=5000;a++)
{
b=10000-2*a;
c=10000-3*b;
if((10000==2*a+b)&&10000==(3*b+c)&&10000==(4*c+a))
{
std::cout<<'a'<<'='<<a<<std::endl<<'b'<<'='<<b<<std::endl<<'c'<<'='<<c<<std::endl;

}
}
system("pause");
return 0;
}
//>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>
a=3600;
b=2800;
c=1600;

本文转自：午时已到

• 赞0
• 
• 踩0