实验1 结构体与共用体
7-1 检查宿舍卫生
不知道是从哪个学校开始兴起的还是哪个领导的决定，学校里每周都要检查宿舍卫生！大家发现没有，检查宿舍卫生是件很奇葩的事情，它剥削了每件物品的意义：垃圾桶里不能有垃圾，挂钩上不能挂东西，桌子上不能放东西，床上不能躺人！！假设检查卫生分为五项成绩：垃圾桶得分、挂钩得分、桌子得分、床铺得分和窗台得分。每项满分20分，总分满分为100分。按照计算机学院奇葩的规定，宿舍成绩在85分以下就要算作不合格。某天，宿管阿姨给了你一个检查完宿舍的打分表，让你帮忙统计下有多少个宿舍没有达到85分(等于85分是可以的)，并且统计成绩最高分。
输入格式:
第一行为一个整数 n (0 < n <= 100)，代表你要统计的宿舍的总数，接下来 n 行每行为 5 个整数，代表宿舍五项成绩的得分。
输出格式:
输出只有一行，由一个空格分隔的两个整数：总分不合格的宿舍数和宿舍总分最高分，如果最高分仍小于85分，则输出为不合格的宿舍数和“No”(不包含引号)。
输入样例:
5
1 2 3 4 5
10 20 10 20 20
20 20 20 20 20
15 15 15 20 20
10 10 10 10 10
输出样例:
3 100
#include <stdio.h>
int main()
{
int n;int i,j,a,b,c,d,e;
int max=-1,k=0;
int m[100];
while(scanf("%d",&n)!=EOF)
{
for(i=1;i<=n;i++)//n行
{
scanf("%d %d %d %d %d",&a,&b,&c,&d,&e);
m[i]=a+b+c+d+e;
}
max=-1;k=0;
for(i=1;i<=n;i++)
{
if(m[i]>max)
{
max=m[i];
}
if(m[i]<85)//不合格
k++;
}
}
if(max<85) printf("%d No",n);
else printf("%d %d",k,max);
return 0;
}
7-2 小 I 的小姐姐
小 I 去天津玩啦，一路上，他跟他的同学发生了许多有趣的事。
当他们路过天津外国语学院时，他发现了许多小姐姐，他眼花缭乱，甚至不知道该去找哪个小姐姐聊天。
怎么办怎么办！
于是他想到了你，他拍了一张照片给你，你发现照片里一共有 n 个小姐姐（序号从 0 到 n - 1），每个小姐姐都有自己的风格，可以按特征划分出 3 个特征值 w1 , w2 , w3 ，你知道小 I 特别喜欢 w1 特征值高的小姐姐，不太看重 w3 ，于是你对于每个特征都赋予一个权重，分别对应为0.7 0.2 0.1，你能帮小 I 找出来他发来的这张照片里他最喜欢的小姐姐吗？
输入格式:
第一行给出一个整数 n (n <= 1000) ，之后有 n 行数。
每行数有三个整数 w1, w2, w3，表示三个特征值。
不存在权值和相等的情况。
输出格式:
输出n 个小姐姐中权值和最高的序号。
输入样例:
3
1 5 10
5 1 10
10 5 1
输出样例:
2
#include <stdio.h>
int a[10000000];
int main()
{
int n;
scanf("%d",&n);
int i=0;int w1,w2,w3;
int result=0,max=-1,k=0;
for(i=0;i<n;i++)
{
scanf("%d %d %d",&w1,&w2,&w3);
result=w1*0.7+w2*0.2+w3*0.1;
if(result>max)
{
max=result;
k=i;
}
}
printf("%d",k);
return 0;
}
7-3 选票统计
某校学生会主席由全校学生投票选举产生，共有ｍ名候选人报名参选，编号为1到ｍ（0＜ｍ＜1000），全校有ｎ名学生（0＜ｎ＜30000），每人都可以投票。但每人只能投一票，每票只能选1名候选人。请你设计一个程序能够统计出哪个候选人得票最高，得了多少票。不会出现得票数相同的情况。
输入格式:
第一行输入候选人数ｍ和学生数ｎ，以空格分开；
下面依次输入每个学生所选的候选人的编号。
输出格式:
第一行输出得票最多的候选人编号；
第二行输出该候选人所得的票数。
输入样例:
3 10
1 2 3 2 3 1 2 3 1 3
输出样例:
3
4
#include <stdio.h>
int a[10000],b[1000000];
int main()
{
int m,n;
scanf("%d %d",&m,&n);
int i=0,max=-1,k=0;
for(i=1;i<=n;i++)
{
scanf("%d",&a[i]);
b[a[i]]++;
}
for(i=1;i<=m;i++)
{
if(b[i]>max)
{
max=b[i];
k=i;
}
}
printf("%d\n%d\n",k,max);
return 0;
}
7-4 小 I 选宾馆
小 I 去天津玩啦，一路上，他跟他的同学发生了许多有趣的事。
到了晚上了，小 I 跟他的同学们要选一个宾馆住下了。但是形形色色的宾馆让小 I 不知所措。
对于一个宾馆来说，有许多特征，比如「价格」、「舒适度」。小I会对每个特征都有一个满意度。
小I会选择出满意度更高一些的宾馆。
其中，「价格」对于小 I 来说是最重要的，其次是「舒适度」。
如果有两个宾馆，如果对「价格」的满意度相同，那么根据「舒适度」进行选择；如果有多个宾馆条件相同，输出编号最小的宾馆。
小 I 现在处于水深火热之中，因为他们面对一堆宾馆不知所措，他想到了会编程的你，如果你不帮他选出来，他可能就会露宿街头了QAQ~
你能帮他按照他的意愿找到小I最满意的宾馆吗？
输入格式:
给出 n (n <= 5000) 代表 n 个宾馆（编号从 1 - n），随后有 n 行数据。
每行数据有两个整数，分别代表小I对「价格」、「舒适度」的满意程度，数值越大满意程度越高，满意度的范围从0 - 5000。
输出格式:
输出按照描述的条件中小I最满意的宾馆编号，如果有多个宾馆条件相同，输出编号最小的宾馆。
输入样例:
4
0 1
1 0
1 1
1 0
输出样例:
3
#include<stdio.h>
struct num
{
int price;
int comfort;
}a[5000];
int main()
{
int i,n,m=0;
scanf("%d",&n);
for(i=0;i<n;i++)
{
scanf("%d %d",&a[i].price,&a[i].comfort);
}
for(i=0;i<n;i++)
{
if(a[i].price>a[m].price)
{
m=i;
}
else if(a[i].price==a[m].price)
{
if(a[i].comfort>a[m].comfort)
{
m=i;
}
}
}
printf("%d\n",m+1);
return 0;
}
7-5 小鑫の日常系列故事（十）——排名次
小鑫在来到SDUT之后，经过十分刻苦的学习和努力终于进入了ACM集训队。很快又一次ACM集训队的选拔就要开始了，集训队员们又忙碌了起来。他也十分幸运的被学长抓来当苦力。 o(∩_∩)o
这次学长给他分配的任务是写一个自动排名的程序，我们知道当选拔赛结束的时候，每一个参与选拔的同学都会有一个自己的分数。而集训队需要根据大家的分数排名来决定谁能够进入集训队，这个任务就落在了小鑫身上。
你能帮小鑫来完成这个程序么？
输入格式:
输入的第一行为n ( 0<n<=50) ;
之后给出n 行，每行为一个人名和ta所得到的分数。保证没有相同的分数。
人名为英文单词，长度不超过10。
输出格式:
输出为n行，每行一个人名与他的得分。每一行最后没有多余的空格。
具体输出格式见样例。
输入样例:
3
Dan 10
John 50
Danny 30
输出样例:
John 50
Danny 30
Dan 10
#include <stdio.h>
struct pai
{
int fen;
char name[10000];
}a[10000],t;
int main()
{
int n,i,j=0;
scanf("%d",&n);
for(i=0;i<n;i++)
{
scanf("%s %d",a[i].name,&a[i].fen);
}
for(i=0;i<n-1;i++)
{
for(j=0;j<n-1-i;j++)
{
if(a[j].fen<a[j+1].fen)
{
t=a[j+1];
a[j+1]=a[j];
a[j]=t;
}
}
}
for(i=0;i<n;i++)
{
printf("%s %d\n",a[i].name,a[i].fen);
}
return 0;
}
7-6 最终排名
第四届山东理工大学ACM网络编程擂台赛比赛完后需要产生一个最终排名，排名按照题数多少来决定。但是有太多的队伍参与，手动计算排名已经不能满足比赛的需求。现在有一份名单记录各个队伍的ID和做出的题目数，需要你写一个程序，产生最终的排名。
为了简化题目，这里的排名规则为：做出题目数量多的队伍排在前面，如果题数相等，保持输入时的相对顺序不要改变。
输入格式:
第一行有一个正整数N（1 < N ≤ 10000）,表示队伍数量。
接下来N 行包含两个整数，1 ≤ ID ≤ 10^7, 0 ≤ M ≤ 100。ID为队伍的编号，M为做出的题数。
输出格式:
输出包含N行;
第i行有两个整数，ID和M表示排在第i位的队伍的ID和做出的题数。
输入样例:
8
1 2
16 3
11 2
20 3
3 5
26 4
7 1
22 4
输出样例:
3 5
26 4
22 4
16 3
20 3
1 2
11 2
7 1
#include <stdio.h>
struct pai
{
int id;
int fen;
}a[10000],t;
int main()
{
int n;int i,j=0;
scanf("%d",&n);
for(i=0;i<n;i++)
{
scanf("%d %d",&a[i].id,&a[i].fen);
}
for(i=0;i<n-1;i++)
{
for(j=0;j<n-1-i;j++)
{
if(a[j].fen<a[j+1].fen)
{
t=a[j+1];
a[j+1]=a[j];
a[j]=t;
}
}
}
for(i=0;i<n;i++)
{
printf("%d %d\n",a[i].id,a[i].fen);
}
return 0;
}
7-7 选夫婿1
倾国倾城的大家闺秀潘小姐要选夫婿啦！武林中各门各派，武林外各大户人家，闻讯纷纷前来，强势围观。前来参与竞选的男生藏龙卧虎，高手云集，才子遍布，帅哥纷纭，更不乏富二代，官二代，可谓声势空前。
每个人参与竞选的帅哥除了进行一段激情洋溢的求婚演讲以外，还要报上自己姓名、身高和体重，以及个人简历。最后再进行文武选拔，最后夺魁者方能得到潘小姐的芳心。
潘小姐不爱名利，只看人，第一关就是身高和体重要合格，即必须在其要求的范围内，否则直接排除在外，不允许参加下一轮的选拔。
作为一个程序员，你没有钱也没有权，擅长的也就是编程了。潘小姐也发现了这一点，所以把首轮根据身高体重进行选拔的任务交给了你，如果完成的好，你可以直接进入下一轮选拔，你笑了。
输入格式:
潘小姐给你了所有报名男生的信息。
输入数据的第一行是一个正整数N (0 < N < 1000)。
之后N 行数据，每行包含三部分，用空格隔开。第一部分是报名者的姓名name(长度小于20的字符串)，然后是整数身高h（0 < h < 300），第三部分是整数体重w (0 < w < 200)。
最后一行是四个整数a,b,c,d.表示身高的合格范围是[a,b],体重的合格范围是[c,d]（0 < a < b < 200, 0 < c < d < 300）。
输出格式:
你需要把合格的男生信息按照身高从低到高输出，格式跟输入一样，也是每行三个信息，共N行，如果身高相同则按体重从轻到重输出，若没有合格人选则输出No，具体格式见样例。
输入样例:
8
武大郎 70 40
西门庆 180 70
李逵 160 150
燕青 175 69
鲁智深 180 100
武松 180 75
小泉纯一狼 30 20
孙二娘 169 60
165 190 60 90
输出样例:
孙二娘 169 60
燕青 175 69
西门庆 180 70
武松 180 75
#include <stdio.h>
struct pai
{
char name[1000];
int sg,tz;
}a[10050],t;
int main()
{
int n,b,c,d,e;
scanf("%d",&n);
int i,j=0,m=0;
for(i=0;i<n;i++)
{
scanf("%s %d %d",a[i].name,&a[i].sg,&a[i].tz);
}
scanf("%d %d %d %d",&b,&c,&d,&e);
for(i=0;i<n;i++)
{
if(a[i].sg>=b&&a[i].sg<=c&&a[i].tz>=d&&a[i].tz<=e)
{
for(i=0;i<n-1;i++)
{
for(j=0;j<n-1-i;j++)
{
if(a[j].sg>a[j+1].sg)
{
t=a[j+1];
a[j+1]=a[j];
a[j]=t;
}
if(a[j].sg==a[j+1].sg)
{
if(a[j].tz>a[j+1].tz)
{
t=a[j+1];
a[j+1]=a[j];
a[j]=t;
}
}
}
}
m++;
}
}
if(m==0)printf("No");
for(i=0;i<n;i++)
{
if(a[i].sg>=b&&a[i].sg<=c&&a[i].tz>=d&&a[i].tz<=e)
printf("%s %d %d\n",a[i].name,a[i].sg,a[i].tz);
}
return 0;
}
7-8 老–质价比
给出n件物品，每件物品有质量和价格两种属性。你要做的是按质量升序排序，若质量相同则按价格降序排序。
输入格式:
第一行输入一个正整数n(1<=n && n <= 100)，代表有n件物品。
接下来的一行有n个正整数Wi(1<= Wi && Wi <= 10000)，代表每件物品的质量。
再接下来的一行有n个正整数Pi(1 <= Pi && Pi <= 10000)，代表每件物品的价格。
输出格式:
输出n行，每行两个数Wi，Pi。顺序为题目描述所要求。
输入样例:
3
1 2 2
3 2 3
输出样例:
1 3
2 3
2 2
#include <stdio.h>
struct pai
{
int jg;int zl;
}a[10000],t;
int main()
{
int n;int i,j=0;
scanf("%d",&n);
for(i=0;i<n;i++)
{
scanf("%d",&a[i].zl);
}
for(i=0;i<n;i++)
{
scanf("%d",&a[i].jg);
}
for(i=0;i<n-1;i++)
{
for(j=0;j<n-1-i;j++)
{
if(a[j].zl>a[j+1].zl)
{
t=a[j+1];
a[j+1]=a[j];
a[j]=t;
}
else if(a[j].zl==a[j+1].zl)
{
if(a[j].jg<a[j+1].jg)
{
t=a[j+1];
a[j+1]=a[j];
a[j]=t;
}
}
}
}
for(i=0;i<n;i++)
{
printf("%d %d\n",a[i].zl,a[i].jg);
}
return 0;
}
7-9 共用体练习
给定n和m，接下来有n个描述，每个描述包含一个类型标志和一组相应的数据。
类型标志共3种：INT DOUBLE STRING，然后对应一组相应的数据。
紧接着有m个询问，每个询问仅包含一个整数x，要求输出第x个描述对应的数据（STRING类型保证不含空格，每组对应STRING数据不会超过19个字符）。
输入格式:
输入的第一行为两个整数，n和m (n<=100000, m<=100000 ), 分别代表描述的个数和询问的个数。
接下来为 n 行描述;
最后为m行询问，具体格式见样例输入输出。
输出格式:
对于每个询问，输出对应的结果，注意：浮点数保留两位小数。
输入样例:
5 4
INT 456
DOUBLE 123.56
DOUBLE 0.476
STRING welcomeToC
STRING LemonTree
0
1
2
4
输出样例:
456
123.56
0.48
LemonTree
提示:
必须使用共用体完成
#include <stdio.h>
union pai
{
int a;
double b;
char c[25];
}a[10000000],t[1000000];
int main()
{
int m,n;int i=0;
scanf("%d %d",&m,&n);
for(i=0;i<m;i++)
{
scanf("%s",a[i].c);
if(a[i].c[0]=='I')
scanf("%d",&t[i].a);
else if(a[i].c[0]=='D')
scanf("%lf",&t[i].b);
else if(a[i].c[0]=='S')
scanf("%s",t[i].c);
}
int x;
for(i=0;i<n;i++)
{
scanf("%d",&x);
if(a[x].c[0]=='I')
printf("%d\n",t[x].a);
else if(a[x].c[0]=='D')
printf("%.2lf\n",t[x].b);
else if(a[x].c[0]=='S')
printf("%s\n",t[x].c);
}
return 0;
}
7-10 简单枚举类型——植物与颜色
请定义具有red, orange, yellow, green, blue, violet六种颜色的枚举类型color，根据输入的颜色名称，输出以下六种植物花朵的颜色：
Rose(red), Poppies(orange), Sunflower(yellow), Grass(green), Bluebells(blue), Violets(violet)。如果输入的颜色名称不在枚举类型color中，例如输入purple，请输出I don’t know about the color purple.
输入格式:
第一行输入一个n, 代表有n 组询问。( 1 <= n <= 10)
接下来的n行, 每行有一个字符串代表颜色名称，颜色名称最多30个字符。
输出格式:
输出n 行。
每行输出对应颜色的植物名称。
例如：Bluebells are blue. 如果输入的颜色名称不在枚举类型color中，例如purple, 请输出I don’t know about the color purple.
输入样例:
3
blue
yellow
purple
AI助手
输出样例:
Bluebells are blue.
Sunflower are yellow.
I don’t know about the color purple.
AI助手
提示:
请用枚举类型实现
#include <stdio.h>
#include <string.h>
enum color{red,orange,yellow,green,blue,violet,no}w;
int main()
{
char a[31];
int n;
scanf("%d",&n);
getchar();
while(n--)
{
gets(a);
if(strcmp(a,"red")==0)
w=red;
else if(strcmp(a,"orange")==0)
w=orange;
else if(strcmp(a,"yellow")==0)
w=yellow;
else if(strcmp(a,"green")==0)
w=green;
else if(strcmp(a,"blue")==0)
w=blue;
else if(strcmp(a,"violet")==0)
w=violet;
else w = no;
switch(w)
{
case red:printf("Rose are red.\n");break;
case orange:printf("Poppies are orange.\n");break;
case yellow:printf("Sunflower are yellow.\n");break;
case green:printf("Grass are green.\n");break;
case blue:printf("Bluebells are blue.\n");break;
case violet:printf("Violets are violet.\n");break;
case no:
printf("I don't know about the color %s.\n",a);
}
}
return 0;
}
实验2 链表
7-1 数据结构实验之链表一：顺序建立链表
输入N个整数，按照输入的顺序建立单链表存储，并遍历所建立的单链表，输出这些数据。
输入格式:
第一行输入整数的个数N(1 <= N <= 100000)。
第二行依次输入每个整数。
输出格式:
输出这组整数。
输入样例:
8
12 56 4 6 55 15 33 62
输出样例:
12 56 4 6 55 15 33 62
#include <stdio.h>
int a[10000000];
int main()
{
int n;
scanf("%d",&n);
int i=0;
for(i=1;i<=n;i++)
{
scanf("%d",&a[i]);
}
for(i=1;i<=n;i++)
{
if(i==1)
printf("%d",a[i]);
else printf(" %d",a[i]);
}
return 0;
}
7-2 数据结构实验之链表二：逆序建立链表
输入整数个数N，再输入N个整数，按照这些整数输入的相反顺序建立单链表，并依次遍历输出单链表的数据。
输入格式:
第一行输入整数N（1<=N<=100000)。
第二行依次输入N个整数，逆序建立单链表。
输出格式:
依次输出单链表所存放的数据。
输入样例:
10
11 3 5 27 9 12 43 16 84 22
输出样例:
22 84 16 43 12 9 27 5 3 11
#include <stdio.h>
int a[100000000090];
int main()
{
int n;
scanf("%d",&n);
int i=0;
for(i=1;i<=n;i++)
{
scanf("%d",&a[i]);
}
for(i=n;i>=1;i--)
{
if(i==1)
printf("%d",a[i]);
else printf("%d ",a[i]);
}
return 0;
}
7-3 数据结构实验之链表三：链表的逆置
输入多个整数，以-1作为结束标志，顺序建立一个带头结点的单链表，之后对该单链表的数据进行逆置，并输出逆置后的单链表数据。
输入格式:
输入多个整数，以-1作为结束标志。（整数个数不超过100000，不低于1）
输出格式:
输出逆置后的单链表数据。
输入样例:
12 56 4 6 55 15 33 62 -1
输出样例:
62 33 15 55 6 4 56 12
#include <stdio.h>
#include <stdlib.h>
struct node
{
int data;
struct node*next;
};
int main()
{
int num;
struct node*head=(struct node*)malloc(sizeof(struct node));
head->next=NULL;
while(scanf("%d",&num)!=EOF&&num!=-1)
{
struct node*p=(struct node*)malloc(sizeof(struct node));
p->next=NULL;
p->data=num;
p->next=head->next;
head->next=p;
}
struct node*r=head->next;
while(r)
{
if(r->next==NULL)
printf("%d",r->data);
else printf("%d ",r->data);
r=r->next;
}
return 0;
}
7-4 数据结构实验之链表四：有序链表的归并
分别输入两个有序的整数序列（分别包含M和N个数据），建立两个有序的单链表，将这两个有序单链表合并成为一个大的有序单链表，并依次输出合并后的单链表数据。
输入格式:
第一行输入M与N的值。(1 <= M <=100000, 1 <= N <= 100000)
第二行依次输入M个有序的整数。
第三行依次输入N个有序的整数。
输出格式:
输出合并后的单链表所包含的M+N个有序的整数。
输入样例:
6 5
1 23 26 45 66 99
14 21 28 50 100
输出样例:
1 14 21 23 26 28 45 50 66 99 100
#include <stdio.h>
#include <stdlib.h>
struct node
{
int data;
struct node*next;
};
int main()
{
int m,n;int i=0;
scanf("%d %d",&m,&n);
struct node *head1,*head2,*tail1;
head1=(struct node*)malloc(sizeof(struct node));
head1->next=NULL;
tail1=head1;
for(i=1;i<=m;i++)
{
struct node*p1;
p1=(struct node*)malloc(sizeof(struct node));
scanf("%d",&p1->data);
p1->next=tail1->next;
tail1->next=p1;
tail1=tail1->next;
}
struct node*tail2,*p2;
head2=(struct node*)malloc(sizeof(struct node));
head2->next=NULL;
tail2=head2;
for(i=1;i<=n;i++)
{
p2=(struct node*)malloc(sizeof(struct node));
p2->next=NULL;
scanf("%d",&p2->data);
p2->next=tail2->next;
tail2->next=p2;
tail2=tail2->next;
}
struct node*a,*b,*c;
a=head1;
b=head1->next;
c=head2->next;
free(head2);
while(b&&c)
{
if(b->data>c->data)
{
a->next=c;
a=c;
c=c->next;
}
else
{
a->next=b;
a=b;
b=b->next;
}
}
if(b)
a->next=b;
if(c)
a->next=c;
//遍历输出
struct node*r;
r=head1->next;
while(r)
{
if(r->next==NULL)
printf("%d",r->data);
else printf("%d ",r->data);
r=r->next;
}
return 0;
}
7-5 数据结构实验之链表五：单链表的拆分
输入N个整数顺序建立一个单链表，将该单链表拆分成两个子链表，第一个子链表存放了所有的偶数，第二个子链表存放了所有的奇数。两个子链表中数据的相对次序与原链表一致。
输入格式:
第一行输入整数N（1<=N<=100000)。
第二行依次输入N个整数。 （保证奇数偶数都存在）
输出格式:
第一行分别输出偶数链表与奇数链表的元素个数；
第二行依次输出偶数子链表的所有数据；
第三行依次输出奇数子链表的所有数据。
输入样例:
10
1 3 22 8 15 999 9 44 6 1001
输出样例:
4 6
22 8 44 6
1 3 15 999 9 1001
#include <stdio.h>
#include <stdlib.h>
int a1[1000000],a2[1000000000];
struct node
{
int data;
struct node *next;
};
int main()
{
int n;
scanf("%d",&n);
int i=0;
struct node*head,*tail;
head=(struct node*)malloc(sizeof(struct node));
head->next=NULL;
tail=head;
for(i=1;i<=n;i++)
{
struct node*p=(struct node*)malloc(sizeof(struct node));
p->next=NULL;
scanf("%d",&p->data);//存进去数据；
//插入--顺序--尾插；
p->next=tail->next;
tail->next=p;
tail=tail->next;
}
int cnt1=0,cnt2=0;
struct node*r=head->next;
while(r)
{
if(r->data%2==0)//偶数；
a1[cnt1++]=r->data;
else a2[cnt2++]=r->data;
r=r->next;
}
printf("%d %d\n",cnt1,cnt2);
for(i=0;i<cnt1;i++)
{
if(i==0)
printf("%d",a1[i]);
else printf(" %d",a1[i]);
}
printf("\n");
for(i=0;i<cnt2;i++)
{
if(i==0)printf("%d",a2[i]);
else printf(" %d",a2[i]);
}
return 0;
}
7-6 数据结构实验之链表七：单链表中重复元素的删除
按照数据输入的相反顺序（逆位序）建立一个单链表，并将单链表中重复的元素删除（值相同的元素只保留最后输入的一个）。
输入格式:
第一行输入元素个数 n (1 <= n <= 15)；
第二行输入 n 个整数，保证在 int 范围内。
输出格式:
第一行输出初始链表元素个数；
第二行输出按照逆位序所建立的初始链表；
第三行输出删除重复元素后的单链表元素个数；
第四行输出删除重复元素后的单链表。
输入样例:
10
21 30 14 55 32 63 11 30 55 30
输出样例:
10
30 55 30 11 63 32 55 14 30 21
7
30 55 11 63 32 14 21
#include <stdio.h>
#include <stdlib.h>
struct node
{
int data;
struct node*next;
};
int main()
{
int n;
scanf("%d",&n);
struct node*head=(struct node*)malloc(sizeof(struct node));
head->next=NULL;
int i=0;
for(i=1;i<=n;i++)
{
struct node*p=(struct node*)malloc(sizeof(struct node));
p->next=NULL;
scanf("%d",&p->data);
p->next=head->next;
head->next=p;
}//插入环节；
printf("%d\n",n);
struct node*r=head->next;
while(r)
{
if(r->next==NULL)
printf("%d",r->data);
else printf("%d ",r->data);
r=r->next;
}
struct node*q=head->next;
while(q)
{
struct node*r=q->next;
struct node*pre=q;
while(r)
{
if(q->data==r->data)
{
pre->next=r->next;
free(r);
n--;
r=pre->next;
}
else
{
r=r->next;
pre=pre->next;
}
}
q=q->next;
}
printf("\n");
printf("%d\n",n);
struct node*z=head->next;
while(z)
{
if(z->next==NULL)
printf("%d",z->data);
else printf("%d ",z->data);
z=z->next;
}
return 0;
}
7-7 师–链表的结点插入
给出一个只有头指针的链表和 n 次操作，每次操作为在链表的第 m 个元素后面插入一个新元素x。若m 大于链表的元素总数则将x放在链表的最后。
输入格式:
多组输入。
每组数据首先输入一个整数n(1<=n<=100)，代表有n次操作。
接下来的n行，每行有两个整数Mi(0<=Mi<=10000)，Xi。
输出格式:
对于每组数据。从前到后输出链表的所有元素,两个元素之间用空格隔开。
输入样例:
4
1 1
1 2
0 3
100 4
输出样例:
3 1 2 4
Hint
样例中第一次操作1 1，由于此时链表中没有元素，1>0,所以此时将第一个数据插入到链表的最后，也就是头指针的后面。
#include <stdio.h>
#include <stdlib.h>
struct node
{
int data;
struct node*next;
};
int main()
{
int n,m,x,cnt=0,i=0;
while(scanf("%d",&n)!=EOF)
{
cnt=0;
struct node*head=(struct node*)malloc(sizeof(struct node));
head->next=NULL;
while(n--)
{
scanf("%d %d",&m,&x);
struct node*p=(struct node*)malloc(sizeof(struct node));
p->next=NULL;
p->data=x;
if(m>cnt)
{
m=cnt;
}
struct node*r=head;
for(i=1;i<=m;i++)
{
r=r->next;
}
p->next=r->next;
r->next=p;
cnt++;
}
struct node*d=head->next;
while(d)
{
if(d->next==NULL)
printf("%d\n",d->data);
else printf("%d ",d->data);
d=d->next;
}
}
return 0;
}
7-8 约瑟夫问题
n个人想玩残酷的死亡游戏，游戏规则如下：
n个人进行编号，分别从1到n，排成一个圈，顺时针从1开始数到m，数到m的人被杀，剩下的人继续游戏，活到最后的一个人是胜利者。
请输出最后一个人的编号。
输入格式:
输入n和m值。 (1<=n<=100 , 1<=m<=100)
输出格式:
输出胜利者的编号。
输入样例:
5 3
输出样例:
4
Hint
第一轮：3被杀
第二轮：1被杀
第三轮：5被杀
第四轮：2被杀
#include <stdio.h>
#include <stdlib.h>
struct node
{
int data;
struct node*next;
};
int main()
{
int n,m,i=0,cnt=0;
scanf("%d %d",&n,&m);
struct node*head=(struct node*)malloc(sizeof(struct node));
head->next=NULL;
struct node*tail=head;
for(i=1;i<=n;i++)
{
struct node*p=(struct node*)malloc(sizeof(struct node));
p->next=NULL;
p->data=i;
p->next=tail->next;
tail->next=p;
tail=tail->next;
}
tail->next=head->next;
struct node*pre=head;
struct node*r=head->next;
while(r->next!=r)
{
cnt++;
if(cnt%m==0)
{
pre->next=r->next;
free(r);
r=pre->next;
}
else
{
pre=pre->next;
r=r->next;
}
}
printf("%d",r->data);
return 0;
}
7-9 数据结构实验之链表九：双向链表
学会了单向链表，我们又多了一种解决问题的能力，单链表利用一个指针就能在内存中找到下一个位置，这是一个不会轻易断裂的链。但单链表有一个弱点——不能回指。比如在链表中有两个节点A,B，他们的关系是B是A的后继，A指向了B，便能轻易经A找到B,但从B却不能找到A。一个简单的想法便能轻易解决这个问题——建立双向链表。在双向链表中，A有一个指针指向了节点B，同时，B又有一个指向A的指针。这样不仅能从链表头节点的位置遍历整个链表所有节点，也能从链表尾节点开始遍历所有节点。对于给定的一列数据，按照给定的顺序建立双向链表，按照关键字找到相应节点，输出此节点的前驱节点关键字及后继节点关键字。
输入格式:
第一行两个正整数n（代表节点个数），m（代表要找的关键字的个数）。第二行是n个数（n个数没有重复），利用这n个数建立双向链表。接下来有m个关键字，每个占一行。(1<=n<=50)
输出格式:
对给定的每个关键字，输出此关键字前驱节点关键字和后继节点关键字。如果给定的关键字没有前驱或者后继，则不输出。
注意：每个给定关键字的输出占一行。
一行输出的数据之间有一个空格，行首、行末无空格。
输入样例:
10 3
1 2 3 4 5 6 7 8 9 0
3
5
0
输出样例:
2 4
4 6
9
#include <stdio.h>
int a[100000];
int main()
{
int n,m;
scanf("%d %d",&n,&m);
int i,j=0;
for(i=1;i<=n;i++)
{
scanf("%d",&a[i]);
}
int x;int pos=0;
for(i=1;i<=m;i++)
{
scanf("%d",&x);
for(j=1;j<=n;j++)
{
if(a[j]==x)
{
pos=j;
break;
}
}
if(pos==1)
printf("%d\n",a[j+1]);
else if(pos==n)
printf("%d\n",a[j-1]);
else printf("%d %d\n",a[j-1],a[j+1]);
}
return 0;
}
7-10 不敢死队问题
说到“敢死队”，大家不要以为我来介绍电影了，因为数据结构里真有这么道程序设计题目，原题如下：
有M个敢死队员要炸掉敌人的一个碉堡，谁都不想去，排长决定用轮回数数的办法来决定哪个战士去执行任务。如果前一个战士没完成任务，则要再派一个战士上去。现给每个战士编一个号，大家围坐成一圈，随便从某一个战士开始计数，当数到5时，对应的战士就去执行任务，且此战士不再参加下一轮计数。如果此战士没完成任务，再从下一个战士开始数数，被数到第5时，此战士接着去执行任务。以此类推，直到任务完成为止。
这题本来就叫“敢死队”。“谁都不想去”，就这一句我觉得这个问题也只能叫“不敢死队问题”。今天大家就要完成这道不敢死队问题。我们假设排长是1号，按照上面介绍，从一号开始数，数到5的那名战士去执行任务，那么排长是第几个去执行任务的？
输入格式:
输入包括多组数据，每行一个整数M（0<=M<=10000)（敢死队人数），若M=0，输入结束，不做处理。
输出格式:
输出一个整数n，代表排长是第n个去执行任务。
输入样例:
9
6
223
0
输出样例:
2
6
132
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <string.h>
// 方便计算，将编号从0到(N-1)映射到1到N int a[16]; // 存储0~N-1 int n; // 有n个人围成一圈 int k; // k表示数到k后的人被踢出队列
// 模拟操作，对每个人返回其下一个被踢出队列的人 int next(int x) { // 获取x的下一个人 int i; for (i = 1; i <= k; i++) { x = (x + 1) % n; while (a[x] == -1) { // 跳过已经被从队列中剔除的人 x = (x + 1) % n; } } return x; }
int main() {
while (scanf("%d", &n) != EOF && n != 0)
{ memset(a, 0, sizeof(a));
int s = 1; // 从编号为1的人开始数数 int i; k = 1; // 第一次踢出下标为1的人，从编号2开始计数
// 初始化数据
for (i = 0; i < n; i++) {
a[i] = i;
}
int left = n; // left表示剩余的人数
while (left > 1) {
// 计算出下一个被踢出队列的人
int x = next(s);
a[x] = -1; // 标记这个位置已经被踢出队列
s = x; // 开始数数的位置向后移动一位
while (a[s] == -1) { // 如果当前这个位置已经被踢出队列，就向后移动一位
s = (s + 1) % n;
}
left--;
}
// 输出答案
for (i = 0; i < n; i++) {
if (a[i] != -1) {
printf("%d\n", a[i] + 1);
break;
}
}
}
实验3 递推
7-1 养兔子
一对成熟的兔子每天能且只能产下一对小兔子，每次都生一公一母，每只小兔子的成熟期是1天，小兔子出生后隔一天才能再生小兔子。第一天某人领养了一对成熟的兔子，一公一母，请问第N天以后，他将会得到多少对兔子。
输入格式:
输入为一个整数n(1≤n≤90)。
输出格式:
对应输出第n天有几对兔子(假设没有兔子死亡现象，而且是一夫一妻制)。
输入样例1:
1
输出样例1:
1
输入样例2:
2
输出样例2:
2
#include<stdio.h>
int main()
{
int n,i;
long long int f[90];
f[1]=1;
f[2]=2;
scanf("%d",&n);
for(i=3;i<=n;i++)
{
f[i]=f[i-1]+f[i-2];
}
printf("%lld",f[n]);
return 0;
}
7-2 母牛的故事
有一对夫妇买了一头母牛，它从第2年起每年年初生一头小母牛。每头小母牛从第四个年头开始，每年年初也生一头小母牛。
请编程实现在第n年的时候，共有多少头母牛？
输入格式:
输入为一个整数n(0< n< 55)
输出格式:
输出在第n年的时候母牛的数量。
输入样例1:
2
输出样例1:
2
输入样例2:
5
输出样例2:
6
#include<stdio.h>
int main()
{
int f[55],i,n;
f[1]=1;
f[2]=2;
f[3]=3;
scanf("%d",&n);
for(i=4;i<=n;i++)
{
f[i]=f[i-1]+f[i-3];
}
printf("%d\n",f[n]);
return 0;
}
7-3 黄金时代
在古希腊时期，有一天毕达哥拉斯走在街上，在经过铁匠铺前他听到铁匠打铁的声音非常好听，于是驻足倾听。他发现铁匠打铁节奏很有规律，这个声音的比例被毕达哥拉斯用数学的方式表达出来。
这个比例就叫做黄金分割比，它是指将整体一分为二，较大部分与整体部分的比值等于较小部分与较大部分的比值，其比值约为0.6180339887。这个比例被公认为是最能引起美感的比例，因此被称为黄金分割。
现在小玉有一个正整数数列，这个数列的前一项和后一项的比值十分趋近于黄金分割比，即（a[i]）/（a[i+1]）~ 0.6180339887，(i>=1)，可是她只知道数列的第一项是5，现在她想通过已有条件推断出数列的任意项，请你帮助她编写一个程序计算。（请留意题目提示）
输入格式:
每次输入一个整数n（1<=n<=20）
输出格式:
输出一个数，代表这个数列的第n项a[n]。
输入样例:
1
输出样例:
5
#include<stdio.h>
int main()
{
int n,i;
int a[20];
scanf("%d",&n);
a[1]=5;
a[2]=8;
for(i=3;i<=n;i++)
{
a[i]=a[i-1]+a[i-2];
}
printf("%d",a[n]);
return 0;
}
7-4 骨牌铺方格
在2×n的一个长方形方格中,用一个1× 2的骨牌铺满方格,输入n ,输出铺放方案的总数.
例如n=3时,为2× 3方格，骨牌的铺放方案有三种,如下图：
输入格式:
输入包含一个整数n,表示该测试实例的长方形方格的规格是2×n (0< n<=50)。
输出格式:
输出铺放方案的总数。
输入样例:
在这里给出一组输入。例如：
3
输出样例:
在这里给出相应的输出。例如：
3
#include<stdio.h>
int main()
{
long long int a[50];
int i,n;
a[1]=1;
a[2]=2;
scanf("%d",&n);
for(i=3;i<=n;i++)
{
a[i]=a[i-1]+a[i-2];
}
printf("%lld",a[n]);
}
7-5 马拦过河卒
棋盘上A点有一个过河卒，需要走到目标B点。卒行走的规则：可以向下、或者向右。同时在棋盘上C点有一个对方的马，该马所在的点和所有跳跃一步可达的点称为对方马的控制点。因此称之为“马拦过河卒”。
棋盘用坐标表示，A点（0，0）、B点（n，m）（n，m为不超过15的整数），同样马的位置坐标是需要给出的。现在要求你计算出卒从A点能够到达B点的路径的条数，假设马的位置是固定不动的，并不是卒走一步马走一步。
输入格式:
一行四个数据，用空格分隔，分别表示B点的坐标和马的坐标。
输出格式:
一个数据，表示所有的路径条数。
输入样例:
6 6 3 3
输出样例:
6
#include<stdio.h>
int main()
{
int j,i,n,m,x,y;
int f[20][20],g[20][20];
scanf("%d %d %d %d",&n,&m,&x,&y);
for(i=0;i<=n;i++)
{
for(j=0;j<=m;j++)
{
f[i][j]=0;//每一点的路径都初始化为0；
}
}
for(i=0;i<=n;i++)
{
for(j=0;j<=m;j++)
{
g[i][j]=0;//先初始化每一个点都为不是🐎的控制点
}
}
g[x][y]=1;
g[x-1][y-2]=1;
g[x+1][y-2]=1;
g[x-2][y-1]=1;
g[x+2][y-1]=1;
g[x-2][y+1]=1;
g[x+2][y+1]=1;
g[x-1][y+2]=1;
g[x+1][y+2]=1;//然后根据🐎的“日”字走向，找到🐎的控制点，🐎的控制点我们就用1来表示
for(i=0;i<=n;i++)//先分析列
{
if(g[i][0]!=1)//如果这一列都不是🐎的控制点，那路径就是一条
f[i][0]=1;
else for(;i<=n;i++)//从该i开始，往后的直接就是0了，不用往下看了
f[i][0]=0;
}
for(j=0;j<=m;j++)
{
if(g[0][j]!=1)
f[0][j]=1;
else for(;j<=m;j++)
f[0][j]=0;
}
for(i=1;i<=n;i++)
{
for(j=1;j<=m;j++)
{
if(g[i][j]==0)
{
f[i][j]=f[i-1][j]+f[i][j-1];//如果不是🐎的控制点，那就是把从左和从上的两个加起来，就是它的路径数
}
}
}
printf("%d",f[n][m]);
return 0;
}
7-6 爬楼梯
小明是个非常无聊的人，他每天都会思考一些奇怪的问题，比如爬楼梯的时候，他就会想，如果每次可以上一级台阶或者两级台阶，那么上 n 级台阶一共有多少种方案？
输入格式:
输入只有一行为一个正整数 n(1 ≤ n ≤ 50)。
输出格式:
输出符合条件的方案数。
输入样例:
在这里给出一组输入。例如：
4
输出样例:
5
#include<stdio.h>
int main()
{
int n,i;
long long int a[50];
a[1]=1;
a[2]=2;
scanf("%d",&n);
for(i=3;i<=n;i++)
{
a[i]=a[i-1]+a[i-2];
}
printf("%lld",a[n]);
return 0;
}
7-7 三国佚事——巴蜀之危
话说天下大势，分久必合，合久必分。。。却道那魏蜀吴三国鼎力之时，多少英雄豪杰以热血谱写那千古之绝唱。古人诚不我欺，确是应了那句“一将功成万骨枯”。
是夜，明月高悬。诸葛丞相轻摇羽扇，一脸愁苦。原来是日前蜀国战事吃紧，丞相彻夜未眠，奋笔急书，于每个烽火台写下安排书信。可想，这战事多变，丞相运筹 帷幄，给诸多烽火台定下不同计策，却也实属不易。
谁成想这送信小厮竟投靠曹操，给诸葛丞相暗中使坏。这小厮将每封书信都投错了烽火台，居然没有一封是对的。不多时小厮便被抓住，前后之事却也明朗。这可急坏了诸葛丞相，这书信传错，势必会让蜀军自乱阵脚，不攻自破啊!
诸葛丞相现在想知道被这小厮一乱，这书信传错共有多少种情况。
输入格式:
输入一个正数n，代表丞相共写了n（1 <= n <= 20）封书信。
输出格式:
输出书信传错的情况数。
输入样例:
3
输出样例:
2
#include<stdio.h>
int main()
{
int n,i;
scanf("%d",&n);
long long int a[20];
a[1]=0;
a[2]=1;
for(i=3;i<=n;i++)
{
a[i]=(i-1)*(a[i-2]+a[i-1]);
}
printf("%lld",a[n]);
return 0;
}
7-8 王小二切饼
王小二自夸刀工不错，有人放一张大的煎饼在砧板上，问他：“饼不许离开砧板，切n(1<=n<=100)刀最多能分成多少块？”
输入格式:
输入切的刀数n。
输出格式:
输出为切n刀最多切的饼的块数。
输入样例:
100
输出样例:
5051
#include<stdio.h>
int main()
{
int n,i;
long long int a[100];
scanf("%d",&n);
a[1]=2;
for(i=2;i<=n;i++)
{
a[i]=a[i-1]+i;
}
printf("%lld",a[n]);
return 0;
}
7-9 蟠桃记
孙悟空在大闹蟠桃园的时候，第一天吃掉了所有桃子总数一半多一个，第二天又将剩下的桃子吃掉一半多一个，以后每天吃掉前一天剩下的一半多一个，到第n天准备吃的时候只剩下一个桃子。这下可把神仙们心疼坏了。
请帮忙计算一下，第一天开始吃的时候一共有多少个桃子？
输入格式:
输入包含一个正整数n（1≤n≤30），表示只剩下一个桃子的时候是在第n天发生的。
输出格式:
输出第一天开始吃的时候桃子的总数。
输入样例:
2
输出样例:
4
#include<stdio.h>
int main()
{
int n,i,m,sum=0;
long long int a[30];
a[1]=1;
scanf("%d",&n);
for(i=2;i<=n;i++)
{
a[i]=(a[i-1]+1)*2;
}
printf("%lld",a[n]);
return 0;
}
7-10 C语言实验——拍皮
球
小瑜3岁了，很喜欢玩皮球，看来今后喜欢打篮球的_。最近她发现球从手中落下时，每次落地后反跳回原高度的一半，再落下，每次球落地时数球跳了几次，数到n次时爸爸在边上喊停，问小瑜现在球到底总共走了多少距离，小瑜故作沉思状，爸爸又问接下来小球能跳多高啊，小瑜摇摇头，心想还没跳我怎么知道啊，难道爸爸是神啊！这时的你在边上出主意想给小瑜写个程序计算一下，因此任务就交给你啦！
假设球的初始高度为h，计算第n次落地时球经过的距离，以及落地后反弹能有多高。
输入格式:
每行有两个数，球的初始高度h(h<=100)和球落地的次数n(n <= 10)，用空格分隔。
输出格式:
输出第n次反弹时球经过的距离和球最后的高度，保留小数点后2位。
输入样例:
100 1
输出样例:
100.00 50.00
#include<stdio.h>
int main()
{
int i,m,j;
double n;
double a[10],b[10];
scanf("%lf %d",&n,&m);
a[0]=n;
b[0]=0;
b[1]=n;
for(i=1;i<=m;i++)
{
a[i]=a[i-1]/2.0;
}
for(j=2;j<=m;j++)
{
b[j]=b[j-1]+a[j-1]*2.0;
}
printf("%.2f %.2f\n",b[m],a[m]);
return 0;
}
实验4 递归
函数题：
6-1 数据结构实验之排序八：快速排序
本题要求实现一个快速排序函数。
给定 N ( N<= 100000 ) 个 int 范围内的整数，要求用快速排序对数据进行升序排列。
函数接口定义：
void Quick_sort (int array[], int l, int r);
AI助手
其中 array[] 、 l 、r 都是用户传入的参数。 array[] 是需要排序的数组，数组长度不会超过100000； l 和 r 是需要进行排序的左端点和右端点。
裁判测试程序样例：
#include <stdio.h>
void Quick_sort (int array[], int l, int r);
int main()
{
int N, array[100000];
scanf(“%d”, &N);
for(int i=0; i<N; i++)
{
scanf(“%d”, &array[i]);
}
Quick_sort(array, 0, N-1);
for(int i=0; i<N; i++)
{
printf(“%d “, array[i]);
}
printf(”\n”);
return 0;
}
/* 请在这里填写答案 */
输入样例：
8
49 38 65 97 76 13 27 49
输出样例：
在这里给出相应的输出。例如：
13 27 38 49 49 65 76 97
void Quick_sort (int array[],int l,int r)
{
int x=array[l],i=l,j=r;
if(l>=r)
return ;
while(i<j)
{
while(i<j&&array[j]>=x)
{
j--;
}
array[i]=array[j];
while(i<j&&array[i]<=x)
{
i++;
}
array[j]=array[i];
}
array[i]=x;
Quick_sort(array,l,i-1);
Quick_sort(array,i+1,r);
}
6-2 二分查找
本题要求实现一个二分查找函数。
给出含有 n 个数的升序序列，保证序列中的数两两不相等，这n个数编号从1 到n。
然后给出 q 次询问，每次询问给出一个数x，若x存在于此序列中，则输出其编号，否则输出-1。
函数接口定义：
int Binary_search(int array[], int l, int r, int x)；
其中 array 、 l 、 r 、 x都是用户传入的参数。 array 是要进行查询的序列，保证序列有序且出现的数字均不重复； l 和 r 是二分查找的区间的左端点和右端点；x 代表要在序列中查询的值。
当在序列中查询到 x 时，函数返回 x 在序列中出现的位置编号；否则函数返回 -1。
裁判测试程序样例：
#include <stdio.h>
int Binary_search(int array[], int l, int r, int x)；
int main()
{
int N, Q, i, x, ans;
int array[100005];
scanf("%d",&N);
for(i=1; i<=N; i++)
{
scanf("%d", &a[i]);
}
scanf("%d",&Q);
while(Q--)
{
scanf("%d", &x);
ans = Binary_search(a, 1, N, x);
printf("%d\n", ans);
}
return 0;
}
/* 请在这里填写答案 */
输入样例：
5
1 3 5 7 9
3
1
5
8
输出样例：
1
3
-1
int Binary_search(int array[],int l,int r,int x)
{
while(l<=r)
{
int mid=(l+r)/2;
if(array[mid]==x)
return mid;
else if(array[mid]>x)
r=mid-1;
else if(array[mid]<x)
l=mid+1;
}
return -1;
}
编程题目：
7-1 计算组合数
计算组合数。C(n,m),表示从n个数中选择m个的组合数。
计算公式如下：
若：m=0，C(n,m)=1
否则， 若 n=1，C(n,m)=1
否则，若m=n，C(n,m)=1
否则 C(n,m) = C(n-1,m-1) + C(n-1,m)
输入格式:
第一行是正整数N (1 <= N<= 100)，表示有N组要求的组合数。
接下来N行，每行两个整数n，m (0 <= m <= n <= 20)。
输出格式:
输出N行。每行输出一个整数表示C(n,m)。
输入样例:
在这里给出一组输入。例如：
3
2 1
3 2
4 0
输出样例:
在这里给出相应的输出。例如：
2
3
1
#include <stdio.h>
int fun(int n,int m)
{
if(m==0||n==1||n==m) return 1;
else return fun(n-1,m-1)+fun(n-1,m);
}
int main()
{
int N;
scanf("%d",&N);
while(N--)
{
int n,m;
scanf("%d %d",&n,&m);
printf("%d\n",fun(n,m));
}
return 0;
}
7-2 神奇的函数
神奇的函数是这样被定义的：
F(n, m) = {
if(n == 1 || m == 1)
F(n, m) = 1;
else
F(n, m) = F(n-1, m) + F(n, m-1);
}
输入格式:
第一行是正整数N (1 <= N<= 30)，表示有N组数据。
接下来N行，每行两个整数n，m (1 <= n, m <= 10)。
输出格式:
输出N行。每行输出一个整数表示F(n,m)。
输入样例:
在这里给出一组输入。例如：
1
1 2
输出样例:
在这里给出相应的输出。例如：
1
#include <stdio.h>
int fun(int n,int m)
{
if(n==1||m==1) return 1;
else return fun(n-1,m)+fun(n,m-1);
}
int main()
{
int a;
scanf("%d",&a);
int n,m;
while(a--)
{
scanf("%d %d",&n,&m);
printf("%d\n",fun(n,m));
}
return 0;
}
7-3 汉诺塔
汉诺塔（又称河内塔）问题是印度的一个古老的传说。
开天辟地的神勃拉玛在一个庙里留下了三根金刚石的棒A、B和C，A上面套着n个圆的金片，最大的一个在底下，其余一个比一个小，依次叠上去，庙里的众僧不倦地把它们一个个地从A棒搬到C棒上，规定可利用中间的一根B棒作为帮助，但每次只能搬一个，而且大的不能放在小的上面。
僧侣们搬得汗流满面，可惜当n很大时这辈子恐怕就很搬完了。
聪明的你还有计算机帮你完成，你能写一个程序帮助僧侣们完成这辈子的夙愿吗？
输入格式:
输入金片的个数n (1 <= n <= 10)。
输出格式:
输出搬动金片的全过程。格式见样例。
输入样例:
在这里给出一组输入。例如：
2
输出样例:
在这里给出相应的输出。例如：
Move disk 1 from A to B
Move disk 2 from A to C
Move disk 1 from B to C
#include <stdio.h>
void m(int n,char a,char b,char c)
{
if(n==1) printf("Move disk %d from %c to %c\n",n,a,c);
else
{
m(n-1,a,c,b);
printf("Move disk %d from %c to %c\n",n,a,c);
m(n-1,b,a,c);
}
}
int main()
{
int n;
scanf("%d",&n);
m(n,'A','B','C');
return 0;
}
7-4 全排列问题
从n个不同元素任取m（m<=n）个元素，按照一定的顺序排列起来，叫做从n个不同元素中取出m个元素的一个排列，当m=n时所有的排列情况叫全排列。现输入n个递增的数，请你输出这n个数的全排列。全排列输出顺序如样例所示。
输入格式:
第一行先输入一个整数n（1<=n<=10）。
接下来是一行输入n个由空格分开的互不相同的整数num （1 <= num <= 90000）。
输出格式:
对于每组数据，每一种排列占一行，各元素间用逗号隔开。
输入样例:
在这里给出一组输入。例如：
3
1 2 3
输出样例:
在这里给出相应的输出。例如：
1,2,3
1,3,2
2,1,3
2,3,1
3,1,2
3,2,1
#include<stdio.h>
int q[15];
int f[15];//当前数是否用过
int n;
int ans[15];//存每一个遍历的结果
void dfs(int u)//当前填的是第几个位置
{
if(u == n + 1)
{
for(int i = 1; i <= n; i++)
{
if(i == 1)
{
printf("%d", ans[i]);
}
else printf(",%d", ans[i]);
}
printf("\n");
}
for(int i = 1; i <= n; i++)
{
if(f[i] == 0)
{
f[i] = 1;//这个下标对应的数用过了
ans[u] = q[i];
dfs(u + 1);
// ans[u] = 0;
f[i] = 0;
}
}
}
int main()
{
scanf("%d", &n);
for(int i = 1; i <= n; i++)
{
scanf("%d", &q[i]);
}
dfs(1);
return 0;
}
7-5 喵帕斯之天才算数少女
莲酱要上一年级了，但是老师给他出了一个特别难的算术题。
4123.png
老师给出了一个函数
F(m, n)的定义是：
若m=0，返回n+1。
若m>0且n=0，返回F(m-1,1)。
若m>0且n>0，返回F(m-1,F(m,n-1))。
给出 m 和 n，计算 F(m, n) 的值。
输入格式:
第一行输入一个整数 t， 代表有 t 组数据。(1 <= t <= 15)
每组数据输入一行，包含两个非负整数 m，n。(0 <= m <= 3, 0 <= n <= 10)
输出格式:
每组数据输出一行，为 F(m, n) 的答案
输入样例:
在这里给出一组输入。例如：
3
3 2
3 10
2 1
输出样例:
在这里给出相应的输出。例如：
29
8189
5
#include <stdio.h>
int fun(int m,int n)
{
if(m==0) return n+1;
else if(m>0&&n==0) return fun(m-1,1);
else if(m>0&&n>0) return fun(m-1,fun(m,n-1));
}
int main()
{
int t;
scanf("%d",&t);
while(t--)
{
int m,n;
scanf("%d %d",&m,&n);
printf("%d\n",fun(m,n));
}
return 0;
}
7-6 青蛙过河
1）一条小溪尺寸不大，青蛙可以从左岸跳到右岸，在左岸有一石柱L，石柱L面积只容得下一只青蛙落脚，同样右岸也有一石柱R，石柱R面积也只容得下一只青蛙落脚。
2）有一队青蛙从小到大编号：1，2，…，n。
3）初始时：青蛙只能趴在左岸的石头 L 上，按编号一个落一个，小的落在大的上面-----不允许大的在小的上面。
4）在小溪中有S个石柱、有y片荷叶。
5）规定：溪中的每个石柱上如果有多只青蛙也是大在下、小在上，每个荷叶只允许一只青蛙落脚。
6）对于右岸的石柱R，与左岸的石柱L一样允许多个青蛙落脚，但须一个落一个，小的在上，大的在下。
7）当青蛙从左岸的L上跳走后就不允许再跳回来；同样，从左岸L上跳至右岸R，或从溪中荷叶、溪中石柱跳至右岸R上的青蛙也不允许再离开。
问题：在已知小溪中有 s 根石柱和 y 片荷叶的情况下，最多能跳过多少只青蛙？
输入格式:
第一行输入一个整数 t， 代表有 t 组数据。(1 <= t <= 15)
每组占一行，每行包含2个数s(s是小溪中的石柱数目)、y(y是小溪中的荷叶数目)。（0 <= s <= 10 , 0 <= y <= 10)
输出格式:
对每组输入，输出有一行，输出最多能跳过的青蛙数目。
输入样例:
在这里给出一组输入。例如：
2
0 2
1 2
输出样例:
在这里给出相应的输出。例如：
3
6
#include <stdio.h>
#include <math.h>
int main()
{
int t;
scanf("%d",&t);
while(t--)
{
int n,m;
scanf("%d %d",&n,&m);
m+=1;
printf("%.0f\n",m*pow(2,n));
}
return 0;
}
7-7 第k小的数
现有一个包含n个整数（1<=n<=900000）的无序序列(保证序列内元素各不相同)，输入一个整数k（1<=k<=n）,请用较快的方式找出该序列的第k小数并输出。
输入格式:
第一行先输入两个整数，n和k。
接下来是一行输入n个由空格分开的互不相同的整数num(1<=num<=90000000)。
输出格式:
输出该组数据中第k小的数num。
输入样例:
6 4
3 2 5 1 4 6
输出样例:
4
#include <stdio.h>
int a[1000000];
void m(int a[],int l,int r)
{
int i=l;int j=r;
if(l>=r) return ;
int x=a[l];
while(i<j)
{
while(i<j&&a[j]>=x)
j--;
a[i]=a[j];
while(i<j&&a[i]<=x)
i++;
a[j]=a[i];
}
a[i]=x;
m(a,l,i-1);
m(a,i+1,r);
}
int main()
{
int n,k;
scanf("%d %d",&n,&k);
int i=0;
for(i=1;i<=n;i++)
{
scanf("%d",&a[i]);
}
m(a,1,n);
printf("%d\n",a[k]);
return 0;
}
7-8 第X大的数
X最近爱上了区间查询问题，给出N (N <= 100000) 个数，然后进行M (M <= 50) 次询问，每次询问时，输入一个数X (1 <= X <= N)，输出N个数中第X大的数。
输入格式:
首先输入一个整数N，代表有N个数，下面一行包含N个整数，用空格隔开。然后为一个整数M，代表有M次询问，下面的M行，每行一个整数X。
输出格式:
输出N个数中第X大的数。
输入样例:
4
1 2 2 3
4
1
2
3
4
输出样例:
在这里给出相应的输出。例如：
3
2
2
1
#include <stdio.h>
int a[1000000000];
void m(int a[],int l,int r)
{
if(l>=r) return ;
int i=l,j=r;
int x=a[l];
while(i<j)
{
while(a[j]<=x&&i<j)
j--;
a[i]=a[j];
while(a[i]>=x&&i<j)
i++;
a[j]=a[i];
}
a[i]=x;
m(a,l,i-1);
m(a,i+1,r);
}
int main()
{
int n;
scanf("%d",&n);
int i=0;
for(i=1;i<=n;i++)
{
scanf("%d",&a[i]);
}
m(a,1,n);
int t;
scanf("%d",&t);
while(t--)
{
int x;
scanf("%d",&x);
printf("%d\n",a[x]);
}
return 0;
}
实验5 贪心
7-1 活动选择
学校的大学生艺术中心周日将面向全校各个学院的学生社团开放，但活动中心同时只能供一个社团活动使用，并且每一个社团活动开始后都不能中断。现在各个社团都提交了他们使用该中心的活动计划（即活动的开始时刻和截止时刻）。请设计一个算法来找到一个最佳的分配序列，以能够在大学生艺术中心安排不冲突的尽可能多的社团活动。
比如有5个活动，开始与截止时刻分别为：
最佳安排序列为：1,4,5。
输入格式:
第一行输入活动数目ｎ（0<ｎ<100）；
以后输入ｎ行，分别输入序号为1到ｎ的活动使用中心的开始时刻ａ与截止时刻ｂ（a,b为整数且0<=a<b<24，a,b输入以空格分隔）。
输出格式:
输出最佳安排序列所包含的各个活动（按照活动被安排的次序，两个活动之间用逗号分隔），如果有多个活动安排序列符合要求输出字典序最小的序列。
输入样例:
6
8 10
9 16
11 16
14 15
10 14
7 11
输出样例:
1,5,4
#include<stdio.h>
struct
{
int begin,end,num;
}a[100],t;
int main()
{
int n,i,j;
scanf("%d",&n);
for(i=0;i<n;i++)
{
scanf("%d %d",&a[i].begin,&a[i].end);
a[i].num=i+1;
}
for(i=0;i<n-1;i++)
{
for(j=0;j<n-i-1;j++)
{
if(a[j].end>a[j+1].end)
{
t=a[j+1];
a[j+1]=a[j];
a[j]=t;
}
}
}
int now=a[0].end;
printf("%d",a[0].num);
for(i=1;i<n;i++)
{
if(a[i].begin>=now)
{
printf(",%d",a[i].num);
now=a[i].end;
}
}
printf("\n");
return 0;
}
7-2 删数问题
键盘输入一个高精度的正整数n（≤100位），去掉其中任意s个数字后剩下的数字按照原来的左右次序组成一个新的正整数。
编程对给定的n与s，寻找一种方案，使得剩下的数字组成的新数最小。
输入格式:
输入两个数字，分别为原始数n，要去掉的数字数s (s < n)；
输出格式:
输出去掉s个数后最小的数。
输入样例:
178543 4
输出样例:
13
#include<stdio.h>
#include<string.h>
char n[250]; //利用字符数组来储存高精度数
int s,i,len,flag=1;
int main()
{
scanf("%s %d",n,&s);
len=strlen(n); //这里是长度函数，取n的长度并赋值给len
while(s!=0) //只要s不是0，取数的工作就没有做完！
{
i=0;
while(n[i]<=n[i+1]) //括号内的条件保证了不降序的条件，当它退出时，就是升序数列的末尾了
i++;
while(i<len-1) //这时已经找到了要取出的数——n[i]，这是取出的过程
{n[i]=n[i+1];i++;}
len--; //取出后数字长度减1
s--; //消耗掉一次取出次数
}
for(i=0;i<len;i++) //输出时要小心最高位是0的问题！处理输出……
{
if(n[i]=='0'&&i<len-1&&flag==1) //如果即将输出的这一位是0且是最高位而且不是最后一个
continue; //跳过
else
{printf("%c",n[i]);flag=0;}//输出并且明确n[i]不再是最高位
}
return 0;
}
7-3 活动选择问题
sdut 大学生艺术中心每天都有n个活动申请举办，但是为了举办更多的活动，必须要放弃一些活动，求出每天最多能举办多少活动。
输入格式:
输入第一行为申请的活动数n(n<100)，从第2行到n+1行，每行两个数，是每个活动的开始时间b，结束时间e；
输出格式:
输出每天最多能举办的活动数。
输入样例:
12
15 20
15 19
8 18
10 15
4 14
6 12
5 10
2 9
3 8
0 7
3 4
1 3
输出样例:
5
#include <stdio.h>
struct node
{
int begin, end;
} q[105], t;
int main()
{
int n;
scanf("%d", &n);
for (int i = 0; i < n; i++)
scanf("%d %d", &q[i].begin, &q[i].end);
for (int i = 0; i < n - 1; i++)
for (int j = 0; j < n - 1 - i; j++)
{
if (q[j].end > q[j + 1].end)
{
t = q[j];
q[j] = q[j + 1];
q[j + 1] = t;
}
}
int ans = 0, pos = 0;
for (int i = 0; i < n; i++)
{
if (q[i].begin >= pos)
{
ans++;
pos = q[i].end;
}
}
printf("%d\n", ans);
return 0;
}
7-4 区间覆盖问题
用i来表示x坐标轴上坐标为[i-1，i]的长度为1的区间，并给出n个不同的整数，表示n个这样的区间。
现在要求画m条线段覆盖住所有的区间，
条件是：每条线段可以任意长，但是要求所画线段的长度之和最小，
并且线段的数目不超过m。
输入格式:
输入包括多组数据，每组数据的第一行表示区间个数n(1≤n≤200) 和所需线段数m(1≤m≤50），第二行表示n个点的坐标i(1≤i≤200）。
输出格式:
每组输出占一行，输出m条线段的最小长度和。
输入样例:
5 3
1 3 8 5 11
输出样例:
7
#include <stdio.h>
int i,j,m,n,t,sum,a[250],b[250];
int main()
{
while(scanf("%d%d",&n,&m)!=EOF)
{
for(i=0;i<n;i++){
scanf("%d",&a[i]);
}
for(i=0;i<n-1;i++)
for(j=0;j<n-i-1;j++)
{
if(a[j]>a[j+1]){
t=a[j];
a[j]=a[j+1];
a[j+1]=t;
}
}
sum=a[n-1]-a[0]+1;
for(i=0;i<n-1;i++)
{
b[i]=a[i+1]-a[i]-1;
}
for(i=0;i<n-1;i++)
for(j=0;j<n-i-1;j++)
{
if(b[j]<b[j+1]){
t=b[j];
b[j]=b[j+1];
b[j+1]=t;
}
}
for(i=0;i<m-1;i++)
{
sum-=b[i];
}
printf("%d\n",sum);
}
}
7-5 最少拦截系统
某国为了防御敌国的导弹袭击,发展出一种导弹拦截系统.但是这种导弹拦截系统有一个缺陷:虽然它的第一发炮弹能够到达任意的高度,但
以后每一发炮弹都不能超过前一发的高度.某天,雷达捕捉到敌国的导弹来袭.由于该系统还在试用阶段,所以只有一套系统,因此有可能不能拦截所有的导弹.
怎么办呢?多搞几套系统呗!你说说倒蛮容易,成本呢?成本是个大问题啊.所以俺就到这里来求救了,请帮助计算一下最少需要多少套拦截系统.
输入格式:
输入包括:导弹总个数(正整数),导弹依此飞来的高度(雷达给出的高度数据是不大于30000的正整数,用空格分隔)
输出格式:
对应输出拦截所有导弹最少要配备多少套这种导弹拦截系统.
输入样例:
8 389 207 155 300 299 170 158 65
输出样例:
2
#include <stdio.h>
#include <string.h>
int main()
{
int n;
int a[201], x;
scanf("%d", &n);
memset(a, -1, sizeof(a));
int m = 0;
while (n--)
{
scanf("%d", &x);
int i;
for (i = 0; i < m; i++)
{
if (x <= a[i])
{
a[i] = x;
break;
}
}
if (i == m)
a[m++] = x;
}
printf("%d\n", m);
return 0;
}
7-6 悼念512汶川大地震遇难同胞
时间：2008年5月16日（震后第4天）
地点：汶川县牛脑寨
人物：羌族老奶奶
【转载整理】牛脑寨是一个全村600多人的羌族寨子，震后几天，这里依然能常常听到隆隆的声音，那是对面山上石头不断滑落的声音。在完成整个突击队的抢修移动基站的任务后，我提着相机开始记录这里的受创情况。
突然，我的视线里出现一个羌族老人，这让我无比的震惊，要知道，那是一个极陡的坡，这个佝偻着腰的老人是怎么艰难地爬上来的？她上来做什么？
老人背后是极陡的坡，她只有一只眼睛有依稀的视力，望着满地废墟，她徘徊了很久。家在哪里，她极力地用很低的视力找寻着。她曾经的家就在旁边，但是满目废墟已经让老人看不出来。她举目远眺，期望那里能看到家的一点点痕迹。原来家就在旁边，左手抓住一个房橼，努力让自己站住，地震过去三天了，她第一次回到曾经的家。
一个倒塌的柜子，里面装着一丝希望，老人很吃力地搬动掩盖在柜子上的薪柴。老人找到一把木匠用的刨子，老泪纵横，或许有哪个逝去的亲人是木匠。睹物思人，逝者已矣。
继续找，一把散碎的挂面出现在我的眼前。她颤颤巍巍地捞起铺满灰尘的挂面，再次流出了眼泪…
看着她仔细地把挂面放进胸前的围腰里，我顿然感觉到，这是老人在得到外援之前赖以生存的口粮了，如果不是交通中断，外部救援进不来，老人家又何必拖着80多岁的躯体，强忍失去亲人的痛苦，重新回到这夺取她亲人生命的废墟，寻找这点点挂面？老人是真饿了…
老人佝偻着腰，低声喃喃地念着那两句话“你们走了，我可怎么活”，拿着那对我们身处城市的人们微不足道的挂面，远去了…
PS: 拍完这组照片后我才知道，5月14号军用运输飞机第一次给汶川空投救援物资就掉在牛脑寨，受灾的村民们没有占为己有，而是汗流浃背地走了两个小时背到山下的县城交给政府。
对于幸存的灾民来说，最急待解决的显然是温饱问题，救灾部队一边在组织人员全力打通交通，一边在组织采购粮食。现在假设下拨了一定数量的救灾经费要去市场采购大米（散装）。如果市场有m种大米，各种大米的单价和重量已知，请问，为了满足更多灾民的需求，最多能采购多少重量的大米呢？
输入格式:
第一行是两个整数n和m（0 < n <= 1000, 0 < m <= 1000 ）,分别表示经费的金额和大米的种类，然后是m行数据，每行包含2个整数p和h(1 <= p <= 25,1 <= h <= 100)，分别表示单价和对应大米的重量。
输出格式:
请输出能够购买大米的最多重量（你可以假设经费买不光所有的大米）。输出占一行，保留2位小数。
输入样例:
7 2
3 3
4 4
输出样例:
2.33
#include <stdio.h>
struct
{
int p,h;
}a[1000],t;
int main()
{
int i,j,n,m;
double ans=0;
scanf("%d%d",&n,&m);
for(i=0;i<m;i++)
{
scanf("%d%d",&a[i].p,&a[i].h);
}
for(i=0;i<m;i++)
{
for(j=0;j<m-i-1;j++)
{
if(a[j].p>a[j+1].p)
{
t=a[j];
a[j]=a[j+1];
a[j+1]=t;
}
}
}
for(i=0;i<m;i++)
{
if(a[i].h*a[i].p>n)
{
break;
}
ans+=a[i].h*1.0;
n-=a[i].h*a[i].p;
}
ans=ans+n*1.0/a[i].p;
printf("%.2f\n",ans);
return 0;
}
7-7 懒虫小鑫
小鑫是个大懒虫，但是这一天妈妈要小鑫去山上搬些矿石去城里卖以补贴家用。小鑫十分的不开心。不开心归不开心，小鑫还是要做这件事情的。
我们把这个事情简化一下。有n块矿石，设第i块矿石由两个数字wi和pi表示。分别表示这块石头的重量和可以卖的价钱。小鑫每次只能搬一块矿石去城里卖，所以他决定每次都会搬重量最小的那块。如果恰好有几块重量相等，那就在这几块中挑选价值最高的带走。
由于路程原因。小鑫每天只能打m个来回，也就意味着他只能卖掉m块矿石。你能计算出他能得到多少钱么？
输入格式:
第一行为n，m。m≤n≤10000。
接下来有n行，每行两个数代表石头的w与p。
输出格式:
对于每组数据，输出有一行为一个数，为答案。
输入样例:
4 2
1 2
1 3
2 2
3 4
输出样例:
5
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
struct node
{
int p, h;
} a[10001], t;
void sort(int l, int r) //快排
{
t = a[l];
int i = l, j = r;
if (l >= r)
return;
while (i < j)
{
while ((a[j].h > t.h || (a[j].h == t.h && a[j].p <= t.p)) && i < j)
j--;
a[i] = a[j];
while ((a[i].h < t.h || (a[i].h == t.h && a[i].p >= t.p)) && i < j)
i++;
a[j] = a[i];
}
a[i] = t;
sort(l, i - 1);
sort(i + 1, r);
}
int main()
{
int n, m;
while (~scanf("%d %d", &n, &m))
{
for (int i = 0; i < n; i++)
{
scanf("%d %d", &a[i].h, &a[i].p);
}
sort(0, n - 1);
int ans = 0;
for (int i = 0; i < m; i++)
ans += a[i].p;
printf("%d\n", ans);
}
return 0;
}
7-8 装船问题
王小二毕业后从事船运规划工作，吉祥号货轮的最大载重量为M吨，有10种货物可以装船。第i种货物有wi吨，总价值是pi。王小二的任务是从10种货物中挑选若干吨上船，在满足货物总重量小于等于M的前提下，运走的货物的价重比最大。
输入格式:
输入数据的第一行有一个正整数M(0 < M < 10000)，表示所有货物最大载重量。在接下来的10行中，每行有若干个数（中间用空格分开），第i行表示的是第i种货物的货物的总价值pi ,总重量wi。(pi是wi的整数倍，0 < pi , wi < 1000)
输出格式:
输出一个整数，表示可以得到的最大价值。
输入样例:
在这里给出一组输入。例如：
100
10 10
20 10
30 10
40 10
50 10
60 10
70 10
80 10
90 10
100 10
输出样例:
在这里给出相应的输出。例如：
550
#include <stdio.h>
struct node
{
int wi, pi, b;
} q[10010], t;
void sort(int l, int r)
{
if (l >= r)
return;
t = q[l];
int i = l, j = r;
while (i < j)
{
while (q[j].b <= t.b && i < j)
j--;
q[i] = q[j];
while (q[i].b >= t.b && i < j)
i++;
q[j] = q[i];
}
q[i] = t;
sort(l, i - 1);
sort(i + 1, r);
}
int main()
{
int n;
scanf("%d", &n);
for (int i = 0; i < 10; i++)
{
scanf("%d %d", &q[i].pi, &q[i].wi);
q[i].b = q[i].pi / q[i].wi;
}
sort(0, 9);
int ans = 0;
for (int i = 0; i < 10; i++)
{
if (q[i].wi <= n)
{
ans += q[i].pi;
n -= q[i].wi;
}
else
{
ans += n * q[i].b;
break;
}
}
printf("%d\n", ans);
return 0;
}
7-9 商人小鑫
小鑫是个商人，当然商人最希望的就是多赚钱，小鑫也一样。
这天，他来到了一个遥远的国度。那里有着n件商品，对于第i件商品需要付出ci的价钱才能得到。当然，对于第i件商品，小鑫在自己心中有一个估价pi：代表着当他买下这件商品后带回他的国家可以卖出的价格。小鑫只能带回m件商品，你能帮他计算一下他最多能赚多少钱么？
输入格式:
第一行是n，m。( 0< m ≤ n ≤ 1000000 )
紧接着有n行，每一行有两个数 c ，p。第i行代表着ci，pi。( ci ≤ pi, 保证数据都在int范围内 )
输出格式:
输出一行一个数，代表小鑫能赚多少钱。
输入样例:
4 2
1 2
1 3
2 2
3 4
输出样例:
3
#include <stdio.h>
#include <stdlib.h>
struct node
{
int sell_price,buy_price;
int profit;
} a[10000000];
void qsort_profit(struct node a[],int left,int right);
//对利润进行快排；
int main()
{
int i;
int num_get,num_have;
while(~scanf("%d%d",&num_have,&num_get))
{
for(i=0; i<num_have; i++)
{
scanf("%d%d",&a[i].buy_price,&a[i].sell_price);
a[i].profit = a[i].sell_price - a[i].buy_price;
}//输入并计算利润；
qsort_profit(a,0,num_have);//对利润进行快排；
int sum_profit = 0;
for(i=0; i<num_get; i++) //计算利润总和；
sum_profit += a[i].profit;
printf("%d\n",sum_profit);
}
return 0;
}
void qsort_profit(struct node a[],int left,int right)
{
int i = left,j = right;
struct node key = a[left];
//将第一个数据储存，作为标准；
while(i>=j) return ;//递归结束的条件；
while(i<j)
{
while(i<j&&a[j].profit<=key.profit)
j--;
a[i] = a[j];
while(i<j&&a[i].profit>=key.profit)
i++;
a[j] = a[i];
}
a[i] = key;
qsort_profit(a,left,i-1);
qsort_profit(a,i+1,right);
}
7-10 商人的诀窍
E_star和von是中国赫赫有名的两位商人，俗话说的好无商不奸，最近E_star需要进一批苹果。可是他需要的苹果只有von才有，von的苹果都存在他的传说中很牛叉的仓库里，每个仓库都存了不同种类的苹果，而且每个仓库里的苹果的价钱不同。如果E_star想要买仓库i里的所有重量为f[i]的苹果他必须付m[i]的金钱。E_star开着他的传说中的毛驴车去拉苹果，而且他只带了N些金钱。E_star作为传说中的奸商希望用它所带的N金钱得到重量最多的苹果。你作为他最好的朋友，所以他向你求出帮助。希望你能帮忙计算出他能买到最多的苹果（这里指重量最大）。并输出最大重量。
提示：这里仅考虑仓库里苹果的重量，不考虑个数。
输入格式:
第一行包括两个非负整数N,M（分别代表E_star带的金币数,von盛苹果的仓库数量，不超过50）。
接下来有M行，每行包括两个数非负整数f[i]和m[i]分别表示第i仓库里存有重量为f[i]的苹果，如果将所有苹果买下要花费m[i]的金钱，E_star不必非要将每个仓库的苹果全部买下。
输出格式:
E_star用N的金币所能买到的最大重量的苹果的重量。结果保留三位小数。
输入样例:
20 3
25 18
24 15
15 10
输出样例:
31.500
#include <stdio.h>
struct node
{
int f, m;
double b;
} q[10001], t;
void sort(int l, int r) // 快排
{
if (l >= r)
return;
t = q[l];
int i = l, j = r;
while (i < j)
{
while (q[j].b <= t.b && i < j)
j--;
q[i] = q[j];
while (q[i].b >= t.b && i < j)
i++;
q[j] = q[i];
}
q[i] = t;
sort(l, i - 1);
sort(i + 1, r);
}
int main()
{
int n, m;
scanf("%d %d", &n, &m);
for (int i = 0; i < m; i++)
{
scanf("%d %d", &q[i].f, &q[i].m);
q[i].b = q[i].f * 1.0 / q[i].m * 1.0;
}
sort(0, m - 1);
double ans = 0;
for (int i = 0; i < m; i++)
{
if (q[i].m <= n)
{
ans += q[i].f * 1.0;
n -= q[i].m;
}
else
{
ans += n * 1.0 * q[i].b;
break;
}
}
printf("%.3lf\n", ans);
return 0;
}
实验6 动态规划
7-1 数字三角形问题
给定一个由n行数字组成的数字三角形如下图所示。试设计一个算法，计算出从三角形的顶至底的一条路径，使该路径经过的数字总和最大。
对于给定的由n行数字组成的数字三角形，计算从三角形的顶至底的路径经过的数字和的最大值。
输入格式:
输入数据的第1行是数字三角形的行数n，1≤n≤100。接下来n行是数字三角形各行中的数字。所有数字在0…99之间。
输出格式:
输出数据只有一个整数，表示计算出的最大值。
输入样例:
在这里给出一组输入。例如：
5
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5
输出样例:
30
#include <stdio.h>
#include <stdlib.h>
int main()
{
int j,n,i,d[101][101],a[101][101];
scanf("%d",&n);
for(i=1;i<=n;i++)
for(j=1;j<=i;j++)
scanf("%d",&d[i][j]);
for(j=1;j<=n;j++)
a[n][j]=d[n][j];
for(i=n-1;i>=1;i--)
for(j=1;j<=i;j++)
{
if(a[i+1][j]>a[i+1][j+1])
a[i][j]=a[i+1][j]+d[i][j];
else a[i][j]=a[i+1][j+1]+d[i][j];
}
printf("%d\n",a[1][1]);
return 0;
}
7-2 小鑫去爬山
马上就要放假了，小鑫打算去爬山。
小鑫要去爬的这座山有n个海拔区间。为了清楚描述我们可以从上到下标号1到n。
第i个区间有i个落脚点，每一个落脚点都有一个危险值。
小鑫需要在第n个海拔区间挑选一个点向上爬，爬到第1个海拔区间（也就是山顶）。他必须规划一条路径，让危险值之和最小。这样才安全的。
并不是任意两个落脚点之间都可以相互到达。我们这样定义对于第i个（i<n）区间的第j个落脚点，只有第i+1个区间的第j个和第j+1个可以到达。
你能帮助他找到最安全的路么？
输入格式:
输入数据为多组，到文件结束。
对于每一组数据，第一行有一个数，为n 。n≤100;
接下来有n行，第i行有i个数。代表第i个区间i个落脚点的危险值。
所有数据均在int范围内。
输出格式:
对于每组数据，输出一行一个数，为答案。
输入样例:
在这里给出一组输入。例如：
5
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5
输出样例:
17
#include <stdio.h>
#include <stdlib.h>
int main()
{
int n,i,j;
int a[101][101],b[101][101];
while(scanf("%d",&n)!=EOF)
{
for(i=1;i<=n;i++)
{
for(j=1;j<=i;j++)
{
scanf("%d",&a[i][j]);
}
}
for(i=1;i<=n;i++)
{
b[n][i]=a[n][i];
}
for(i=n-1;i>=1;i--)
{
for(j=1;j<=i;j++)
{
if(b[i+1][j]<b[i+1][j+1])b[i][j]=b[i+1][j]+a[i][j];
else b[i][j]=b[i+1][j+1]+a[i][j];
}
}
printf("%d\n",b[1][1]);
}
return 0;
}
7-3 最长公共子序列问题
给定两个序列 X={x1,x2,…,xm} 和 Y={y1,y2,…,yn}，找出X和Y的最长公共子序列。
输入格式:
输入数据有多组，每组有两行 ，每行为一个长度不超过500的字符串（输入全是大写英文字母（A,Z）），表示序列X和Y。
输出格式:
每组输出一行，表示所求得的最长公共子序列的长度，若不存在公共子序列，则输出0。
输入样例:
ABCBDAB
BDCABA
输出样例:
4
#include <stdio.h>
#include <string.h>
#define N 510
int i,j,len1,len2,c[N][N];
char x[N],y[N];
int main()
{
while(scanf("%s %s",x,y)!=EOF){
len1=strlen(x);
len2=strlen(y);
for(i=0;i<=len1;i++)
{c[i][0]=0;}
for(j=0;j<=len2;j++) {c[0][j]=0;}
for(i=1;i<=len1;i++){
for(j=1;j<=len2;j++)
{
if(x[i-1]==y[j-1])//这里一定要注意
{
c[i][j]=c[i-1][j-1]+1;
}
else
{
if(c[i-1][j]>c[i][j-1])
{c[i][j]=c[i-1][j];}
else{ c[i][j]=c[i][j-1];}
}
}}
printf("%d\n",c[len1][len2]); }
return 0;
}
7-4 最长公共子序列
从一个给定的串中删去（不一定连续地删去）0个或0个以上的字符，剩下地字符按原来顺序组成的串。例如：“ ”，“a”，“xb”，“aaa”，“bbb”，“xabb”，“xaaabbb”都是串“xaaabbb”的子序列。（例子中的串不包含引号。）
编程求N个非空串的最长公共子序列的长度。限制：2<=N<=100；N个串中的字符只会是数字0，1，…，9或小写英文字母a，b，…，z；每个串非空且最多含100个字符；N个串的长度的乘积不会超过30000。
输入格式:
文件第1行是一个整数T，表示测试数据的个数（1<=T<=10）。接下来有T组测试数据。各组测试数据的第1行是一个整数Ni，表示第i组数据中串的个数。各组测试数据的第2到N+1行中，每行一个串，串中不会有空格，但行首和行末可能有空格，这些空格当然不算作串的一部分。
输出格式:
输出T行，每行一个数，第i行的数表示第i组测试数据中Ni个非空串的最长公共子序列的长度。
输入样例:
1
3
ab
bc
cd
输出样例:
0
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
char a[110][110];//二维字符数组保存字符
int d[30010];
int len[110];//一维len保存每个字符数组的长度
int n;
int f(int l[])
{
int i, j, index, ret, t;
for (i = 1; i <= n; i++)
if (l[i] == 0)//判断字符长的是否为0,为0直接以0退出
return 0;
//-------------------------------------------------------------
for (index = l[n] - 1, i = n - 1; i >= 1; i--)
index = index * len[i] + l[i] - 1;//转化为一维数组，原理有待考究（对我来说）
if (d[index] >= 0)
return d[index];//一但有值，直接返回
//-------------------------------------------------------------
for (i = 2; i <= n; i++)
if (a[1][l[1] - 1] != a[i][l[i] - 1])
break;//在看每个字符串的末尾（我当时看错了，，以为是倒数第二）
if (i > n)//字符串末尾全相同
{
for (j = 1; j <= n; j++)
l[j]--;
ret = f(l) + 1;
for (j = 1; j <= n; j++)
l[j]++;//记得恢复
}
else//有不同，递归
{
ret = 0;
for (j = 1; j <= n; j++)
{
l[j]--;//感觉类似于dfs,历遍了
t = f(l);
if (t > ret)
ret = t;
l[j]++;
}
}
d[index] = ret;
return ret;
}
//-------------------------------------------------------------
int main()
{
int T, i;
int l[110];//保存多维字符数组长度的动态变化
scanf("%d", &T);
while (T--)
{
scanf("%d", &n);
for (i = 1; i <= n; i++)
{
scanf("%s", a[i]);
len[i] = strlen(a[i]);
l[i] = strlen(a[i]);
}
memset(d, -1, sizeof(d));
printf("%d\n", f(l));
}
return 0;
}
7-5 最长上升子序列
一个数的序列bi，当b1 < b2 < … < bS的时候，我们称这个序列是上升的。对于给定的一个序列(a1, a2, …, aN)，我们可以得到一些上升的子序列(ai1, ai2, …, aiK)，这里1<= i1 < i2 < … < iK <= N。比如，对于序列(1, 7, 3, 5, 9, 4, 8)，有它的一些上升子序列，如(1, 7), (3, 4, 8)等等。这些子序列中最长的长度是4，比如子序列(1, 3, 5, 8)。
你的任务，就是对于给定的序列，求出最长上升子序列的长度。
输入格式:
输入的第一行是序列的长度N (1 <= N <= 1000)。第二行给出序列中的N个整数，这些整数的取值范围都在0到10000。
输出格式:
最长上升子序列的长度。
输入样例:
在这里给出一组输入。例如：
7
1 7 3 5 9 4 8
输出样例:
在这里给出相应的输出。例如：
4
#include<stdio.h>
#define MAX_N 1005
int dp[MAX_N];
int main() {
int n, a[MAX_N];
// 读入序列
scanf("%d", &n);
for (int i = 1; i <= n; ++i) {
scanf("%d", &a[i]);
}
// 动态规划求解
for (int i = 1; i <= n; ++i) {
dp[i] = 1;
for (int j = 1; j < i; ++j) {
if (a[j] < a[i] && dp[j]+1 > dp[i]) {
dp[i] = dp[j] + 1;
}
}
}
// 找到最长上升子序列的长度
int max_len = 0;
for (int i = 1; i <= n; ++i) {
if (dp[i] > max_len) max_len = dp[i];
}
// 输出结果
printf("%d\n", max_len);
return 0;
}
7-6 上升子序列
一个只包含非负整数的序列bi，当b1 < b2 < … < bS的时候，我们称这个序列是上升的。对于给定的一个序列{a1, a2, …,aN}，我们可以得到一些上升的子序列{ai1, ai2, …, aiK}，这里1 ≤ i1 < i2 <…< iK ≤ N。例如：对于序列{1, 7, 3, 5, 9, 4, 8}，有它的一些上升子序列，如{1, 7}, {3, 4, 8}等等。这些子序列中序列和最大的是子序列{1, 3, 5, 9}，它的所有元素的和为18。
对于给定的一个序列，求出它的最大的上升子序列的和。
注意：最长的上升子序列的和不一定是最大的哦。
输入格式:
输入包含多组测试数据，对于每组测试数据：
输入数据的第一行为序列的长度 n(1 ≤ n ≤ 1000)，
第二行为ｎ个非负整数 b1，b2，…，bn(0 ≤ bi ≤ 1000)。
输出格式:
对于每组测试数据，输出其最大上升子序列的和。
输入样例:
7
1 7 3 5 9 4 8
输出样例:
在这里给出相应的输出。例如：
18
#include<stdio.h>
#include<string.h>
#define MAX_N 1005
int dp[MAX_N]; // dp[i] 表示以第 i 个数结尾的最大上升子序列的和
int main() {
int n, a[MAX_N];
while(scanf("%d", &n) != EOF) {
// 初始化
memset(dp, 0, sizeof(dp));
int max_sum = 0;
// 读入序列
for (int i = 0; i < n; ++i) scanf("%d", &a[i]);
// 动态规划求解
for (int i = 0; i < n; ++i) {
dp[i] = a[i]; // 初始化 dp[i] 为 a[i]
for (int j = 0; j < i; ++j) {
if (a[j] < a[i] && dp[j] + a[i] > dp[i]) {
dp[i] = dp[j] + a[i];
}
}
// 更新 max_sum
if (dp[i] > max_sum) max_sum = dp[i];
}
// 输出结果
printf("%d\n", max_sum);
}
return 0;
}
7-7 递归的函数
给定一个函数 f(a, b, c)：
如果 a ≤ 0 或 b ≤ 0 或 c ≤ 0 返回值为 1；
如果 a > 20 或 b > 20 或 c > 20 返回值为 f(20, 20, 20)；
如果 a < b 并且 b < c 返回 f(a, b, c−1) + f(a, b−1, c−1) − f(a, b−1, c)；
其它情况返回 f(a−1, b, c) + f(a−1, b−1, c) + f(a−1, b, c−1) − f(a-1, b-1, c-1)。
看起来简单的一个函数？你能做对吗？
输入格式:
输入包含多组测试数据，对于每组测试数据：
输入只有一行为 3 个整数a, b, c(a, b, c < 30)。
输出格式:
对于每组测试数据，输出函数的计算结果。
输入样例:
1 1 1
2 2 2
输出样例:
2
4
#include <stdio.h>
int f(int a, int b, int c)
{
if (a <= 0 || b <= 0 || c <= 0) {
return 1;
} else if (a > 20 || b > 20 || c > 20) {
return f(20, 20, 20);
} else if (a < b && b < c) {
return f(a, b, c - 1) + f(a, b - 1, c - 1) - f(a, b - 1, c);
} else {
return f(a - 1, b, c) + f(a - 1, b - 1, c) + f(a - 1, b, c - 1) - f(a - 1, b - 1, c - 1);
}
}
int main()
{
int a, b, c;
while (scanf("%d%d%d", &a, &b, &c) == 3) {
printf("%d\n", f(a, b, c));
}
return 0;
}
7-8 走迷宫
有一个mn格的迷宫（表示有m行、n列），其中有可走的也有不可走的，如果用1表示可以走，0表示不可以走，输入这mn个数据和起始点、结束点（起始点和结束点都是用两个数据来描述的，分别表示这个点的行号和列号）。现在要你编程找出所有可行的道路，要求所走的路中没有重复的点，走时只能是上下左右四个方向。如果一条路都不可行，则输出相应信息（用-1表示无路）。
输入格式:
第一行是两个数m，n（1< m, n< 15)，接下来是m行n列由1和0组成的数据，最后两行是起始点和结束点。
输出格式:
所有可行的路径，输出时按照左上右下的顺序。描述一个点时用（x，y）的形式，除开始点外，其他的都要用“->”表示。如果没有一条可行的路则输出-1。
输入样例:
在这里给出一组输入。例如：
5 4
1 1 0 0
1 1 1 1
0 1 1 0
1 1 0 1
1 1 1 1
1 1
5 4
输出样例:
在这里给出相应的输出。例如：
(1,1)->(1,2)->(2,2)->(2,3)->(3,3)->(3,2)->(4,2)->(4,1)->(5,1)->(5,2)->(5,3)->(5,4)
(1,1)->(1,2)->(2,2)->(2,3)->(3,3)->(3,2)->(4,2)->(5,2)->(5,3)->(5,4)
(1,1)->(1,2)->(2,2)->(3,2)->(4,2)->(4,1)->(5,1)->(5,2)->(5,3)->(5,4)
(1,1)->(1,2)->(2,2)->(3,2)->(4,2)->(5,2)->(5,3)->(5,4)
(1,1)->(2,1)->(2,2)->(2,3)->(3,3)->(3,2)->(4,2)->(4,1)->(5,1)->(5,2)->(5,3)->(5,4)
(1,1)->(2,1)->(2,2)->(2,3)->(3,3)->(3,2)->(4,2)->(5,2)->(5,3)->(5,4)
(1,1)->(2,1)->(2,2)->(3,2)->(4,2)->(4,1)->(5,1)->(5,2)->(5,3)->(5,4)
(1,1)->(2,1)->(2,2)->(3,2)->(4,2)->(5,2)->(5,3)->(5,4)
#include<stdio.h>
#include<string.h>
int s[20][20];//模拟地图
int a[1000][1000];// 记录这个点是否被走过
struct node
{
int x;
int y;
}p[1007]; //记录从起点到终点走的方案，也是用来输出的
int n,m,k,flag;
int enx,eny;
int next[4][2]={{0,-1},{-1,0},{0,1},{1,0}}; //左上右下的顺序
void move(int x1,int y1,int k) //k是用来记录几步的，也是方便下面用循环输出
{
p[k].x=x1; //坐标 x ,因为经过下面if的判断，来到这里的点都是符合要求的
p[k].y=y1; //坐标 y ，
if(x1==enx&&y1==eny) //走到终点
{
flag=1; //声明有走到终点的路线
for(int q=0;q<=k;q++)
{ //把记录的都输出，把记录的连起来输出，就是一个路线
if(q==0)
{
printf("(%d,%d)",p[q].x,p[q].y);
}
else printf("->(%d,%d)",p[q].x,p[q].y);
}
printf("\n");
return;
}
//类似于穷举，或者平行宇宙，走一步后，又会出现4个方向可走，依次如此
for(int h=0;h<4;h++)
//试试所有的方向，按照题目的要求的顺序来碰壁，因为有四个方向，所以h<4
{
int nx=next[h][0]+x1;//开始加数进行位移，按照左上右下来位移
int ny=next[h][1]+y1;
if(nx>0&&ny>0&&nx<=n&&ny<=m&&s[nx][ny]==1&&a[nx][ny]==0)
{
//只要走的坐标位置不超过地图范围，且没走过，且在迷宫上是1就可以执行
a[nx][ny]=1;//标记此点已经走过
move(nx,ny,k+1);//递归一次说明走了一步就加一，因为是在k的基础上加1，函数结束时，回溯后，还是恢复原来的值。
//如果是用自加就在下面搭配个自减就行
a[nx][ny]=0;//回溯 ，
}
}
return;
}
int main()
{
int x,y;
while(~scanf("%d %d",&n,&m)) //多组输入
{
memset(s,0,sizeof(s)); //涉及多组输出要进行初始化
memset(a,0,sizeof(a));
memset(p,0,sizeof(p));
for(int i=1;i<=n;i++) //写迷宫地图
{
for(int j=1;j<=m;j++)
{
scanf("%d",&s[i][j]);
}
}
scanf("%d%d",&x,&y); //写入始点和终点
scanf("%d%d",&enx,&eny);
a[x][y]=1; //起点标记为1，因为一上来就在这个点
move(x,y,0);//从起点开始走
if(flag==0)
{
printf("-1\n");//如果是0说明一条路径都没有
}
}
return 0;
}
7-9 取数字问题
给定M×N的矩阵，其中的每个元素都是-10到10之间的整数。你的任务是从左上角(1,1)走到右下角(M,N)，每一步只能够向右或者向下，并且不能够走出矩阵的范围。你所经过的方格里面的数字都必须被选取，请找出一条最合适的道路，使得在路上被选取的数字之和是尽可能小的正整数。
输入格式:
输入第1行是两个整数M和N,(2<=M<=10,2<=N<=10)，分别表示矩阵的行和列的数目。接下来M行，每行包括N个整数，就是矩阵中的每一行的N个元素。
输出格式:
输出只有一行，就是一个整数，表示所选道路上数字之和所能达到的最小正整数。如果不能达到任何正整数，输出-1。
输入样例:
2 2
0 2
1 0
输出样例:
1
#include <stdio.h>
#include <string.h>
#define MAXNM 14
#define oo 123456789
int a[MAXNM][MAXNM], ans;
int m, n;
void search(int i, int j, int sum)
{
sum += a[i][j];
if(i < m)
search(i+1, j, sum);
if(j < n)
search(i, j+1, sum);
if(i == m && j == n && sum < ans && sum > 0)
{
ans = sum;
}
}
int main()
{
int i, j, sum;
scanf("%d %d", &m, &n);
for(i = 1; i <= m; i++)
for(j = 1; j <= n; j++)
scanf("%d", &a[i][j]);
ans = oo;
sum = 0;
search(1, 1, sum);
if(ans != oo)
printf("%d\n", ans);
else
printf("-1\n");
return 0;
}
7-10 免费馅饼
都说天上不会掉馅饼，但有一天gameboy正走在回家的小径上，忽然天上掉下大把大把的馅饼。说来gameboy的人品实在是太好了，这馅饼别处都不掉，就掉落在他身旁的10米范围内。馅饼如果掉在了地上当然就不能吃了，所以gameboy马上卸下身上的背包去接。但由于小径两侧都不能站人，所以他只能在小径上接。由于gameboy平时老呆在房间里玩游戏，虽然在游戏中是个身手敏捷的高手，但在现实中运动神经特别迟钝，每秒种只有在移动不超过一米的范围内接住坠落的馅饼。现在给这条小径如图标上坐标：
为了使问题简化，假设在接下来的一段时间里，馅饼都掉落在0-10这11个位置。开始时gameboy站在5这个位置，因此在第一秒，他只能接到4,5,6这三个位置中期中一个位置上的馅饼。问gameboy最多可能接到多少个馅饼？（假设他的背包可以容纳无穷多个馅饼）
输入格式:
输入数据有多组。每组数据的第一行为以正整数n(0 < n < 100000)，表示有n个馅饼掉在这条小径上。在结下来的n行中，每行有两个整数x,T(0 <= T < 100000),表示在第T秒有一个馅饼掉在x点上。同一秒钟在同一点上可能掉下多个馅饼。n=0时输入结束。
输出格式:
每一组输入数据对应一行输出。输出一个整数m，表示gameboy最多可能接到m个馅饼。
提示：本题的输入数据量比较大，建议用scanf读入，用cin可能会超时。
输入样例:
6
5 1
4 1
6 1
7 2
7 2
8 3
0
输出样例:
4
#include<stdio.h>
#include<string.h>
int dp[12][100005];
int pos,time;
int max(int a,int b)
{
return a>b?a:b;
}
int main()
{
int n;
int a;
while(scanf("%d",&n)!=EOF)
{
if(n==0)
{
break;
}
int i,j;
int ma=0;
memset(dp,0,sizeof(dp));
for(i=1;i<=n;i++)
{
scanf("%d%d",&pos,&time);
dp[pos][time]++;
ma=max(time,ma);
}
for(i=ma-1;i>=0;i--)
{
dp[0][i]+=max(dp[0][i+1],dp[1][i+1]);
dp[10][i]+=max(dp[9][i+1],dp[10][i+1]);
for(j=1;j<10;j++)
{
dp[j][i]+=max(max(dp[j-1][i+1],dp[j][i+1]),dp[j+1][i+1]);
}
}
printf("%d\n",dp[5][0]);
}
}