给定N张扑克牌和一个随机函数，设计一个洗牌算法_

推荐

ChrisNewbie

void shuffle(int cards[],int n)
{
	if(cards==NULL)
		return ;

	srand(time(0));

	for(int i=0;i<n-1;++i)
	{
		//保证每次第i位的值不会涉及到第i位以前
		int index=i+rand()%(n-i);
		int temp=cards[i];
		cards[i]=cards[index];
		cards[index]=temp;
	}
}

编辑于 2015-07-26 19:36:31 回复(2)

Tommyzt

假定Ｎ=54，首先，我们有一个随机函数发生器，能够产生1-54之间的随机数，如何保证抽第一张牌是54中可能，抽第二张牌是53中可能，……

可以这样做，假设扑克牌是一个54维的数组card，我们要做的就是从这个数组中随机取一个元素，然后在剩下的元素里再随机取一个元素… 这里涉及到一个问题，就是每次取完元素后，我们就不会让这个元素参与下一次的选取。

我们要实现的目的是以等概率的方式将这54个数随机打乱排列，因此，可以这样处理：

第一次抽牌在初始54张牌中，将随机产生的牌x，与第一个元素互换，

第二次抽牌在剩下的53张牌中，将随机产生的牌y，与第二个元素互换，

……

void RandomShuffle(int a[], int n){  
    for(int i=0; i<n; ++i){  
        int j = rand() % (n-i) + i;// 产生i到n-1间的随机数  
        Swap(a[i], a[j]);//交换位置  
    }  
}

发表于 2015-08-05 09:09:35 回复(3)

NSDaBen

解析：
最直观的思路是什么？很简单，每次从牌堆中随机地拿一张出来。那么，第一次拿有52种可能，拿完后剩下51张；第二次拿有51种可能，第三次拿有50种可能， …，一直这样随机地拿下去直到拿完最后1张，我们就从52!种可能中取出了一种排列，这个排列对应的概率是1/(52!)，正好是题目所要求的。

接下来的问题是，如何写代码去实现上面的算法？假设扑克牌是一个52维的数组cards，我们要做的就是从这个数组中随机取一个元素，然后在剩下的元素里再随机取一个元素… 这里涉及到一个问题，就是每次取完元素后，我们就不会让这个元素参与下一次的选取。这个要怎么做呢。

我们先假设一个5维数组：1，2，3，4，5。如果第1次随机取到的数是4，那么我们希望参与第2次随机选取的只有1，2，3，5。既然4已经不用，我们可以把它和1交换，第2次就只需要从后面4位(2,3,1,5)中随机选取即可。同理，第2次随机选取的元素和数组中第2个元素交换，然后再从后面3个元素中随机选取元素，依次类推。
代码：
#include <iostream>
#include <cstdlib>
using namespace std;

void Swap(int &a, int &b){// 有可能swap同一变量，不能用异或版本
 int t = a;
 a = b;
 b = t;
}
void RandomShuffle(int a[], int n){
 for(int i=0; i<n; ++i){
 int j = rand() % (n-i) + i;// 产生i到n-1间的随机数
 Swap(a[i], a[j]);
 }
}
int main(){
 srand((unsigned)time(0));
 int n = 9;
 int a[] = {
 1, 2, 3, 4, 5, 6, 7, 8, 9
 };
 RandomShuffle(a, n);
 for(int i=0; i<n; ++i)
 cout<<a[i]<<endl;
 return 0;
}

发表于 2015-08-21 14:38:13 回复(3)

🖇20190726190609

/**  * java代码  * 思路：产生0到n-i的随机整数rNum作为索引，将数组中的第rNum个数字和第n-1-i个数字交换  * 思路很简单，可能是我审题不清，不知道参数n有什么用，希望大家能指点一  * 按照我的理解参数n和cards的长度是相等的，  * 相等的话n是没必要传递的，直接 n=cards.length 就行  */ static void shuffle(int[] cards, int n) {     Random r = new Random();     for (int i = 0; i < n; i++) {         int rNum = r.nextInt(n - i);         cards[rNum] = cards[n - 1 - i] + cards[rNum] - (cards[n - 1 - i] = cards[rNum]);     } }

发表于 2019-07-29 00:22:59 回复(0)

牛客906914930号

随机函数对 N--求余然后用一个N维数组接收

发表于 2020-05-18 04:03:16 回复(0)

永恒的灯火1

void Rand(int a[],int N)
{
int j=0;
for(int i=0;i<N;i++)
{
j=rand%(n-i)+i;
swap(a[i],a[j]);
}
}

