大学IT网 - 最懂大学生的IT学习网站! QQ资料交流群:367606806
当前位置:大学IT网 > C++技巧 > 什么是迭代跟递归算法?二者有什么区别?

什么是迭代跟递归算法?二者有什么区别?(4)

关键词:递归有什么区别算法迭代  阅读(1897) 赞(10)

[摘要]本文是对什么是迭代跟递归算法?二者有什么区别?的讲解,对学习C++编程技术有所帮助,与大家分享。

为了理解上述算法,特举以下实例。设有4件物品,它们的重量和价值见表:

物品 0 1 2 3

重量 5 3 2 1

价值 4 4 3 1

并设限制重量为7。则按以上算法,下图表示找解进程。由图知,一旦找到一个解,算法就进一步找更好的佳。如能判定某个查找分支不会找到更好的解,算法不会在该分支继续查找,而是立即终止该分支,并去调查下一个分支。

按上述算法编写函数和顺序如下:

【顺序】

以下是引用片段:
  # include
  # define N 100
  double limitW,totV,maxV;
  int option[N],cop[N];
  struct { double weight;
  double value;
  }a[N];
  int n;
  void find(int i,double tw,double tv)
  { int k;
  /*思索物品i包括在当前方案中的可以性*/
  if (tw+a.weight<=limitW)
  { cop=1;
  if (i
  else
  { for (k=0;k
  option[k]=cop[k];
  maxv=tv;
  }
  cop=0;
  }
  /*思索物品i不包括在当前方案中的可以性*/
  if (tv-a.value>maxV)
  if (i
  else
  { for (k=0;k
  option[k]=cop[k];
  maxv=tv-a.value;
  }
  }
  void main()
  { int k;
  double w,v;
  printf(“输入物品种数\n”);
  scanf((“%d”,&n);
  printf(“输入各物品的重量和价值\n”);
  for (totv=0.0,k=0;k
  { scanf(“%1f%1f”,&w,&v);
  a[k].weight=w;
  a[k].value=v;
  totV+=V;
  }
  printf(“输入限制重量\n”);
  scanf(“%1f”,&limitV);
  maxv=0.0;
  for (k=0;k find(0,0.0,totV);
  for (k=0;k
  if (option[k]) printf(“%4d”,k+1);
  printf(“\n总价值为%.2f\n”,maxv);
  }

作为对比,下面以异常的解题思想,思索非递归的顺序解。为了提高找解速度,顺序不是复杂地逐终身成一切候选解,而是从每个物品对候选解的影响来构成值得进一步思索的候选解,一个候选解是经过依次调查每个物品构成的。对物品i的调查有这样几种情况:当该物品被包括在候选解中照旧满足解的总重量的限制,该物品被包括在候选解中是应该继续思索的;反之,该物品不应该包括在当前正在构成的候选解中。异常地,仅当物品不被包括在候选解中,还是有可以找到比目前暂时最佳解更好的候选解时,才去思索该物品不被包括在候选解中;反之,该物品不包括在当前候选解中的方案也不应继续思索。关于任一值得继续思索的方案,顺序就去进一步思索下一个物品。

【顺序】

以下是引用片段:
  # include
  # define N 100
  double limitW;
  int cop[N];
  struct ele { double weight;
  double value;
  } a[N];
  int k,n;
  struct { int ;
  double tw;
  double tv;
  }twv[N];
  void next(int i,double tw,double tv)
  { twv.=1;
  twv.tw=tw;
  twv.tv=tv;
  }
  double find(struct ele *a,int n)
  { int i,k,f;
  double maxv,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)
  { case 1: twv.++;
  if (tw+a.weight<=limitW)
  if (i
  { next(i+1,tw+a.weight,tv);
  i++;
  }
  else
  { maxv=tv;
  for (k=0;k
  cop[k]=twv[k].!=0;
  }
  break;
  case 0: 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;
  }
  }
  return maxv;
  }
  void main()
  { double maxv;
  printf(“输入物品种数\n”);
  scanf((“%d”,&n);
  printf(“输入限制重量\n”);
  scanf(“%1f”,&limitW);
  printf(“输入各物品的重量和价值\n”);
  for (k=0;k
  scanf(“%1f%1f”,&a[k].weight,&a[k].value);
  maxv=find(a,n);
  printf(“\n选中的物品为\n”);
  for (k=0;k
  if (option[k]) printf(“%4d”,k+1);
  printf(“\n总价值为%.2f\n”,maxv);
  }



相关评论