問題 0と1をそれぞれ確率1/2で出力する問題を考える。利用できるのは0か1かを出力する手続きBIASED-RANDOMである。BIASED-RANDOMは1を確率p、0を確率1-pで出力する(0 やっぱり実装まで。期待実行時間は出していない。あと証明もまだ(これはたぶんすぐできる)…

問題： RANDOM(0,1) に対する呼び出しだけを用いて手続き RANDOM(a,b) を実現せよ。実現された手続きの平均実行時間を a と b の関数として表現せよ。 RANDOM(a,b) とは、a とりあえず実装まで。発想： RANDOM(a,b)を実現するのはRANDOM(0,n)を実現するのと…