一个关于通信的例子 间题78 两台计算机采用通信方式协同计算一个函数： 为什么镜这个 Choicen:{0,1”×{1,2,,n}→{0,1} 随机算法代价 可证明”好 第一台计算机生成的报文， 第二台计算机的输入 发给第二台计算机 于任何”确 定算法？ Las Vegas One-Way Protocol (DI,DII) Input:(x,j),x=x1.xn∈{0,1}n,j∈{1，，n}. Step 1:DI chooses a random bit r∈{0，l. Step 2:DI sends the message cic2...cn/2+1=01...n/1/2+1 if r=0,and DI sends the message cic2...cn/2+1=n/1..n1)n/2+1 if r=1. Step3:lfr=0andj∈{1,2，.，n/2}then DI outputs cj+1=xj If r 1 and je [n/2+1,...,n}then DIl outputs cj-n/2+1= i =Choice(x,j). Else,DII outputs“?