[原创]彩票选号后的数学——抽牌算法的实现

此回复为自动发出,仅用于显示而已，并无任何其他特殊作用
楼主【talent_marquis】截止到2008-07-04 12:59:33的历史汇总数据(不包括此帖)：
发帖的总数量:9                        发帖的总分数:562
结贴的总数量:7                        结贴的总分数:462
无满意结贴数:0                        无满意结贴分:0
未结的帖子数:2                        未结的总分数:100
结贴的百分比:77.78 %               结分的百分比:82.21 %
无满意结贴率:0.00  %               无满意结分率:0.00  %
楼主加油

版主请帮忙编辑一下code部分的代码，我标签多写了一个"s"导致不能按照java代码显示code了。

作个循环往set里查值，key是不能重复的Set set=new LinkedHashSet();
    while(set.size()<7)
    {
     set.add((int)(Math.random()*36));

    }
这样更简单

-------------------------------------------------------------
Quietly through .....

其实楼主算法算不上是“抽牌算法”啊？？！！
关键点是：抽出一张牌放一边，原来的顺序是不变的。
按楼主的例子，第一次抽到7，那么抽出7这张牌后，顺序应该为[1...6,8......34,35,36,7] 才对啊直接用List很容易实现，removeItem就好了

确实如此！
大致代码如下，简化了很多很多啊。
ArrayList list = new ArrayList( Data );
int[] result = new int[size];
for( int i =0 ; i < size ; i++ )
{
    int index = Rondom.nextInt( list.size() );
    resut[i] = list.get( index );
    list.remove( index );
}

完整改进版如下：
private static Random random = new Random();
public static int[] getRandomIntWithoutReduplicate2( int min, int max, int size )
{
int[] result = new int[size];
List<Integer> list = new ArrayList< Integer >();
//init list
for( int i = min; i < max; i++ )
{
list.add( i );
}
for( int i = 0; i < size; i++ )
{
int index = random.nextInt( list.size() );
result[i] = list.get( index );
list.remove( index );
}
return result;
}

这先把背包系统背后所需要的东西整理出来才行我现在能想起来的就是这些：物品类：包含属性：大小，价值
背包类：包含属性：大小，放东西的算法就应该放在这个背包类里面
物品生成类：用来随机生成指定数量的物品，能够随机生成物品大小，价值
显示背包类：可以直观地用二维数组的方式来显示背包里东西放置的样式，例如
[3x3,15],*,*,[1x1,5], 0
* ,*,*,[2x2,10],*
* ,*,*, *, *最后还要有一个统计背包价值的类，计算谁放入背包内的东西价值最高不过感觉这个背包竞赛如果真正想实施的话，还有很多细节需要完善，现在还只能说是一个初步构想，有漏洞。

刚进行了测试，这种方法效率极差，可能和list的数据结构有关，进行remove操作后数据有一个重排的过程。

写个效率高速度快的，如下：import java.util.Arrays;
import java.util.Random;/**
* <code>RandomUtil</code> - Random Tool Class.
* @author SageZk
* @version 1.0
*/
public class RandomUtil { private RandomUtil() {} private static Random rnd = null; /**
* 初始化随机数发生器。
*/
private static void initRnd() {
if (rnd == null) rnd = new Random();
} /**
* 计算并返回无重复值的以 <code>min</code> 为下限 <code>max</code> 为上限的随机整数数组。
* @param min 随机整数下限（包含）
* @param max 随机整数上限（包含）
* @param len 结果数组长度
* @return 结果数组
*/
public static int[] getLotteryArray(int min, int max, int len) {
//参数校验及性能优化
if (len < 0) return null;  //长度小于 0 的数组不存在
if (len == 0) return new int[0];  //返回长度为 0 的数组
if (min > max) {  //校正参数 min max
int t = min;
min = max;
max = t;
}
final int LEN = max - min + 1;  //种子个数
if (len > LEN) return null;  //如果出现 35 选 36 的情况就返回 null
if (len == 1) return new int[] {min};  //即 min == max 的情况
//计算无重复值随机数组
initRnd();  //初始化随机数发生器
int[] seed = new int[LEN];  //种子数组
for (int i = 0, n = min; i < LEN;) seed[i++] = n++;  //初始化种子数组
for (int i = 0, j = 0, t = 0; i < len; ++i) {
j = rnd.nextInt(LEN - i) + i;
t = seed[i];
seed[i] = seed[j];
seed[j] = t;
}
return Arrays.copyOf(seed, len);  //注意：copyOf 需要 JRE1.6
} //Unit Testing
public static void main(String[] args) {
final int N = 10000;  //测试次数
for (int i = 0; i < N; ++i) {
int[] la = RandomUtil.getLotteryArray(1, 35, 7);
if (la == null) continue;
for (int v : la) System.out.printf("%0$02d ", v);
System.out.println();
}
}}

