方法1：给每个元素A[i]随机分配一个优先级p[i]，然后按照优先级对数组A进行排序。例如初始A=<1,2,3,4>而且随机得到的优先级数组P=<36,3,97,19>，则得出随即数组B=<2,4,1,3>。这个过程称为PERMUTE_BY_SORTING。时间复杂度为O(nlgn)

方法2：原地排列给定数列。在第i次迭代时，元素A[i]是从元素A[i]到A[n]中随机选取的。时间复杂度为O(n)

n=length[A];

for i=1 to n

do swap(A[i], A[RANDOM(i,n)])

2、生日悖论

对于n=365，如果k=28，即如果至少有28个人，则可以期望至少有1对人的生日相同。

在n天中，k个人生日互不相同的组合有P(n,k)中，所有的组合（包括相同的）有n的k次方中，记为n^k，则k个人生日互不相同的概率为P(n,k)/n^k。

当k>=23时，P(n,k)/n^k<50%，则1-P(n,k)/n^k>50%，也就是说，当一个房间里有23个人时，至少有两个人生日相同的概率大于50%。

3、赠券收集者问题

一个人如果想要收集齐b种不同赠券中的每一种，大约需要b*lnb张随机得到的赠券才能完成。

用球和盒子的模型说明：把相同的球随机投到b个盒子中去。  

1>有多少个求落入指定的盒子中？服从二态分布(k；n，1/b)，则期望值为n/b

2>在给定的盒子中至少一个球之前，平均需要投多少个球？服从几何分布，概率为1/b，成功前的期望个数为1/(1/b)=b

3>在每个盒子至少有一个球之前，要投多少个球？

我们称一次投球中落入一个空盒子为“击中”。

将n次投球分成b个阶段，阶段i包括第i-1次击中到i次击中之间的投球次数。第i阶段的每一次投球有i-1个盒子有球，n-k+1个盒子是空的，这样第i阶段的所有投球击中的概率都为（n-k+1）/b

用ni表示第i阶段的投球次数

n=SUM(ni)<i=1 to b>    每个随机变量ni都服从几何分布，成功概率为(n-k+1)/b

则      E(ni)=b/(b-k+1)

E(n)=E(SUM(ni))=SUM(E(ni))=SUM(b/(b-k+1))=b*SUM(1/(b-k+1))

根据调和级数的界可得 E(n)=b*(b+……+1/2+1)=b*(ln(n)+O(1))

所以大约投球b*lnb次就可以满足条件

4、最长序列问题

抛一枚均匀硬币n次，期望看到连续正面的最长序列有多长？答案是O(lgn)。

用X(i,k)=I{A(i,k)}表示对应于长度为k的序列开始于第i次抛硬币的指示器随机变量。

定义 X=SUM(X(i,k))<i=1 to n-k+1>

则     E(X)=E(....)=...=SUM(1/2^k)=(n-k+1)/2^k

令     k=clgn，对某个常数c，有

E(X)=......=O(1/n^(c-1))

当c<1/2时，E(X)=O(n^(1/2))，期望会有大量长为1/2*lgn的序列，因此，最长序列期望值长度为O(lgn)

5、苏格拉底的捡麦穗问题

怎么才可以捡到期望的最大麦穗呢？

方法是在前k次中不捡麦穗，但是比较找出最大麦穗并记住，在后面的n-k个麦穗中第一次遇到比前k个中的最大的还要大的麦穗就捡起，就是目标麦穗。如果没有发现比前k个还要大的，就捡最后一个第n个。

这里的关键是取好k的值，使得能够捡到最大的麦穗的可能性最大，根据算法导论（中文版）第67和68页分析，这个k值取n/e时，则可以至少有1/e的概率渠道最大的麦穗。k=n/e

Time Limit:2000MS Memory Limit:65536K
Total Submit:200 Accepted:66

Description

n个元素{1,2,..., n }有n!个不同的排列。将这n!个排列按字典序排列，并编号为0，1，…，n!-1。每个排列的编号为其字典序值。例如，当n=3时，6 个不同排列的字典序值如下：

任务：给定n 以及n 个元素{1,2,..., n }的一个排列，计算出这个排列的字典序值，以及按字典序排列的下一个排列。
Input

第1 行是元素个数n(n < 15)。接下来的1 行是n个元素{1,2,..., n }的一个排列。

Output

第一行是字典序值，第2行是按字典序排列的下一个排列。

