问个很基础的问题# Programming - 葵花宝典
g*i
1 楼
现在有从1到100这100个整数，每次随机从中抽取一个数，直至把这100个数全部抽出。
怎么十分高效地实现？
问题很初级，请各位表笑，还请赐教。谢谢！
怎么十分高效地实现？
问题很初级，请各位表笑，还请赐教。谢谢！
P*e
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个数全部抽出。
: 怎么十分高效地实现？
: 问题很初级，请各位表笑，还请赐教。谢谢！
搞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
3 楼
你要再多一些限制条件吧
比如这100个数是什么形式数据结构存储的
不同的结构可能结果不同
如果是linked list，每次取一个就把list的长度减1，100次就搞定了,O(N)
不能再快了吧？
【在 g**i 的大作中提到】
: 现在有从1到100这100个整数，每次随机从中抽取一个数，直至把这100个数全部抽出。
: 怎么十分高效地实现？
: 问题很初级，请各位表笑，还请赐教。谢谢！
比如这100个数是什么形式数据结构存储的
不同的结构可能结果不同
如果是linked list，每次取一个就把list的长度减1，100次就搞定了,O(N)
不能再快了吧？
【在 g**i 的大作中提到】
: 现在有从1到100这100个整数，每次随机从中抽取一个数，直至把这100个数全部抽出。
: 怎么十分高效地实现？
: 问题很初级，请各位表笑，还请赐教。谢谢！
c*t
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个数全部抽出。
: 怎么十分高效地实现？
: 问题很初级，请各位表笑，还请赐教。谢谢！
这个题的基本思路就是 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
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 的大作中提到】
: 判断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
6 楼
晚上了，刚才跟一个经常污蔑中国的台湾白痴吵架，吵的脑子不清楚了
我理解成，一直抽，直到100个都抽出来，而不是从1-100中抽
【在 t****t 的大作中提到】
: 这个问题基本上等价于把1-100做随机排列
: 搞得那么复杂, 难道你们都没看过精华区吗...
我理解成，一直抽，直到100个都抽出来，而不是从1-100中抽
【在 t****t 的大作中提到】
: 这个问题基本上等价于把1-100做随机排列
: 搞得那么复杂, 难道你们都没看过精华区吗...
t*t
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];
【在 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
8 楼
stl里面的random_shuffle
【在 g**i 的大作中提到】
: 现在有从1到100这100个整数，每次随机从中抽取一个数，直至把这100个数全部抽出。
: 怎么十分高效地实现？
: 问题很初级，请各位表笑，还请赐教。谢谢！
【在 g**i 的大作中提到】
: 现在有从1到100这100个整数，每次随机从中抽取一个数，直至把这100个数全部抽出。
: 怎么十分高效地实现？
: 问题很初级，请各位表笑，还请赐教。谢谢！
g*i
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];
#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
10 楼
我没见到coconut教你用random()啊?
不要把责任推到人家头上
【在 g**i 的大作中提到】
: 不好意思，你这个编译的时候怎么总报错啊？
: #include
: #include
: #include
: #include
: int main()
: {
: ....
: return 0;
: }
不要把责任推到人家头上
【在 g**i 的大作中提到】
: 不好意思，你这个编译的时候怎么总报错啊？
: #include
: #include
: #include
: #include
: int main()
: {
: ....
: return 0;
: }
g*i
11 楼
呵呵，我并没有推责任啊，我只是问问题而已。
况且，在他给我的源程序里有一句
int swapindex=random(100-i);
就是这句通不过啊。
【在 t****t 的大作中提到】
: 我没见到coconut教你用random()啊?
: 不要把责任推到人家头上
况且，在他给我的源程序里有一句
int swapindex=random(100-i);
就是这句通不过啊。
【在 t****t 的大作中提到】
: 我没见到coconut教你用random()啊?
: 不要把责任推到人家头上
t*t
12 楼
哦,我看漏了,我的错.
他说的random(100-i)是个示意, 你应该翻译成你自己系统上正确的随机函数调用, 使
之产生0 ~ 100-i-1之间的均匀随机整数
【在 g**i 的大作中提到】
: 呵呵，我并没有推责任啊，我只是问问题而已。
: 况且，在他给我的源程序里有一句
: int swapindex=random(100-i);
: 就是这句通不过啊。
他说的random(100-i)是个示意, 你应该翻译成你自己系统上正确的随机函数调用, 使
之产生0 ~ 100-i-1之间的均匀随机整数
【在 g**i 的大作中提到】
: 呵呵，我并没有推责任啊，我只是问问题而已。
: 况且，在他给我的源程序里有一句
: int swapindex=random(100-i);
: 就是这句通不过啊。
g*i
13 楼
明白了，谢谢
【在 t****t 的大作中提到】
: 哦,我看漏了,我的错.
: 他说的random(100-i)是个示意, 你应该翻译成你自己系统上正确的随机函数调用, 使
: 之产生0 ~ 100-i-1之间的均匀随机整数
【在 t****t 的大作中提到】
: 哦,我看漏了,我的错.
: 他说的random(100-i)是个示意, 你应该翻译成你自己系统上正确的随机函数调用, 使
: 之产生0 ~ 100-i-1之间的均匀随机整数
c*z
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];
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
15 楼
just use std::random_shuffle ... don't make wheels
【在 g**i 的大作中提到】
: 明白了，谢谢
【在 g**i 的大作中提到】
: 明白了，谢谢
I*s
16 楼
正在读Bentley的"More programming pearls". 这在column 13有详细讨论,
用的是Robert Floyd的算法.
如果有ACM digital library的帐号, 可以在这里下载column 13:
http://portal.acm.org/citation.cfm?doid=30401.315746
用的是Robert Floyd的算法.
如果有ACM digital library的帐号, 可以在这里下载column 13:
http://portal.acm.org/citation.cfm?doid=30401.315746
相关阅读
怎样才能相对公平的判断程序员的贡献大小马工们难道就没有办法阻止3哥了么java,, auto keyword和c++是不是功能基本一样？老中真愚昧，看这里就知道C, C++, Java, C#, Objective-C,FYI动不动30万年薪的为啥啊spark download page里面的CDH， HDP，MapRAny good machine learning model for extracting personal info from resume?大牛们讲讲MQ到底好在哪里？ms百度识图也蛮厉害的是不是越南人做admin/DevOps挺多的？？C* scala driver用extjs做前端的多吗？从网页周期性抓取信息然后自动发邮件，应该怎么做？骑驴找马的简历需要注明现在所在公司吗？ (转载)Java 快死翘了吗？有熟悉go的可以说说关于Package里面function如何隐藏么有人给过SURF的专利费么？“神”programming language