分享
 
 
 

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

王朝other·作者佚名  2006-01-08
窄屏简体版  字體: |||超大  

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

递推 第4页

一辆重型卡车欲穿过1删公里的沙漠,卡车耗油为1升/公里,卡车总裁油能力为500

公升。显然卡车装一次油是过不了沙漠的。因此司机必须设法在沿途建立几个储油点,

使卡车能顺利穿越沙漠,试问司机如何建立这些贮油点?每一贮泊点应存多少汽油,才能

使卡车以消耗最少汽油的代价通过沙漠?

题解:

#include<iostream.h>

#include<iomanip.h>

void oil_lib()

{

int k;float d,dl;

float oil[10],dis[10];

cout<<"No."<<setw(20)<<" distance(k.m)"<<setw(90)<<" oil(l.)"<<endl;

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<k;i++)

cout<<i<<setw(20)<<(1000-dis[k-i])<<setw(90)<<oil[k-i]<<endl;

}

贪心法 第10页

有一个贼在偷窃一家商店时发现有N件物品:第i件物品值Vi元,重Wi磅,(1<=i

<=n), 此处Vi和Wi都是整数。他希望带走的东西越值钱越好,但他的背包中最多只能

装下W磅的东西(W为整数)。

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

的重量是多少?

题解:

#include<iostream.h>

#include<stdio.h>

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<n;i++)

cout<<list[i].num<<" "<<list[i].w<<" "<<list[i].v<<endl;

cout<<endl;

}

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<N;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<N){

W-=list[j].w;

V+=list[j].v;

printf("%d%8.2f%8.2f\n",list[j].num,list[j].w,list[j].v);

j++;

}

if(j<N&&W!=0){

V+=W*list[j].vper;

printf("%d%8.2f%8.2f\n",list[j].num,W,W*list[j].vper);

W=0;

}

cout<<"total value: "<<V<<endl;

}

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<iostream.h>

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<n;i++)

cout<<list[i].k<<" "<<list[i].d<<" "<<list[i].w<<endl;

cout<<endl;

}

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<N;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<N;i++){

t=0;

for(j=0;j<num;j++)

if(list[pck[j]].d<=num)

t++;

/* cout<<"t:"<<t<<" ";*/

if(t<list[i].d){

pck[num]=i; list[i].k=-list[i].k; j=num++; /*cout<<"j:"<<j<<" ";*/

while(j>0){

if(list[pck[j]].d<list[pck[j-1]].d){

t=pck[j];pck[j]=pck[j-1];pck[j-1]=t;

}

j--;

}

}

}

for(i=0;i<num;i++)

cout<<(-list[pck[i]].k)<<" ";

cout<<endl;

for(i=0;i<N;i++)

if(list[i].k>0){

cout<<list[i].k<<" ";

sum+=list[i].w;

}

cout<<endl;

cout<<"total fine= "<<sum<<endl;

}

int main()

{

int N;

cin>>N;

Tasks_with_limit_and_fine(N);

return 1;

}

 
 
 
免责声明:本文为网络用户发布,其观点仅代表作者个人观点,与本站无关,本站仅提供信息存储服务。文中陈述内容未经本站证实,其真实性、完整性、及时性本站不作任何保证或承诺,请读者仅作参考,并请自行核实相关内容。
2023年上半年GDP全球前十五强
 百态   2023-10-24
美众议院议长启动对拜登的弹劾调查
 百态   2023-09-13
上海、济南、武汉等多地出现不明坠落物
 探索   2023-09-06
印度或要将国名改为“巴拉特”
 百态   2023-09-06
男子为女友送行,买票不登机被捕
 百态   2023-08-20
手机地震预警功能怎么开?
 干货   2023-08-06
女子4年卖2套房花700多万做美容:不但没变美脸,面部还出现变形
 百态   2023-08-04
住户一楼被水淹 还冲来8头猪
 百态   2023-07-31
女子体内爬出大量瓜子状活虫
 百态   2023-07-25
地球连续35年收到神秘规律性信号,网友:不要回答!
 探索   2023-07-21
全球镓价格本周大涨27%
 探索   2023-07-09
钱都流向了那些不缺钱的人,苦都留给了能吃苦的人
 探索   2023-07-02
倩女手游刀客魅者强控制(强混乱强眩晕强睡眠)和对应控制抗性的关系
 百态   2020-08-20
美国5月9日最新疫情:美国确诊人数突破131万
 百态   2020-05-09
荷兰政府宣布将集体辞职
 干货   2020-04-30
倩女幽魂手游师徒任务情义春秋猜成语答案逍遥观:鹏程万里
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案神机营:射石饮羽
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案昆仑山:拔刀相助
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案天工阁:鬼斧神工
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案丝路古道:单枪匹马
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案镇郊荒野:与虎谋皮
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案镇郊荒野:李代桃僵
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案镇郊荒野:指鹿为马
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案金陵:小鸟依人
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案金陵:千金买邻
 干货   2019-11-12
 
推荐阅读
 
 
 
>>返回首頁<<
 
靜靜地坐在廢墟上,四周的荒凉一望無際,忽然覺得,淒涼也很美
© 2005- 王朝網路 版權所有