C++高手帮忙!今天想了很久还是想不出洗牌的的原理.上百度下了个程序也看不懂.请大神们给我注释下.

请求大神指导我怎样看懂这个C++程序 我搞了好几天还是看不懂 注释看了不太有用 我要看懂它是怎么远行的~

我要先夸赞一下题主，初中就开始接触C++是很多人都做不到的一件了不起的事。你要问的其实是一个数学问题，关键词是坐标系中向量叉积计算三角形面积。程序中a,b,c是三个点，在类中构建坐标。具体意思如下

想弄清楚这一块可以去网上看看叉积的定义，不难理解。学习C++还是推荐CSDN博客，可以学到很多。好好加油！

几乎所有的程序员都写过类似于“洗牌”的算法，也就是将一个数组随机打乱后输出，虽然很简单，但是深入研究起来，这个小小的算法也是大有讲究。我在面试程序员的时候，就会经常让他们当场写一个洗牌的函数，从中可以观察到他们对于这个问题的理解和写程序的基本功。

在深入讨论之前，必须先定义出一个基本概念：究竟洗牌算法的本质是什么？也就是说，什么样的洗牌结果是“正确”的？

云风曾经有一篇博文，专门讨论了这个问题，他也给出了一个比较确切的定义，在经过洗牌函数后，如果能够保证每一个数据出现在所有位置的概率是相等的，那么这种算法是符合要求的。在这个前提下，尽量降低时间复杂度和空间复杂度就能得到好的算法。

第一个洗牌算法：

随机抽出一张牌，检查这张牌是否被抽取过，如果已经被抽取过，则重新抽取，直到找到没被抽出过的牌，然后把这张牌放入洗好的队列中，重复该过程，直到所有的牌被抽出。

大概是比较符合大脑对于洗牌的直观思维，这个算法经常出现在我遇到的面试结果中，虽然它符合我们对于洗牌算法的基本要求，但这个算法并不好，首先它的复杂度为O(N2)，而且需要额外的内存空间保存已经被抽出的牌的索引。所以当数据量比较大时，会极大降低效率。

第二个算法：

设牌的张数为n，首先准备n个不容易碰撞的随机数，然后进行排序，通过排序可以得到一个打乱次序的序列，按照这个序列将牌打乱。

这也是一个符合要求的算法，但是同样需要额外的存储空间，在复杂度上也会取决于所采用的排序算法，所以仍然不是一个好的算法。

第三个算法：

每次随机抽出两张牌交换，重复交换一定次数次后结束

void shuffle(int* data, int length)

{

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

{

//Rand(min, max)返回[min, max)区间内的随机数

int index1 = Rand(0, length);

int index2 = Rand(0, length);

std::swap(data[index1], data[index2]);

}

}

这又是一个常见的洗牌方法，比较有意思的问题是其中的“交换次数”，我们该如何确定一个合适的交换次数？简单的计算，交换m次后，具体某张牌始终没有被抽到的概率为((n-2)/n)^m，如果我们要求这个概率小于1/1000,那么 m>-3*ln(10)/ln(1-2/n),对于52张牌，这个数大约是176次，需要注意的是，这是满足“具体某张牌”始终没有被抽到的概率，如果需要满足“任意一张牌”没被抽到的概率小于1/1000，需要的次数还要大一些，但这个概率计算起来比较复杂，有兴趣的朋友可以试一下。

Update: 这个概率是，推算过程可以参考这里，根据这个概率，需要交换280次才能符合要求

第四个算法：

从第一张牌开始，将每张牌和随机的一张牌进行交换

void shuffle(int* data, int length)

{

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

{

int index = Rand(0, length);

std::swap(data[i], data[index]);

}

}

很明显，这个算法是符合我们先前的要求的，时间复杂度为O(N)，而且也不需要额外的临时空间，似乎我们找到了最优的算法，然而事实并非如此，看下一个算法。

第五个算法：

void shuffle(int* data, int length)

{

for(int i=1; i<length; i++)

{

int index = Rand(0, i);

std::swap(data[i], data[index]);

}

}

一个有意思的情况出现了，这个算法和第三种算法非常相似，从直觉来说，似乎使数据“杂乱”的能力还要弱于第三种，但事实上，这种算法要强于第三种。要想严格的证明这一点并不容易，需要一些数学功底，有兴趣的朋友可以参照一下这篇论文，或者matrix67大牛的博文，也可以这样简单理解一下，对于n张牌的数据，实际排列的可能情况为n! 种，但第四种算法能够产生n^n种排列，远远大于实际的排列情况，而且n^n不能被n!整除，所以经过算法四所定义的牌与牌之间的交换程序，很可能一张牌被换来换去又被换回到原来的位置，所以这个算法不是最优的。而算法五输出的可能组合恰好是n!种，所以这个算法才是完美的。

事情并没有结束，如果真的要找一个最优的算法，还是请出最终的冠军吧！

第六个算法：

void shuffle(int* data, int length)

{

std::random_shuffle(data, data+length);

}

没错，用c++的标准库函数才是最优方案，事实上，std::random_shuffle在实现上也是采取了第四种方法，看来还是那句话，“不要重复制造轮子”


不想写 - -

