百度面试题:不使用随机数的洗牌算法

dolby_xiong 2012-08-31 10:44:03
加精
RT,网上流传了各种洗牌算法,基本上都是建立在随机数的基础之上的。

前段时间去百度实习面试,二面问了一个洗牌算法,不允许使用随机数,请问如何实现?至今没有想到一个合理的算法。。。。

多谢各位爱思考的牛人参与讨论。
...全文
31587 223 打赏 收藏 转发到动态 举报
写回复
用AI写文章
223 条回复
切换为时间正序
请发表友善的回复…
发表回复
  • 打赏
  • 举报
回复
看不懂!!!
yazinihao 2015-03-06
  • 打赏
  • 举报
回复
不明觉厉啊!
RNACHEN 2014-04-04
  • 打赏
  • 举报
回复
这个算法还是比较简单的的吧,个人觉得可以使用类似于hash的计算的方法,将牌的面值和位置的值进行运算,比如A[i] * i%13,这样子就算出一个值,然后就可以进行冒泡了,而且每次都会不一样的
yongmingmmm 2014-01-19
  • 打赏
  • 举报
回复
取得系统纳秒级时间或者毫秒级时间,我用java实现了下效果还是不错。纳秒级时间作为种子洗牌的时间最少。 public static void main(String[] args) { Set<Integer> s = new HashSet<Integer>(); for (int i=0; i<54; ++i){ int num = generateWhihNanoTime(); while (s.contains(num)){ num = generateWhihNanoTime(); } s.add(num); System.out.print(num+" "); } } // 纳秒时间 static int generateWhihNanoTime(){ long now = System.nanoTime(); int num = (int)(now%54); return num; } // 毫秒时间 static int generateWhihMillisTime(){ long now = System.currentTimeMillis(); long a = now*(now%100); int num = (int)(a % 54); return num; }
limenghhuc 2013-12-10
  • 打赏
  • 举报
回复
以系统时间做种子
king_on 2013-10-02
  • 打赏
  • 举报
回复
当前(21世纪处)的计算机的一个最重要的特性或者说最大的限制就是确定。即我们无法容忍一个计算机计算“错误”。再一个输入确定后,输出必然是确定的,除非出错。 不过这得排除我的“计算机”,我设计的计算机已经从本质上超越了当前的这些,甚至已经完全超越了人类本身。
ch1234sup 2013-08-23
  • 打赏
  • 举报
回复
冒泡算法,从最后一个数开始,循环移位a[i]个位置(或者循环移位fun(a[i],a[i-1],a[i+]),fun是一个自定义函数),冒泡掉最后一个数,从n-1个数开始继续上述过程。这样会得到一个打乱的序列,虽然下一轮的洗牌序列是根据上一轮确定来的,但是每一次洗牌的结果都不一样。
vssvss 2013-05-31
  • 打赏
  • 举报
回复
引用 214 楼 qq1299793687 的回复:
定义一个变量,取其地址,再做一点处理作为随机的行不行
这个倒是可以的哦 不过一段时间内申请地址是连续的
qq1299793687 2013-05-07
  • 打赏
  • 举报
回复
定义一个变量,取其地址,再做一点处理作为随机的行不行
蛋泥 2012-12-18
  • 打赏
  • 举报
回复
我来打酱油,结果发现没的打
Sugeei 2012-11-19
  • 打赏
  • 举报
回复
引用 15 楼 supersonic0410 的回复:
是否可以参考正常洗牌的过程? 分2堆,互相插入,插入点根据当前时刻的奇偶进行选择? 据说洗7次还原?还是7次最乱?忘了~
七次最乱
wanttoflysky 2012-11-15
  • 打赏
  • 举报
回复
我倒是觉得在冒泡的基础上把if(a[i]>a[j])改成if(date.gettime()%2)这样就有了随机洗牌,因为每条语句执行都需要一个一定范围内的随机毫秒数,mod 2最直观了
he416253656 2012-10-16
  • 打赏
  • 举报
回复
设定一个初始值1 再设定一个平均自增时间,然后由用户点击触发一个自增时间,每一个自增时间取出一个牌,应该会不一样吧,因为每一次点击时间会有所不同
浪漫E族 2012-10-15
  • 打赏
  • 举报
回复
我猜一种吧:
取系统运行时间,例如100MS为洗牌时间,这样就和本机有关,还有就是每次运行代码的速度都会有一点点差异的。
在这100MS里
我们将编号为0~53的牌进行循环,模仿快速排序一样的冒泡
1和2加起来然后对2求余,奇数就兑换,偶数就不换什么的。。然后2和3 。。。
第二轮1和3然后2和4.。。。一共进行54次。。
假如时间没有用完就继续。。。
然后可以人为的Thread.sleep(若干)。。。
一直添加干扰。。这样,在用一个足够大的时间里,就会产生一个不可预料的结果了吧。。。因为和本地机子绑定了。。
苍龙出海 2012-10-15
  • 打赏
  • 举报
回复
[Quote=引用 18 楼 的回复:]
个人的看法:冒泡排序是采用比较大小的方法排序,比较a[i]与a[j]的大小,然后交换位置。

如果把这个比较大小的逻辑更改一下,就可以排列出不同的结果。
比如给定一个常数 int N = 100 比较 a[i] % N 与 a[j] % N的大小,就可以得出一个比较奇怪的序列。

每次运行洗牌程序时,N取不同的数字,第一次100,下一次可以101, 102等等,就可以得到不同的洗牌结果了……
[/Quote]

看了你写的思路有种让人恍然大悟的感觉
invoke 2012-10-05
  • 打赏
  • 举报
回复
学习了。呵呵
翱翔的苍鹰 2012-09-25
  • 打赏
  • 举报
回复
求的 答案了,看了大家的东西,还是不懂呀。
jediael_lu 2012-09-24
  • 打赏
  • 举报
回复
到底有没有代码
flexstruts 2012-09-21
  • 打赏
  • 举报
回复
时间戳不可以。。使用时间戳要看牌是有序还是无序的情况
sanguorewrite 2012-09-21
  • 打赏
  • 举报
回复
用无理数。比如说pi.
加载更多回复(183)

33,006

社区成员

发帖
与我相关
我的任务
社区描述
数据结构与算法相关内容讨论专区
社区管理员
  • 数据结构与算法社区
加入社区
  • 近7日
  • 近30日
  • 至今
社区公告
暂无公告

试试用AI创作助手写篇文章吧