Sample Input
8
2 6 4 5 8 1 7 3

Sample Output
8227
2 6 4 5 8 3 1 7
-----------------------------------------------------------------------------------------------------------------------

字典序法：
字典序法中，对于数字1、2、3......n的排列，不同排列的先后关系是从左到右逐个比较对应的数字的先后来决定的。例如对于5个数字的排列 12354和12345，排列12345在前，排列12354在后。按照这样的规定，5个数字的所有的排列中最前面的是12345，最后面的是 54321。
字典序算法如下：
设P是1～n的一个全排列:p=p1p2......pn=p1p2......pj-1pjpj+1......pk-1pkpk+1......pn
1）从排列的右端开始，找出第一个比右边数字小的数字的序号j（j从左端开始计算），即   j=max{i|pi<pi+1}
2）在pj的右边的数字中，找出所有比pj大的数中最小的数字pk，即 k=max{i|pi>pj}（右边的数从右至左是递增的，因此k是所有大于pj的数字中序号最大者）
3）对换pi，pk
4）再将pj+1......pk-1pkpk+1pn倒转得到排列p'=p1p2.....pj-1pjpn.....pk+1pkpk-1.....pj+1，这就是排列p的下一个下一个排列。
例如839647521是数字1～9的一个排列。从它生成下一个排列的步骤如下：
自右至左找出排列中第一个比右边数字小的数字4          839647521
在该数字后的数字中找出比4大的数中最小的一个5        839647521
将5与4交换                                                                         839657421
将7421倒转                                                                          839651247
所以839647521的下一个排列是839651247。

--------------------------------------------------------------------------------------------------------------------------

#include<stdio.h>
#include<stdlib.h>

void dict_sort(int arr[],int size);
int find_first_small(int arr[],int size);
int find_smallest(int arr[],int start,int size);
void swap(int arr[],int idx1,int idx2);
void converse(int arr[],int start,int end);
int factorial(int n);
int find_position(int arr[],int size,int *pos);

int main(void)
{
int i,n,val;
int pos;
int *a;

scanf("%d",&n);
a=(int*)malloc(n*sizeof(int));

for(i=0;i<n;i++)
{
   scanf("%d",&a[i]);
   //a[i]=val;
}

dict_sort(a,n);
find_position(a,n,&pos);

printf("%d\n",pos);
for(i=0;i<n;i++)
   printf("%d ",a[i]);

return 0;
}

void dict_sort(int arr[],int size)
{

int idx1;
int idx2;

idx1=find_first_small(arr,size);

if(idx1==-1)
{
   printf("the last one...\n");
   return ;
}

idx2=find_smallest(arr,idx1+1,size);
swap(arr,idx1,idx2);
converse(arr,idx1+1,size-1);
}

int find_position(int arr[],int size,int *pos)
{
int i,nr;
int sum=0;
for(i=0;i<size-1;i++)
{
   nr=get_counter(arr,i,size);

   if(nr>0)
    sum += nr*factorial(size-i-1);
}
*pos=sum+1;

return *pos;
}

int factorial(int n)
{
int rt=1;
while(n>0)
{
   rt *=n;
   n--;
}
}

int find_first_small(int arr[],int size)
{
int i=size-1;

for(i=size-1;i>=0;i--)
{
   if(arr[i-1]<arr[i])
    return i-1;
}

return -1;
}

int get_counter(int arr[],int start,int size)
{
int i;
int counter=0;
int start_val=arr[start];

for(i=start+1;i<size;i++)
{
   if(arr[i]<start_val)
    counter++;
}

return counter;
}

int find_smallest(int arr[],int start,int size)
{
int i;
int pos=start;
int start_val=arr[start-1];
int key=arr[start];

for(i=start+1;i<size;i++)
{
   if(arr[i]>start_val&&arr[i]<key)
   {
    key=arr[i];
    pos=i;
   }

}

return pos;
}

void swap(int arr[],int idx1,int idx2)
{
int tmp=arr[idx1];

arr[idx1]=arr[idx2];
arr[idx2]=tmp;
}

void converse(int arr[],int start,int end)
{
int i=end;

for(i=end;i>=(start+end+1)/2;i--)
{
   swap(arr,end-i+start,i);
}
}

-------------------------------------------------------------------------------------------------------------

第一天出来的人作为“计数者”（第一个出来的人确定自己是“计数者”，其他人确定自己不是“计数者”）

