如何匹配两个函数，使得得分最高
由\(M\)个函数\(f_i(x)\)构成集合\(F=\{f_i(x)|i=1\space to\space M\}\)，其中\(f_i(x)\)的定义域都为\(X=\{i|i=1\space to\space K\}\)，值域都为\(Y=\{i|i=1\space to\space L\}\)。
\(M,K,L\)有限，且为正整数。
现在，
随机生成在\(1\)到\(M\)之间均匀分布的一个整数\(i\)，从F中选择函数\(f_i(x)\),
随机生成在\(1\)到\(K\)之间均匀分布的一个整数\(n\),
令\(j=1\space to \space n\),对每个\(j\)
随机生成在\(1\)到\(K\)之间均匀分布的一个整数\(k\),
随机生成在\(1\)到\(L\)之间均匀分布的一个整数\(l\),
用整数\(l\)替换\(f_i(k)\)的值。
循环完毕，得到\(f_i(x)\)的值被替换后的函数\(g(x)\)。
___________________________________________________________________
若只有\(F,X,Y\)对应的数据，和\(g\)的输入与输出的对应关系，
如何回答\(g\)是由哪个\(f_i\)生成的？
答案可以是：
不确定，得\(a\)分
确定并且指出\(f_i(x)\)是\(F\)的第几个元素，得\(b=1\)分
错误答案，得\( 0 \)分
其中\( 0 \le a \le b = 1 \)
以上的随机试验重复\(n\)次，当\(n \to \infty \),
如何回答，能使得得分率\(S=\dfrac{总得分}{n}\)最多？
若存在方案使得得分率\(S\)最大，那么该得分率\(S\)是多少？ 测试数据
M=32,K=8,L=2
a=0.5,b=1
F={{1,1,2,2,1,1,2,1},{2,1,2,1,2,1,2,2},{1,2,2,1,1,1,1,1},{2,2,2,2,2,1,2,1},{2,2,2,2,1,1,1,1},{2,1,1,2,2,1,1,1},{1,1,2,2,1,2,1,2},{1,2,1,1,1,1,1,1},{2,1,1,1,1,2,1,2},{1,1,2,2,1,2,2,1},{2,2,2,2,1,2,1,1},{2,2,1,1,2,2,1,1},{1,1,2,2,2,2,2,1},{2,1,1,1,1,1,2,2},{1,1,2,2,1,2,2,2},{1,2,1,1,2,2,2,2},{2,1,1,1,2,2,2,2},{2,2,2,2,2,2,2,1},{2,1,1,1,2,2,1,1},{1,2,2,2,2,2,2,1},{1,1,1,1,2,2,1,2},{1,2,2,2,1,1,1,2},{1,2,2,1,1,2,2,1},{2,1,2,1,1,2,2,2},{1,1,2,2,2,2,1,2},{1,1,2,1,2,2,2,1},{1,1,1,2,2,1,1,2},{2,2,1,2,1,1,1,1},{2,2,1,1,2,1,2,1},{1,2,2,2,1,1,2,2},{2,2,1,1,1,1,1,2},{1,2,2,2,1,1,2,2}}
策略总是按最小距离给出答案，不回答不确定
测试100000次，得到0.355546的得分率
这里正确率的误差要如何估计呢？
mathematica测试代码：
mM=32;kK=8;lL=2;
testcount=100000
correct=0
xX=Table
yY=Table
Table=Table,{j,1,kK}],{i,1,mM}]
For[n=1,n<=testcount,++n,
i=RandomInteger[{1,mM}];
ff=f;
nn=RandomInteger[{1,kK}];
For[j=1,j<=nn,++j,
k=RandomInteger[{1,kK}];
l=RandomInteger[{1,lL}];
ff[]]]=yY[];
];
match=Ordering-ff,1],{j,1,mM}],1];
If]==i,correct++];
];
N
页:
[1]