发表于 2017-09-17 18:45:30 回复(0)

laniakea0811


	依次遍历数组，对第n个元素，以1/n的概率与前n个元素中的某个元素互换位置，最后生成的序列即满足要求，1/n的概率可通过rand() % n实现。见如下程序：



	void swap(int &a, int &b)



	{



	    int tmp = a;



	    a = b;



	    b = tmp;



	}



	 



	void shuffle(int *arr, int n)



	{



	    int i;



	    for(i = 0; i < n; i++) {



	        int idx = rand() % (i + 1); //选取互换的位置



	        swap(&arr[idx], &arr[i]);



	    }



	}

发表于 2015-09-14 10:13:58 回复(0)

牛客387403号

可以先将N张扑克牌生成一个全排列，将每个排列的编号存入一个数组中，然后用随机函数生成一个索引，可以在数组中任意取一种排列就算一种洗牌的方式。

发表于 2015-09-01 22:33:39 回复(0)

米醋

voidshuffle(inta[],intlen)

{

if (a == NULL) return;

for(int i = 0; i < len; ++i)

{

int j = i + random() % (len - i);

swap(a[i], a[j]);

}

发表于 2015-07-26 19:02:22 回复(0)

simmon_hu

  void shuffle(int arr[],int n) 
  { 
      for(int i=0;i<n-1;i++)
          { 
              int val=i+rand()%(n-i);
              int temp=a[i];
              a[i]=a[val];
              a[val]=temp;
          }
  }

编辑于 2015-06-29 12:10:02 回复(0)

小小娃爱吃甜食

void get_rand_number(int card[],int size)
 {
  int m1,m2,temp;
  if(card==NULL||size==0)
      return ;
  for(int i=0;i<size;i++)
  {
  m1=i+rand()/size-i;
  temp=card[i];
  card[i]=card[m1];
  card[m1]=card[i];
  }
 }

编辑于 2015-06-29 12:10:14 回复(0)

请叫我小奋青

public class Test {
public static void main(String[] args) {
 String[] s = {"2","3","4","5","6","7","8","9","10","J","Q","K","A"};
 pushCard(s);
}

static void pushCard(String[] s){
 Random random = new Random();
 for (int i = 0; i < 30; i++) {
 int rand = random.nextInt(13);
 int rand2 = random.nextInt(13);
 String t = s[rand];
 s[rand] = s[rand2];
 s[rand2] = t;
 }
 for (String string : s) {
 System.out.print(string+" ");

}
}
}

随机交换任意两张牌的顺序N次即可完成洗牌

发表于 2015-06-04 20:23:07 回复(0)

Yaphets强神

public class User {
     public static void main(String[] args) {
         shuffle();
     }
     public static void shuffle() {
         List<Integer> list = new ArrayList<Integer>();
         int a=(int)( Math.random()*10);
         a=a+1;
         list.add(a);
         for (int i = 1; i < 10; i++) {
             
             a=(int) (Math.random()*10);
             a=a+1;
             if(list.contains(a)){
                 i--;
             }else{
                 list.add(a);
             }
         }
         for(int i=0;i<list.size();i++){
             System.out.print(list.get(i)+" ");
         }
     }
 }

编辑于 2015-06-29 12:10:31 回复(0)

affiliu

  void xipai(int &a[],int len) 
  { 
      for(int i=0;i<len;i++)
      {
          int j=i+rand()%(len-i);
          int temp=a[i]; 
          a[i]=a[j]; 
          a[j]=temp;
      } 
  }

编辑于 2015-06-29 12:10:46 回复(0)

noble4cc

/**
 * @brief shuffle 洗牌算符
 * @param a 扑克牌，里面存放着扑克盘的数值
 * @param len 扑克的数量
 */
void shuffle(int a[],int len)
{
    for(int i=0;i<len;++i)
    {
        int val=i+rand()%(len-i);//通过随即按函数获得要交换的扑克的位置
        int temp=a[val];
        a[val]=a[i];
        a[i]=temp;
    }
}

编辑于 2015-05-19 18:34:43 回复(0)

gqqh

for(int i = 0; i < N; i++){
int j = random(i, n-1);
swap(card[i], card[j]);
}

发表于 2015-05-11 16:21:52 回复(0)

陈木木

只要能够保证洗牌算法均匀即可，下面给出个经典的洗牌算法的伪代码:

for i in 1….n:
 randomly select a card j from [1,i]
 swap card i with card j

编辑于 2015-05-18 13:04:45 回复(0)

给定N张扑克牌和一个随机函数，设计一个洗牌算法

问题信息

热门推荐

相关试题