求教一个算法题

Question

写一个java函数，实现扑克洗牌功能，具体要求如下：
1. 只能使用一个可以输出0到1之间任意小数的random函数，不能使用其它库函数。
2. 函数每次执行要输出任意顺序的1到54之间所有的整数，不能重复（即洗牌）。
3. 时间复杂度和空间复杂度要尽量的小。

Answer 1

显然不是作业，哪个老师会出这么容易copy的作业题

Answer 2

既然指定要用Math.random()，那么时间复杂度就不好确定了一个思路,未必很好，但可以实现：原始数组：1~54，一个count记录次数。1、Math.random()随即出0~53之间任何一个数index
2、判断index下标中的数是否为0，如果是，continue1;如果不是，转3
3、打印这个数，同时把数组中的该数赋为0；
4、count++。如果count<数组的长度，继续从1循环

Answer 3

//随机获取一个长度为'randomCount'的数组，且数组中的数字不不会重复，随机数的范围由start到end
    private static int[] randomInts(int start,int end,int randomCount){
     int count=end-start+1;
     int[] ints=new int[count];
        //初始化数组内容为start到end的数字数组
     for(int i=0;i<count;i++){
     ints[i]=i+start;
     }
     Random r=new Random();
     int index=0,temp=0;
        //进行randomCount次随机调换，不过随机调换次数越多随机性越大
     for(int i=0;i<randomCount;i++){
                //随机出被调换的数组元素的下标
     index=r.nextInt(count);
                //每次调换与最后一个元素调换，打乱数组原有的循序
     temp=ints[count-1];
     ints[count-1]=ints[index];
     ints[index]=temp;
     }
        //从最后一次调换的元素的randomCount个元素前开始，取randomCount个元素出来 作为随机出来的数字组合，如果这个元素的下标小于0则 从0开始
     index=index-randomCount;
     if(index<0){
     index=0;
     }
        //给随机数字组赋值
     int[] rs=new int[randomCount];
     for(int i=0;i<randomCount;i++){
     rs[i]=ints[index+i];
     }
     return rs;
    }

Answer 4

正解。
创建一个54长度的数组，初始化数据。
每洗一次，random生成两个数组索引，数组的两个位置的数据交换一下就OK了。
可以洗N次。
时间复杂度N
空间复杂度1

Answer 5

不能用其它函数，ArrayList 呢？

Answer 6

public class ShuffleCard { 
    public static void main(String args[]) { 
        final int N = 52; 
        int[] poker = new int[N + 1];         // 初始化阵列 
        for(int i = 1; i <= N; i++) 
            poker[i] = i;         // 洗牌 
        for(int i = 1; i <= N; i++) { 
            int j = (int) (Math.random() * N);            if(j == 0)
                j = 1;            int tmp = poker[i]; 
            poker[i] = poker[j]; 
            poker[j] = tmp; 
        }         for(int i = 1; i <= N; i++) { 
            // 判断花色 
            switch((poker[i]-1) / 13) { 
                case 0: 
                    System.out.print("桃"); break; 
                case 1: 
                    System.out.print("心"); break; 
                case 2: 
                    System.out.print("砖"); break; 
                case 3: 
                    System.out.print("梅"); break; 
            }             // 扑克牌数字 
            int remain = poker[i] % 13; 
            switch(remain) { 
                case 0: 
                    System.out.print("K "); break; 
                case 12: 
                    System.out.print("Q "); break; 
                case 11: 
                    System.out.print("J "); break; 
                default: 
                    System.out.print(remain + " "); break; 
            }             if(i % 13 == 0) 
                System.out.println(""); 
        } 
    } 
}

Answer 7

