问个很基础的问题# 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
相关阅读
怎么读javascript？剪切很难算吗？并联100只猩猩, 能不能过图灵测试? (转载)node.js用http实现websocket,真是神了。强关联分布能拿什么奖12306 我太土了 都不知道这是啥玩意硅谷泡沫破裂前兆：高楼+应召女郎 独角兽到独角尸股的霸强劲出手share a aws account请问怎样打开一个有密码的Access数据库 (转载)card.com手机app源代码：ionic/angular19路围棋的所有合法图案终于出来了 Number of legal Go positi问一道狗家Boggle变形难题 (转载)TeacherWei 的订票机的问题spark java这东西咋样呀？stackexchange疯了王垠新文 为Java说句公道话有啥好的c语言编辑器推荐么？搞java确实没啥技术含量、很多生物钱老都会java (转载)做一个网站，把其他网站地址列表拉出来在地图上显示,怎么做?