玖富娱乐平台全网唯一指定1956注册开户网站

条记-数学希冀_玖富娱乐主管发布

日期:2019-01-04 浏览:
玖富娱乐是一家为代理招商,直属主管信息发布为主的资讯网站,同时也兼顾玖富娱乐代理注册登录地址。

希冀真是个很奇异的器械啊,虽然应用方程移项能够证实,但总觉得很妙

界说

设数(x)(n)种取值,每种取值(a_i)对应几率为(p_i),则(x)的数学希冀为(E(x)=sum a_ip_i)

  • 好比说扔掷一枚硬币,界说正面为(1),不和为(0),则抛一枚硬币的希冀为(E(x)=0.5times 1 0.5times 0=0.5)
  • 掷骰子的希冀为(frac 16times 1 frac 16times 2 cdots frac 16times 6=frac 16sum_{i=1}^6i=3.5)
  • 彩票一张(1)元,中奖几率为(frac 1{10^6}),奖金(10^5),则买一张彩票的收益希冀为(frac 1{10^6}times 10^5=0.1)

虽然这些希冀都是小数,是取不到的值,但希冀透露表现的并非一个能够发生的状况,而是状况的一个均匀,能够抽象地理解为当试验举行越来越多的时刻,均匀状况会趋于靠近希冀(好比掷骰子(100)次的时刻,均匀状况会靠近(3.5),而当掷(10^6)次的时刻,会越发靠近(3.5)

更一样平常的,若(x)的取值并非离散的,那末能够用积分表达希冀 换汤不换药

基本希冀

一枚硬币,抛到正面的几率为(p),问希冀抛频频取得一个正面

先设谜底为(x)次,依据希冀的界说能够列出式子(x=pcdot 1 (1-p)(x 1)),能够移项得出(x=frac 1p)

解释一下谁人式子的右侧,斟酌掷一次有两种状况:

  • (p)的几率为正面,这个时刻只须要一次操纵(即以后此次),取值(1),几率(p),以是第一项为(pcdot 1)
  • (1-p)的几率为不和,由于抛到不和即返回末了的状况,以是还须要抛(x)次,加上这一次,取值(x 1),几率(1-p),以是第二项为((1-p)(x 1))

列出这个方程能够解出个中某一项,能够这就是希冀问题的大抵弄法吧

给定一个有(n)个面的骰子,问希冀多少次能掷出一切面(SPOJ-FAVDICE)

发明这题不克不及像上一题那样只设一个变量,以是须要应用dp头脑,设(f_i)透露表现还剩(i)面未被掷到时希冀还需多少次完成

应用上一题的头脑罗列一切后继状况,假定以后还剩(i)面未被掷到

  • 这一次掷到了还未被掷到的面,几率为(frac in),剩余次数为(f_{i-1} 1)
  • 这一次掷到了已被掷到的面,几率为(frac {n-i}n),剩余次数为(f_i)

而这两个之和为(f_i),即(f_i=frac in(f_{i-1} 1) frac {n-i}n(f_i 1)),移项可得(f_i=f_{i-1} frac ni)

(f_0=0),则递推出(f_n)即为谜底

从这题能够看出一种解题要领,设置状况,列出方程,解出个中某一项,举行dp转移

你有一个战斗力(v),有(n)扇门,天天随机抽取一扇门(i),若(vleq c_i),则会用(t_i)天的时候脱离,不然(v)增添(c_i),求脱离天数的希冀(ZOJ-3640)

这题也差不多,算是一个小演习,设(f_i)透露表现当战斗力为(i)时脱离的希冀天数

(ileq c_i)(f_i =frac 1nf_{i c_i}),不然(f_i =frac 1nt_i)

综合这末了这两题能够看出,若是用Dp解简朴的希冀题,状况的设置须要满足可反复应用(好比当战斗力为一个确值(x)时,希冀天数一定是个定值)

double f(int x){
    if(x>max_c)return sum_t/n;
    if(dp[x]>-0.5)return dp[x];
    double res=0;
    for(int i=1;i<=n;  i)
        if(x<=c[i])res =1 f(x c[i]);
        else res =t[i];
    return dp[x]=res/n;
}

轮回转移

有些问题是没有像上面问题那样的单项转移的,好比说下面这题

一个(n)(m)边无向连通图,在图上举行随机游走,初始时在(1)号极点,每一步以相称的几率随机挑选以后极点的某条边,沿着这条边走到下一个极点,取得即是这条边的编号的分数。当抵达(n)号极点时游走完毕,总分为一切取得的分数之和。 请求对一切边举行编号((1)~(m)),使得总分的希冀值最小。(HNOI-2013游走)

很明显的贪婪思绪:求每条边的接见次数希冀,依照希冀巨细序次给定边权,再给边权赋值

然则求边的希冀又能够由边双方的点的希冀取得,以是这题的重要难度在于求每一个点的接见次数希冀

-玖富娱乐是一家为代理招商,直属主管信息发布为主的资讯网站,同时也兼顾玖富娱乐代理注册登录地址。-

用之前的要领举行设置。设(f_i)透露表现走到(i)节点的次数希冀

由于恣意两点间都有能够相互接见,以是关于恣意一条边((u,v))(f_u =frac 1{deg_v}f_v,f_v =frac 1{deg_u}f_u)

发明这里不克不及像之前几道题来解方程了,由于这里存在轮回((f_1)要用(f_2)推导,(f_2)要用(f_1)推导)

能够应用高斯消元求解,时候复杂度(O(n^3))

相似的题另有许多,好比HNOI-2011XOR和途径

轮回转移的非高斯消元解法

下面引见两种轮回转移的非高斯消元解法(复杂度(O(n))

线性状况

有三个骰子,离别有(k_1,k_2,k_3)面,每次同时扔掷得(x_1,x_2,x_3),分数增添(x_1 x_2 x_3),若三者的值离别为(a,b,c),则分数清零,若分数大于(n),则完毕操纵。求希冀多少次扔掷后完毕操纵(zoj-3329)

实验用上一题的做法来解,设(f_i)透露表现以后分数为(i)时的希冀还要举行多少次,令(p_k)透露表现三个骰子分数和为(k)的几率

则能够列出方程:(f_i=sum_kp_k(f_{i k} 1))

(1)提出来,把(p_0)零丁提出来,取得(f_i=1 f_0p_0 sum_{knot =0}p_kf_{i k})

舍弃之前说的高斯消元做法,引见一种更优异的做法

由于一切式子都要用到(p_0),以是无妨假定(f_i=a_ip_0 b_i)

然后将(f_{i k}=a_{i k}p_0 b_{i k})套到之前的式子里去,取得

(f_i=1 f_0p_0 sum_{knot =0}p_k(a_{i k}f_0 b_{i k})\=(p_0 sum_{knot =0}p_ka_{i k})f_0 sum_{knot =0}p_kb_{i k} 1)

对照式子:(f_i=a_ip_0 b_i),发明两个式子构造雷同,可得:

(a_i=p_0 sum_{knot =0}p_ka_{i k}\b_i=1 sum_{knot =0}p_kb_{i k})

由于(a_i,b_i=0(i>n)),而上面的式子中一切量是能够递推而得,没有轮回转移干系的,以是能够递推取得(a_0,b_0)

(i=0)代入,取得(f_0=a_0f_0 b_0),即(f_0=frac {b_0}{1-a_0}),得解

树上状况

一棵 (n) 个结点的树,从点 (x) 动身,每次等几率随机挑选一条与地点点相邻的边走曩昔。(Q) 次讯问,每次讯问给定一个鸠合 (S),求若是从 (x) 动身一向随机游走,直到点集 (S) 中一切点都最少经由一次的话,希冀游走几步。(pkuwc2018随机游走)

这题之前就写过题解,在这,能够看看中央如何将树上状况的轮回转移优化成递推

基本思绪也是设每一个节点从父亲转移,递推求得系数(a_i,b_i),如许是(O(n))

分层图状况&一样平常图状况

这个待填坑吧,分层图彷佛能够玩,据说客岁pkuwc上有人想出了一个在一样平常图上高斯消元的高效算法

-玖富娱乐是一家为代理招商,直属主管信息发布为主的资讯网站,同时也兼顾玖富娱乐代理注册登录地址。


平台知识

联系方式丨CONTACT

  • 全国热线:7711177
  • 传真热线:010-88888888
  • Q Q咨询:7711177
  • 企业邮箱:
首页
电话
短信