扫二维码下载作业帮
3亿+用户的选择
下载作业帮安装包
扫二维码下载作业帮
3亿+用户的选择
从一副扑克牌中抽出13张从a到k然后把上面的一张抽出来放最低下,第二张是1拿出来摆桌上,再把最上的放最底第二张是2,以此类推,怎么摆才能按顺序把这些牌摆出来?
扫二维码下载作业帮
3亿+用户的选择
要不你反推一下试试.
为您推荐：
其他类似问题
扫描下载二维码彩票选号后的数学——抽牌算法的实现 - OO - Java - ITeye论坛
彩票选号后的数学——抽牌算法的实现
& 上一页 1
锁定老帖子
精华帖 (0) :: 良好帖 (2) :: 新手帖 (0) :: 隐藏帖 (0)
等级: 初级会员
来自: 北京
发表时间：&&
相关知识库：
很简单的一个小算法，抛砖引玉了。
中国的彩票选号，例如36选7，从36个数字中随机选取7个，这在算法上如何实现呢？
最简单的想法就是，每次都从1～36随机选取一个数，一共选7次，不就可以了吗？
但这样会有一个问题——重复。彩票选号是不能重复的，这也即是说如果你第一次选到的数是10，那么以后再从1～36中选数的时候，10就不能再选了。
有人可能会说了，这还不好办，如果重复了就废掉，重新再选一个呗。
这的确是一种解决方法，但是会有很大的问题，比如说5选4吧，前三个都已经选好了是2，3，4，现在取第4个数，这种情况下，取到1和5的几率要比取到2，3，4的几率还要小，也就是说，最坏的情况下，有可能会取很多次2，3，4，扔掉很多次，才最终能取到1或5，完成4个随机数字的选择。显然，这样效率是有很大问题的。
下面就介绍一种算法：抽牌算法，来实现这种不允许重复的选号，同时不会出现这种效率上的问题。
[separator]
抽牌算法的核心思想如下：
以36选7为例
一副牌，一共36张，抽出其中一张牌，放到一边，再从剩下的牌中抽出第二张，放到一边……以此类推，直到抽完了7张牌为止。
很显然，这样抽牌是绝对不会重复的。而其核心就是抽出的牌要放到一边。
用算法如何实现呢？
其实很简单，只要能模拟实现把抽出的牌放到一边这个概念就可以了，而模拟实现的方法是非常简单的：把一个数组模拟成一个牌盒，用数组里存的数模拟牌，而抽出的牌放到一边的动作，只需进行一次数组交换，把它放到数组的末尾即可。
以36选7为例
初始化数组，其结构为[1,2.....35,36]
第一轮，从1～36序号中选取随机序号，抽取到序号7， 把序号7和序号36的值交换，7放到数组的末尾，数组结构变成[1...6,36,8......34,35,7]
第二轮，从1～35序号中选取随机序号，抽取到7（这时位置7所存的数就是36了），把36和35交换，数组结构就变成了[1..6,35,8...34,36,7]
第三轮，从1～34序号中选取随机序号，抽取到5，把5和34交换，数组结构变成了[1...4,34,6,35,8....5,36,7]
...
每一次，都把抽出的“牌”放到数组的最后，然后再抽牌时，就不抽最后那张牌，这样就实现了抽出的牌放到一边这样一个概念。
请看以下Java代码：
//获得不重复的随机数数组，取值范围[min,max)，个数size
public static int[] getRandomIntWithoutReduplicate( int min, int max, int size )
int[] result = new int[size];//用于存储结果的数组
int arraySize = max -//用于放"牌"的数组大小
int[] intArray = new int[arraySize];//用于放"牌"的数组
// 初始化"牌盒"，比如取值范围是[3,10)则"牌盒"里放的"牌"就是3，4，5，6，7，8，9
for( int i = 0 ; i & intArray. i++ )
intArray[i] = i +
// 获取不重复的随机数数组
for( int i = 0 ; i & i++ )
int c = getRandomInt( min, max - i );//获取到一个随机数
int index = c -//这个随机数在"牌盒"里的位置
swap( intArray, index, arraySize - 1 - i );//将这张"牌"放到"牌盒"的最后面
result[i] = intArray[ arraySize - 1 - i ];//把这张"牌"的值扔到存储结果的数组里
//获取随机数，随机数取值范围为[min, max)
public static int getRandomInt( int min, int max )
// include min, exclude max
int result = min + new Double( Math.random() * ( max - min ) ).intValue();
private static void swap( int[] array, int x, int y )
{//交换数组arry, 序号x与序号y值的顺序
int temp = array[x];
array[x] = array[y];
array[y] =
等级: 初级会员
来自: 北京
发表时间：&&
甜菜侯爵 写道很简单的一个小算法，抛砖引玉了。
这的确是一种解决方法，但是会有很大的问题，比如说5选4吧，前三个都已经选好了是2，3，4，现在取第4个数，这种情况下，取到1和5的几率要比取到2，3，4的几率还要小，也就是说，最坏的情况下，有可能会取很多次2，3，4，扔掉很多次，才最终能取到1或5，完成4个随机数字的选择。显然，这样效率是有很大问题的。
……
确实如楼主所言，有这样的问题存在。
之前我也做过一个类似彩票选号的程序，在一定范围内随机选择数字，不能重复。当时也想到过会有这样的问题存在，可能不会非常的极端，不会影响到实际的应用。
当时偷懒，就没有去实现楼主说说的算法。
顺便贴一下当时偷懒的程序，做个反面教材：
*随机生成数值。nums表示个数，size表示范围即最大数。
static int[] getNums(int nums,int size){
int[] arr=new int[nums];
Random r=new Random();
for (int i=0;i&i++ ){
//生成范围内的随机数。
arr[i]=r.nextInt(size)+1;
//剔除重复的数值。
for (int j=0;j&i;j++){
if (arr[j]==arr[i]){
//排序。从小到大排列。
Arrays.sort(arr);
请登录后投票
等级: 初级会员
来自: 上海
发表时间：&&
以前做过一个抽奖活动，当时采用下面的做法：
List&Integer& userList = lotteryTaskDao.getUsersByDay(day);
long size = userList.size();
StringBuffer userIds = new StringBuffer();
if (size & prizeCount) {
for (int i = 0; i & prizeC i++) {
int prize = (int) (Math.random() * size);
userIds.append(String.valueOf(userList.get(prize))).append(",");
userList.remove(prize);
for (int i = 0; i & i++) {
userIds.append(String.valueOf(userList.get(i))).append(",");
userList 是参与抽奖的用户ID集合，prizeCount需要抽出中奖的用户数。
请登录后投票
等级: 初级会员
来自: 上海
发表时间：&&
当时忘记怎么做了
只记得有个linkedlist
每次在搜有list的size去随即
得到的那个remove放到数组里面
swap就好比数组里面的get remove
请登录后投票
等级: 初级会员
来自: 珠海
发表时间：&&
引用……比如说5选4吧，前三个都已经选好了是2，3，4，现在取第4个数，这种情况下，取到1和5的几率要比取到2，3，4的几率还要小，也就是说，最坏的情况下，有可能会取很多次2，3，4，扔掉很多次，才最终能取到1或5，完成4个随机数字的选择。显然，这样效率是有很大问题的……
不明白楼主上面的话，查看API帮助文档，用随机返回的值都是均匀分布的，为什么楼主说取2，3，4，的机会会比1，5多呢？
写了一个小程序测试：
public class RandomTest {
public static void main(String[] args) {
Map&Integer, Integer& map = new HashMap&Integer, Integer&();
int ramdonV
for (int i = 0; i & ; i++) {
ramdonValue = (int) (Math.random() * 10);
if (map.get(ramdonValue) != null) {
map.put(ramdonValue, map.get(ramdonValue) + 1);
map.put(ramdonValue, ramdonValue);
for (Integer key : map.keySet()) {
System.out.println(key + ": " + map.get(key));
执行了次，获得的1-10的结果离平均值在本机的N次运行中发觉不会大于士800次……下面的是一个参考结果：
0: 1000477
1: 1000093
2: 1000188
3: 1000643
4: 999796
5: 1000063
6: 998529
7: 998709
8: 1000817
9: 1000720
是不是楼主的说法有误呢？
请登录后投票
等级: 初级会员
来自: 北京
发表时间：&&
我的意思是说，去到2，3，4的总的几率是3/5，取到1，5的几率是2/5，自然是取到2，3，4的机会比取到1，5的机会要大一些了。
扩展开去，比如100选99，假设前98个数已经选好了，现在选第99个数，那么，如果按照1～100随机取值的方法去选第99个数，选到前98个数字的机率要远高于没选到的那2个数字，机率分别是0.98和0.02，不知我这样解释还算明白？&
xieboxin 写道引用……比如说5选4吧，前三个都已经选好了是2，3，4，现在取第4个数，这种情况下，取到1和5的几率要比取到2，3，4的几率还要小，也就是说，最坏的情况下，有可能会取很多次2，3，4，扔掉很多次，才最终能取到1或5，完成4个随机数字的选择。显然，这样效率是有很大问题的……
不明白楼主上面的话，查看API帮助文档，用随机返回的值都是均匀分布的，为什么楼主说取2，3，4，的机会会比1，5多呢？
写了一个小程序测试：
public class RandomTest {
public static void main(String[] args) {
Map&Integer, Integer& map = new HashMap&Integer, Integer&();
int ramdonV
for (int i = 0; i & ; i++) {
ramdonValue = (int) (Math.random() * 10);
if (map.get(ramdonValue) != null) {
map.put(ramdonValue, map.get(ramdonValue) + 1);
map.put(ramdonValue, ramdonValue);
for (Integer key : map.keySet()) {
System.out.println(key + ": " + map.get(key));
执行了次，获得的1-10的结果离平均值在本机的N次运行中发觉不会大于士800次……下面的是一个参考结果：
0: 1000477
1: 1000093
2: 1000188
3: 1000643
4: 999796
5: 1000063
6: 998529
7: 998709
8: 1000817
9: 1000720
是不是楼主的说法有误呢？
请登录后投票
等级: 初级会员
来自: 珠海
发表时间：&&
甜菜侯爵 写道我的意思是说，去到2，3，4的总的几率是3/5，取到1，5的几率是2/5，自然是取到2，3，4的机会比取到1，5的机会要大一些了。
扩展开去，比如100选99，假设前98个数已经选好了，现在选第99个数，那么，如果按照1～100随机取值的方法去选第99个数，选到前98个数字的机率要远高于没选到的那2个数字，机率分别是0.98和0.02，不知我这样解释还算明白？&
xieboxin 写道引用……比如说5选4吧，前三个都已经选好了是2，3，4，现在取第4个数，这种情况下，取到1和5的几率要比取到2，3，4的几率还要小，也就是说，最坏的情况下，有可能会取很多次2，3，4，扔掉很多次，才最终能取到1或5，完成4个随机数字的选择。显然，这样效率是有很大问题的……
不明白楼主上面的话，查看API帮助文档，用随机返回的值都是均匀分布的，为什么楼主说取2，3，4，的机会会比1，5多呢？
写了一个小程序测试：
public class RandomTest {
public static void main(String[] args) {
Map&Integer, Integer& map = new HashMap&Integer, Integer&();
int ramdonV
for (int i = 0; i & ; i++) {
ramdonValue = (int) (Math.random() * 10);
if (map.get(ramdonValue) != null) {
map.put(ramdonValue, map.get(ramdonValue) + 1);
map.put(ramdonValue, ramdonValue);
for (Integer key : map.keySet()) {
System.out.println(key + ": " + map.get(key));
执行了次，获得的1-10的结果离平均值在本机的N次运行中发觉不会大于士800次……下面的是一个参考结果：
0: 1000477
1: 1000093
2: 1000188
3: 1000643
4: 999796
5: 1000063
6: 998529
7: 998709
8: 1000817
9: 1000720
是不是楼主的说法有误呢？
嗯，终于明白，受教了，谢谢。
请登录后投票
等级: 初级会员
发表时间：&&
也可以借助Java内部实现来实现这个功能
List&Integer& box = new ArrayList&Integer&();
for(int i=0; i & 36; ++i){
box.add(i+1);
Collections.shuffle(box);
return box.subList(0,4);
代码是示意性的,借助Collections内置的shuffle(洗牌)之后,取前五个就可以了
请登录后投票
文章: 1544
积分: 1795
来自: 上海
发表时间：&&
甜菜侯爵 写道很简单的一个小算法，抛砖引玉了。
这的确是一种解决方法，但是会有很大的问题，比如说5选4吧，前三个都已经选好了是2，3，4，现在取第4个数，这种情况下，取到1和5的几率要比取到2，3，4的几率还要小，也就是说，最坏的情况下，有可能会取很多次2，3，4，扔掉很多次，才最终能取到1或5，完成4个随机数字的选择。显然，这样效率是有很大问题的。
明显站不住脚，5选4等价于5选1，根本用不着多此一举。
请登录后投票
等级: 初级会员
发表时间：&&
用ArrayList是不是更方便一点，直接可以remove被选中元素。
请登录后投票
& 上一页 1
跳转论坛:移动开发技术
Web前端技术
Java企业应用
编程语言技术账号 电子邮箱地址
记住登录状态
还没有33IQ账号？
通过社交网站直接登录
条@我的评论，
条新私信，
条新评论，
07:00 提供
大家都玩过抽王八的，规则大致是这样，里除了有一张王和一张8是单独存在的，剩下的牌都有对子。发好牌后，每个人所有的对子都要拿出来消掉。然后从某人开始抽下一个人的一张牌，如果出现对子就消掉。到了最后，对子都消掉的时候，王和8会留在某人手里，这时那个人就输了。以上是规则，这里有一个残局：A手里有一张2，B手里有王、8、2，A先抽。那么A和B谁胜利的可能性大？
您也可能感兴趣的题目
登录33IQ，提升智力水平，让你越玩越聪明！
33IQ v4.26.90.89
Copyright & 2008- All Rights Reserved第八章第二讲：抽屉原理.课后练习_百度文库
两大类热门资源免费畅读
续费一年阅读会员，立省24元！
第八章第二讲：抽屉原理.课后练习
阅读已结束，下载文档到电脑
想免费下载本文？
定制HR最喜欢的简历
下载文档到电脑，方便使用
还剩3页未读，继续阅读
定制HR最喜欢的简历
你可能喜欢}