问题 A: 随机数
题目描述
有一个rand(n)的函数，它的作用是产生一个在[0,n)的随机整数。现在有另外一个函数，它的代码如下：
int random(int n, int m)
{
return rand(n)+m;
}
显而易见的是函数random(n,m)可以产生任意范围的随机数。现在问题来了，如果我想要产生范围在[a,b)内的一个随机数，那么对应的n，m分别为多少？
输入
输入的第一行为一个正整数T (T<=1000)，表示一共有T组测试数据。
对于每组测试数据包含两个整数a，b (a<=b)。
输出
对于每组测试数据，输出一行包含两个整数n和m，两个整数中间有一个空格分隔。
样例输入 Copy
2
0 5
1 4
样例输出 Copy
5 0
3 1
#include <stdio.h>
int main() {
int T,a,b,m,n;
while(scanf("%d",&T)!=EOF){
for(int i=0;i<T;i++){
scanf("%d%d",&a,&b);
printf("%d %d\n",b-a,a);
}
}
return 0;
}问题 B: 随机化快速排序
题目描述
使用Java或C++等语言中内置的随机函数实现随机化快速排序，在数组中随机选择一个元素作为分区的主元(Pivot)。
输入
多组样例输入，每组由一个一维整型数组组成。
输出
随机化快速排序之后的一维整型数组（升序排列）。
样例输入 Copy
6 1 8 6 5 3 4 5 12 42 2 5 8样例输出 Copy
1 3 4 5 6 8 2 5 8 12 42
样例输出并没有消除重复的数字！
#include <stdio.h>
#include<stdlib.h>
//生成随机数
int random(int p,int q){
return rand()%(q-p+1)+p;
}
//交换
void swap(int a[],int i,int j){
int t=a[i];
a[i]=a[j];
a[j]=t;
}
//分区
int partition(int a[],int p,int q){
int x=a[p];
int i=p,j;
for(j=p+1;j<=q;j++){
if(a[j]<=x){
i++;
swap(a,i,j);
}
}
swap(a,p,i);
return i;
}
//排序
void quick(int a[],int p,int q){
if (p < q) {
int r = random(p,q);
swap(a, q, r);
r = partition(a, p, q);
quick(a, p, r - 1);
quick(a, r + 1, q);
}
}
int main() {
int n;
int a[100];
while (scanf("%d", &n) == 1) {
for (int i = 0; i < n; ++i) {
scanf("%d", &a[i]);
}
quick(a, 0, n- 1);
for (int i = 0; i <n; ++i) {
printf("%d ", a[i]);
}
printf("\n");
}
return 0;
}问题 C: 第k小元素问题
题目描述
输入一个整数数组，请求出该数组的第k小元素。要求时间复杂度为O(n)。
输入
每组输入包括两行，第一行为一个整数数组，两个数字之间用空格隔开；第二行为k值。数组中元素个数小于1000。
输出
输出第k小元素的值。
样例输入 Copy
2 5 6 1 8 7 9 2样例输出 Copy
2
#include <stdio.h>
#include <stdlib.h>
//交换
void swap(int a[],int i,int j){
int t=a[i];
a[i]=a[j];
a[j]=t;
}
//分区
int partition(int a[],int p,int q){
int x=a[p];
int i=p,j;
for(j=p+1;j<=q;j++){
if(a[j]<=x){
i++;
swap(a,i,j);
}
}
swap(a,p,i);
return i;
}
int random(int a[], int p, int q) {
if(q>=p){
int k =(int)(rand()%(q-p+1)+p);
swap(a, k, p);
return partition(a, p, q);
}
}
//找第K小元素
int quick(int a[],int s,int t,int k){
if(s==t) return a[s];
int i = random(a,s,t);
int j = i-s+1;//左边个数
if(k<=j) return quick(a,s,i,k);
else return quick(a,i+1,t,k-j);
}
int main() {
int n,k;
int a[1000];
while(~scanf("%d",&a[0])){
int i =1;
while (scanf("%d",&a[i++])) {
if(getchar()=='\n'){
break;
}
}
scanf("%d",&k);
printf("%d\n",quick(a,0,i-1,k));
}
return 0;
}问题 D: 找中位数
题目描述
请设计一个算法，不排序，快速计算出一个无序数列的中位数。 时间复杂度要求为O(n)。
如果有奇数个元素，中位数则是数组排序后最中间的那个数字。
如果是偶数个元素，中位数则是数组排序后最中间两个元素的平均值。输入
有多组输入，每组输入的第一行为n(1<=n<=1e5)，表示该数列的元素个数。
第二行为n个整数组成的无序数列输出
每组样例输出一行，表示该无序数列的中位数。
若为偶数，请保留三位小数
若为奇数，直接输出样例输入 Copy
5 5 3 2 1 4样例输出 Copy
3
#include <stdio.h>
#include <stdlib.h>
#define N 100000
// 交换
void swap(int *a, int *b) {
int t = *a;
*a = *b;
*b = t;
}
// 分区
int partition(int a[], int l, int h) {
int p = a[h];
int i = l - 1;
for (int j = l; j < h; j++) {
if (a[j] <= p) {
i++;
swap(&a[i],&a[j]);
}
}
swap(&a[i+1],&a[h]);
return i+1;
}
// 快速选择
int quick(int a[], int l, int h, int k) {
if (l == h) {
return a[l];
}
int p = partition(a, l, h);
if (k == p) {
return a[k];
} else if (k < p) {
return quick(a, l, p - 1, k);
} else {
return quick(a, p + 1, h, k);
}
}
// 计算中位数
double find(int a[], int n) {
if (n%2==1) {
return (double)quick(a,0,n-1,n/2);
} else {
int m1 = quick(a,0,n - 1,n / 2 - 1);
int m2 = quick(a,0,n - 1,n / 2);
return (m1 + m2) / 2.0;
}
}
int main() {
int n,a[N];
while (scanf("%d",&n)!=EOF) {
for (int i = 0; i < n; i++) {
scanf("%d",&a[i]);
}
double m = find(a, n);
if (n % 2 == 0) {
printf("%.3f\n",m);
} else {
printf("%d\n",(int)m);
}
}
return 0;
}问题 E: 数组合并
题目描述
编写一个程序，将两个有序数组合并成一个更大的有序数组，要求时间复杂度为O(n)。
输入
多组数据输入，每组输入包括两行，每行第一个数字为数组长度n，然后输入n个有序整数。
输出
输出合并后的数组（升序），每组输出用一个空行隔开。
样例输入 Copy
3 1 3 5 3 2 4 6 2 1 2 4 3 4 5 6样例输出 Copy
1 2 3 4 5 6 1 2 3 4 5 6
#include <stdio.h>
#include <stdlib.h>
int main() {
int n1, n2;
while (scanf("%d",&n1)!=EOF) {
int a1[100],a2[100],a[10000];
for (int i = 0;i < n1;i++) {
scanf("%d",&a1[i]);
}
scanf("%d",&n2);
for (int i = 0; i < n2; i++) {
scanf("%d",&a2[i]);
}
int i=0,j=0,q=0;
while (i<n1 && j<n2) {
if (a1[i] < a2[j]) {
a[q++]=a1[i++];
} else {
a[q++]=a2[j++];
}
}
while(i<n1) {
a[q++]=a1[i++];
}
while(j<n2) {
a[q++]=a2[j++];
}
for (i=0;i<n1+n2;i++) {
printf("%d%c",a[i],(i==n1+n2-1)? '\n':' ');
}
printf("\n");
}
return 0;
}问题 F: 归并排序
题目描述
编写一个程序，使用分治策略实现二路归并排序（升序）。
输入
多组输入，每组第一个数字为数组长度，然后输入一个一维整型数组。
输出
输出排序之后（升序）的一维整型数组，每组输出占一行。
样例输入 Copy
6 1 8 6 5 3 4 5 12 42 2 5 8样例输出 Copy
1 3 4 5 6 8 2 5 8 12 42
#include <stdio.h>
#include <stdlib.h>
void merge(int sr[],int tr[],int s,int m,int t){
int i=s,j=m+1,k=s;
while(i<=m&&j<=t){
if(sr[i]<=sr[j]) tr[k++]=sr[i++];
else tr[k++]=sr[j++];
}
while(i<=m) tr[k++]=sr[i++];
while(j<=t) tr[k++]=sr[j++];
}
void mergeSort(int sr[],int tr[],int s,int t){
if(s<t){
int m=(s+t)/2;
mergeSort(sr,tr,s,m);
mergeSort(sr,tr,m+1,t);
merge(sr,tr,s,m,t);
for(int i=s;i<=t;i++){
sr[i]=tr[i];
}
}
}
int main() {
int n,sr[100000],tr[100000];
while (scanf("%d",&n)!=EOF) {
for(int i=0;i<n;i++){
scanf("%d",&sr[i]);
}
mergeSort(sr,tr,0,n-1);
for(int j=0;j<n;j++){
printf("%d%c",tr[j],(j==n-1)?'\n':' ');
}
}
return 0;
}