日度归档:2013 年 11 月 27 日

53张牌中找出缺少的牌的花色和点数–raid3,4,5,6的容错原理

一副扑克牌,抽出一张,要求找出抽出的牌的点数和花色。

算法的主要思想就是用异或运算来确定丢的牌的花色。四种花色分别如下表示:红桃用1(二进制0001)表示,黑桃用2(二进制0010)表示,黑桃用4(0100)表示,方块用8(1000)表示,这样当同一点数的四个花色都齐全的话,则四种花色异或的结果再与15(1111)异或之后,结果为0。如果确实一种花色,则三张存在的牌的花色值异或后与15异或所得的结果为抽出的花色的值。比如说:抽出的花色为红桃,则0010^0100^1000^1111=0001,正好等于红桃的值。具体实现见下面的代码。

#include
#include

#define NUMS 2 //NUMS = 2 用于演示,如果是一副牌的话NUMS应定义为53
using namespace std;

typedef struct Card{
  int num; //num用0-13分别表示A,2,3,4……,10,J,Q,K,王
  int flower; //flower表示花色 1表示红桃,3表示大王,2表示黑桃,12表示小王,3表示梅花,4表示方块
}Card;

void find(Card cards[])
{
int i;
map numclass_Map;
for(i=0;i<NUMS;i++)numclass_Map[i] = 15;

for(i = 0;i<NUMS*4-1;i++)
{
  numclass_Map[cards[i].num]^=cards[i].flower;
  if(numclass_Map[cards[i].num] == 0) numclass_Map.erase(cards[i].num);
}
map::iterator it;
it = numclass_Map.begin();
printf(“点数:%d 花色:%d\n”,it->first+1,it->second);
}

void main()
{
//just for test
Card cards[NUMS*4-1];

cards[0].num = 0;
cards[0].flower = 1;

cards[1].num = 0;
cards[1].flower = 2;

cards[2].num = 0;
cards[2].flower = 4;

cards[3].num = 0;
cards[3].flower = 8;

cards[4].num = 1;
cards[4].flower = 1;

cards[5].num = 1;
cards[5].flower = 2;

cards[6].num = 1;
cards[6].flower = 4;

//cards[7].num = 1;
//cards[7].flower = 8;

find( cards);
}

输出:

点数:2 花色:8

如果是抽出两种牌,这个算法也是可以分别找出抽出的牌的点数和花色的。这种容错的方法也就是raid3,4,5,6的容错方法,也就是奇偶校验方法。

抽样问题

需求:从正整数1-100中随机抽取20个数。

以下算法均来自与《编程珠玑》

1.精妙的算法,运用概率的知识。

或许你不理解rand()%(n-i)<m这一句,我开始也不理解,请教了高人之后才理解的,所以就写了这篇博客,以免忘了。

从n中选m个数,每个数被选中概率为m/n。

第一个数被选中的概率是m/n。

第二数被选中概率的计算如下:如果第一数被选中了,(m-1)/(n-1); 如果第一个数没有被选中,m/(n-1)。所以总体概率为m/n * (m-1)/(n-1) +(n-m)/n * m/(n-1) = m/n

以此类推。。。每个数被选中的概率都是m/n。

假设一个随机数生成器R,生成的数属于[0,Z-1],且生成每个数的概率相等。

对任意一个小于Z的数Q,那么R()<Q的概率即Q/Z。所以rand()%(n-i) < m 即表示m/n-i的概率,也就是当前数字被选中的概率。

严格来说,rand()%(n-i)并不是一个等概率生成器,因为rand()显然不是对每个i都是n-i的整数倍。

(以上解释出自肖微)

2.往一个初始为空的集合中插入随机整数,直到填入足够的整数。需要额外的m*size(int)的空间,最大的问题是需要查询重复元素。

3.弄乱n个元素,时间复杂度是O(m),但需要做交换操作。