1-1 数据结构实验之排序八:快速排序
任务描述:
本题要求实现一个快速排序函数。给定 N ( N<= 100000 ) 个 int 范围内的整数,要求用快速排序对数据进行升序排列。
函数接口定义:
void Quick_sort (int array[], int l, int r);
其中 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
相关限制:
代码长度限制16KB 时间限制400ms 内存限制64MB 栈限制8192KB
答案:
#include <stdio.h> void Quick_sort(int array[],int l,int r) { int k = array[l],i=l,j=r; if(l>=r)return; while(i<j) { while(i<j&&array[j]>=k) j--; array[i] = array[j]; while(i<j&&array[i]<=k) i++; array[j] = array[i]; } array[i]=k; Quick_sort(array,l,i-1); Quick_sort(array,i+1,r); }
1-2 删数问题
任务描述:
键盘输入一个高精度的正整数n(≤100位),去掉其中任意s个数字后剩下的数字按照原来的左右次序组成一个新的正整数。编程对给定的n与s,寻找一种方案,使得剩下的数字组成的新数最小。
输入格式:
输入两个数字,分别为原始数n,要去掉的数字数s (s < n);
输出格式:
输出去掉s个数后最小的数。
输入样例:
178543 4
输出样例:
13
相关限制:
代码长度限制16KB 时间限制1000ms 内存限制64MB 栈限制8192KB
答案:
#include <stdio.h> #include int main() { char num[200]={'\0'}; int s,i,j; scanf("%s %d",num,&s); while(s>0) { i=0; while(num[i]!='\0'&&num[i]<=num[i+1]) i++; for(j=i;j<strlen(num);j++) { num[j]=num[j+1]; } s--; } i=0; while(num[i]=='0') i++; if(num[i]=='\0') printf("0\n"); else printf("%s\n",&num[i]); return 0; }
1-3 母牛的故事
任务描述:
有一对夫妇买了一头母牛,它从第2年起每年年初生一头小母牛。每头小母牛从第四个年头开始,每年年初也生一头小母牛。请编程实现在第n年的时候,共有多少头母牛?
输入格式:
输入为一个整数n(0< n< 55)
输出格式:
输出在第n年的时候母牛的数量。
输入样例:
在这里给出一组输入。例如:
5
输出样例:
在这里给出相应的输出。例如:
6
相关限制:
代码长度限制16KB 时间限制400ms 内存限制64MB 栈限制8192KB
答案:
#include <stdio.h> #include int main() { int n,i; long long int f[100]; scanf("%d",&n); f[1]=1; f[2]=2; f[3]=3; f[4]=4; for(i=5;i<=n;i++) { f[i]=f[i-1]+f[i-3]; } printf("%d\n",f[n]); return 0; }
1-4 骨牌铺方格
任务描述:
在2×n的一个长方形方格中,用一个1× 2的骨牌铺满方格,输入n ,输出铺放方案的总数.例如n=3时,为2× 3方格,骨牌的铺放方案有三种。
输入格式:
输入包含一个整数n,表示该测试实例的长方形方格的规格是2×n (0< n<=50)。
输出格式:
输出铺放方案的总数。
输入样例:
在这里给出一组输入。例如:
3
输出样例:
在这里给出相应的输出。例如:
3
相关限制:
代码长度限制16KB 时间限制400ms 内存限制64MB 栈限制8192KB
答案:
#include <stdio.h> #include int main() { int n,i; long long int f[100]; scanf("%d",&n); f[1]=1; f[2]=2; for(i=3;i<=n;i++) { f[i]=f[i-1]+f[i-2]; } printf("%lld\n",f[n]); return 0; }
1-5 青蛙过河
任务描述:
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
相关限制:
代码长度限制16KB 时间限制400ms 内存限制64MB 栈限制8192KB
答案:
#include <stdio.h> int f(int n,int m); int main() { int t,s,y,c; scanf("%d",&t); while(t--) { scanf("%d%d",&s,&y); c=f(s,y); printf("%d\n",c); } return 0; } int f(int n,int m) { int t; if(n==0) t=m+1; else t=2*f(n-1,m); return t; }
1-6 数字三角形问题
任务描述:
给定一个由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
相关限制:
代码长度限制16KB 时间限制1000ms 内存限制64MB 栈限制8192KB
答案:
#include <stdio.h> int main () { int a[120][120],b[120][120],n,i,j; scanf("%d",&n); for(i=0;i<n;i++) { for(j=0;j<=i;j++) { scanf("%d",&b[i][j]); } } for(i=0;i<n;i++) { a[n][i]=b[n][i]; } for(i=n-1;i>=0;i--) { for(j=0;j<=i;j++) { if(a[i+1][j]>a[i+1][j+1]) { a[i][j]=a[i+1][j]+b[i][j]; } else a[i][j]=a[i+1][j+1]+b[i][j]; } } printf("%d\n",a[0][0]); return 0; }
1-7 蟠桃记
任务描述:
孙悟空在大闹蟠桃园的时候,第一天吃掉了所有桃子总数一半多一个,第二天又将剩下的桃子吃掉一半多一个,以后每天吃掉前一天剩下的一半多一个,到第n天准备吃的时候只剩下一个桃子。这下可把神仙们心疼坏了。请帮忙计算一下,第一天开始吃的时候一共有多少个桃子?
输入格式:
输入包含一个正整数n(1≤n≤30),表示只剩下一个桃子的时候是在第n天发生的。
输出格式:
输出第一天开始吃的时候桃子的总数。
输入样例:
在这里给出一组输入。例如:
2
输出样例:
在这里给出相应的输出。例如:
4
相关限制:
代码长度限制16KB 时间限制400ms 内存限制64MB 栈限制8192KB
答案:
#include <stdio.h> int main () { int n,i; long long int f[100]; scanf("%d",&n); f[n]=1; f[n-1]=4; for(i=n-1;i>=1;i--) { f[i-1]=2*(f[i]+1); } printf("%d\n",f[1]); return 0; }
1-8 汉诺塔
任务描述:
汉诺塔(又称河内塔)问题是印度的一个古老的传说。开天辟地的神勃拉玛在一个庙里留下了三根金刚石的棒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
相关限制:
代码长度限制16KB 时间限制400ms 内存限制64MB 栈限制8192KB
答案:
#include <stdio.h> void move(int,char,char,char); int main() { int n; scanf("%d",&n); move(n,'A','B','C'); return 0; } void move(int m,char p,char q,char r) { if(m==1) { printf("Move disk %d from %c to %c\n",m,p,r); } else { move(m-1,p,r,q); printf("Move disk %d from %c to %c\n",m,p,r); move(m-1,q,p,r); } }