C语言数组元素怎么删除(比如彩票22选5中)算法最优!

见若不见 发布于 2012/06/22 10:56
阅读 863
收藏 0

例如 1-22中选出五个不重复的数字

我的思路是用一个有22元素下标对应值的数组 每次随机取他们的下标  有没有一个算法 取一次之后就相当于删除这个元素 然后再21个中去 然后依次。。20  19 。。 实现只需要5次就完成

我看过一个程序写的是每次生成1-22的数 然后遍历前面生成的数 如果已经有了 再重新随机 虽然也是可以 但是这样如果 需要选出的数 比例变大的时候 次数可能会加大 !

刚刚学C语言 突然对这个问题感兴趣!

加载中
0
Lunar_Lin
Lunar_Lin

设1-22的数组,   随机数22取余 , 找到一个后,与下标21元素交换元素(如果找到的就是21,就相当于没操作),  然后再21取余,找到后与下标20元素交换,  然后再20取余, (每次把找到的数字丢到数组最后,不参与下次随机取余即可). 直到找出5个数字即可.
每次找一个数的代价:  random取余,保存结果, 交换位置.

见若不见
见若不见
嗯 这个方法不错 谢谢你们了
0
小苏打
小苏打
数组不能删的,在我看来,要么继续用数组设定标致(删掉的值设为-1,然后在随机,这时不能再取下标,只能遍历),还有更方便的是用链表。
见若不见
见若不见
嗯 我在去看看链表 对这个还不知道 谢谢你
0
Grrrr
Grrrr

楼主可以考虑试下"蓄水池抽样" 算法. 就是等概率替换已有的元素.

算法比较简单.时间是O(N)

0
zkqian
zkqian
不想破坏原有数据的话,可以用一个数组做位图取走数组的相应元素有将其设置为一个值
0
中山野鬼
中山野鬼

@Lunar_Lin 的思路我赞同。基本可以按照如下方式处理。

1、获取random,其为 0到1的值,然后做区域放大。例如你是在 [X,Y)区间随机处理,则有如下映射关系:

unsigned int getRandomPos(unsigned int first ,unsigned int last){
    //last > first
    float f = random();
    return (unsigned int)(f * (last - first)+0.5 + first );
}

2、利用@Lunar_Lin 的方式,对每次找到的数据,进行位置替换。同时将替换的情况放到一个记录表里,因为你数组的数量可能远大于你要取数据的数量,所以这个替换表的使用对资源占用并没有太多影响。A为你待取的数据存放的数组。times位第几次取数。pos为获得的随机位置。

static unsigned int change_pos[MAX_N];
#define SWAP_UI(a,b) do {unsigned int t = a ; a = b; b = t; }while (0)
void change_var(unsigned int A,unsigned int pos, unsigned int times){
     SWAP_UI(A[pos],A[times]);
     change_pos[times] = pos;
     return ;
}

以上代码完成是,当你确认第times次,随机取到pos位置的数据时,就将pos的位置的数据和times位置的数据互换,并记录pos。

3、大循环,仍然是使用@Lunar_Lin的思想,因为你第N次取数据,是在前N-1次取剩下的数据中再取,所以如下

for (i = 0 ; i < N ; i++){
    pos = getRandomPos(i,MAX_ARRAY);
    change_var(A,pos,i);
}

当上述循环结束后,A中间,0,到 N-1存放的,就是随机N次所取出的数据。getRandomPos会帮你完成随机位置的正确映射。

而你每次处理完后,需要将数据进行恢复摆放。代码我就不写了。而相反,我要告诉你,前面我实际挖了个坑。我写了

static unsigned int change_pos[MAX_N]

其实这个更本不需要。为什么呢?因为你的随机性,保证了,A数组内的数据和随机位置无关。因此,上一次,随机取出N个数据,导致A数组的数据产生了SWAP,如果能影响本次随机取数的随机性,那么我们可以直接证明,两次随机现象存在关联,直接否定了随机函数的存在意义。

因此,你更本不需要上面的change_pos和恢复数据操作。我写出来,只是想在那一步,少解释问题而已。

 

 

中山野鬼
中山野鬼
回复 @见若不见 : 哈。。。大家讨论而已。要积分有毛用?如果我看中积分,会用两种方式,1、用人民币砸@虫虫 ,2、用美女勾引@红薯 ,并取证要挟他。哈。靠发贴混积分,也太没有投入产出性价比了。
见若不见
见若不见
非常谢谢你 没积分送你 这么晚帮我实现代码 (ˇˍˇ)
返回顶部
顶部