g**i
发帖数: 167 | 1 现在有从1到100这100个整数，每次随机从中抽取一个数，直至把这100个数全部抽出。
怎么十分高效地实现？
问题很初级，请各位表笑，还请赐教。谢谢！ |
P********e
发帖数: 2610 | 2 判断100个数全部都抽出是关键
搞4个unsigned int, 128bit中的前100个bit来代表， 0是没抽出，1是抽出
main()
{
unsigned int a[4] = {0,0,0,0};
while(a[0] != ~0 && a[1] != ~0 && a[2] != ~0 && a[3] != 31) {
int ran = rand()%100;
int q/*quotient*/ = ran/32-1;
int r/*remainder*/ = ran%32;
a[q] |= 1 << r;
}
}
I ran the code, it works.
【在 g**i 的大作中提到】
: 现在有从1到100这100个整数，每次随机从中抽取一个数，直至把这100个数全部抽出。
: 怎么十分高效地实现？
: 问题很初级，请各位表笑，还请赐教。谢谢！
|
c***c
发帖数: 21374 | 3 你要再多一些限制条件吧
比如这100个数是什么形式数据结构存储的
不同的结构可能结果不同
如果是linked list，每次取一个就把list的长度减1，100次就搞定了,O(N)
不能再快了吧？
【在 g**i 的大作中提到】
: 现在有从1到100这100个整数，每次随机从中抽取一个数，直至把这100个数全部抽出。
: 怎么十分高效地实现？
: 问题很初级，请各位表笑，还请赐教。谢谢！
|
c*****t
发帖数: 1879 | 4 很奇怪，我几个月前刚回答过该问题。很久以前也回答过，JHQ 里找不到 :(
这个题的基本思路就是 random index，而不 random 数值本身。
int index[100];
for (int i = 1; i <= 100; ++i)
index[i] = i;
for (int i = 0; i < 100; ++i)
{
int swapIndex = random (100 - i);
int t = index[i + swapIndex];
index[i + swapIndex] = index[i];
index[i] = t;
}
【在 g**i 的大作中提到】
: 现在有从1到100这100个整数，每次随机从中抽取一个数，直至把这100个数全部抽出。
: 怎么十分高效地实现？
: 问题很初级，请各位表笑，还请赐教。谢谢！
|
t****t
发帖数: 6806 | 5 这个问题基本上等价于把1-100做随机排列
搞得那么复杂, 难道你们都没看过精华区吗...
【在 P********e 的大作中提到】
: 判断100个数全部都抽出是关键
: 搞4个unsigned int, 128bit中的前100个bit来代表， 0是没抽出，1是抽出
: main()
: {
: unsigned int a[4] = {0,0,0,0};
: while(a[0] != ~0 && a[1] != ~0 && a[2] != ~0 && a[3] != 31) {
: int ran = rand()%100;
: int q/*quotient*/ = ran/32-1;
: int r/*remainder*/ = ran%32;
: a[q] |= 1 << r;
|
P********e
发帖数: 2610 | 6 晚上了，刚才跟一个经常污蔑中国的台湾白痴吵架，吵的脑子不清楚了
我理解成，一直抽，直到100个都抽出来，而不是从1-100中抽
【在 t****t 的大作中提到】
: 这个问题基本上等价于把1-100做随机排列
: 搞得那么复杂, 难道你们都没看过精华区吗...
|
t****t
发帖数: 6806 | 7 精华区23->13. 没有算法, 只有证明. 不过证明能看明白, 算法应该不成问题.
【在 c*****t 的大作中提到】
: 很奇怪，我几个月前刚回答过该问题。很久以前也回答过，JHQ 里找不到 :(
: 这个题的基本思路就是 random index，而不 random 数值本身。
: int index[100];
: for (int i = 1; i <= 100; ++i)
: index[i] = i;
: for (int i = 0; i < 100; ++i)
: {
: int swapIndex = random (100 - i);
: int t = index[i + swapIndex];
: index[i + swapIndex] = index[i];
|
k****f
发帖数: 3794 | 8 stl里面的random_shuffle
【在 g**i 的大作中提到】
: 现在有从1到100这100个整数，每次随机从中抽取一个数，直至把这100个数全部抽出。
: 怎么十分高效地实现？
: 问题很初级，请各位表笑，还请赐教。谢谢！
|
g**i
发帖数: 167 | 9 不好意思，你这个编译的时候怎么总报错啊？
#include
#include
#include
#include
int main()
{
....
return 0;
}
g++编译的时候总报说：
too many arguments to function `int random()'
怎么才能解决这个问题？
谢谢！
【在 c*****t 的大作中提到】
: 很奇怪，我几个月前刚回答过该问题。很久以前也回答过，JHQ 里找不到 :(
: 这个题的基本思路就是 random index，而不 random 数值本身。
: int index[100];
: for (int i = 1; i <= 100; ++i)
: index[i] = i;
: for (int i = 0; i < 100; ++i)
: {
: int swapIndex = random (100 - i);
: int t = index[i + swapIndex];
: index[i + swapIndex] = index[i];
|
t****t
发帖数: 6806 | 10 我没见到coconut教你用random()啊?
不要把责任推到人家头上
【在 g**i 的大作中提到】
: 不好意思，你这个编译的时候怎么总报错啊？
: #include
: #include
: #include
: #include
: int main()
: {
: ....
: return 0;
: }
|
|
|
g**i
发帖数: 167 | 11 呵呵，我并没有推责任啊，我只是问问题而已。
况且，在他给我的源程序里有一句
int swapindex=random(100-i);
就是这句通不过啊。
【在 t****t 的大作中提到】
: 我没见到coconut教你用random()啊?
: 不要把责任推到人家头上
|
t****t
发帖数: 6806 | 12 哦,我看漏了,我的错.
他说的random(100-i)是个示意, 你应该翻译成你自己系统上正确的随机函数调用, 使
之产生0 ~ 100-i-1之间的均匀随机整数
【在 g**i 的大作中提到】
: 呵呵，我并没有推责任啊，我只是问问题而已。
: 况且，在他给我的源程序里有一句
: int swapindex=random(100-i);
: 就是这句通不过啊。
|
g**i
发帖数: 167 | 13 明白了，谢谢
【在 t****t 的大作中提到】
: 哦,我看漏了,我的错.
: 他说的random(100-i)是个示意, 你应该翻译成你自己系统上正确的随机函数调用, 使
: 之产生0 ~ 100-i-1之间的均匀随机整数
|
c*****z
发帖数: 182 | 14 this problem should be the same as an exercise in clrs
in which it asks to shuffle a deck of card
【在 c*****t 的大作中提到】
: 很奇怪，我几个月前刚回答过该问题。很久以前也回答过，JHQ 里找不到 :(
: 这个题的基本思路就是 random index，而不 random 数值本身。
: int index[100];
: for (int i = 1; i <= 100; ++i)
: index[i] = i;
: for (int i = 0; i < 100; ++i)
: {
: int swapIndex = random (100 - i);
: int t = index[i + swapIndex];
: index[i + swapIndex] = index[i];
|
p***o
发帖数: 1252 | 15 just use std::random_shuffle ... don't make wheels
【在 g**i 的大作中提到】
: 明白了，谢谢
|
I**********s
发帖数: 441 | 16 正在读Bentley的"More programming pearls". 这在column 13有详细讨论,
用的是Robert Floyd的算法.
如果有ACM digital library的帐号, 可以在这里下载column 13:
http://portal.acm.org/citation.cfm?doid=30401.315746 |
