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 时间限制600ms 内存限制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 个数的升序序列，保证序列中的数两两不相等，这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
相关限制：
代码长度限制16KB 时间限制400ms 内存限制64MB 栈限制8192KB
答案：
int Binary_search(int array[], int l, int r, int x)
{
int mid;
while (l <= r)
{
mid = (l + r) / 2;
if (array[mid] >x)
{
r = mid - 1;
}
else if (array[mid] < x)
{ l = mid + 1; }
else
{
return(mid);
break;
}
}
if (l>r)
return -1;
}
1-3 计算组合数
任务描述:
计算组合数。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
相关限制：
代码长度限制16KB 时间限制400ms 内存限制64MB 栈限制8192KB
答案：
#include <stdio.h>
int f(int n,int m);
int main()
{
int t,n,m,c;
scanf("%d",&t);
while(t--)
{
scanf("%d%d",&n,&m);
c=f(n,m);
printf("%d\n",c);
}
return 0;
}
int f(int n,int m)
{
int t;
if(m==0||n==1||m==n)
t=1;
else
t=f(n-1,m-1)+f(n-1,m);
return t;
}
1-4 神奇的函数
任务描述:
神奇的函数是这样被定义的：
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
相关限制：
代码长度限制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 == 1 || m == 1)
t = 1;
else
t= F(n-1, m) + F(n, m-1);
return t;
}
1-5 汉诺塔
任务描述:
汉诺塔（又称河内塔）问题是印度的一个古老的传说。开天辟地的神勃拉玛在一个庙里留下了三根金刚石的棒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);
}
}
1-6 全排列问题
任务描述:
从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
相关限制：
代码长度限制16KB 时间限制3500ms 内存限制64MB 栈限制8192KB
答案：
#include <stdio.h>
#include
#define maxn 11
int n;
int used[maxn];
int mat[maxn];
int num[maxn];
void solve(int l)
{
int i;
if(l>=n)
{
printf("%d",num[0]);
for(i=1;i<n;++i)
printf(",%d", num[i]);
puts("");
return;
}
for(i=0;i<n;++i)
{
if(!used[i])
{
used[i]=1;
num[l]=mat[i];
solve(l+1);
used[i]=0;
}
}
}
int main()
{
int i;
scanf("%d",&n);
for(i=0;i<n;++i)
{
scanf("%d",&mat[i]);
}
memset(used,0,sizeof(used));
solve(0);
return 0;
}
1-7 喵帕斯之天才算数少女
任务描述:
莲酱要上一年级了，但是老师给他出了一个特别难的算术题。老师给出了一个函数。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) 的答案
输入样例:
在这里给出一组输入。例如：
29 8189 5
输出样例:
在这里给出相应的输出。例如：
2
相关限制：
代码长度限制16KB 时间限制400ms 内存限制64MB 栈限制8192KB
答案：
#include <stdio.h>
int f(int m, int n)
{
int fmn;
if(m == 0)
{
fmn = n + 1;
}
else if(m > 0 && n == 0)
{
fmn = f(m - 1, 1);
}
else if(m > 0 && n > 0)
{
fmn = f(m - 1, f(m, n - 1));
}
return fmn;
}
int main()
{
int i, t, n, m, fmn;
scanf("%d", &t);
for(i = 0; i < t; i++)
{
scanf("%d %d", &m, &n);
fmn = f(m, n);
printf("%d\n", fmn);
}
return 0;
}
1-8 青蛙过河
任务描述:
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-9 第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
相关限制：
代码长度限制16KB 时间限制250ms 内存限制64MB 栈限制8192KB
答案：
#include <stdio.h>
int a[1000001];
void st(int a[],int l,int r)
{
int key=a[l];
int i=l;
int j=r;
if(l>=r)return;
if(l<r)
{
while(i<j)
{
while(i<j&&a[j]>=key)j--;
a[i]=a[j];
while(i<j&&a[i]<=key)i++;
a[j]=a[i];
}
a[i]=key;
st(a,l,i-1);
st(a,i+1,r);
}
}
int main()
{
int n,m,i;
scanf("%d%d",&n,&m);
for(i=1; i<=n; i++)
scanf("%d",&a[i]);
st(a,1,n);
printf("%d\n",a[m]);
return 0;
}
1-10 第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
相关限制：
代码长度限制16KB 时间限制1000ms 内存限制64MB 栈限制8192KB
答案：
#include <stdio.h>
int a[110000];
void QuickSort(int a[],int l,int r)
{
int i=l,j=r,k=a[l];
if(l>=r)return;
while(i<j)
{
while(i<j&&a[j]<=k)j--;
a[i]=a[j];
while(i<j&&a[i]>=k)i++;
a[j]=a[i];
}
a[i]=k;
QuickSort(a,l,i-1);
QuickSort(a,i+1,r);
}
int main()
{
int n,m,i,x;
while(scanf("%d",&n)!=EOF)
{
for(i=0; i<n; i++)scanf("%d",&a[i]);
QuickSort(a,0,n-1);
scanf("%d",&m);
for(i=0; i<m; i++)
{
scanf("%d",&x);
printf("%d\n",a[x-1]);
}
}
return 0;
}
