ITPub博客

首页 > 应用开发 > IT综合 > 《实用算法的分析与程序设计》的读书笔记(第1天) (转)

《实用算法的分析与程序设计》的读书笔记(第1天) (转)

原创 IT综合 作者:worldblog 时间:2007-12-13 13:11:47 0 删除 编辑
《实用算法的分析与程序设计》的读书笔记(第1天) (转)[@more@]

  由于很多网友的推荐,终于使我静下心来好好的看一下《实用算法的分析与程序设计》这本书!果然是名付其实!现在将我看书过程中遇到的题目用c++给出,原文是用pascal给出的!很多朋友甚至因为这个原因而放弃这本书!很可惜!注:这些程序我都在bc5。0中通过了!

  递推 第4页

一辆重型卡车欲穿过1删公里的沙漠,卡车耗油为1升/公里,卡车总裁油能力为500 公升。显然卡车装一次油是过不了沙漠的。因此司机必须设法在沿途建立几个储油点,使卡车能顺利穿越沙漠,试问司机如何建立这些贮油点?每一贮泊点应存多少汽油,才能使卡车以消耗最少汽油的代价通过沙漠? 题解:


#include


#include


void oil_lib()


{


int k;float d,dl;


float oil[10],dis[10];


cout<<"No."<

k=1;


d=500;


dis[1]=500;


oil[1]=500;


do{


k++;


d+=500/(2*k-1);


dis[k]=d;


oil[k]=oil[k-1]+500;


}while(d<1000);


dis[k]=1000;


dl=1000-dis[k-1];


oil[k]=dl*(2*k+1)+oil[k-1];


for(int i=0;i

cout<

}


贪心法 第10页

有一个贼在偷窃一家商店时发现有N件物品:第i件物品值Vi元,重Wi磅,(1<=i <=n), 此处Vi和Wi都是整数。他希望带走的东西越值钱越好,但他的背包中最多只能装下W磅的东西(W为整数)。


如果允许小偷可带走某个物品的一部分,小偷应该带走哪几件东西, 每件东西的重量是多少?


题解:


#include
#include
const maxn=1000;
class Node{
public:
 Node(){}
  Node(int a,float b,float c):num(a),w(b),v(c){vper=c/w;}
 int num; float w,v,vper;
};
Node list[maxn],lt[maxn];
void print(int n)
{
 for(int i=0;i   cout<  cout<}


void merge(int p,int q,int r)
{
 int i,j,t;
  t=p;i=p;j=q+1;
  while(t<=r){
   if( (i<=q)&&((j>r)||(list[i].vper>=list[j].vper)) ){
   lt[t]=list[i]; i++;
  }else{ lt[t]=list[j]; j++;  }
  t++;
  }
  for(int s=p;s<=r;s++)
   list[s]=lt[s];
}
void merge_sort(int p,int r)
{
  int q;
  if(p!=r){
   q=(p+r)/2;
  merge_sort(p,q);
  merge_sort(q+1,r);
  merge(p,q,r);
  }
}
void Partial_Bag_Problem(int N,float W)
{
 float V=0;
  float w,v;
  for(int i=0;i   cin>>w>>v;
  Node node((i+1),w,v);
  list[i]=node;
  }
  /*print(N)*/
  merge_sort(0,N-1);
  /*print(N)*/
  int j=0;
  while(W>list[j].w&&j   W-=list[j].w;
  V+=list[j].v;
   printf("%d%8.2f%8.2fn",list[j].num,list[j].w,list[j].v);
  j++;
  }
  if(j   V+=W*list[j].vper;
  printf("%d%8.2f%8.2fn",list[j].num,W,W*list[j].vper);
  W=0;
  }
  cout<<"total value: "<}
int main()
{
 int N,W;
  cin>>N>>W;
  Partial_Bag_Problem(N,W);
  return 1;
}


 


贪心法 第15页

任务调度问题 一个单位时间任务是个作业,如要在计算机上运行一个程序,它恰覆盖一个单位的运行时间。给定一个单位时间任务的集合S,对S的一个调度即S的一个排列,其中规定了这些任务的执行顺序。该调度中的第一个任务开始于时间0,结束于时间15第二个任务开始于时间1,结束于时间2;……。 单处理器上具有期限和罚款的单位时间任务调度问题的输人如下: 1.包含n个单位时间任务的集合S=f1,2,……,n75 2.n个取整的期限d1,I。.…,d n,(1<d5之n),任务i要求在di前完成; 3.21个非负的权(或罚款)w:,·,b…,wno如果任务i没在时间di之前结束罚款w5;. 要求找出S的一个调度,使之最小化总的罚款。


题解:


 #include
const maxn=500;
class Node{
public:
 Node(){}
  Node(int a,int b,int c):k(a),d(b),w(c){}
  int k,d,w;
};
Node list[maxn],lt[maxn];
void print(int n)
{
 for(int i=0;i   cout<  cout<}


void merge(int p,int q,int r)
{
 int i,j,t;
  t=p,i=p,j=q+1;
  while(t<=r){
   if((i<=q)&&((j>r)||(list[i].w>=list[j].w)))
   lt[t]=list[i++];
  else lt[t]=list[j++];
  t++;
  }
  for(int s=p;s<=r;s++)
   list[s]=lt[s];
}
void merge_sort(int p,int r)
{
 int q;
  if(p!=r){
   q=(p+r-1)/2;
  merge_sort(p,q);
  merge_sort(q+1,r);
  merge(p,q,r);
  }
}
void Tasks_with_limit_and_fine(int N)
{
  int d,w;
  int pck[maxn];
  int num=0,t,sum=0;  /*当前完成的任务个数  罚款总数*/
 for(int i=0;i   cin>>d>>w;
  Node node((i+1),d,w);
  list[i]=node;
  }
  /*print(N);*/
  merge_sort(0,N-1);
  /*print(N);*/
  int i,j;
  for(i=0;i   t=0;
  for(j=0;j   if(list[pck[j]].d<=num)
   t++;
  /* cout<<"t:"<  if(t  pck[num]=i; list[i].k=-list[i].k; j=num++;  /*cout<<"j:"<  while(j>0){
   if(list[pck[j]].d   t=pck[j];pck[j]=pck[j-1];pck[j-1]=t;
  }
  j--;
  }
  }
  }
  for(i=0;i   cout<<(-list[pck[i]].k)<<"  ";
  cout<  for(i=0;i   if(list[i].k>0){
   cout<  sum+=list[i].w;
  }
  cout<  cout<<"total fine= "<}


int main()
{
 int N;
  cin>>N;
  Tasks_with_limit_and_fine(N);
  return 1;
}



 

 

来自 “ ITPUB博客 ” ,链接:http://blog.itpub.net/10752043/viewspace-992860/,如需转载,请注明出处,否则将追究法律责任。

下一篇: 文件关联 (转)
请登录后发表评论 登录
全部评论
  • 博文量
    6241
  • 访问量
    2410986