迭代算法与递归算法的概念及区别(4)时间:2009-01-25 本站整理
作为对比，下面以同样的解题思想，考虑非递归的程序解。为了提高找解速度，程序不是简单地逐一生成所有候选解，而是从每个物品对候选解的影响来形成值得进一步考虑的候选解，一个候选解是通过依次考察每个物品形成的。对物品i的考察有这样几种情况：当该物品被包含在候选解中依旧满足解的总重量的限制，该物品被包含在候选解中是应该继续考虑的;反之，该物品不应该包括在当前正在形成的候选解中。同样地，仅当物品不被包括在候选解中，还是有可能找到比目前临时最佳解更好的候选解时，才去考虑该物品不被包括在候选解中;反之，该物品不包括在当前候选解中的方案也不应继续考虑。对于任一值得继续考虑的方案，程序就去进一步考虑下一个物品。
【程序】
以下是引用片段：
#include
#defineN100
doublelimitW;
intcop[N];
structele{doubleweight;
doublevalue;
}a[N];
intk,n;
struct{int;
doubletw;
doubletv;
}twv[N];
voidnext(inti,doubletw,doubletv)
{twv.=1;
twv.tw=tw;
twv.tv=tv;
}
doublefind(structele*a,intn)
{inti,k,f;
doublemaxv,tw,tv,totv;
maxv=0;
for(totv=0.0,k=0;k
totv+=a[k].value;
next(0,0.0,totv);
i=0;
While(i>=0)
{f=twv.;
tw=twv.tw;
tv=twv.tv;
switch(f)
{case1:twv.++;
if(tw+a.weight
if(i
{next(i+1,tw+a.weight,tv);
i++;
}
else
{maxv=tv;
for(k=0;k
cop[k]=twv[k].!=0;
}
break;
case0:i--;
break;
default:twv.=0;
if(tv-a.value>maxv)
if(i
{next(i+1,tw,tv-a.value);
i++;
}
else
{maxv=tv-a.value;
for(k=0;k
cop[k]=twv[k].!=0;
}
break;
}
}
returnmaxv;
}
voidmain()
{doublemaxv;
printf(“输入物品种数
”);
scanf((“%d”,&n);
printf(“输入限制重量
”);
scanf(“%1f”,&limitW);
printf(“输入各物品的重量和价值
”);
for(k=0;k
scanf(“%1f%1f”,&a[k].weight,&a[k].value);
maxv=find(a,n);
printf(“
选中的物品为
”);
for(k=0;k
if(option[k])printf(“%4d”,k+1);
printf(“
总价值为%.2f
”,maxv);
}
递归的基本概念和特点
程序调用自身的编程技巧称为递归( recursion)。
一个过程或函数在其定义或说明中又直接或间接调用自身的一种方法，它通常把一个大型复杂的问题层层转化为一个与原问题相似的规模较小的问题来求解，递归策略只需少量的程序就可描述出解题过程所需要的多次重复计算，大大地减少了程序的代码量。递归的能力在于用有限的语句来定义对象的无限集合。用递归思想写出的程序往往十分简洁易懂。
一般来说，递归需要有边界条件、递归前进段和递归返回段。当边界条件不满足时，递归前进;当边界条件满足时，递归返回。
注意：
(1) 递归就是在过程或函数里调用自身;
2) 在使用递增归策略时，必须有一个明确的递归结束条件，称为递归出口。
本文来自编程入门网：http://www.bianceng.cn/Programming/sjjg/200901/11200_4.htm
迭代算法与递归算法的概念及区别(4)时间:2009-01-25 本站整理
作为对比，下面以同样的解题思想，考虑非递归的程序解。为了提高找解速度，程序不是简单地逐一生成所有候选解，而是从每个物品对候选解的影响来形成值得进一步考虑的候选解，一个候选解是通过依次考察每个物品形成的。对物品i的考察有这样几种情况：当该物品被包含在候选解中依旧满足解的总重量的限制，该物品被包含在候选解中是应该继续考虑的;反之，该物品不应该包括在当前正在形成的候选解中。同样地，仅当物品不被包括在候选解中，还是有可能找到比目前临时最佳解更好的候选解时，才去考虑该物品不被包括在候选解中;反之，该物品不包括在当前候选解中的方案也不应继续考虑。对于任一值得继续考虑的方案，程序就去进一步考虑下一个物品。
【程序】
以下是引用片段：
#include
#defineN100
doublelimitW;
intcop[N];
structele{doubleweight;
doublevalue;
}a[N];
intk,n;
struct{int;
doubletw;
doubletv;
}twv[N];
voidnext(inti,doubletw,doubletv)
{twv.=1;
twv.tw=tw;
twv.tv=tv;
}
doublefind(structele*a,intn)
{inti,k,f;
doublemaxv,tw,tv,totv;
maxv=0;
for(totv=0.0,k=0;k
totv+=a[k].value;
next(0,0.0,totv);
i=0;
While(i>=0)
{f=twv.;
tw=twv.tw;
tv=twv.tv;
switch(f)
{case1:twv.++;
if(tw+a.weight
if(i
{next(i+1,tw+a.weight,tv);
i++;
}
else
{maxv=tv;
for(k=0;k
cop[k]=twv[k].!=0;
}
break;
case0:i--;
break;
default:twv.=0;
if(tv-a.value>maxv)
if(i
{next(i+1,tw,tv-a.value);
i++;
}
else
{maxv=tv-a.value;
for(k=0;k
cop[k]=twv[k].!=0;
}
break;
}
}
returnmaxv;
}
voidmain()
{doublemaxv;
printf(“输入物品种数
”);
scanf((“%d”,&n);
printf(“输入限制重量
”);
scanf(“%1f”,&limitW);
printf(“输入各物品的重量和价值
”);
for(k=0;k
scanf(“%1f%1f”,&a[k].weight,&a[k].value);
maxv=find(a,n);
printf(“
选中的物品为
”);
for(k=0;k
if(option[k])printf(“%4d”,k+1);
printf(“
总价值为%.2f
”,maxv);
}
递归的基本概念和特点
程序调用自身的编程技巧称为递归( recursion)。
一个过程或函数在其定义或说明中又直接或间接调用自身的一种方法，它通常把一个大型复杂的问题层层转化为一个与原问题相似的规模较小的问题来求解，递归策略只需少量的程序就可描述出解题过程所需要的多次重复计算，大大地减少了程序的代码量。递归的能力在于用有限的语句来定义对象的无限集合。用递归思想写出的程序往往十分简洁易懂。
一般来说，递归需要有边界条件、递归前进段和递归返回段。当边界条件不满足时，递归前进;当边界条件满足时，递归返回。
注意：
(1) 递归就是在过程或函数里调用自身;
2) 在使用递增归策略时，必须有一个明确的递归结束条件，称为递归出口。
本文来自编程入门网：http://www.bianceng.cn/Programming/sjjg/200901/11200_4.htm