C#算法解決張老師的生日問(wèn)題
C#算法實(shí)現(xiàn)張老師的生日問(wèn)題是怎么辦到的呢？首先我們來(lái)回顧下這個(gè)張老師的生日問(wèn)題：
小明和小強(qiáng)都是張老師的學(xué)生，張老師的生日是M月N日， 2人都知道張老師的生是下列10組中的一天，張老師把M值告訴了小明，把N值告訴了小強(qiáng)， 張老師問(wèn)他們知道他的生日是那一天嗎？
3月4日 3月5日 3月8日
6月4日 6月7日
9月1日 9月5日
12月1日 12月2日 12月8日
小明說(shuō)：如果我不知道的話，小強(qiáng)肯定也不知道
小強(qiáng)說(shuō)：本來(lái)我也不知道，但是現(xiàn)在我知道了
小明說(shuō)：哦，那我也知道了
請(qǐng)根據(jù)以上對(duì)話推斷出張老師的生日是哪一天？？
相信很多朋友都看過(guò)這個(gè)邏輯推理題吧，正確的答案是9月1日，推理過(guò)程我這里就不在再說(shuō)了，Google一下一大堆，我要說(shuō)的是用C#來(lái)得到這個(gè)推理結(jié)果^_^
C#算法解決張老師的生日問(wèn)題推理過(guò)程如下：
1、分析所有生日集合，月份有{3,6,9,12}，日有{4,5,8,7,1,5,2}。
2、小明說(shuō)：“如果我不知道的話，小強(qiáng)肯定也不知道”，在日的集合中，{2,7}只出現(xiàn)一次。小明會(huì)這樣說(shuō)，那就可以推出小明得到的M不是{6,12}。因?yàn)樾?qiáng)的N值是{2,7}的話，他可以直接得到張老師的生日，小明的M值就沒(méi)有意義了。而小明這樣說(shuō)了，那就說(shuō)明小明手中的M不是{6,12}。
3、小強(qiáng)說(shuō)：“本來(lái)我也不知道，但是現(xiàn)在我知道了”?？鄢齅={6,12}，剩下可能的為{{3,4},{3,5},{3,8},{9,1},{9,5}}小強(qiáng)說(shuō)他知道了，由于小強(qiáng)只知道N，而他能肯定得到張老師的生日，所以他的N值一定是剩下集合中日數(shù)唯一的。這就可以排除{{3,5},{9,5}}了。
4、小明說(shuō)：“哦，那我也知道了”。小明的是月份，剩下集合是{{3,4},{3,8},{9,1}}，如果小明的M是3，那就有兩個(gè)日期可以選擇，不能確定生日。既然小明能確定張老師的生日，那小明手中的M就是9。
所以張老師的生日是：9月1日。
下面的代碼也是照著這個(gè)思路來(lái)寫(xiě)的。
C#算法解決張老師的生日問(wèn)題的演示代碼
- class Program
- {
- /// <summary>
- /// 小明和小強(qiáng)都是張老師的學(xué)生，張老師的生日是M月N日，
- /// 2人都知道張老師的生是下列10組中的一天，
- /// 張老師把M值告訴了小明，把N值告訴了小強(qiáng)，
- /// 張老師問(wèn)他們知道他的生日是那一天嗎？
- /// 3月4日 3月5日 3月8日
- /// 6月4日 6月7日
- /// 9月1日 9月5日
- /// 12月1日 12月2日 12月8日
- /// 小明說(shuō)：如果我不知道的話，小強(qiáng)肯定也不知道
- /// 小強(qiáng)說(shuō)：本來(lái)我也不知道，但是現(xiàn)在我知道了
- /// 小明說(shuō)：哦，那我也知道了
- /// 請(qǐng)根據(jù)以上對(duì)話推斷出張老師的生日是哪一天？？
- ///
- /// </summary>
- /// <param name="args"></param>
- static void Main(string[] args)
- {
- Dictionary<int, int[]> birthdays = new Dictionary<int, int[]>();
- birthdays.Add(1,new int[]{3,4});
- birthdays.Add(2,new int[]{3,5});
- birthdays.Add(3,new int[]{3,8});
- birthdays.Add(4,new int[]{6,4});
- birthdays.Add(5,new int[]{6,7});
- birthdays.Add(6,new int[]{9,1});
- birthdays.Add(7,new int[]{9,5});
- birthdays.Add(8,new int[]{12,1});
- birthdays.Add(9,new int[]{12,2});
- birthdays.Add(10,new int[]{12,8});
- AnalyseBirthday(birthdays);
- if (birthdays.Keys.Count > 0)
- {
- foreach (KeyValuePair<int, int[]> item in birthdays)
- {
- Console.WriteLine("張老師可能的生日為：{0}月{1}日", item.Value[0], item.Value[1]);
- }
- }
- else
- {
- Console.WriteLine("無(wú)解");
- }
- Console.ReadLine();
- }
- private static void AnalyseBirthday(Dictionary<int, int[]> birthdays)
- {
- //days:所有N值集合，TKey:是N值，TValue:是出現(xiàn)次數(shù)
- Dictionary<int, int> days = new Dictionary<int, int>();
- //months:所有N值集合，TKey:是M值，TValue:是出現(xiàn)次數(shù)
- Dictionary<int, int> months = new Dictionary<int, int>();
- //遍歷birthdays并分別對(duì)days,months賦值
- foreach (KeyValuePair<int, int[]> item in birthdays)
- {
- if (days.ContainsKey(item.Value[1]))
- days[item.Value[1]] += 1;
- else
- days.Add(item.Value[1], 1);
- if (months.ContainsKey(item.Value[0]))
- months[item.Value[0]] += 1;
- else
- months.Add(item.Value[0], 1);
- }
- //聲明一個(gè)臨時(shí)用的List:tempDays，用來(lái)存儲(chǔ)N值
- List<int> tempDays = new List<int>();
- //聲明一個(gè)臨時(shí)用的List:tempMonths，用來(lái)存儲(chǔ)M值
- List<int> tempMonths = new List<int>();
- //聲明一個(gè)臨時(shí)用的List:keys，用來(lái)存儲(chǔ)birthdays的TKey值
- List<int> keys = new List<int>();
- //查找所有可能生日中N值只出現(xiàn)一次的對(duì)應(yīng)值，并將其保存到tempDays中
- //并獲取到唯一N值相對(duì)應(yīng)的M值，并將其保存到tempMonths中
- foreach (KeyValuePair<int, int> item in days)
- {
- if (item.Value == 1)
- {
- tempDays.Add(item.Key);
- foreach (KeyValuePair<int, int[]> birthday in birthdays)
- {
- if (birthday.Value[1] == item.Key)
- {
- if (!tempMonths.Contains(birthday.Value[0]))
- tempMonths.Add(birthday.Value[0]);
- }
- }
- }
- }
- //遍歷所有可能的生日，并獲取tempMonths中的所有
- //值在birthdays相應(yīng)對(duì)應(yīng)的TKey，存儲(chǔ)到keys中
- foreach (int month in tempMonths)
- {
- foreach (KeyValuePair<int, int[]> birthday in birthdays)
- if (birthday.Value[0] == month)
- keys.Add(birthday.Key);
- }
- //遍歷keys，在birthdays移除M=key的不可能的生日
- //移除months中相應(yīng)的值
- //days出現(xiàn)的次數(shù)減一
- foreach (int key in keys)
- {
- months.Remove(birthdays[key][0]);
- days[birthdays[key][1]] -= 1;
- birthdays.Remove(key);
- }
- //在days中移除不可能生日
- foreach (int day in tempDays)
- {
- days.Remove(day);
- }
- //清空tempDays
- tempDays.Clear();
- //清空keys
- keys.Clear();
- //遍歷所有可能的生日，移除N值出現(xiàn)過(guò)兩次的日期
- foreach (KeyValuePair<int, int> item in days)
- {
- if (item.Value > 1)
- {
- tempDays.Add(item.Key);
- foreach (KeyValuePair<int, int[]> birthday in birthdays)
- {
- if (birthday.Value[1] == item.Key)
- {
- if (!keys.Contains(birthday.Key))
- keys.Add(birthday.Key);
- months[birthday.Value[0]] -= 1;
- }
- }
- }
- }
- foreach (int key in keys)
- birthdays.Remove(key);
- keys.Clear();
- tempMonths.Clear();
- //遍歷所有可能的生日，移除M值出現(xiàn)過(guò)兩次的日期
- foreach (KeyValuePair<int, int> item in months)
- {
- if (item.Value > 1)
- if (!tempMonths.Contains(item.Key))
- tempMonths.Add(item.Key);
- }
- foreach (int month in tempMonths)
- {
- foreach (KeyValuePair<int, int[]> item in birthdays)
- if (item.Value[0] == month)
- if (!keys.Contains(item.Key))
- keys.Add(item.Key);
- }
- foreach (int key in keys)
- birthdays.Remove(key);
- }
- }
整個(gè)過(guò)程foreach太多了，效率上有很大的問(wèn)題，水平有限。還請(qǐng)網(wǎng)友不吝賜教！謝謝，嘿嘿:-)
C#算法解決張老師的生日問(wèn)題就向你介紹到這里，希望對(duì)你學(xué)習(xí)C#算法有所幫助。
【編輯推薦】
