`
bcyy
  • 浏览: 1881063 次
文章分类
社区版块
存档分类
最新评论

Craking the coding interview 面试题:完美随机洗牌

 
阅读更多

给定一个序列,随机打乱这个序列,新产生的序列和任意一个序列产生的可能性是一样的,就是所谓的完美随机洗牌。

看下面的运行结果:


上面第一列是原数列,下面一行是新产生的打乱的数列。

基本思想:如果n-1个数是乱序的,我们可以使用一个随机数发生器,如C的rand(),那么产生一个数字代表数列下标,把这个下标和n下标的数值对换,那么就产生了n个乱序数。

问题是我们怎么得到n-1个乱序数?

这就是从底到顶的思想方法:如果数列只有一个数,那么可以说这个数就是个乱序数列了。接下来就是2个,然后是3个数……

这是个经典的思想方法,要记住!

最后就得到n个乱序数了。

下面是递归和非递归的程序。

int rangeRandNum(int a, int b)
{
	return rand()%(b-a+1) + a;
}

int *shuffleRecur(int cards[], int n)
{
	if (n == 1) return cards;
	shuffleRecur(cards, n-1);

	int k = rangeRandNum(0, n-1);
	swap(cards[k], cards[n-1]);
	return cards;
}

int *shuffleIter(int cards[], int n)
{
	for (int i = 1; i < n; i++)
	{
		int t = rangeRandNum(0, i);
		swap(cards[t], cards[i]);
	}
	return cards;
}

int main() 
{
	int tar = 7;
	int cand[] = {1,2,3,0,3,2,0,3,1,4,5,3,2,7,5,3,0,1,2,1,3,4,6,8,1,8};
	
	srand(time(NULL));

	for (int x:cand)
		cout<<x<<" ";
	cout<<endl;

	int *r = shuffleRecur(cand, sizeof(cand)/sizeof(int));

	for (int i = 0; i < sizeof(cand)/sizeof(int); i++)
	{
		cout<<r[i]<<" ";
	}
	cout<<endl;

	system("pause"); 
	return 0;
}


所谓的真随机,也是随机因素的程度高低罢了,比如下面的文章解析:

http://engineering.mit.edu/ask/can-computer-generate-truly-random-number

下面的网站是依靠大气等因素产生随机性非常高的随机:

http://www.random.org/





分享到:
评论

相关推荐

Global site tag (gtag.js) - Google Analytics