伪随机数并不是假随机数，这里的“伪”是有规律的意思，就是计算机产生的伪随机数既是随机的又是有规律的。怎样理解呢？产生的伪随机数有时遵守一定的规律，有时不遵守任何规律；伪随机数有一部分遵守一定的规律；另一部分不遵守任何规律。比如“世上没有两片形状完全相同的树叶”，这正是点到了事物的特性，即随机性，但是每种树的叶子都有近似的形状，这正是事物的共性，即规律性。从这个角度讲，你大概就会接受这样的事实了：计算机只能产生伪随机数而不能产生绝对随机的随机数。（严格地说，这里的计算机是指由冯诺依曼思想发展起来的电子计算机。而未来的量子计算机有可能产生基于自然规律的不可重现的“真”随机数）。
　　那么计算机中随机数是怎样产生的呢？有人可能会说，随机数是由“随机种子”产生的。没错，随机种子是用来产生随机数的一个数，在计算机中，这样的一个“随机种子”是一个无符号整形数。那么随机种子是从哪里获得的呢？我教你一个方法，你可以不用调用java的库，但是可以自己写库。但是我会调用一个库不知道你能不能允许，就java的时间库，因为只有时间是永远在1ms后变化的，所以。建议看看我的代码public class Test { public static void main(String[] args) {
long time1=0;
long time2=0;
int i=1;
Num[] randomArray=new Num[54];
while (i<=54) {
int modNum=(int) (System.nanoTime()%54);
if (randomArray[modNum]!=null) {
continue;
}
randomArray[modNum]=new Num(i);
i++;
}


for (int j = 0; j < randomArray.length; j++) {
System.out.println(randomArray[j].getValue());
}
}

static class Num{
boolean num=false;
int value=0;
public Num(int value){
this.value=value;
} public int getValue() {
return value;
} }
}

Answer 8

如果楼主想纯不用java库代码，我建议你看看rondom的实现，rondom的随机数都是根据时间来生成的，所以楼主说不准用任何库函数是基本不可以的，而且生成的随机数都是伪随机。所以楼主不要相信计算机有真的随机数，即使用汇编也实现不了你的。除非你绕过java的api，直接调用系统的时间api，那你就不应该在java这里发表了

Answer 9

上面那几位仁兄，不知道你们有没有看楼主的要求，rondom只能生成0，1这两个，表示只有两个随机组合。你们都用54个随机组合，虽然实现了，但是都是还没看题目的人做的

Answer 10

java.lang.Math.random()方法不太好用，用java.util.Random比较方便，思路：1~54依次放在数组pokerNumbers里，首先写一个交换两张牌的方法，Random随机产生一个整数N，用Random两次随机产生两个0~54的数，将他们分别加1，再交换他们，这样重复N次，OK！
import java.util.Random;public class Shuffle {
public static void main(String args[]) {
int pokerNumbers[]=new int[54];
for(int i=0;i<54;i++) {
pokerNumbers[i]=i+1;
//System.out.println(pokerNumbers[i]);
}
Random r=new Random();
int N=r.nextInt(1000);//这里可以根据实际洗牌打乱程度加以限制交换次数上限
//System.out.println(N);
for(int j=0;j<N;j++) {
int a=r.nextInt(54)+1;//因为r.nextInt(54)产生0~53之间的任意数（包含0和53），所以加1得1~54之间任意数（包含1和54）
int b=r.nextInt(54)+1;
while(a==b) {
b=r.nextInt(54)+1;
}
int temp=-1;
temp=pokerNumbers[a-1];
pokerNumbers[a-1]=pokerNumbers[b-1];
pokerNumbers[b-1]=temp;
}
for(int k=0;k<54;k++) {
System.out.print(pokerNumbers[k]+"   ");
}
}}

Answer 11

我也没看清楚楼主的题目，楼主要的是0到1间的小数，这个容易，把1除以random得到的小数，取mod，思路还是我时间那个，不过这次的随机种子由Random类生成，不用我利用时间作为随机种子

Answer 12

public static void main(String[] args) {
// TODO Auto-generated method stub Random r=new Random(System.currentTimeMillis());
int s[]=new int[54];
for (int j=0;j<54;j++)
s[j]=j;
int k=0;
while (k<54){
          int i=r.nextInt(54);
          if(s[i]==0)
           continue;
          else{
              System.out.println(i);
              s[i]=0;
          }
          k++;
}
        
}

Answer 13

import java.util.*;
class Te {
public static void main(String []args) {
go();
}
static void go(){
ArrayList<Integer>nums = new ArrayList<Integer>();
int i = 1;
for(;i<55;i++){
nums.add(i);
}
while (!nums.isEmpty()){
int n = (int)(Math.random()*54+1);
for(;i<nums.size();i++){
if (n == nums.get(i)){
System.out.print(n+" ");
nums.remove(i);
break;
}
}if (nums.size()==27) System.out.println("\n");
i=0;
}
}
}
用了个ArrayList, 或许不合你要求，贴出来参考下还有希望指点下效率问题，这个我不怎么会考虑