如果是“计数者”就把灯打开（关闭的情况下打开），计数+1，若灯开着的话就什么也不做

如果不是“计数者”，如果是第一次出来放风而且灯开着就关闭它，否则什么也不做

当“计数者”的 counter=100的时候就可以想国王申请走人了。

-------------------------------------------------------------------------------------------------------------

这种算法需要多长的时间才可以获得释放呢，写代码验证之。答案是10000天左右，也就是20-30年的时间，够漫长的。不知道还有没有其他更好的方法。

#include<iostream>
#include<vector>
#include<ctime>
using namespace std;

int   getDays(void);
bool not_selected(vector<int> v,int key);

int main(void)
{
cout<<getDays()<<endl;
return 0;
}

int getDays(void)
{
int observer=-1;
int rd=-1;
int counter=0;
int days=0;
vector<int> prison;
volatile bool b_light=false;

srand(time(NULL));
observer=rand()%100;
b_light=true;
days++;

while(1)
{
   days++;
   if((rd=rand()%100)==observer)
   {
    if(b_light==false)
    {
     counter++;
     b_light=true;
    }
    if(counter==99)
     break;
   }
   else
   {
    if(b_light&&not_selected(prison,rd))
    {
     prison.push_back(rd);
     b_light=false;
    }
   } //else
} //while

return days;
}

bool not_selected(vector<int> v, int key)
{
for(vector<int>::iterator iter=v.begin();iter!=v.end();++iter)
{
   if(*iter==key)
    return false;
}

return true;
}

--------------------------------------C++ Primer----------------------------------------------------------------

执行语句 delete p; 后，p变成没有定义。

在很多机器上，尽管 p 没有定义，但仍然存放了它之前所指向对象的地址，然而 p 所指向的内存已经被释放，因此 p 不再有效。

删除指针后，该指针变成悬垂指针。

悬垂指针指向曾经存放对象的内存，但该对象已经不再存在了。悬垂指针往往导致程序错误，而且很难检测出来。

一旦删除了指针所指向的对象，立即将指针置为 0，这样就非常清楚地表明指针不再指向任何对象。

堆排序可以原地排序，这一点上优于合并排序（需要一个辅助数组）；插入排序也是原地排序，可是时间复杂度是O(n^2)

1、保持堆（大顶堆）的性质的算法（A是输入堆，从i开始保持大顶堆的性质）：

