C# アルゴリズムが張さんの誕生日問題を解決する

C# アルゴリズムは張さんの誕生日問題をどのように実装するのでしょうか?まず、張さんの誕生日に関する質問を見直してみましょう。

シャオミンとシャオチアンは二人とも張先生の生徒です。張先生の誕生日はM月N日です。二人とも張先生の誕生日が次の10日のうちの1日であることを知っています。張先生はシャオミンにMの値を、シャオチアンにNの値を教えました。張先生は二人に、自分の誕生日が何日か知っているか尋ねました。

3月4日 3月5日 3月8日

6月4日から6月7日まで

9月1日から9月5日まで

12月1日 12月2日 12月8日

シャオミンは言った: 私が知らないなら、シャオチアンも知らないはずです。

シャオチアンは言った：最初は知らなかったけど、今は分かっている

シャオミンは言った: ああ、それなら私も知っています。

上記の会話に基づいて、張先生の誕生日は何日か推測してください。 ?

この論理推論問題は皆さんも見たことがあると思います。正解は9月1日です。ここでは推論のプロセスについては触れません。Googleで検索すればたくさんの答えが見つかります。私が言いたいのは、この推論結果を得るためにC#をどのように使用するかということです^_^

張さんの誕生日問題を解く C# アルゴリズムの推論プロセスは次のとおりです。

1. すべての誕生日セットを分析します。月は {3,6,9,12}、日は {4,5,8,7,1,5,2} です。

2. シャオミンは言った。「私が知らないなら、シャオチアンもきっと知らないよ。」その日のセットでは、{2,7}は1回だけ登場します。 Xiao Mingはこう言うだろうから、Xiao Mingが得たMは{6,12}ではないと推測できる。なぜなら、XiaoqiangのN値が{2,7}であれば、張先生の誕生日を直接取得でき、XiaomingのM値は無意味になるからです。そして、シャオミンがこれを言った場合、それはシャオミンの手札のMが{6,12}ではないことを意味します。

3. シャオチアンは言いました。「最初は知らなかったけど、今は分かりました。」 M={6,12} を差し引いた後、残りの可能性は {{3,4},{3,5},{3,8},{9,1},{9,5}} です。Xiaoqiang はそれを知っていると言いました。Xiaoqiang は N しか知らず、張先生の誕生日も確信していたため、残りのセットでは彼の N 値が一意である必要があります。これにより、{{3,5},{9,5}} が除外されます。

4. シャオミンは言いました。「ああ、それなら私も知っています。」シャオミンのMは月で、残りのセットは{{3,4},{3,8},{9,1}}です。シャオミンのMが3の場合、選択できる日付は2つあり、誕生日を決定できません。シャオミンは張先生の誕生日を判断できるので、シャオミンの手にあるMは9です。

張先生の誕生日は9月1日です。

以下のコードもこの考え方に従って書かれています。

張さんの誕生日問題を解く C# アルゴリズムのデモコード

