一道关于自由算法的面试题(转)

每首歌曲播放的概率应该正比于它的评分,每首歌曲都是一个评分,每首歌曲播放的概率应该正比于它的评分,每首歌曲都是一个评分,2、将播放历史的n首歌曲之前加上s首歌曲,以s首为区间,研究讨论了一些在笔试面试中常见的和随机函数以及概率相关的问题,但不仅仅限于随机取样问题

先把评分从小到大排序,之后把依据每首歌的评分,生成一个半闭开区间,然后生成三个随机数,看随机数落在哪些区间,就是选项的那首歌。比如,有三首歌,评分是[1,2,3]
那么相应是生成四个区间
[0-1,1-3,3-6],之后生成四个0-6里边的私行数,随机数落在哪个区间,就挑选相应的歌曲。思虑排序的功用,那是一个nLogn的算法。

ps:作者是回家路上才回想这种解法的,笔者和自个儿内人说,化学系完成学业的他向来就交付了不错的解法,哎,被数学学霸碾压的味道就是这么销魂。

  

可能率难点选编

1.(习题12.4)对于会集插入难点,每便发生随机数后都亟需在联谊中检查测试该因素是或不是业已存在,那些测验次数和调用随机数函数的次数一样。对于从n个元素中选取m个成分的难题,平均要求测量检验多少次手艺保障选拔了m个成分?

此处先管理极度的题目,即“赠券搜集难题”:必需搜罗多少张棒球员卡才具保证全体有着的n种卡?

记Pi为从收集了i-1种到i种的概率,Pi=(n-i+1)/n

此时亟需收罗的卡牌数目ni = 1*
Pi + 2*(1-Pi)*Pi +
3*(1-Pi)2*Pi\ +
+ n\*(1-Pi)n*Pi\ +\ …,这几个无穷级数能够求解为ni=1/Pi

那正是说所急需总的卡片数目sum(ni)
 = n1+n2 +… +nn约为nlnn + γn +
O(1)。连锁维基百科

对此从n个成分中挑选m个,相应地sum(ni)
 = n1+n2 +…
+nm,约为nlnm+γn。(依据调和数的推理)

 

2.(习题12.11)各类游戏用户有一张带有十六个覆盖点的卡牌,覆盖点上面遮掩着1~16的自由排列。游戏发烧友每便刮开二个点,假设出现3,则判游戏用户负;假若出现1或2,则判游戏者胜。那么,随机挑选覆盖点刮开,获胜的概率是稍稍?

解答:

骨子里胜负只对应三种排列:1和2都冒出在3前则胜,不然负。前面一个的即*1*2*3*或*2*1*3*,后面一个为任何两种排列。明显获胜的可能率为2/3。

毫不把标题复杂化,应该尽量简化。4~16的数字都是未曾用的。

不过,那些算法是有漏洞的,未有设想到评分重复的气象,若是三首歌的评分是[1,2,2],那么应该是生成四个区间[0-1,1-5],
假如落在其次个区间,还亟需从两首评分为2的歌曲里面随机选出一首来。那样的话,达成起来就一定复杂了。

立异:深夜和V站的V友探讨之后,发掘面试官说的那种映射是能够完成的,比如有三首歌,评分是[1,2,3]那就是说区间段是[0-1,2-4,4-6]本条时候,只必要存三个数组[1,4,6],之后用2分查找就能够得出精确的下结论了,当然还需求思索评分重复的状态。

  • i和200001 + i。

抽样难点:从一窍不通总的数量的因素中选取二个

  从事先未知总量为n的指标中随机选拔二个的方法。有二种普及的有血有肉难题:

  1.读取一个不明不白行数的文本,随机输出当中的的一行,同有的时候候最两只好缓冲一行的剧情(《编制程序珠玑(续)》习题15.3运用了这种情势);

  2.对链表进行一趟遍历,随机输出当中的二个结点的要素,只好选拔叁个一时指针。

  解法是,以可能率1选项第一个要素存入缓存,以可能率51%用第二个要素交替掉缓存,…,直至遍历完全体因素,最终输出缓存的内容。能够深入分析出此时具有因素留在缓存的概率均为1/n,譬喻1,是1*(1/2)*(2/3)*…*((n-1)/n)。