这是相对比较低效的，每次随即生成一张牌，遍历一遍，原来没有生成过则加入牌组，否则丢弃。
#include <stdio.h>
#include <math.h>
#include <stdlib.h>
#include <time.h>
int main()
{
int card[52];
int a,j,n,i=0,nosame=1;
char c;
randomize(); //只要初始化一次就行，否则一秒内的随机数是一样的
while(i<52)
{
a = rand()%52+1;
nosame=1; //nosame每次循环都要重置一下，**先假设是没有重复的**
for(j=0;j<i;j++) {\\a遍历，找到相同的牌则丢弃
if(card[j]==a) {\\a
nosame=0;\\a
break;\\a

if(nosame) card[i++]=a; //是nosame == 1的时候才可以放牌，i这时要加1
}

//以上就分完牌了，下面就输出结果
for(j=0;j<52;j++) {
if(card[j]>0&&card[j]<14) {c=3;n=card[j];}
else if(card[j]>13&&card[j]<27) {c=4;n=card[j]-13;}
else if(card[j]>26&&card[j]<40) {c=5;n=card[j]-26;}
else {c=6;n=card[j]-39;}
putchar(c);
switch(n) {
case 11:putchar('J');break;
case 12:putchar('Q');break;
case 13:putchar('K');break;
default:printf("%d", n);
}
printf("\t",n);
if(j%13==12)putchar('\n');
}
return 0;
}

原理到底是怎么样的啊。 是不是和那个八皇后问题差不多.
A：完全不一样。这算半个穷尽（不太准确），八皇后是回溯。

m

---

新晃侗族自治县17523222550： C++程序高手帮个忙啊!!？
漫兰盐酸： 时间比较忙,先做了3个,你参考一下 #include<iostream> using namespace std; int main() { int system(＂pause＂);i,sum1=0,sum2=0; for(i=0;i<=100;i++) if(i%2==0) sum1+=i; else sum2+=i; cout<<＂1~100所有偶数之和为＂<<sum1<<endl; cout<<...

新晃侗族自治县17523222550： C++高手进来下! 帮个忙! 很简单的! - ？
漫兰盐酸： 一楼的有没有测试啊,一楼的不能用这个希望能帮到你#include using namespace std;int main(){ int i=1; while(i<=10) { int j=1; while(j<=20) { cout...

新晃侗族自治县17523222550： C++程序设计数字图形,哪位高手帮作出来!!谢谢了,想了好长时间了!! - ？
漫兰盐酸： #include<iostream.h> int main() { int i,k,l,m,n; cout<<＂n=＂; cin>>n; m=0; for(i=0;i<n;i++) { m=m+i; l=m+1; cout<<l<<＂ ＂; for(k=1;k<n-i;k++) { l=l+k+i+1; cout<<l<<＂ ＂; } cout<<endl; } return 0; }cout<<endl; } return 0; 经过上机验证,结果正确无误

新晃侗族自治县17523222550： 各位c++高手 小弟有几个问题 想了很久 百思不得其解,请哪位高手指点 - ？
漫兰盐酸： 以下代码已经编译运行通过:#include <stdlib.h> #include<stdio.h> #include<conio.h> int N; void main() { int a,s=0,i,j,temp=1,result=0; do { printf(＂请输入一个一位正整数: ＂); scanf(＂%d＂,&a); if( a>9 ) printf(＂\n错误输入!!\n＂); }while(a...

新晃侗族自治县17523222550： 求C++高手帮助下？
漫兰盐酸： 建议先看一下谭浩强的C++程序设计然后再看离散数学和数据结构(他俩一起看)

新晃侗族自治县17523222550： C++的一个题目.小弟想好久都没想到.求高手帮忙! - ？
漫兰盐酸： 这是我的代码,用栈实现的,仅供参考 #include <iostream> using namespace std; class Stack{ public:Stack():top(0){}bool pop(char &c){c = '0';if (top<=0)return false;c = elem[--top];return true;}bool push(char c){if (top>=1002) return false;...

新晃侗族自治县17523222550： c++ 高手帮忙! - ？
漫兰盐酸： 分层计算,return fac(3)->进入fac(3) return fac(2)*3->进入fac(2) return fac(1)*2->进入fac(1) return 1;=>开始向上返回,计算出fac(2)=1*2=2 然后向上,计算出fac(3)=2*3=6

新晃侗族自治县17523222550： C++请高手帮忙？
漫兰盐酸：#include<iostream> using namespace std; int main() { int n,cn1,cn2; float sum,avg; cn1=cn2=0; sum = 0; do { cin>>n; if(n>0) { cn1++; } else if(n<0) { cn2++; } sum += n; } while (n!=0); avg = sum / (cn1+cn2); cout<<＂平均值:＂<<avg<<endl; cout<<＂正数个数:＂<<cn1<<endl; cout<<＂负数个数:＂<<cn2<<endl; return 0; }

新晃侗族自治县17523222550： c++高手帮帮忙 一个菜鸟问题 - ？
漫兰盐酸： #include using namespace std; void main() { int i=2,j=1,k,n; int fang; double sum=0.0; cin>>k; for(n=1;n{ fang=i; sum+=(double)i/j; i+=j; j=fang; } cout} 这道是很简单的算法.就是 分子=前一项分子+分母;分母=等于前一项分母;

新晃侗族自治县17523222550： 诚心求C++高手帮忙解决一下？
漫兰盐酸： #include<iostream.h> #define N 6 void pr(int *a) { int i; for(i=0;i<N;i++) cout<<a[i]<<＂ ＂; cout<<endl; } void dui(int *a,int k) { int t,max; int r,l; l=2*k+1; r=2*k+2; if(l>=N)//不存在左右子女,返回 return ; if(r<N) //存在右子 max=a[r]>a[l]?r:l; //取右左中大...