病犬問題--仮説法の解

タイトル:
村には50人がいて、一人に犬がいます.この50匹の犬には病気の犬がいます(この病気は伝染しません).そこで人々は病気の犬を見つけなければなりません.誰もが他の49匹の犬を観察して、病気かどうかを判断することができます.(病気があれば必ず見える)と、自分の犬だけは見ることができない.観察した結果はコミュニケーションが取れず、病気の犬の飼い主に知らせることもできず、一日に一度しか見ることができない.飼い主が自分の家が病気の犬だと推測すると、自分の犬を銃殺する(発見後は1日以内に銃殺しなければならない)、しかも誰もが自分の犬を銃殺する権利しかなく、他の人の犬を殺す権利がない.初日はみんな見終わったが、銃は鳴らず、翌日も銃声が聞こえなかった.3日目になると銃声が聞こえて、村に病気の犬が何匹いるか聞いて、どうやって推定したのか.
 
 
=======================================
 1. 思考:最初の時間はまだ直接解く方法を考えていません.まず仮定法を採用し,処理を簡略化する.ふふ..偽の犬が1匹設置されていて、数日目に銃声がします.仮に2匹の犬が設置されていて、数日目に銃声がします. ... 2. この考え方に従う.情報を2つのクラスに抽象化します.村と犬を持つ村人.村人は犬を持っていて、犬の状態は可変ではありません.他人の犬を見る動作がある.キル自身の犬の動きがあります.また、自分の犬の状態を他の人に見せる動作も提供する必要があります.村落(村長に簡略化して動きを起こす...村長と村長の奇妙な合体...はははは、)村民が入居する動きがある.村長は村民を組織して犬を見る...村長は村民にしばらくの間、自分の家の犬を殺すために使う.
 3. まとめ:この解法によれば,利用できる技術は主に同時計算である.  1). すべての人とすべての人の動作は互いに独立していて、関連がなくて、完全に結合することができます.並行できます.  2). 1人1人が全ての犬(自分以外)を観察した上で判断し、殺すか殺さないかを決めることができる.3).毎日の出来事も並行して処理できる.しかし過大計算の問題が発生する.割り込みや取り消しの仕組みを増やす必要がある.第一時間はより良い解決策が思いつかなかった.へえ.思惟が短かったなぁ....
 
 
code:
 

import java.util.List;

/**
 * Created by zkai on 2015/1/21.
 */
public class PetOwner {
    private final boolean isSickDog;
    private boolean consideredOwnerSickDog;

    public PetOwner(boolean isSickDog) {
        this.isSickDog = isSickDog;
    }

    /**
     * @param day    
     * @return        
     */
    public boolean watchOtherDogAndThink(int day, List<PetOwner> petOwners) {
        int count = 0;
        for (PetOwner petOwner : petOwners) {
            if (petOwner != this && petOwner.dogStatus(this)) {
                count++;
            }
        }
        //        。day   count    。
        consideredOwnerSickDog = day - count == 1; //        ，      。
        return consideredOwnerSickDog;
    }

    /**
     *
     * @return          。true：  ，false：  
     */
    public boolean killMyselfDog() {
        if (consideredOwnerSickDog) {
            System.out.println("▄︻┳═          ~~~  ~~~");
        }
        return consideredOwnerSickDog;
    }

    /**
     *       ，      
     * @param watcher
     * @return
     */
    public boolean dogStatus(PetOwner watcher) {
        if (watcher == null || watcher == this) {
            throw new IllegalStateException("         ");
        }
        return isSickDog;
    }
}

 
 
 
 
 
 

package com.wyfbilling.common.logger.contract;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

/**
 * 
 *
 *
 * Created by zkai on 2015/1/21.
 */
public class Village {
    private final List<PetOwner> petOwners;

    /**
     *
     * @param petOwnerCount     
     * @param sickDogCount      
     */
    public Village(int petOwnerCount,int sickDogCount) {
        petOwners = Collections.unmodifiableList(init(petOwnerCount, sickDogCount));
    }

    /**
     *     
     * @param petOwnerCount     
     * @param sickDogCount      
     */
    private List<PetOwner> init(int petOwnerCount, int sickDogCount) {
        List<PetOwner> list = new ArrayList<>();
        for (int i = 0; i < petOwnerCount; i++) {
            PetOwner petOwner;
            if (i < sickDogCount) {
                //        
                petOwner = new PetOwner(true);
            } else {
                //         
                petOwner = new PetOwner(false);
            }
            list.add(petOwner);
        }
        return list;
    }

    /**
     *    ，             
     * @param day
     */
    public void watchDogAndThinkTime(int day) {
        for (PetOwner petOwner : petOwners) {
            petOwner.watchOtherDogAndThink(day, petOwners);
        }
    }

    /**
     *     。。。
     *
     * @return         true:      。
     */
    public int killDogTime() {
        int killDogEventCount = 0;
        for (PetOwner petOwner : petOwners) {
            if (petOwner.killMyselfDog())
                killDogEventCount++;
        }
        return killDogEventCount;
    }

    public static void main(String[] args) {
        Village village = new Village(50, 10);//        50   ， 3   。

        for (int day = 1; day < 10000; day++) {//      ，day    ，            。
            village.watchDogAndThinkTime(day);
            int killDogEventCount = village.killDogTime();
            if (killDogEventCount > 0) {
                System.out.format("    %d ,     %s     ！！！", day, killDogEventCount);
                break;
            }
        }
    }
}