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);
}
}
