美团笔试题
博客专区 > SibylY 的博客 > 博客详情
美团笔试题
SibylY 发表于4年前
美团笔试题
  • 发表于 4年前
  • 阅读 58
  • 收藏 0
  • 点赞 0
  • 评论 0

腾讯云 新注册用户 域名抢购1元起>>>   

已有一个随机数发生器,生成0的概率为p,生成1的概率为1-p,求如何利用这个随机数发生器制作一个生成1~n的概率都是 1/n 的发生器

制作 1 2 发生概率都是 1 / 2 的发生器,连续发生2次,则发生00,11的概率为p*p,(1-p)(1-p),发生10,01的概率都为p(1-p),在发生10时返回1,发生01时返回2,则发生1,2的概率相等

制作 1 2 3 发生概率都是 1 / 3的发生器,连续发生3次,则发生001,010,100的概率都为p*p*(1-P),或者是110,101,011概率都为p*(1-p)*(1-p),则用001,010,100分别对应1,2,3返回,即可使得发生1,2,3的概率都为1/3

字符串ABCD,可以由字符串BCDA或者CDAB通过循环移位而得到

考虑一下数组A中元素123456循环右移2位到底是怎么个情况!!!可不可以这样实现呢?将数组A分成两个部分:A[0~n-k-1] 和 A[n-k~n-1] ,将这两个部分分别翻转,然后放在一起在翻转(逆序)。具体是这样的:

(1)翻转1234:123456 ---> 432156

(2)翻转56:     432156 ---> 432165

(3)翻转432165:432165 ---> 561234



//逆序
 2 void Reverse(int A[],int b,int e)
 3 {
 4     for(;b < e;b++,e--)
 5     {
 6         int temp = A[b];
 7         A[b] = A[e];
 8         A[e] = temp;
 9     }
10 }
11 //循环右移
12 void RightShift(int A[],int,int n,int k)
13 {
14     Reverse(A,0,n-k-1);
15     Reverse(A,n-k,n-1);
16     Reverse(A,0,n-1);
17 }
复制代码
细心的读者可能就发现,这里的右移并没有说小于n呀,那么一个k>n那就会出现问题,经过简单的分析,我们发现如果A[]={1,2,3,4,5,6},数组长度是6,那么循环右移7位和循环右移1位是一样的,所以只需要把函数RightShift()中的k取值为k=k%n。如此一来问题就解决了。


【列方程】有四个足球队A,B,C,D分入同一个小组进行单循环比赛,争夺出线权,比赛规定:胜一场得3分,平一场得1分,负一场得0分,小组中名列第一的出现。小组赛结束后,如果A队积分为7分。讨论:①这一小组中共进行多少场比赛?②A队的成绩是几胜几平几负?③请你判断A队能否一定出线?
共有 人打赏支持
粉丝 29
博文 372
码字总数 312960
×
SibylY
如果觉得我的文章对您有用,请随意打赏。您的支持将鼓励我继续创作!
* 金额(元)
¥1 ¥5 ¥10 ¥20 其他金额
打赏人
留言
* 支付类型
微信扫码支付
打赏金额:
已支付成功
打赏金额: