主题：[原创]第29次编程比赛第1题
zhiyanglee [专家分：0] 发布于 2006-06-02 22:21:00
以下是第29次编程比赛第1题的相关事宜：
比赛时间：
星期四晚上8：00到星期六晚上10：00
注意事项与ccpp的第二题相同，这里就不再重复。
有一整数序列，求其序列第k小的数。已知序列每个数不大于1000，
长度不超过1000，有可能有重复数字。
如：10 50 2 31 7 6 16第二小的数为6。[color=FF0000]（k以1为起点）[/color]
函数接口为：
int KthNumOfList(int List[],int len,int k);
int List[]为整型序列
int len为序列长度
int k 为要求第几小
返回值为第k小的数
附加题：（没有什么思路，拿出来给大家讨论,不是比赛题目)
同济ACM的题
在古埃及，人们使用单位分数的和(形如1/a的, a是自然数)表示一切有理数。
如：2/3=1/2+1/6,但不允许2/3=1/3+1/3,因为加数中有相同的。
对于一个分数a/b,表示方法有很多种，但是哪种最好呢？
首先，加数少的比加数多的好，其次，加数个数相同的，最小的分数越大越好。
如：
19/45=1/3 + 1/12 + 1/180
19/45=1/3 + 1/15 + 1/45
19/45=1/3 + 1/18 + 1/30,
19/45=1/4 + 1/6 + 1/180
19/45=1/5 + 1/6 + 1/18.
最好的是最后一种，因为1/18比1/180,1/45,1/30,1/180都大。
给出a,b(0〈a〈b〈1000),编程计算最好的表达方式。
Input
第一行:N 表示有N组测试数据，每组测试数据为一行包含a,b(0〈a〈b〈1000)。
Output
每组测试数据若干个数，自小到大排列，依次是单位分数的分母。
Sample Input
1
19 45
Sample Output
5 6 18
回复列表 （共27个回复）
沙发
fenix124 [专家分：70] 发布于 2006-06-01 22:50:00
//题目可能没有读懂，成功返回该值，否则为-1
#include <stdlib.h>
int compare(const void *a,const void *b)
{
int *c,*d;
c = (int*)a;
d = (int*)b;
return *c-*d;
}
int KthNumOfList(int List[],int len,int k)
{
int *temp,i,j;
temp = new int[len];
for(i = 0; i < len;i++)
temp[i] = List[i];
qsort(temp,len,sizeof(int),compare);
j = 1;
for(i = 1;i < len;i++)
{
if(temp[i] != temp[i-1])j++;
if(j == k) break;
}
if(j == k)
{
j = temp[i];
delete []temp;
return j;
}
delete []temp;
return -1;
}
板凳
fenix124 [专家分：70] 发布于 2006-06-01 22:55:00
//另外一种方法,如果每个数都是大于等于0的话
#include <string.h>
int KthNumOfList(int List[],int len,int k)
{
int temp[1010],i,j;
memset(temp,0,1010*4);
for(i = 0; i < len;i++)
temp[i] = 1;
j = 0;
for(i = 0;i < 1005;i++)
{
if(temp[i]) j++;
if(j == k) return i;
}
return -1;
}
3 楼
xieyong456 [专家分：2620] 发布于 2006-06-01 23:05:00
/*第一次参加人生地不熟啊，就这一题就看出自己肚子里墨水少的可怜啊*/
#include <stdio.h>
#define N 7
int KthNumOfList(int List[] ,int len, int k);
int main(void)
{
int A[N], i, n;
printf("请输入你需要判断第几大的数 : ");
scanf("%d", &n);
printf("请输入数组 : ");
for(i = 0; i < N; i++)
scanf("%d", &A[i]);
printf("第%d大的数是====%d\n", n, KthNumOfList(A, N, n));
return 0;
}
int KthNumOfList(int List[],int len,int k)
{
int i, j, m, temp;
int count = 0;
if(len > 1000 || k > len)
return 0;
for(i = 0; i < len; i++) {
m = i;
for(j = i + 1; j < len; j++) {
if(List[j] < List[m])
m = j;
}
temp = List[i];
List[i] = List[m];
List[m] = temp;
if(count == k)
return List[i];
count++;
}
}
4 楼
iAkiak [专家分：8460] 发布于 2006-06-02 00:51:00
一般来说第1大的数字就是最大的数字，第2大的数字就是次大的数字。
第i大的数字Ni和第j大的数字Nj有 Ni <= Nj iff j >= i
不过看题目的例子，k表示的应该是按从小到大排序的次序。
有O(n * log n)的方法来计算第k大的问题，形如快排。不过既然题目给出的数据范围是1000，那么就可以写个O(n)的了。
int KthNumOfList(int List[], int len, int k)
{
int count[1001] = {0}, i;
assert(k <= len);
for (i = 0; i < len; i++)
count[List[i]]++;
for (i = 0; i <= 1000; i--)
{
if (count[i] != 0)
{
k -= count[i];
if (k <= 0)
return i;
}
}
return 0;
}
5 楼
johnywoo [专家分：1290] 发布于 2006-06-02 09:31:00
int partition(int *p,int left,int right);
int* nth_element(int* p,int left,int right,int n);
int KthNumOfList(int List[],int len,int k);
int partition(int *p,int left,int right)
{
int pivot=left++;
while(left<=right)
{
while(left<=right&&p[left]<p[pivot])
{
left++;
}
while(left<=right&&p[right]>=p[pivot])
{
right--;
}
if(left<right)
{
int tmp=p[left];
p[left]=p[right];
p[right]=tmp;
left++;
right--;
}
}
if(pivot!=right)
{
int tmp=p[pivot];
p[pivot]=p[right];
p[right]=tmp;
}
return right;
}
//返回[left,right]下标范围内的第n小的元素位置
int* nth_element(int* p,int left,int right,int n)
{
int i;
if(left>right||n<1||n>right-left+1) return NULL;
i=partition(p,left,right);
if(left+n-1<i)
return nth_element(p,left,i-1,n);
if(left+n-1>i)
return nth_element(p,i+1,right,n-(i-left+1));
return p+i;
}
int KthNumOfList(int List[],int len,int k)
{
if(k<=0 || k>=len)
return 1001;//k超出范围
return *nth_element(List,0,len-1,len-k+1);
}
6 楼
爱与恨007 [专家分：110] 发布于 2006-06-02 11:21:00
int KthNumOfList(int List[],int len,int k)
{
int list_x[1001]={0},i,n,m=0;
for(i=0;i<len;i++)
{
n=List[i];
list_x[n]=n;
if(List[i]==0)
m++;
}
for(i=0;i<1001;i++)
{
if(list_x[i]!=0)
m++;
if(m==k)
{
return list_x[i];break;
}
}
}
7 楼
yunzhou008 [专家分：410] 发布于 2006-06-02 11:54:00
#include <iostream>
using namespace std;
int KthNumOfList(int List[],int len,int k);
void QuickSort(int List[],int Start,int End);
int main()
{
int List[]={10,50,2,31,7,6,16};
cout<<KthNumOfList(List,7,2)<<endl;
cin.get();
return 0;
}
int KthNumOfList(int List[],int len,int k)
{
QuickSort(List,0,len-1);
return List[k-1];
}
void QuickSort(int List[],int Start,int End)
{
int i=Start,j=End+1;
int s=List[Start];
while(i<j)
{
do ++i;while(List[i]>s);
do --j;while(List[j]<s);
if(i<j)
{
int temp=List[i];
List[i]=List[j];
List[j]=temp;
}
}
List[Start]=List[j];
List[j]=s;
if(Start<j-1)
QuickSort(List,Start,j-1);
if(j+1<End)
QuickSort(List,j+1,End);
}
8 楼
yunzhou008 [专家分：410] 发布于 2006-06-02 12:43:00
#include <iostream>
using namespace std;
int KthNumOfList(int List[],int len,int k);
void QuickSort(int List[],int Start,int End);
int main()
{
int List[]={10,50,2,31,7,6,16};
cout<<KthNumOfList(List,7,2)<<endl;
cin.get();
return 0;
}
int KthNumOfList(int List[],int len,int k)
{
QuickSort(List,0,len-1);
return List[k-1];
}
void QuickSort(int List[],int Start,int End)
{
int i=Start,j=End+1;
int s=List[Start];
while(i<j)
{
do ++i;while(List[i]<s);
do --j;while(List[j]>s);
if(i<j)
{
int temp=List[i];
List[i]=List[j];
List[j]=temp;
}
}
List[Start]=List[j];
List[j]=s;
if(Start<j-1)
QuickSort(List,Start,j-1);
if(j+1<End)
QuickSort(List,j+1,End);
}
10 楼
goal00001111 [专家分：4030] 发布于 2006-06-02 14:28:00
/*
Name:
Copyright:
Author:goal00001111
Date: 02-06-06 13:21
Description:
有一整数序列，求其序列第k大的数。已知序列每个数不大于1000，
长度不超过1000，有可能有重复数字。
如：10 50 2 31 7 6 16第二大的数为6。（k以1为起点）
函数接口为：
int KthNumOfList(int List[],int len,int k);
int List[]为整型序列
int len为序列长度
int k 为要求第几大
返回值为第k大的数
*/
/*
算法介绍：
(1) 设置一个最小长度least，当len <= least时，直接对数组按递增排序，第k个元素即为所求元素；否则，转步骤(2).
(2) 把元素划分为lenp = len/5 组, 每组5个元素,不足5个元素的那组先不予考虑.
(3) 取每组的中值元素,构成一个长度为lenp的数组p[].
(4) 对数组p[]递归地执行本算法,得到其中值元素m.
(5) 把原数组List[]划分成p,q,r三组,使得小于m的元素存放在p[],等于m的元素存放在q[],大于m的元素存放在r[].
(6) 如果lenp > k, 对p[]递归地执行本算法,并把最后返回的值存储到m;否则,转步骤(7).
(7) 如果lenp + lenq < k,对r[]递归地执行本算法,并把最后返回的值存储到m.
(8) 很明显,此时的m就是所要选择的元素, 销毁p,q,r, 并返回m.
*/
#include <iostream>
using namespace std;
int KthNumOfList(int List[],int len,int k);
static int Compare(const void *p1, const void *p2);
void Mid(int a[], int i, int p[]);
void Swap(int & a, int & b);
int main()
{
int a[8] = {10,20,30,40,5,6,7,8};
int n = KthNumOfList(a, 8, 2);
cout << n << "\n";;
getchar();
return 0;
}
int KthNumOfList(int List[], int len, int k)
{
const int least = 64; //设置一个最小长度least
if (len <= least)
{
qsort(List, len, sizeof(int), Compare); //对数组按递增排序
return List[k-1];
}
int *p = new int[3*len/4];
int lenp = len/5; //把元素划分为lenp = len/5 组, 每组5个元素,不足5个元素的那组先不予考虑.
for (int i=0; i<lenp; i++)
{
Mid(List, i, p); //取每组的中值元素,构成一个长度为lenp的数组p[].
}
int m = KthNumOfList(p, lenp, lenp/2 + lenp%2);//对数组p[]递归地执行本算法,得到其中值元素m.
int *q = new int[3*len/4];
int *r = new int[3*len/4];
int lenq = 0;
int lenr = 0;
lenp = 0;
//把原数组List[]划分成p,q,r三组,使得小于m的元素存放在p[],等于m的元素存放在q[],大于m的元素存放在r[].
for (int i=0; i<len; i++)
{
if (List[i] < m)
p[lenp++] = List[i];
else if (List[i] == m)
q[lenq++] = List[i];
else
r[lenr++] = List[i];
}
if (lenp > k)
{
m = KthNumOfList(p, lenp, k);
}
else if(lenp + lenq < k)
{
m = KthNumOfList(r, lenr, k-lenp-lenq);
}
//很明显,此时的m就是所要选择的元素, 销毁p,q,r, 并返回m.
delete []p;
delete []q;
delete []r;
return m;
}
static int Compare(const void *p1, const void *p2)
{
return (*(int *)p1) - (*(int *)p2);
}
/*
函数介绍：从数组a[]中,每5个元素为一组,取第i组的中值元素作为数组p[]的第i个元素.
输入： 数组a[].
组号 i .
输出：存放中值元素的数组p[].
*/
void Mid(int a[], int i, int p[])
{
int k = 5 * i;
if (a[k] > a[k+2])
Swap(a[k], a[k+2]);
if (a[k+1] > a[k+3])
Swap(a[k+1], a[k+3]);
if (a[k] > a[k+1])
Swap(a[k], a[k+1]);
if (a[k+2] > a[k+3])
Swap(a[k+2], a[k+3]);
if (a[k+1] > a[k+2])
Swap(a[k+1], a[k+2]);
if (a[k+4] > a[k+2])
p[i] = a[k+2];
else if (a[k+4] > a[k+1])
p[i] = a[k+4];
else
p[i] = a[k+1];
}
void Swap(int & a, int & b)
{
int temp = a;
a = b;
b = temp;
}
我来回复
您所在位置：