征求代码
函数
参数:string[20] 存取待选择的20个string
返回值: string[n] 选中的string
功能:
从string[20]中任意(随机)取出n个string
要求
效率高
问题点数：20、回复次数：7Top
1 楼blue_coco（椰子）回复于 2002-10-11 15:48:31 得分 20
最优的就是随机选择后交换元素的算法
#include <time.h>
#include <stdlib.h>
#define NUM 20
#define N 10
#define SWAP(p,q) {u=(p);(p)=(q);(q)=u;}
const int a[] = {0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19};
int x[N];
void out(int *x)
{
int u,i,p;
for(i=0;i<N;i++)
{
p=rand()%(NUM-i);
x[i]=a[p];
SWAP(a[p],a[NUM-i]);
}
}
数组x中存放被选的n个string号。Top
2 楼zhf777（八步）回复于 2002-10-11 15:57:44 得分 0
好麻烦阿Top
3 楼asvaboy1980（蓝boy）回复于 2002-10-11 16:14:31 得分 0
有点,支持一下Top
4 楼jimi_chen（小鸡吃米）回复于 2002-10-11 16:21:02 得分 0
完美的算法Top
5 楼jimi_chen（小鸡吃米）回复于 2002-10-11 16:36:41 得分 0
完美的算法
bug?:SWAP(a[p],a[NUM-i-1]);Top
6 楼xdspower（杂食菜熊）回复于 2002-10-11 16:43:14 得分 0
你的n参数怎么传入,后面看你是要接收一个字符串数组，则你该提供标准的接口别人才好提供代码,还有你的选取串按理是不能有重复的吧。由于你只有20个字符串，量比较小，其实用简单的方法就可以获得好的效率。
我用伪码实现：
bool out(int n,(string * )rtu,const string in[20]){//0<n<=20 表示要选取的量，rtu用于接收结果，in是源串
int a[20]={0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19};//表示string位置的变量
string * rp＝rtu;//用于接收rtu指针基址
int wap;//位置标号交换变量
int rini;//获得的随机变量值
if (n>20) return false;
for (int i=0;i<20;i++){
rini=rand（20-1）;//取[0,19]的随机整数
wap=a[i];
a[i]=a[rini];
a[rini]=wap;
}
for (int i=0;i<n;i++)
{if(in[a[i]]!=null) *(rp+i)=in[a[i]];
elss return false;
}
*(rp+n)=null;
return true;
}
整个算法时间复杂度是基本上是个常量,因为n十分小，最大才20，其实也没有讨论复杂度的必要了，注意的是算法中不要出现不能匹配的问题，比如这个问题用简单抽取法（取一个位置随机数，取值后把相应位置置空，再取位置随机数），要保证最后的串不重复就可能怎么也匹配不了。
Top
7 楼xdspower（杂食菜熊）回复于 2002-10-11 16:56:01 得分 0
blue_coco(椰子)的算法可能存在重复串问题。Top
相关问题
关键词
得分解答快速导航
相关链接
广告也精彩
反馈