max_heapify(A,i)
    l=LEFT(i)
    r=RIGHT(i)
    if(l<=heap_size(A)&&A[l]>A[i]）
            then largest=l
    else largest=i
    if(r<=heap_size(A)&&A[r]>A[largest])
           largest=r
    if(largest!=i)
           then exchange A[i]<->A[largest]
          max_heapify(A,largest)

2、建堆（从最后一个非叶子节点开始使其保持堆的性质）：

共有n个元素，则最后一个非叶子节点位置是n/2。

不妨设最后一个非叶子节点为(n+1)/2，则其左孩子是n+1>n，矛盾，所以是n/2，则算法描述为

build_maxHeap(A)
    for i=heap_size(A)/2 downto 1
           do max_heapify(A,i)

3、堆排序

首先建立大顶堆，然后把根元素（最大元素）与最后一个叶子节点交换位置，heap-size--，然后从根元素开始调整堆，使其保持大顶堆的性质。

算法描述为

   heap_sort(A)
           build_maxHeap(A)
          for i=heap_size(A) downto 2
               do exchange A[1]<->A[i]
                    heap_size(A)=heap_size(A)-1
                    max_heapify(A,1)

-------------------------------------------------示例演示---------------------------------------------------------------------

示例输入：9                 /*堆大小*/

                  5                 /*元素个数*/

                  1 5 2 4 3     /*输入元素值*/

输出：5 4 3 2 1

-------------------------------------------------C代码实现---------------------------------------------------------------------

#include<stdio.h>
#include<stdlib.h>

#define LEFT(i)   2*i
#define RIGHT(i) 2*i+1
#define PARENT(i) i/2

struct HeapType{
int *base;   /*base[0]存放heap_size，因此heap_size字段也可以去掉*/
int length;
int heap_size; /*可去掉，用base[0]来代替*/
};

void max_heapify(struct HeapType heap,int i);
void build_maxHeap(struct HeapType heap);
void heap_sort(struct HeapType heap);
void swap(int *val1,int *val2);

int main(void)
{
int i=-1;
int n=-1;
int val=-1;
struct HeapType heap;

heap.length=0;
heap.heap_size=0;

scanf("%d",&n);

heap.length=n;
heap.base=(int*)malloc((heap.length+1)*sizeof(int));

scanf("%d",&heap.heap_size);

if(heap.heap_size>heap.length)
   return -1;

for(i=1;i<=heap.heap_size;i++)
{
   scanf("%d",&val);
   heap.base[i]=val;
   /*heap.heap_size +=1;*/
}

heap.base[0]=heap.heap_size;
i=heap.heap_size;

heap_sort(heap);
for( ;i>0;i--)
   printf("%d ",heap.base[i]);

return 0;
}

void max_heapify(struct HeapType heap,int i)
{
int largest=-1;
int l=LEFT(i);
int r=RIGHT(i);

if(l<=heap.heap_size && heap.base[l]>heap.base[i])
   largest=l;
else
   largest=i;

if(r<=heap.heap_size && heap.base[r]>heap.base[largest])
   largest=r;

if(largest!=i)
{
   swap(&heap.base[largest],&heap.base[i]);
   max_heapify(heap,largest);
}   
}

void build_maxHeap(struct HeapType heap)
{
int i=-1;

for(i=(heap.heap_size)>>1;i>0;i--)
   max_heapify(heap,i);
}

void heap_sort(struct HeapType heap)
{
int i=-1;

build_maxHeap(heap);

for(i=heap.heap_size;i>1;i--)
{
   swap(&heap.base[1],&heap.base[i]);
   heap.heap_size -=1;
   max_heapify(heap,1);
}
}

void swap(int *val1,int *val2)
{
int tmp=*val1;
*val1=*val2;
*val2=tmp;
}

-----------------------------------------------------------------------------------------------------------------------------------

函数可以返回指向函数的指针，但是，正确写出这种返回类型相当不容易：

// ff is a function taking an int and returning a function pointer

// the function pointed to returns an int and takes an int* and an int

int (*ff(int))(int*, int);

阅读函数指针声明的最佳方法是从声明的名字开始由里而外理解

要理解该声明的含义，首先观察：

ff(int)

将 ff 声明为一个函数，它带有一个 int 型的形参。该函数返回

int (*)(int*, int);

它是一个指向函数的指针，所指向的函数返回 int 型并带有两个分别是int* 型和 int 型的形参。

使用 typedef 可使该定义更简明易懂：

// PF is a pointer to a function returning an int, taking an int* and an int

typedef int (*PF)(int*, int);

PF ff(int);

// ff returns a pointer to function

允许将形参定义为函数类型，但函数的返回类型则必须是指向

函数的指针，而不能是函数。

具有函数类型的形参所对应的实参将被自动转换为指向相应函数类型的指针。但是，当返回的
是函数时，同样的转换操作则无法实现：

// func is a function type, not a pointer to function!

typedef int func(int*, int);

void f1(func);    // ok: f1 has a parameter of function type

func f2(int);        // error: f2 has a return type of function type

func *f3(int);       // ok: f3 returns a pointer to function type

------------------------------------------------------------------简单例子---------------------------------------------------------------------------------

#include<iostream>
using namespace std;

int (*ff(int f))(int val1,int val2);
int (*fun)(int val1,int val2);
int foo(int a,int b);

int main()
{
   fun=ff(0);
   cout<<fun(1,2)<<endl;
   return 0;
}

int foo(int a,int b)
{
   cout<<a<<" "<<b<<" foo is calling..."<<endl;
   return b+1;
}

int (*ff(int f))(int val1,int val2)
{
   cout<<f<<" ff is calling..."<<endl;
   return foo;
}

-------------------------------------------------------------------------------输出------------------------------------------------------------------------------

0 ff is calling...
1 2 foo is calling...
3

----------------------------------------------------------------------------使用typedef-----------------------------------------------------------------------

#include<iostream>
using namespace std;

typedef int (*fun)(int val1,int val2);
fun ff(int);
int foo(int a,int b);

int main()
{
   cout<<ff(0)(1,2)<<endl;
   return 0;
}

int foo(int a,int b)
{
    cout<<a<<" "<<b<<" foo is calling..."<<endl;
    return b+1;
}

fun ff(int f)
{
   cout<<f<<" ff is calling..."<<endl;
   return foo;
}