解析在下一篇博客
问题 A: 折半查找的次数
题目描述
给你一个无重复数的有序序列，如果采用折半查找的方式，对于给定的数，需要比较几次找到，请编程实现。
#include<cstdio>
using namespace std;
int a[1005];
int main() {
int n,x;
scanf("%d",&n);
for(int i=1;i<=n;i++) {
scanf("%d",&a[i]);
}
scanf("%d",&x);
int l=1,r=n,mid;
int ans=0;
bool flag=false;
while(l<r) {
mid = (l+r)>>1;
if(a[mid]==x) {
flag=true;
ans++;
break;
}
if(x>a[mid]) {
l = mid + 1;
}
else {
r = mid;
}
ans++;
}
if(!flag) printf("NO");
else printf("%d",ans);
return 0;
}
问题 B: 二叉搜索树中的查找
题目描述
给你一个数据序列，请构造一个二叉搜索树，然后计算出找到给定数据需比较的次数。
#include<cstdio>
using namespace std;
struct node {
int data,l,r;
}e[1005];
int cnt=0;
void insert(int x) {
if(!cnt) {
e[++cnt].data=x;
e[cnt].l=-1;
e[cnt].r=-1;
return;
}
int cur=1;
while(cur<=cnt) {
if(x==e[cur].data) {
break;
}
if(x>e[cur].data) {
if(e[cur].r==-1) {
e[++cnt].data=x;
e[cnt].l=-1;
e[cnt].r=-1;
e[cur].r = cnt;
break;
}
else cur = e[cur].r;
}
else {
if(e[cur].l==-1) {
e[++cnt].data=x;
e[cnt].l=-1;
e[cnt].r=-1;
e[cur].l = cnt;
break;
}
else cur = e[cur].l;
}
}
}
int find(int x) {
int cur=1;
int ans=0;
while(cur<=cnt&&cur!=-1) {
ans++;
if(e[cur].data==x) {
return ans;
}
if(e[cur].data>x) {
cur = e[cur].l;
}
else {
cur = e[cur].r;
}
}
return -1;
}
int main() {
int n,x;
scanf("%d",&n);
for(int i=1;i<=n;i++) {
scanf("%d",&x);
insert(x);
}
scanf("%d",&x);
int ans = find(x);
if(ans==-1) printf("NO");
else printf("%d",ans);
return 0;
}
问题 C: 有向图的最短路径长度
题目描述
已知一个有向图，每个边都有一个正整数表示边长，请编程求出其中两个顶点间的最短路径长度。
#include<iostream>
#include<cstring>
using namespace std;
int d[30][30];
int main() {
int m,n;
cin>>m>>n;
char a,b;
int w;
memset(d,0x3f,sizeof(d));
for(int i=1;i<=m;i++) d[i][i]=0;
for(int i=1;i<=n;i++) {
cin>>a>>b>>w;
d[a-'A'+1][b-'A'+1] = w;
d[b-'A'+1][a-'A'+1] = w;
}
for(int k=1;k<=m;k++) {
for(int i=1;i<=m;i++)
for(int j=1;j<=m;j++)
if(d[i][k]+d[k][j]<d[i][j])
d[i][j] = d[i][k]+d[k][j];
}
cin>>a>>b;
cout<<d[a-'A'+1][b-'A'+1];
return 0;
}
问题 D: 有向图的最短路径
题目描述
已知一个有向图，每个边都有一个正整数表示边长，请编程求出其中两个顶点间的最短路径长度。
#include<iostream>
#include<cstring>
#include<queue>
using namespace std;
struct edge {
char a,b;
int w,next;
}e[105];
int cnt,dis[105],head[105];
bool vis[105];
int pre[105];
struct node {
int w,now;
inline bool operator <(const node &x) const {
return w>x.w;
}
};
priority_queue<node> q;
void add(char a,char b,int w) {
e[++cnt].a = a;
e[cnt].b = b;
e[cnt].w = w;
e[cnt].next = head[a-'A'+1];
head[a-'A'+1] = cnt;
}
void dijkstra(char fir) {
dis[fir-'A'+1]=0;
node x = {0,fir-'A'+1};
char v;
q.push(x);
while(!q.empty()) {
x = q.top();
q.pop();
int u = x.now;
if(vis[u]) continue;
vis[u] = true;
for(int i=head[u];i;i=e[i].next) {
v = e[i].b;
if(dis[v-'A'+1]>dis[u]+e[i].w) {
dis[v-'A'+1] = dis[u]+e[i].w;
pre[v-'A'+1] = u;
x = {dis[v-'A'+1],v-'A'+1};
q.push(x);
}
}
}
}
void findPath(int a,int b) {
if(a==b) {
cout<<char(a+'A'-1)<<" ";
return;
}
findPath(a,pre[b]);
cout<<char(b+'A'-1)<<" ";
}
int main() {
int m,n;
cin>>m>>n;
char a,b;
int w;
memset(dis,0x3f,sizeof(dis));
for(int i=1;i<=n;i++) {
cin>>a>>b>>w;
add(a,b,w);
}
cin>>a>>b;
dijkstra(a);
findPath(a-'A'+1,b-'A'+1);
return 0;
}
问题 E: 5个数的从大到小排序
题目描述
数学课上，老师公布了一个小组的5名同学的成绩，你能编程把成绩从大到小排序吗，以便老师知道考试名次？
#include<cstdio>
#include<algorithm>
using namespace std;
bool cmp(int x,int y) {
return x>y;
}
int main() {
int a[6];
for(int i=0;i<5;i++) {
scanf("%d",&a[i]);
}
sort(a,a+5,cmp);
for(int i=0;i<5;i++) {
printf("%d ",a[i]);
}
return 0;
}
问题 F: 病人排队
题目描述
病人登记看病，编写一个程序，将登记的病人按照以下原则排出看病的先后顺序：
1.老年人（年龄 >= 60岁）比非老年人优先看病。
2.老年人按年龄从大到小的顺序看病，年龄相同的按登记的先后顺序排序。
3.非老年人按登记的先后顺序看病。
#include<cstdio>
#include<algorithm>
#include<string>
#include<iostream>
using namespace std;
struct person {
string id;
int age,num;
}p[105];
bool cmp(person x,person y) {
if(x.age==y.age&&x.age>=60) return x.num<y.num;
if(x.age<60&&y.age<60) return x.num<y.num;
return x.age>y.age;
}
int main() {
int n,age;
scanf("%d",&n);
string x;
for(int i=1;i<=n;i++) {
cin>>p[i].id>>p[i].age;
p[i].num = i;
}
sort(p+1,p+n+1,cmp);
for(int i=1;i<=n;i++) {
cout<<p[i].id<<'\n';
}
return 0;
}