クラスプログラム
{ 
     // / <要約> 
     /// 小明と小強は二人とも張先生の生徒です。張先生の誕生日はN月M日です。  
     /// 二人とも、張さんの誕生日が次の10グループのうちの1つであることを知っています。  
     /// 張先生は、小明にMの値を伝え、小強にNの値を伝えました。  
     /// 張先生は生徒たちに、自分の誕生日がいつか知っているか尋ねました。  
     /// 3月4日 3月5日 3月8日 
     /// 6月4日 6月7日 
     /// 9月1日 9月5日 
     /// 12月1日 12月2日 12月8日 
     /// シャオミンは言った: 私が知らないなら、シャオチアンもきっと知らない 
     /// Xiaoqiangは言った: 以前は知らなかったが、今は知っている 
     /// シャオミンは言った: ああ、それなら私も知っています。  
     /// 上記の会話に基づいて、張先生の誕生日は何日か推測してください。 ?  
     ///  
     /// </要約>  
     /// <param name="args"></param>  
    静的  void Main(文字列[]引数)
    {
        Dictionary< int , int []> birthdays = new Dictionary< int , int []>();
        誕生日.Add(1,新しい 整数[]{3,4});
        誕生日.Add(2,新しい 整数[]{3,5});
        誕生日.Add(3,新しい 整数[]{3,8});
        誕生日.Add(4,新しい 整数[]{6,4});
        誕生日.追加(5,新しい 整数[]{6,7});
        誕生日.Add(6,新しい 整数[]{9,1});
        誕生日.Add(7,新しい 整数[]{9,5});
        誕生日.Add(8,新しい 整数[]{12,1});
        誕生日.Add(9,新しい 整数[]{12,2});
        誕生日.Add(10,新しい 整数[]{12,8}); 
    
        誕生日を分析します(誕生日); 
    
         if (誕生日.キー.カウント > 0)
        { 
             foreach (KeyValuePair< int , int []> 誕生日内の項目)
            {
                Console.WriteLine( "張さんの誕生日は{0}月{1}日と考えられます" , item.Value[0], item.Value[1]);
            }
        } 
        それ以外    
        {
            Console.WriteLine( "解決策はありません" );
        }
        コンソールの行を読み取ります。
    } 
    
    プライベート 静的  void AnalyseBirthday(Dictionary< int , int []> 誕生日)
    { 
         //days: N 個の値のコレクション、TKey: は N 個の値、TValue: は発生回数 
        Dictionary< int , int > days =新しいDictionary< int , int >(); 
         //months: N 個の値すべてのコレクション、TKey: M 値、TValue: 発生回数 
        Dictionary< int , int > months = new Dictionary< int , int >(); 
    
         //誕生日を走査し、それぞれ日と月に値を割り当てます 
         foreach (KeyValuePair< int , int []> 誕生日内の項目)
        { 
             days.ContainsKey(item.Value[1])の場合
                日数[item.Value[1]] += 1; 
            それ以外    
                days.Add(item.Value[1], 1); 
             (months.ContainsKey(item.Value[0]))の場合
                月[item.Value[0]] += 1; 
            それ以外    
                months.Add(item.Value[0], 1);
        } 
    
         //N 個の値を格納するための一時リスト tempDays を宣言します 
        リスト< int > tempDays =新しいリスト< int >(); 
         //M 値を格納するための一時リスト tempMonths を宣言します 
        リスト< int > tempMonths =新しいリスト< int >(); 
         //誕生日のTKey値を格納するための一時的なList:keysを宣言する 
        リスト< int > keys =新しいリスト< int >(); 
    
         //値 N が 1 回だけ出現する可能性のあるすべての誕生日を検索し、tempDays に保存します。  
         // 一意の N 値に対応する M 値を取得し、tempMonths に保存します。  
         foreach (KeyValuePair< int , int > 項目の日数)
        { 
             (item.Value == 1)の場合
            {
                tempDays.Add(アイテム.Key); 
    
                 foreach (KeyValuePair< int , int []>誕生日内の誕生日)
                { 
                     if (誕生日.値[1] == 項目.キー)
                    { 
                         if (!tempMonths.Contains(birthday.Value[0]))
                            tempMonths.Add(誕生日.Value[0]);
                    }
                }
            }
        } 
    
         // すべての誕生日を反復処理し、tempMonths にあるすべての誕生日を取得します 
         //値はキー内の誕生日の対応するTKeyに格納されます 
         foreach ( int月in tempMonths)
        { 
             foreach (KeyValuePair< int , int []>誕生日内の誕生日) 
                 if (誕生日.値[0] == 月)
                    キーを追加します(誕生日のキー)。
        } 
    
         // キーをトラバースし、M=誕生日のキーであるあり得ない誕生日を削除します 
         //月内の対応する値を削除します 
         // 日の出現回数が1つ減ります 
         foreach ( intキーinキー)
        {
            months.Remove(誕生日[キー][0]);
            日数[誕生日[キー][1]] -= 1;
            birthdays.Remove(キー);
        } 
    
         //日付から不可能な誕生日を削除する 
         foreach ( int日数in tempDays )
        {
            days.Remove(day);
        } 
    
         // tempDays をクリア 
        tempDays.Clear(); 
         // キーをクリアする 
        キーをクリアします。 
    
         // 可能性のあるすべての誕生日を走査し、値 N が 2 回出現する日付を削除します 
         foreach (KeyValuePair< int , int > 項目の日数)
        { 
             if (item.Value > 1)
            {
                tempDays.Add(アイテム.Key); 
                 foreach (KeyValuePair< int , int []>誕生日内の誕生日)
                { 
                     if (誕生日.値[1] == 項目.キー)
                    { 
                         if (!keys.Contains(birthday.Key))
                            キーを追加します(誕生日のキー)。
                        月[誕生日.値[0]] -= 1;
                    }
                }
            }
        } 
         foreach ( intキーinキー)
            birthdays.Remove(キー); 
    
        キーをクリアします。
        tempMonths.Clear(); 
    
         //すべての誕生日を走査し、値Mが2回出現する日付を削除します 
         foreach (KeyValuePair< int , int >月単位の項目)
        { 
             if (item.Value > 1) 
                 if (!tempMonths.Contains(item.Key))
                    tempMonths.Add(item.Key);
        } 
         foreach ( int月in tempMonths)
        { 
             foreach (KeyValuePair< int , int []> 誕生日内の項目) 
                 if (item.Value[0] == 月) 
                     if (!keys.Contains(item.Key))
                        キーを追加します。(item.Key);
        } 
         foreach ( intキーinキー)
            birthdays.Remove(キー); 
                
    }
 }