问题描述
- 大家觉得我这个算法够随机吗？
- 是阿里巴巴的一道笔试题，用nextInt(int i)，这个方法能产生0~ （i-1）的其中一个随机数，
去产生1~1000中不重复的900个随机数，我只弄了1~1000个随机数，计数截取的部分省略import java.util.*;public class TestString { public static void main(String[] args) { myWay(1 4); } public static void myWay(int star int end) { if(star == end ) { System.out.println(star); return; } Random r1 = new Random(); int i = star + r1.nextInt(end - star + 1) ; System.out.println(i); Random r2 = new Random(); int j = r2.nextInt(2); if(j == 0) { if(i != star) myWay(star i - 1); if(i != end) myWay(i + 1 end); } if(j == 1) { if(i != end) myWay(i + 1 end); if(i != star) myWay(star i - 1); } }}
解决方案
你的代码有很严重的问题，就是你递归调用myway，而Random r2 = new Random();不断执行，由于时间很短，而它又是根据时间产生的随机种子，所以这样会导致随机数不随机。
而且你的算法也有问题，你的目标是随机，而不是均匀。
具体算法不表了，自己google 洗牌算法
解决方案二：
http://developer.51cto.com/art/200906/128348.htm
解决方案三：
很简单，你可以产生 1 2 3 4 ... 900
这个结果么？
虽然这个概率极低，但是从数学上说不是没有可能。如果你的算法被证明不能产生这个结果，那么它就不随机。
你还可以设计别的随机实验去验证。
解决方案四：
哎 朋友，这个题这样审题对吗?我在想看了你的题意只是说他告诉你了一个nextInt函数，让你直接用，在nextInt的基础上产生900个随机数。
就是不用java自己的随机算法，通过巧妙利用nextInt来写程序。
这种题应该是偏向于算法的，我认为应该这么审题：
因为nextInt是只能连续数中取出随机的，所以应该利用一些数学知识来把随机取好几次改变成在剩余的不连续的数中依然使用nextInt取随机。
具体方法我认为是链表法，就是建立一个1000长的ArrayList，然后通过get(int n)方法抽出来随机取出的数并删除节点。这样就达到了题目的要求，我并没有用任何java内部的生成随机数的方法就解决了这个题。
简单的代码：
Arraylist a blablabla
int results=new int[900];
for(int count=1000;count>100;count--){
int i=nextInt(count);
results[1000-count]=a.get(i);
a.remove(i);
}
我觉得这才是题目的本意