十进制转26进制 && 生成等概率事件

下午面试了依图科技，感觉最后一个题目没有发挥好，辜负了面试老师百般引导

1 十进制转26进制

最开始，没有处理好进位的问题，对于非26的整数倍，都是可以打印出来的，然后如果是26的整数倍，那么就会有问题；

void Dto26(const int& aa){
   
    int a=aa;
    stack<int> ret;
    while(a){
   
        int c=a%26;
        ret.push(c);
        a/=26;
    }
    while(!ret.empty()){
   
       cout<<(char)('a'+ret.top()-1);
        ret.pop();
    }
}

52 的时候，结果应该为az; 后面一直在考虑这个进位的问题，企图通过flag来消除这个进位；但是发现了更好的一种写法；

void Dto26V2(const int& aa){
   
    int a=aa;
    stack<int> ret;
    while(a){
   
        int c=a%26;
        if(c==0) c=26;
        ret.push(c);
        //a/=26;
        a=(a-c)/26;
    }
    while(!ret.empty()){
   
       cout<<(char)('a'+ret.top()-1);
        ret.pop();
    }
}

这个版本，如果求余等于0，直接将其赋值为26，紧接着，a=(a-c)/26,这样就将进位消除了；

完整代码

#include<iostream>
#include<stack>
#include<string>
using namespace std;

void Dto26(const int& aa){
   
    int a=aa;
    stack<int> ret;
    while(a){
   
        int c=a%26;
        ret.push(c);
        a/=26;
    }
    while(!ret.empty()){
   
       cout<<(char)('a'+ret.top()-1);
        ret.pop();
    }
}

void Dto26V2(const int& aa){
   
    int a=aa;
    stack<int> ret;
    while(a){
   
        int c=a%26;
        if(c==0) c=26;
        ret.push(c);
        //a/=26;
        a=(a-c)/26;
    }
    while(!ret.empty()){
   
       cout<<(char)('a'+ret.top()-1);
        ret.pop();
    }
}

int main(){
   
    // D2H(16);
    cout<<"Dto26"<<endl;
    Dto26(52);
    cout<<endl<<"Dto26V2"<<endl;
    Dto26V2(52);
    return 0;
}

2 生成等概率事件

假设函数int func()，以概率p输出0，以概率（1-p）输出1；那么如何通过编程，可以使其以1/2概率输出1，以1/2概率输出0？

我以为是需要通过期望，最终得到1和0，然后概率正好为1/2；后来老师提示，如果你两次调用这个函数，那么可能的结果是什么样的，以及他们的概率；核心就是得到两个等概率事件；

两次调用输出值	概率
00	p^2
01	p(1-p)
10	(1-p)p
11	(1-p)^2

虽然给了这些提示给我，但是我还是在纠结00和11的情况；其实，把这两种情况省略掉就可以了，反映在程序上面，就是如果是这两种组合，程序就continue；

int Rand()
{
   
    int i1 = rand();
    int i2 = rand();
    if(i1==0 && i2==1)
        return 1;
    else if(i1==1 && i2==0)
        return 0;
    else
        return Rand();
    return -1;
}

更进一步，如何利用你的Rand()函数以1/n概率生成[1,2,3…n]
相当于等概率生成1到n之间的数字；
由于Rand()生成0和1的概率相等，所以，如果我循环调用Rand()m次，得到的数字排列组合是一个m位的二进制数，并且概率相等；从这个角度出发，我们可以首先计算出n的位数k，然后调用Rand()函数k次，这样就是等概率的出现1,2,3…n；

其实这个地方，自己也有点纠结，出现某一个特定数字的概率应该是(1/2)^k?

int newRand()
{
   
    int result = 0;
    for(int i = 0 ; i < k ; ++i)
    {
   
        if(Rand() == 1)
            result |= (1<<i);
    } //每次一定会出现一个数字，他们是等概率的，所以最终都是1/n的概率
    if(result > n) //因为是算出n的二进制位数，所以存在着超过n的情况
        return newRand()    
    return result;
}