Bug 修复：
if (len == 1) return new int[] {min};
这句去了，修复后：
import java.util.Arrays;
import java.util.Random;/**
* <code>RandomUtil</code> - Random Tool Class.
* @author SageZk
* @version 1.0
*/
public class RandomUtil { private RandomUtil() {} private static Random rnd = null; /**
* 初始化随机数发生器。
*/
private static void initRnd() {
if (rnd == null) rnd = new Random();
} /**
* 计算并返回无重复值的以 <code>min</code> 为下限 <code>max</code> 为上限的随机整数数组。
* @param min 随机整数下限（包含）
* @param max 随机整数上限（包含）
* @param len 结果数组长度
* @return 结果数组
*/
public static int[] getLotteryArray(int min, int max, int len) {
//参数校验及性能优化
if (len < 0) return null;  //长度小于 0 的数组不存在
if (len == 0) return new int[0];  //返回长度为 0 的数组
if (min > max) {  //校正参数 min max
int t = min;
min = max;
max = t;
}
final int LEN = max - min + 1;  //种子个数
if (len > LEN) return null;  //如果出现 35 选 36 的情况就返回 null
//计算无重复值随机数组
initRnd();  //初始化随机数发生器
int[] seed = new int[LEN];  //种子数组
for (int i = 0, n = min; i < LEN;) seed[i++] = n++;  //初始化种子数组
for (int i = 0, j = 0, t = 0; i < len; ++i) {
j = rnd.nextInt(LEN - i) + i;
t = seed[i];
seed[i] = seed[j];
seed[j] = t;
}
return Arrays.copyOf(seed, len);  //注意：copyOf 需要 JRE1.6
} //Unit Testing
public static void main(String[] args) {
final int N = 10000;  //测试次数
for (int i = 0; i < N; ++i) {
int[] la = RandomUtil.getLotteryArray(1, 35, 7);
if (la == null) continue;
for (int v : la) System.out.printf("%0$02d ", v);
System.out.println();
}
}}

帽子的效率是挺高的（代码风格真好，pfpf），不过不是又回去楼主的“非抽牌”算法了吗？？不知道楼主的“完整改正版效率极差是到什么程度”，我试了100000次35选7也只需235ms啊，应该足够效率了吧，我觉得。确实List删除元素后会调用System.arraycopy()方法进行重排。

我说的是下面这个算法效率有问题，不是顶楼的那个抽牌算法。    private static Random random = new Random();
    public static int[] getRandomIntWithoutReduplicate2( int min, int max, int size )
    {
        int[] result = new int[size];
        List<Integer> list = new ArrayList< Integer >();
        //init list
        for( int i = min; i < max; i++ )
        {
            list.add( i );
        }
        for( int i = 0; i < size; i++ )
        {
            int index = random.nextInt( list.size() );
            result[i] = list.get( index );
            list.remove( index );
        }
        return result;
    }

import java.util.*;
public class ChouJiang {
public static void main(String[] args) {
Scanner in=new Scanner(System.in);
   System.out.print("你需要抽取多少个数？");
   int k=in.nextInt();
   System.out.print("你的数字最大的是多少？");
       int n=in.nextInt();
       int [] numbers=new int[n];
       for(int i=0;i<numbers.length;i++)
        numbers[i]=i+1;
       int[]  result=new int[k];
       for(int i=0;i<result.length;i++)
       {
          int r=(int)(Math.random()*n);
          result[i]=numbers[r];
          numbers[r]=numbers[n-1];
          n--;
       }
       Arrays.sort(result);
       //System.out.println("赌中接下来的这个号码组合，你就有钱了！");
       for(int r=0;r<result.length;r++)
        System.out.println(result[r]);
}}

用集合Set set = new HashSet();
这样，就不不会重复了吗？
在来一个for循环出7个数。放在set中去。干嘛，用数组呢。代码多。看着还累。。

调试易

[原创]彩票选号后的数学——抽牌算法的实现

解决方案 »