第四章：随机数

1.第2题解答

找到t对应的下标后，继续向左线性查找相等元素，直到遇到不相等的元素。

2.第6题解答

1.1结论

每次执行一次，罐子中的豆子数量就减去1,所以此过程可以终止。如果开始时候白豆的个数为奇数，那么最后留下的是白豆的，否则为黑豆的。(source)

1.2编码验证

#include<iostream>
#include<vector>
#include<algorithm>
#include<random>

using namespace std;

enum color{ black, white };

unsigned rand(int n){
    uniform_int_distribution<unsigned> u(0, n);
    static default_random_engine e;
    return u(e);
}


void lastBean(vector<color> &bean1,vector<color> &bean2){
    vector<color> bean(bean1.size() + bean2.size());
    merge(bean1.begin(), bean1.end(), bean2.begin(), bean2.end(), bean.begin());
    unsigned i, j;
    while (bean.size()>1){
        i = rand(bean.size() - 1);
        j = rand(bean.size() - 1);
        while (j == i){
            j = rand(bean.size() - 1);
        }
        if (bean[i] == bean[j]){
            if (i<j){
                swap(i, j);
            }
            bean.erase(bean.begin() + i);
            bean.erase(bean.begin() + j);
            bean.push_back(black);
        }
        else{
            if (bean[i] == black){
                bean.erase(bean.begin() + i);
            }
            else{
                bean.erase(bean.begin() + j);
            }
        }
    }
    cout <<bean[0] << endl;
}

int main(){
    vector<color> bean1(11, black);
    vector<color> bean2(12, black);
    vector<color> bean3(11, white);
    vector<color> bean4(12, white);
    lastBean(bean1, bean3);//开始时有奇数颗白豆
    lastBean(bean2, bean3);
    lastBean(bean1, bean4);//开始时有偶数颗白豆
    lastBean(bean2, bean4);
    system("pause");
    return 0;
}

运行结果:(0->黑，1->白)

1.3随机数问题

因为要随机选择两颗豆子，所以需要根据随机数范围生成一对不相等随机数。方法如下：

1. 对不同的n需生成不同的分布
2. 对同一个n(即同一分布)需生成新的随机数

最终编写的随机函数如下：

unsigned rand(int n){
    uniform_int_distribution<unsigned> u(0, n);
    static default_random_engine e;
    return u(e);
}

Explian:

unsigned rand(int n){
    uniform_int_distribution<unsigned> u(0, n);
    default_random_engine e;
    return u(e);
}

对于上述代码，随机数引擎e会生成一个随机序列(可能含有相同的数)，不断调用u(e)会生成一个[0,n]之间的随机数序列(可能含有相同的数，记为序列S)，问题是每次调用函数rand(n)都会返回S中的第一个数，这不是我们想要的，为此需在default_random_engine e 前加上static,这样e在函数rand(n)调用之间会保持状态，即调用rand(n)会依次返回S中的随机数。至此，条件2已得到满足。为满足条件1，uniform_int_distribution<unsigned> u(0,n) 前不加static即可。有时两个地方均要加static(见C++ Primer中文版P662)。

这样做并不能保证对于同一个n生成的一对随机数不相等，编写如下代码解决：

i = rand(bean.size() - 1);
j = rand(bean.size() - 1);
while (j == i){
    j = rand(bean.size() - 1);
}