int random_select(void)
{
    int i,num=1;
    for(i=1;i<n;i++)
    //i<n代表某种终止条件,n未知    
        if(rand()%i ==0)
            num = i;
    return num;
}

   对于那个主题素材的常见应用:马尔科夫文本生成器里挑选哈希表中某项对应链表的人身自由三个结点。

 


 

count = Map(2 -> 477, 1 -> 4312, 3 -> 970, 0 -> 4241)

可是,这几个算法是有尾巴的,未有思念到评分重复的状态,假设三首歌的评分是[1,2,2],那么相应是生成三个区间[0-1,1-5],
假如落在其次个区间,还索要从两首评分为2的歌曲里面随机选出一首来。那样的话,达成起来就一定复杂了。

题意:已知歌单中的歌曲数目s,和部分的播报历史,问下一首大概播放的歌曲种数。

    1.对C语言中或别的语言中等价的rand()、srand()有所领悟。本文不琢磨种子的设定和伪随机数的难点;

最终,固然照上面那样思量,就总体了,不过贯彻起来的话,会意识,未有很好的数据结构能判断哪些随机数是落在哪些区间的,除非遍历全数的间距。

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cctype>
#include<cmath>
#include<iostream>
#include<sstream>
#include<iterator>
#include<algorithm>
#include<string>
#include<vector>
#include<set>
#include<map>
#include<stack>
#include<deque>
#include<queue>
#include<list>
#define lowbit(x) (x & (-x))
const double eps = 1e-8;
inline int dcmp(double a, double b){
    if(fabs(a - b) < eps) return 0;
    return a > b ? 1 : -1;
}
typedef long long LL;
typedef unsigned long long ULL;
const int INT_INF = 0x3f3f3f3f;
const int INT_M_INF = 0x7f7f7f7f;
const LL LL_INF = 0x3f3f3f3f3f3f3f3f;
const LL LL_M_INF = 0x7f7f7f7f7f7f7f7f;
const int dr[] = {0, 0, -1, 1, -1, -1, 1, 1};
const int dc[] = {-1, 1, 0, 0, -1, 1, -1, 1};
const int MOD = 1e9 + 7;
const double pi = acos(-1.0);
const int MAXN = 300000 + 10;
const int MAXT = 10000 + 10;
using namespace std;
int a[MAXN];
map<int, int> mp;
bool ans[MAXN];
int s, n;
int solve(){
    int sum = 0;
    for(int i = 1; i < n + s; ++i){
        int et = s + i - 1;
        if(--mp[a[i - 1]] == 1) --sum;
        if(++mp[a[et]] == 2) ++sum;
        if(sum != 0) ans[i % s] = false;
    }
    int cnt = 0;
    for(int i = 0; i < s; ++i){
        if(ans[i]){
            ++cnt;
        }
    }
    return cnt;
}
int main(){
    int T;
    scanf("%d", &T);
    while(T--){
        mp.clear();
        memset(a, 0, sizeof a);
        memset(ans, true, sizeof ans);
        scanf("%d%d", &s, &n);
        for(int i = 0; i < s; ++i){
            a[i] = 100001 + i;
            ++mp[a[i]];
        }
        for(int i = 0; i < n; ++i){
            scanf("%d", &a[i + s]);
        }
        for(int i = 0; i < s; ++i){
            a[s + n + i] = 200001 + i;
        }
        printf("%d\n", solve());
    }
    return 0;
}
  •  利用任性数函数生成随机数
  •  动用自由数函数产生随机事件
  •  抽样难题:从n个元素中甄选m个
    • 从概率角度出发
    • 从集结插入出发
    • 从“打乱顺序”出发
    • 从一般到特别
  • 抽样难题:从一窍不通总量的因素中甄选三个
  • 可能率难题选编

ps:作者是回家路上才想起这种解法的,笔者和本人太太说,化学系结业的他一向就付给了不利的解法,哎,被数学学霸碾压的味道正是那样销魂。

分析:

  目录

结果

图片 1

4、判别距离里歌曲独一的措施,记录每首歌出现次数,步向区间则加1,离开区间则减1,若区间长为s,里面每首歌都出现过1次,则此时sum一定为0,区间内是一种有效的播音顺序。

    2.中学或上述水平的可能率基本概念。