`
鞠文婷
  • 浏览: 16807 次
  • 性别: Icon_minigender_2
  • 来自: 江苏南通
社区版块
存档分类
最新评论

抽牌算法

抽牌算法随机数 
阅读更多

      打听到明天中午的密码学实验内容，今天晚上在寝室先行完成Java版，明天上完课再补上C++版。

      实验要求很简单：生成一个元素不重复的随机序列，长度由用户输入，但是元素大小需在0~10000之间，生成这种序列的算法有个比较简单易懂的名字：抽牌算法。

      显然，这个算法的核心在两点：随机 & 不重复。因此可以先创建一个有10000个元素的数组，随机取出一个元素，将其放在一边，而放在一边的方式就是与最后一个元素对换，之后取随机数的范围就排除对换至数组后端的元素，同时将选出的元素存入一个新的数组，即为生成序列。

      这里我就先直接附上源码：

/**
 * @author 鞠文婷
 * 抽牌算法
 */
package getRandomInt;

import java.util.Scanner;

public class getRandomInt {
	public static int[] getRandomInt(int n) {
		int[] result = new int[n];    //用于存储输出序列
		
		int[] intArray = new int[10000];
		// 初始化原数组
		for(int i=0;i<intArray.length;i++) {
			intArray[i] = i+1;
		}
		
		// 获取不重复的随机数数组
		for(int i=0;i<n;i++) {
			int c = getRandom(0,10000-i,n);
			int index = c;
			swap(intArray,index,10000-i-1);
			result[i] = intArray[10000-i-1];
			
//			System.out.println(i+" "+result[i]);
//			if(result[i] == 9999)
//				System.out.println("--------------------------------");
		}
		
		// 判断是否有重复元素
		for(int m=0;m<result.length;m++) {
			for(int a=m+1;a<result.length;a++) {
				if(result[m] == result[a])
					System.out.println("~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~"+result[m]+"  m = "+m+"  a = "+a);
			}
		}
		
		return result;
	}
	
	// 交换数组内元素
	public static void swap(int[] array,int x,int y) {
		int temp = array[x];
		array[x] = array[y];
		array[y] = temp;
	}
	
	// 获取随机数（方法其一~）
	public static int getRandom(int min,int max,int n) {
		int result = min + new Double(Math.random() * (max - min)).intValue();
//		System.out.println("result = "+result);
		return result;
	}
	public static void main(String args[]){
		System.out.println("Please enter an integer between 0 to 10000:");
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		
		System.out.println("The random list is: ");
		getRandomInt(n);
	}

}

 

 

      鉴于抽牌算法没有一个固定的套路，因此我这里再附上两个思路：

      I、每次抽取一个随机数后，定义一个新的数组，存储剩余元素，显然这种方法效率太低，而且大致思路与上面相同，没有必要；

      II、假设输出序列为n，则将0~10000分成n部分，从每部分中随机抽取一个元素，组成最终的序列。关于这个方法，可能很多人乍眼看上去会觉得所取元素不够随机，但实际上，从概率论的角度来说，这种情况下每个元素被抽到的概率是一样的，只不过可能的情况变少了。如果大家心里还是有隔阂的话，也可以在原数组上做点改动再分组，毕竟没有一个固定的格式，只要符合随机&不重复的要求，抽牌算法怎样捣腾都是可以的。 

      这里就不附上源码了，如果有更好的思路，欢迎大家讨论围观，相互学习~

 

      算法思想很简单，但还是有些东西值得学习的，比如说，生成随机序列。这里介绍地挺详细，我只是采用了一种很简单的方法。

 

      Java版的算法收获了不少人的建议，因此C++版我采用了一个新的算法思想：每获取一个元素，则将其值变为范围之外的值，比如我的范围是1~x，则将取过的值变为x+1，之后重新取随机数，如果它对应的元素是范围之外的则重新取，这也算是标志法的一个变种吧，源码如下：

 

#include<iostream>
#include<stdlib.h>
using namespace std;
int getRandomInt(int n);
int getRandom(int min,int max);

int x;     // 定义总数组长，即范围上限，默认下限为1（10000）

// 生成随机序列
int getRandomInt(int n) {
	cout<<"Please enter x:"<<endl;
	cin>>x;
	cout<<"Please enter the length of list you want to print:"<<endl;
	cin>>n;

	int *array = new int[x];
	for(int i=1;i<=x;i++) {
		array[i] = i;
	}

	int *result = new int[n]; //存储输出序列

	for(int j=0;j<n;j++) {
		int index = getRandom(1,x);
		if(array[index] < x+1) {
			result[j] = array[index];
			cout<<j+1<<"\t"<<result[j]<<endl;
		}
		else j--;
		array[index] = x+1;
	}

	return 0;
}

// 选取min~max的随机数
int getRandom(int min,int max) {
	int random = rand() % (max-min+1) + min;
	return random;
}

int main() {
	int n;
	cout<<getRandomInt(n);
	return 0;
}

 最后附上程序流程图一份儿：



 

        想要“正宗”的标记法做法，请看评论~ 

 

欢迎批评指正！~

 

 

  • 大小: 69.9 KB
3
顶
2
踩
分享到：
| 浅析Mac OS X与Linux的启动过程
评论
22 楼 kidding87 2014-10-17  
hashset就完啦
	public static HashSet<Integer> generate(int from,int to,int size){
		assert to>from;
		Random r = new  Random();
		HashSet<Integer> set = new HashSet<>(size);
		while(set.size()!=size){
			set.add(r.nextInt(to-from+1)+from);
		}
		return set;
	}
21 楼 鞠文婷 2014-10-16  
357236417 写道
到此一游~

欢迎经常来踩  话说大神你能不能把名字换了~
20 楼 357236417 2014-10-16  
到此一游~
19 楼 鞠文婷 2014-10-16  
yangguo 写道
public class Test {
	
	static  int[] createRandomArray(int max,int count){
		int[] flags = new int[max];
		int[] result = new int[count];
			
		for (int i = 0; i < count; i++) {
			int rand = 0;
			do{
				rand = new Random().nextInt(max) + 1;
			}while(flags[rand] == 1);
			flags[rand] = 1;
			result[i] = rand;
		}
		return result;
	}
	public static void main(String[] args) {
		int[] rands = createRandomArray(10000,100);
		for (int i = 0; i < 50; i++) {
			System.out.println(rands[i]);
		}
	}
	

}

学习了
18 楼 鞠文婷 2014-10-16  
yangguo 写道
public class Test {
	
	static  int[] createRandomArray(int max,int count){
		int[] flags = new int[max];
		int[] result = new int[count];
			
		for (int i = 0; i < count; i++) {
			int rand = 0;
			do{
				rand = new Random().nextInt(max) + 1;
			}while(flags[rand] == 1);
			flags[rand] = 1;
			result[i] = rand;
		}
		return result;
	}
	public static void main(String[] args) {
		int[] rands = createRandomArray(10000,100);
		for (int i = 0; i < 50; i++) {
			System.out.println(rands[i]);
		}
	}
	

}

前辈好热心  我的C++版是基于你的建议写的，用的标志法~
17 楼 yangguo 2014-10-16   
public class Test {
	
	static  int[] createRandomArray(int max,int count){
		int[] flags = new int[max];
		int[] result = new int[count];
			
		for (int i = 0; i < count; i++) {
			int rand = 0;
			do{
				rand = new Random().nextInt(max) + 1;
			}while(flags[rand] == 1);
			flags[rand] = 1;
			result[i] = rand;
		}
		return result;
	}
	public static void main(String[] args) {
		int[] rands = createRandomArray(10000,100);
		for (int i = 0; i < 50; i++) {
			System.out.println(rands[i]);
		}
	}
	

}
16 楼 yangguo 2014-10-16  
鞠文婷 写道
yangguo 写道
fsplove520 写道
yangguo 写道
算法错误，效率低下。随便举一例，只要第一个随机数出来不是9999，那以后怎么也不可能是9999了。

用 筛选法 可秒出。


这倒不一定，他是把已经选到的值替换到后面去了，也就是 9999有可能被替换到中间的某个元素，还是有可能选到 9999的



胡说八道，第一个值出来后，随机值就变成在【0,9999）之间，出来个鬼啊。

你可能没有细看我的算法思想，如果前两个没有选到9999的话，那它在第二个数出来后会被换到前面去，我加了个判断语句，你输入10000时是可以输出9999的，而且我试了两次都不是第一个~ 还有筛选法是筛选出素数的吧


重新看了下。那应该是不用判断重复的了，因为根本不会重复。
好吧，标志法
15 楼 yangguo 2014-10-16  
fsplove520 写道
yangguo 写道
fsplove520 写道
yangguo 写道
算法错误，效率低下。随便举一例，只要第一个随机数出来不是9999，那以后怎么也不可能是9999了。

用 筛选法 可秒出。


这倒不一定，他是把已经选到的值替换到后面去了，也就是 9999有可能被替换到中间的某个元素，还是有可能选到 9999的



胡说八道，第一个值出来后，随机值就变成在【0,9999）之间，出来个鬼啊。


具体他这个实现能不能取到我就不清楚了，但是按照他的设计，取完第一个之后如果不是9999，那么9999是被替换到前面去了，最后一个元素的值并不是9999了，话说，这样取不到9999?


好吧，我错了。这算法太诡异。
14 楼 鞠文婷 2014-10-16  
鞠文婷 写道
yangguo 写道
fsplove520 写道
yangguo 写道
算法错误，效率低下。随便举一例，只要第一个随机数出来不是9999，那以后怎么也不可能是9999了。

用 筛选法 可秒出。


这倒不一定，他是把已经选到的值替换到后面去了，也就是 9999有可能被替换到中间的某个元素，还是有可能选到 9999的



胡说八道，第一个值出来后，随机值就变成在【0,9999）之间，出来个鬼啊。

你可能没有细看我的算法思想，如果前两个没有选到9999的话，那它在第二个数出来后会被换到前面去，我加了个判断语句，你输入10000时是可以输出9999的，而且我试了两次都不是第一个~ 还有筛选法是筛选出素数的吧

随机数是用作的数组下标，不一定是对应元素
13 楼 鞠文婷 2014-10-16  
yangguo 写道
fsplove520 写道
yangguo 写道
算法错误，效率低下。随便举一例，只要第一个随机数出来不是9999，那以后怎么也不可能是9999了。

用 筛选法 可秒出。


这倒不一定，他是把已经选到的值替换到后面去了，也就是 9999有可能被替换到中间的某个元素，还是有可能选到 9999的



胡说八道，第一个值出来后，随机值就变成在【0,9999）之间，出来个鬼啊。

你可能没有细看我的算法思想，如果前两个没有选到9999的话，那它在第二个数出来后会被换到前面去，我加了个判断语句，你输入10000时是可以输出9999的，而且我试了两次都不是第一个~ 还有筛选法是筛选出素数的吧
12 楼 fsplove520 2014-10-16  
yangguo 写道
fsplove520 写道
yangguo 写道
算法错误，效率低下。随便举一例，只要第一个随机数出来不是9999，那以后怎么也不可能是9999了。

用 筛选法 可秒出。


这倒不一定，他是把已经选到的值替换到后面去了，也就是 9999有可能被替换到中间的某个元素，还是有可能选到 9999的



胡说八道，第一个值出来后，随机值就变成在【0,9999）之间，出来个鬼啊。


具体他这个实现能不能取到我就不清楚了，但是按照他的设计，取完第一个之后如果不是9999，那么9999是被替换到前面去了，最后一个元素的值并不是9999了，话说，这样取不到9999?
11 楼 yangguo 2014-10-16  
fsplove520 写道
yangguo 写道
算法错误，效率低下。随便举一例，只要第一个随机数出来不是9999，那以后怎么也不可能是9999了。

用 筛选法 可秒出。


这倒不一定，他是把已经选到的值替换到后面去了，也就是 9999有可能被替换到中间的某个元素，还是有可能选到 9999的



胡说八道，第一个值出来后，随机值就变成在【0,9999）之间，出来个鬼啊。
10 楼 鞠文婷 2014-10-16  
sjynt131 写道
鞠文婷 写道
sjynt131 写道
呵呵，思路挺清晰，但代码问题不少啊，没测试吧？

怎么可能没测试... 算法代码的问题有哪些？

1. n是 用于存储输出序列 的长度，swap(intArray,index,n-i-1); 这里是把n当做原数组intArray的长度了吧？ 看你的逻辑是应该把抽出的随机数放到原数组后面，但实际是放到前面去了，所以有可能结果会重复。
2. getRandom(int min,int max,int n)多了个没有使用的参数n,不知道建方法时有什么用意。
3. 在性能优化上没有考虑，比如在抽取数量较小时没必要有原数组并做交换，直接在范围内取足够数量的不重复的随机数返回即可。或者抽取数较大时(大于原数组一半长度)，抽取的随机数是去除的数据之类的考虑...

一语惊醒梦中人！我昨天加了判断语句后发现的确是有重复，但一直不知道哪里出错，谢谢你~
9 楼 sjynt131 2014-10-16  
鞠文婷 写道
sjynt131 写道
呵呵，思路挺清晰，但代码问题不少啊，没测试吧？

怎么可能没测试... 算法代码的问题有哪些？

1. n是 用于存储输出序列 的长度，swap(intArray,index,n-i-1); 这里是把n当做原数组intArray的长度了吧？ 看你的逻辑是应该把抽出的随机数放到原数组后面，但实际是放到前面去了，所以有可能结果会重复。
2. getRandom(int min,int max,int n)多了个没有使用的参数n,不知道建方法时有什么用意。
3. 在性能优化上没有考虑，比如在抽取数量较小时没必要有原数组并做交换，直接在范围内取足够数量的不重复的随机数返回即可。或者抽取数较大时(大于原数组一半长度)，抽取的随机数是去除的数据之类的考虑...
8 楼 鞠文婷 2014-10-15  
sjynt131 写道
呵呵，思路挺清晰，但代码问题不少啊，没测试吧？

怎么可能没测试... 算法代码的问题有哪些？
7 楼 fsplove520 2014-10-15  
yangguo 写道
算法错误，效率低下。随便举一例，只要第一个随机数出来不是9999，那以后怎么也不可能是9999了。

用 筛选法 可秒出。


这倒不一定，他是把已经选到的值替换到后面去了，也就是 9999有可能被替换到中间的某个元素，还是有可能选到 9999的
6 楼 yangguo 2014-10-15  
算法错误，效率低下。随便举一例，只要第一个随机数出来不是9999，那以后怎么也不可能是9999了。

用 筛选法 可秒出。
5 楼 sjynt131 2014-10-15  
呵呵，思路挺清晰，但代码问题不少啊，没测试吧？
4 楼 鞠文婷 2014-10-15  
fsplove520 写道
我的意思是 用这个，得到了重复元素

我修改了下，每次循环的时候，下标随机数的范围相应-1，因为相应元素会被移到数组尾，就相当于将已选随机数对应的元素从原数组中删除，这样就不会有重复了~ 多谢指正！
3 楼 fsplove520 2014-10-15  
我的意思是 用这个，得到了重复元素
发表评论

您还没有登录,请您登录后再发表评论

相关推荐

    易语言源码易语言抽牌算法模块源码

    易语言的抽牌算法模块是易语言编程中用于模拟抽牌（比如卡牌游戏中的随机抽取一张卡牌）的程序代码。这种模块通常会包含如何在一组卡牌中进行随机选择的算法实现。 抽牌算法的具体实现通常需要考虑以下几个关键点：...

    易语言抽牌模块例程源码,易语言抽牌算法模块

    "易语言抽牌模块例程源码"是一个基于易语言编写的程序，主要用于实现抽牌算法，这种算法常用于模拟游戏中的随机事件或者进行数据排序等场景。抽牌算法的核心在于能够生成一个无重复且有序或无序的随机序列。 抽牌...

    易语言源码抽牌算法模块源码.rar

    在“易语言源码抽牌算法模块源码.rar”这个压缩包中，包含了一个易语言实现的抽牌算法模块以及相关的使用说明。 抽牌算法在游戏开发、模拟实验等领域中广泛应用，例如在扑克游戏中，随机抽取一定数量的牌，保证每次...

    抽牌算法模块源码和调用例程

    易语言作为一款面向中文编程学习者的编程语言，拥有丰富的模块资源，其中抽牌算法模块是非常实用且有趣的一类。抽牌算法，又称作洗牌算法，广泛应用于游戏设计、模拟实验以及密码学等多个领域。通过该算法，计算机...

    易语言抽牌算法模块源码.zip易语言项目例子源码下载

    这个"易语言抽牌算法模块源码.zip"文件是一个易语言项目实例，提供了抽牌算法的实现，适合初学者、学生以及小团队用于学习和开发项目。抽牌算法在各种游戏和模拟场景中广泛应用，例如扑克牌游戏。 抽牌算法的核心...

    易语言源码易语言抽牌算法模块源码.rar

    易语言源码易语言抽牌算法模块源码.rar 易语言源码易语言抽牌算法模块源码.rar 易语言源码易语言抽牌算法模块源码.rar 易语言源码易语言抽牌算法模块源码.rar 易语言源码易语言抽牌算法模块源码.rar 易语言源码...

    易语言抽牌算法模块源码-易语言

    在这个“易语言抽牌算法模块源码”中，我们可以学习到如何用易语言实现一个抽牌算法，这在游戏开发、随机选择算法等方面具有广泛的应用。 抽牌算法通常指的是从一副扑克牌（52张）中随机抽取指定数量的牌，而这个...

    易语言-抽牌算法模块源码和调用例程

    在这个“易语言-抽牌算法模块源码和调用例程”压缩包中，包含了一个用于生成随机序列的易语言模块。这个模块的核心功能是创建一个不重复的随机数字序列，其成员个数可由用户指定。 抽牌算法通常指的是从一个集合中...

    抽奖随机数算法java

    一种实现方式是使用Fisher-Yates洗牌算法（又称Knuth shuffle），先将奖品编号进行洗牌，然后再抽取顶部的一个元素，这样可以实现不均匀的概率分布。 在实际编程中，`Lottery`文件可能包含了实现这些功能的Java类。...

    抽奖算法最新

    一种实现方法是使用Fisher-Yates洗牌算法，对带有权重的参与者列表进行排序后再随机抽取。 3. **循环抽奖**：如果希望保证每个参与者都有一定次数的抽奖机会，可以使用循环抽奖算法。每次未中奖的参与者会再次进入...

    洗牌算法思路讲解（程序员面试题）

    洗牌算法是编程领域中一个有趣的议题，常用于模拟各种随机事件，比如电子游戏中抽取卡片、抽奖系统等。本文将探讨三种不同的洗牌算法思路，它们各有优缺点，适用于不同的场景。 首先，我们来理解洗牌算法的核心目标...

    javascript随机之洗牌算法深入分析

    【洗牌算法详解】 洗牌算法，又称为随机排列生成，是编程中处理随机性问题的一个常见场景，常用于游戏中的随机事件、随机选择等。它的目标是将一个有序序列（如1到M的整数）随机重排，形成一个看似无规律的新序列。...

    C#制作扑克牌抽取

    7. **洗牌算法**：为了让每次抽取的牌序都是随机的，需要设计一个洗牌算法。Fisher-Yates（也称为Knuth）洗牌算法是一个常见的选择，它通过在数组或集合的范围内随机交换元素来达到洗牌效果。 8. **异常处理**：在...

    php实现简单洗牌算法

    在编程领域中，洗牌算法主要用于实现数组元素的随机排序，常常应用于游戏开发、模拟随机事件等场景。PHP（PHP: Hypertext Preprocessor）是一种广泛使用的开源服务器端脚本语言，非常适合用来编写这类算法。本篇将...

    【算法】扑克发牌算法实现

    在这个过程中，每次随机选择一个牌的索引，并将其分配给当前玩家，然后将这张牌移动到数组的末尾，以便下一次抽牌时不会再次被抽到。每为一位玩家发一张牌，剩余可发牌的数量就减少一。当所有玩家都获得了25张牌后，...

    50个优秀经典PHP算法大集合

    │ ├── Kmp.php 算法导论-KMP算法 │ ├── DijkstraQuery.php 迪克斯特拉算法 │ │ └── QulickQuery.php 快速查找 │ │ │ ├── Structure 数据结构 │ │ ├── Stack...

    随机生成牌和洗牌问题

    洗牌算法 - Fisher-Yates Shuffle (Fisher-Yates 洗牌算法) 这是一种常见的洗牌算法，能够高效地对数组进行随机排序。算法的核心思想是从数组尾部开始，每次随机选择一个元素与当前位置的元素交换，从而保证每个...

Magicbox
Global site tag (gtag.js) - Google Analytics