1、會計學1算法合集之淺析競賽中一類數(shù)學期望問算法合集之淺析競賽中一類數(shù)學期望問題的解決方法題的解決方法iiixXYExXPXYEEYE)|()()|()(E(Y | X = 1)=4E(Y | X = 2)=3P(X = 2)=0.4P(X = 1)=0.6E(Y)=0.43 + 0.64 = 3.6第2頁/共30頁第3頁/共30頁第4頁/共30頁123410.50.51第5頁/共30頁123410.50.51第6頁/共30頁123410.50.51EkiijkkijiWFPF),(1,第7頁/共30頁EkiijkkijiWFPF),(1,123410.50.51第8頁/共30頁iiWF0,Ek

2、iijkkijiWFPF),(1,123410.50.51第9頁/共30頁iiWF0,EkiijkkijiWFPF),(1,若Fi,j當 j時收斂，設收斂于Fi那么答案即為Fs。123410.50.51第10頁/共30頁EkiijkkijiWFPF),(1,123410.50.51第11頁/共30頁EkiijkkijiWFPF),(1,015 . 05 . 01144133221FFFFFFFF123410.50.51第12頁/共30頁EkiijkkijiWFPF),(1,1-100101-101-0.501-0.5100010123410.50.51第13頁/共30頁EjijijjiiWFP

3、F),(,)(第14頁/共30頁)(,kjiP問題描述問題描述第15頁/共30頁11,)4(, 1)3(,1,)2(, 1)1 (,jijijijijijijijijiEPEPEPEPEm, n 40Accept?時間復雜度O(m3n3)Time limit exceeded 分析分析第16頁/共30頁方程未知量 第i行第j列的格子表示了方程：11,)4(, 1)3(,1,)2(, 1)1(,jijijijijijijijijiEPEPEPEPE優(yōu)化優(yōu)化第17頁/共30頁方程未知量 第i行第j列的格子表示了未知量：jiE,優(yōu)化優(yōu)化第18頁/共30頁123方程未知量優(yōu)化優(yōu)化第19頁/共30頁方程未知量Ex, yyyxx優(yōu)化優(yōu)化第20頁/共30頁方程未知量yyxx優(yōu)化優(yōu)化Ex, y第21頁/共30頁方程未知量11,)4(, 1)3(,1,)2(, 1)1(,jijijijijijijijijiEPEPEPEPEyyxx優(yōu)化優(yōu)化Ex, y第22頁/共30頁方程未知量yyxx優(yōu)化優(yōu)化Ex, y第23頁/共30頁方程未知量yyxx優(yōu)化優(yōu)化Ex, y第24頁/共30頁方程未知量xxyy時空復雜度時空復雜度Ex, y第25頁/共30頁期望模型有限遞推無限遞推有環(huán)有環(huán)無環(huán)無環(huán)方程組高斯消元近似解，效率低精確解，效率高第26頁/共30頁期望模型具體問題對應對應第27頁/共30頁