ユニファ開発者ブログスマートフォン用の表示で見るユニファ開発者ブログユニファ株式会社システム開発部メンバーによるブログです。2018-10-11練習問題こんにちは、ヘルスケア事業部のちょうです。Programming」という本をひたすら読んでいます。この本はコンピューターサイエンス修士の教科書として使われるらしく、宿題も付いています。第一章の練習問題の中で、一問を選び、みなさんと一緒に検討しようと思います。第一章なので、何を前提に学ばないと解けない程度ではなく、かつ選んだ一問は並列処理に詳しくなくても問題ないのでご安心ください。thing.訳して君は最近逮捕されたP人の囚人の一人です。看守長は危険なコンピューター科学者でこのようなアナウンスをしました。今日で君はほかの囚人と会い、策を考える。今日以降君が隔離された監房に居て他の囚人とコミニュケーションできない。私は一つのスイッチルームを準備した。ルームの中ではライトのスイッチがあります。そのスイッチはONかOFFかの状態です。スイッチは何とも繋がってないです。時々私はランダムで一人の囚人を選び、スイッチルームに入らせる。囚人はスイッチを入れる(もしくはOFFにする)か、スイッチをそのままにしてルームから去る。(選べられた囚人)以外の人はこのルームは入れない。囚人の一人一人は何回でもルームを訪ねる。精確にいえば、どんなNでも、最終的に君らの一人一人はすくなくともN回以上訪ねる。いつでも、君らの一人はこんな宣言をできる。「私達は全員一人一人すくなくとも1回以上スイッチルームを訪ねた」。その宣言は正しければ、私はあなたを自由にする。なければ、あなたをワニの餌とする。ON:書き込み何回でも訪ねる:何回でも参照できるになりますが、これら知らなくても問題ないです。ヒントからそれぞれ同じことをやる必要がないから、すくなくとも二種類にあることがわかりました。すべての囚人がルームを訪ねたというのを証明できる方法の中で、一番簡単なのは、カウンターです。P人がいるので、P人が数えたということです。この2つ合わせて、P人の中で一人はカウンター役ほかの人は数字を増やすになります。スイッチなので、数字を増やせないです。Pは偶数か奇数によって、スイッチの状態を確認すれば?残念ですが、カウンター役の前に何人が訪ねたのがわからないです、間違って宣言する可能性があります。Pは偶数として、最初スイッチの状態はOFF。カウンター役以外の人はスイッチを切り替える。するとカウンター役の前に1人、3人がルームを訪ねた状態は区別がつかないです(共にONになる)。とうすればいいですか。ここのポイントは多分スイッチの状態ではなく、スイッチは何回状態を変えたことです。言い換えれば、ONになった回数です。具体的にカウンター役の人は、スイッチがONだと、OFFにします。ほかの人はOFFだと、ONにして、ONだと、何もしない。重複計算しないように、ほかの人は最初の一回だけ、OFFからONにします。このあと、OFFだろうか、ONだろうか、何もしません。1になったら宣言します。1の理由はカウンター役自身はカウンターに入りません。1になると宣言するほかの人、最初の一回だけ、OFFだと、ONにするもちろん、この策は最初からスイッチの状態を知る必要があります。1になる時点で宣言できます。最初スイッチがONだと、正しいカウンターはPになるのです。問2はこの方法では解決できません。1になった時点で宣言できますが、最初の状態はわかりません。分かってもカウンター役と通信できないし、ルームに入る順番も決められません。すればいいでしょうか。自分がここで詰まったので、解答を見てしまったんです。2になると宣言するほかの人、最初の二回だけ、OFFだと、ONにする単なる問1の解答を2倍にするだけではないか。思ったら、最初スイッチがONとOFFのケースを別々考えましょう。最初OFFだと、2回カウンターだけです。