来看看这个题目,请大家提出效率高的方法 - 编程论坛

#2

aipb20072007-08-10 02:07

可以达到线性O(n)。

#3

小糊涂仙2007-08-10 02:29

楼上说的上什么?偶笨笨~不懂

#4

雨中飞燕2007-08-10 02:33

洗牌法打乱O(n)
过程是先声明数值从1到1000的数组list[1000]
然后i从0到n-1变化，list[i]和list[rand()%1000]交换
如果觉得不够乱就多次运行上一个过程就可以了

#5

blueboy820062007-08-10 07:47

看了上面的发言，似懂非懂，可能是基础太差了吧
可以发个简短的程序来看看吗？
不胜感激啊

#6

aipb20072007-08-10 09:19

我说的就是4楼的方法，不过不需要运行两次，因为得到的排列概率为1/n!。

不过修正一点，

i <--- 1 to length[a]
在第i次迭带里，将a[i]与a[random(i,n)]交换。

#7

野比2007-08-10 13:27

喂喂...1000以内要1000个随机数.. 还要不一样的? ...

在开玩笑吗? 那不就是 1 到1000吗?...

你不如说" 把1 到1000的排列打乱"...

#8

小糊涂仙2007-08-10 23:31

呵呵

,楼上的,给你举个例子,1~5之间产生5个随机数和产生5个不一样的随机数字是不一样的
1~5产生5个随机数,可以产生重复的,例如随机产生 3,4,3,3,1
而产生5个不一样的随机数,指的是所产生的5个数字"不能相同"

#9

野比2007-08-11 00:42

那麻烦你在1-5之间给我产生5个不一样的随即数看看...谢了

#10

小糊涂仙2007-08-11 18:36

例子很多
例如 1,2,3,4,5
再如 2,4,5,1,3
再再如 3,4,5,1,2
再再再如 5,4,1,2,3
...
......

#11

野比2007-08-11 20:08

那不就是我说的意思吗?
---------
在开玩笑吗? 那不就是 1 到1000吗?...
你不如说" 把1 到1000的排列打乱"...

#12

kisscjy2007-08-11 21:11

明白LS的意思~

想问下函数库中有没有直接的函数可以使用呢

拜托了~~

#13

狂人老大2007-08-11 21:21

工作量也太大了啊
能行的吗

#14

aipb20072007-08-11 21:29

以下是引用狂人老大在2007-8-11 21:21:46的发言：
工作量也太大了啊
能行的吗

我6楼提的都线性了，还大？再高效率的还没怎么见过！

#15

野比2007-08-12 02:02

2次线性运算...
2个for..
没嵌套..
打乱排序....

#16

HJin2007-08-12 06:58

回复：（小糊涂仙）来看看这个题目,请大家提出效率高的...

try the following code to see if it works for you.

HJin
===========================================================

/*---------------------------------------------------------------------------
File name: random_shuffle_fuctor.cpp
Author: HJin (email: fish_sea_bird [at] yahoo [dot] com )
Created on: 8/11/2007 15:57:48
Environment: Windows XP Professional SP2 English +
Visual Studio 2005 v8.0.50727.762

Modification history:
===========================================================================

Note that the internal "rand()" function is not a good one, you may
want to use a better one.
*/

#include <iostream>
#include <vector>
#include <algorithm>
#include <ctime>
using namespace std;

class RandFunctor
{
public:
RandFunctor()
{
srand(time(0));
}

int operator()(int m)
{
return (rand()| (rand()<<16) )%m;
}
};

int main()
{
const int kSize=20;
int i;

vector<int> vi(kSize);
for(i=0; i<kSize; ++i)
vi[i] = i+1;

RandFunctor rf;
std::random_shuffle(vi.begin(), vi.end(), rf);

std::copy(vi.begin(), vi.end(), ostream_iterator<int>(cout, " "));
cout<<endl;

return 0;
}

#17

wingyip2007-08-12 09:03

樓上的實在看不懂啊。
是不是程序原本c++就有的？ random我一直也在想怎么實現。

#18

kisscjy2007-08-12 09:46

想问一下这两个函数是有什么用的~~
在哪个库文件中~~

std::random_shuffle(vi.begin(), vi.end(), rf);

std::copy(vi.begin(), vi.end(), ostream_iterator<int>(cout, " "));

#19

leng2007-08-12 10:12

你们说的产生的1000个随机数可不可以用一个程序写出来呀？乌笨没搞懂你们讲的方法。

#20

leng2007-08-12 10:16

可以先写从1到10 随机生成10个数让我搞懂一下你们的思想谢谢

#21

aipb20072007-08-12 12:10

[CODE]#include <iostream>
#include <ctime>
#include <cstdlib>
using namespace std;

int random(int low,int high){
int range = high-low+1;
return low+rand()%range;
}
void swap(int &a,int &b){
int t = a;
a = b;
b = t;
}

int main(){
srand((unsigned)time(0));
int a[100],i,j;
for (i = 0;i < 100;++i)
a[i] = i+1;
for (i = 0;i < 100;++i){
j = random(i,100);
if (i != j)
swap(a[i],a[j]);
}
for (i = 0 ;i < 100;++i)
cout << a[i] << " ";
cout << endl;
system("pause");
}[/CODE]

#22

未完成交响曲2007-08-12 13:31

我觉得提问题的人并没有把问题提清楚，这1000个数显然不是同时给出的。
也就是说，相当于顺序的每次给出一个数，但是每次给出的数都不同。并且在本身的
算法里面要求，每个数出现的概率都是1/1000。请问楼主是这个意思吗？

#23

小糊涂仙2007-08-12 15:08

rand()可以产生一个随机数,是吧?
我的意思就是一直用rand()产生1--1000之间的随机数,并且要求所产生的随机数字不能相同,就是这个意思啦~

#24

野比2007-08-12 23:17

random + seed ...
...
LZ你为什么不能换中思路呢?
问题已经很明显了, 你非要在随机数上纠缠...
若完全按你的方法, 那就
生成rand() -> 比较以前生成的结果 -> 生成... 直到不同 -> 存入...
这样当然效率低了...
就按前面aipb和我给的方法, 效率自然就高了, 而且也能保证是随机排列...

#25

terisevend2007-08-12 23:53

又看到一个可以当成随机排列看待的问题了...