Seven machines send information to each other.As long as the number sent is within 2.0 of the correct number,the answer is correct.Two of the machines are faulty.Find the number that each machine would compute it it use:
Sender | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
Receiver | OK | OK | OK | OK | OK | Faulty | Faulty |
1 | 3 | 1.1 | 2.5 | 4.7 | 1.4 | 4.5 | 4.8 |
2 | 3 | 1.1 | 2.5 | 4.7 | 1.4 | 5 | 5 |
3 | 3 | 1.1 | 2.5 | 4.7 | 1.4 | 4.9 | 5 |
4 | 3 | 1.1 | 2.5 | 4.7 | 1.4 | 1 | 0.9 |
5 | 3 | 1.1 | 2.5 | 4.7 | 1.4 | 5 | 4.7 |
6 | 3 | 1.1 | 2.5 | 4.7 | 1.4 | 1.2 | 1 |
7 | 3 | 1.1 | 2.5 | 4.7 | 1.4 | 5.1 | 5.1 |
Dolev算法:
算法步骤:
1.去除每个PE所收到的信号的t=2个最大值,和t=2个最小值;(此处t为允许出错的最大PE数,t=(N-1)/3)
2.对每个PE保留的其余值求均值;
3.将每个PE得到的均值作为该PE的新信号发给其他PE,但6#、7#PE因故障仍然按最初的情形将信号发给其他PE。
4.再从第1步开始新的迭代,当各PE的均值收敛时,停止迭代。
Mathematica程序:
r={ {3,1.1,2.5,4.7,1.4,4.5,4.8},{3,1.1,2.5,4.7,1.4,5,5},{3,1.1,2.5,4.7,1.4,4.9,5},{3,1.1,2.5,4.7,1.4,1,0.9},{3,1.1,2.5,4.7,1.4,5,4.7},{3,1.1,2.5,4.7,1.4,1.2,1},{3,1.1,2.5,4.7,1.4,5.1,5.1}}; d=Length[r];n=IntegerPart[(d-1)/3];f[list_]:=TrimmedMean[Transpose[list],n/d];a=NestWhileList[(r[[All,1;;(d-n)]] = Drop[#,-n];f@r)&,f@r,Mean[Abs[#2-#1]]>=0.01&,2];a//LastListLinePlot[a,AxesOrigin->{1,1.5}]ClearAll[r,d,f,a]
运行结果:
{3.4, 3.4, 3.4, 3.39259, 3.4, 3.39259, 3.4}
FCA算法:
算法步骤:
1.找出各PE每一个收到的值在其±2.0范围内与之相交的该PE收到的其他值的个数。
此处采取如下办法:
设某个PE从第i个PE和第j个PE接收到的值分别为a±2.0和b±2.0,则这两个值域相交的条件为
若a>b时,须a-2.0<b+2.0 即a-b<4.0;
同理,a<b时,须b-a<4.0;
即只要|a-b|<4.0,则这两个值域必相交。
2.判断各PE值是否可接受。若与该值相交的值域个数大于等于4个(N-t-1),则该值是可接受的;
3.对每个PE的可接受值求均值,并以该均值替代该PE不可接受的值;
4.对每个PE求均值,并作为该PE的新信号发给其他PE,但6#、7#PE因故障仍然按最初的情形将信号发给其他PE。
5.再从第1步开始新的迭代,当各PE的均值收敛时,停止迭代。
Mathematica程序:
Clear["Golbal`*"];r={ {3,1.1,2.5,4.7,1.4,4.5,4.8},{3,1.1,2.5,4.7,1.4,5,5},{3,1.1,2.5,4.7,1.4,4.9,5},{3,1.1,2.5,4.7,1.4,1,0.9},{3,1.1,2.5,4.7,1.4,5,4.7},{3,1.1,2.5,4.7,1.4,1.2,1},{3,1.1,2.5,4.7,1.4,5.1,5.1}}; d=Length[r];n=IntegerPart[(d-1)/3];f[list_] := Mean@Select[list,Tr[UnitBox[(list-#)/8.0]]>4&];a=NestWhileList[(r[[All,1;; d-n]]=Drop[#,-n];f/@r)&,f/@r,Mean[Abs[#2-#1]]>=0.01 &,2][[2 ;; -2]];a//LastListLinePlot[a, AxesOrigin -> {1, 2}]Clear[r, d, n, f, a]
运行结果:
{4.21569, 4.31569, 4.30141, 3.15855, 4.27284, 3.20141, 4.34427}
(未完待续)
两个算法是有很大差异的,具体大家自己体悟吧。
感谢Mathematica吧的无影冬瓜等网友对程序提出的指导和改进意见。
写这篇文也是为了让大家跟我一起学习和了解Mathematica的Powerful Ability。
真心希望Mathematica这个强大的软件不要在中国蒙尘!