主题：[原创]第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个回复）
11 楼
maobingwen [专家分：0] 发布于 2006-06-02 15:07:00
int KthNumOfList(int List[],int len,int k)
{ int i,j;
for(i=0;i<len;i++)
{ for(j=i+1;j<len;j++)
{
if(List[i]>List[j])
{
int temp=List[j];
List[i]=List[j];
List[j]=temp;
}
}
}
return List[k-1];
}
12 楼
情若江水 [专家分：0] 发布于 2006-06-02 15:13:00
[em4][em2][em10]
13 楼
火海时代 [专家分：230] 发布于 2006-06-02 16:28:00
#include <iostream>
using namespace std;
int KthNumOfList(int List[],int len,int k)
{
int temp = 1001;
int count = 0,l = 0;
int *a = new int[k];
int i,j,x,m;
for(i = 0; i < k; i++)
a[i] = 1001;
for(i = 0; i < len; i++)
{
if(List[i] < temp)
{
for(j = 0; j < k; j++)
{
if((List[i] < a[j]))
;
else
break;
}
if(j!=0&&j!=-1)
{
if(j == k-1&&i == 0)
j = k;
else if(j == 1)
{
a[0] = List[i];
continue;
}
l = a[j-1];
for(m = j-1; m > 0; m--)
{
count = a[m -1];
a[m-1] = l;
l = count;
}
a[j-1] = List[i];
}
temp = a[0];
}
}
temp = a[0];
delete []a;
return temp;
}
14 楼
天国龙 [专家分：490] 发布于 2006-06-02 16:50:00
int KthNumOfList(int List[],int len,int k)
{
int n,t,*left,*right,ln(0),rn(0),*l,*r,*m,*lt,i;
left=new int[len-1];
right=new int[len-1];
l=left;
r=right;
m=List;
while(1)
{
n=len/2;
t=m[n];
m[n]=m[0];
m[0]=t;
for (i=1;i<len;i++)
{
if (m[i]<=m[0])
{
l[ln]=m[i];
ln++;
}
else
{
r[rn]=m[i];
rn++;
}
}
if (ln+1==k)
return m[0];
if (ln+1<k)
{
len=rn;
lt=m;
m=r;
r=lt;
k-=(ln+1);
rn=ln=0;
}
else
{
len=ln;
lt=m;
m=l;
l=lt;
rn=ln=0;
}
}
}
15 楼
hmlb [专家分：90] 发布于 2006-06-02 16:51:00
先排序吗？
16 楼
天国龙 [专家分：490] 发布于 2006-06-02 17:07:00
第几大:
int KthNumOfList(int List[],int len,int k)
{
int n,t,*left,*right,ln(0),rn(0),*l,*r,*m,*lt,i;
left=new int[len];
right=new int[len];
l=left;
r=right;
m=List;
while(1)
{
n=len/2;
t=m[n];
m[n]=m[0];
m[0]=t;
for (i=1;i<len;i++)
{
if (m[i]>m[0])
{
l[ln]=m[i];
ln++;
}
else
{
r[rn]=m[i];
rn++;
}
}
if (ln+1==k)
return m[0];
if (ln+1<k)
{
len=rn;
lt=m;
m=r;
r=lt;
k-=(ln+1);
rn=ln=0;
}
else
{
len=ln;
lt=m;
m=l;
l=lt;
rn=ln=0;
}
}
}
17 楼
hmlb [专家分：90] 发布于 2006-06-02 17:17:00
第1题的解
#include <stdio.h>
int KthNumOfList(int* pList, int nLen, int k);
int main(int argc, char* argv[])
{
int pList[] = {10, 50, 2, 31, 7, 6, 16};
int n = KthNumOfList(pList, 7, 2);
if(n <= 1000)
printf("The %dth number: %d\n",
2, n);
else
printf("Can't find the number\n");
return 0;
}
/********************************************
pList:数组入口地址
nLen:数组长度
k:第几大
返回值：返回第k大的数
********************************************/
int KthNumOfList(int* pList, int nLen, int k)
{
//有效性校验超出范围，肯定不对
if((k > nLen) || (k <= 0))
return 1001;
//索性拿选择排序试试
int nRet;
int nIndex = 0; //目前到了第几大
for(int i=0; i<nLen; i++)
{
int nLowIndex = nLen -1;
for(int j=nLen-1; j >= i; j--)
{
if(pList[j] < pList[nLowIndex])
nLowIndex = j;
}
//交换
int temp = pList[nLowIndex];
pList[nLowIndex] = pList[i];
pList[i] = temp;
if(i == 0)
{
nIndex++;
nRet = pList[i];
}
else
{
if(pList[i] > pList[i-1])
{
nIndex++;
nRet = pList[i];
}
}
if(nIndex == k)
break;
}
if(nIndex == k)
return nRet;
else
return 1001;
}
18 楼
Atins [专家分：20] 发布于 2006-06-02 20:53:00
不知道理解有没有错，不自量力。
希望没有错……
#include<stdio>;
#include<math.h>;
void Sort(int a[],int len,int k);
/* 起泡法排序，因为要求得到第K大，所以只要排K次。?*/
void Qsort(int a[],int low,int high);
/* 快速排序，当K较大时用 */
int KthNumOfList(int List[],int len,int k);
/*void main()
{
int len=10;
int k=3;
int list[]={25,98,76,65,32,13,45,87,43,1};
KthNumOfList(list,len,k);
getch();
}*/
/*加上主程序只是为了调试*/
int KthNumOfList(int list[],int len,int k)
{
if (!k||(k>len)){printf("Out of the list");exit(1);}
/* 超出查找范围 */
if (k*k>len*log(len))Sort(list,len,k);/* K次起泡法平均时间度为O（K*K），而长度为len的起泡法是（len*(log(len))) */
else Qsort(list,0,len);/* 比较选择较快的方法 */
printf("the %d large munber is :%d",k,list[k]);
return list[k];
}
void Sort(int list[],int len,int k)
{
int i,j,temp;
for(i=0;i<=k;i++)
{
for(j=len;j>i;j--)
{
if(list[j-1]>list[j])
{
temp=list[j];list[j]=list[j-1];list[j-1]=temp;
}
}
}
}
int Sort1(int a[],int low,int high)
{ int temp=0;
int key=a[low];
while(low<high)
{
while(low<high&&a[high]>=key)--high;
temp=a[low];a[low]=a[high];a[high]=temp;
while(low<high&&a[low]<=key)++low;
temp=a[low];a[low]=a[high];a[high]=temp;
}
return low;
}
void Qsort(int a[],int low,int high)
{
int pivotkey;
if(low<high)
{
pivotkey=Sort1(a,low,high);
Qsort(a,low,pivotkey-1);
Qsort(a,pivotkey+1,high);
}
}
19 楼
廖增祥 [专家分：3930] 发布于 2006-06-02 23:07:00
int KthNumOfList(int List[], int len, int k)
{
int max, min, a;
max = min = List[0];
for(int j = 1; j <= k; j ++) //求第 k 大的数，循环 k 次
{
for(int i = 1; i <= len - 2; i ++) //循环一次，取出最大值和最小值
{
if(List([i] > max)
{
max = List[i];
a = i;
}
if(List[i] < min)
min = List[i];
}
List[a] = min; //再将这个最大值赋最小值的值
}
return max; //此时的 max 则为第 k 大的数
}
20 楼
laoqiang [专家分：0] 发布于 2006-06-03 00:02:00
int KthNumOfList(int List[],int len,int k);
{int i,j;
int min=List[0],k=0;
for(i=1;i<=k;i++)
{for(j=i+1;j<len;j++)
{if(min>List[j])
min=List[j];
}
min=List[i];
}
}
我来回复
您所在位置：