试题四[题目略] 是个贪心的算法题..
(1) k=0
(2) j<=N
(3) k=k+1
(4) d[i] + 6
(5) O(N)
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
#include <iostream>
using namespace std;
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) void Fun(int *d,int N) {
int i=1,j,k=0;
int *s=new int[N+1];
memset(s,0,sizeof(s));
while(i<=N)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
j=i+1;
while(j<=N&&d[j]-d[i]<=12) //如果2个房子可以用一个基站覆盖
j=j+1;
++k; //建一个基站
s[k]=d[i]+6; //s[k]为第k个基站到公路A端的距离
i=j; //继续从没有覆盖的开始搜索.
}
cout<<k<<endl;
delete []s;
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) int main() {
int N;
freopen("in.cpp","r",stdin);
//6 2 7 12 13 16 20
//5 8 15 22 29 36
while(cin>>N&&N)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
int *d=new int[N+1];
for(int i=1;i<=N;++i)
scanf("%d",&d[i]);
d[0]=0;
Fun(d,N);
delete []d;
}
return 0;
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
试题五[题目略] 2叉树的数据结构考题
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) typedef struct TreeNode {
int id; //当前节点的识别号
int ChildNum; //当前节点的子节点数目
int d; //父亲点到当前节点的信号衰减值
struct TreeNode **childptr; //向量,存放当前节点到其所有子节点的指针
int M; //当前节点到其所有子节点的信号衰减值中的最大值
bool boost; //是否在当前节点放置信号放大器的标志
}TreeNode;
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) void placeBoosters(TreeNode *root) {
//计算root所指节点处的衰减量,如果衰减量超出了容忍值,则放置放大器
TreeNode *p;
int i,degradation;
if(root)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
degradation=0;root->M=0;
i=0;
if(i>=root->ChildNum) //没有孩子返回
return;
p=root->childptr[0];
for(;i<root->ChildNum&&p;i++,p=root->childptr[i])
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
p->M=0;
placeBoosters(p);
if(p->d+p->M>Tolerance)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
p->boost=true;
p->M=0;
}
if(p->d+p->M>degradation)
degradation=p->d+p->M;
}
root->M=degradation;
}
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
试题六[题目略] 考的是抽象类,纯虚函数,继承和派生的知识。
#include <iostream>
using namespace std;
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) class FlyBehavior {
public:
virtual void fly()=0;
};
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) class QuackBehavior {
public:
virtual void quack()=0;
};
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) class FlyWithWings:public FlyBehavior {
public:
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) void fly() { cout<<"使用翅膀飞行!"<<endl;}
};
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) class FlyNoWay:public FlyBehavior {
public:
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) void fly() { cout<<"不能飞行!"<<endl;}
};
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) class Quack:public QuackBehavior {
public:
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) void quack() { cout<<"发出\'嘎嘎\'声!"<<endl;}
};
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) class Squeak:public QuackBehavior {
public:
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) void quack() { cout<<"发出空气与橡皮摩擦声!"<<endl;}
};
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) class QuackNoWay:public QuackBehavior {
public:
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) void quack() { cout<<"不能发声!"<<endl;}
};
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) class Duck {
protected:
FlyBehavior *flyBehavior;
QuackBehavior *quackBehavior;
public:
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) void fly() { flyBehavior->fly();}
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) void quack() { quackBehavior->quack();}
virtual void display()=0;
};
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) class RubberDuck:public Duck {
public:
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) RubberDuck() {
flyBehavior=new FlyNoWay();
quackBehavior=new Squeak();
}
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) ~RubberDuck() {
if(!flyBehavior) delete flyBehavior;
if(!quackBehavior) delete quackBehavior;
}
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) void display() {}
};
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
.....~ 如有错误,请指出
|
|
随笔:5
文章:28
评论:1
引用:0
| 日 | 一 | 二 | 三 | 四 | 五 | 六 |
---|
28 | 29 | 30 | 31 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 | 21 | 22 | 23 | 24 | 25 | 26 | 27 | 28 | 29 | 30 | 31 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
|
公告
Blog里的内容如果没有注明为转载,就是原创文章,需要转载的朋友请注明出处。文章中如有错误,请指出。转载内容如果有侵权行为,请与我联系,----issac_asimoy@qq.com。
常用链接
留言簿(1)
随笔分类(5)
随笔档案(5)
文章分类(28)
文章档案(28)
相册
My World
Study Web
最新随笔
搜索
积分与排名
最新评论
![](/images/xml.gif)
阅读排行榜
评论排行榜
|
|