张老师的生日问题C#算法实现
张老师生日问题答案9月1日，我记得好像还有个经理年龄问题，答案36岁，代码如下：
?Download Program.cs
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 | using System; using System.Collections.Generic; using System.Linq; using System.Text; namespace birthday { class Program { /**/ /// <summary> /// 小明和小强都是张老师的学生，张老师的生日是M月N日， /// 2人都知道张老师的生是下列10组中的一天， /// 张老师把M值告诉了小明，把N值告诉了小强， /// 张老师问他们知道他的生日是那一天吗？ /// 3月4日 3月5日 3月8日 /// 6月4日 6月7日 /// 9月1日 9月5日 /// 12月1日 12月2日 12月8日 /// 小明说：如果我不知道的话，小强肯定也不知道 /// 小强说：本来我也不知道，但是现在我知道了 /// 小明说：哦，那我也知道了 /// 请根据以上对话推断出张老师的生日是哪一天？？ /// /// Author : 木子 /// CopyRight: http://blogmoozinet /// </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("无解"); } Console.ReadLine(); } private static void AnalyseBirthday(Dictionary<int, int[]> birthdays) { //days:所有N值集合，TKey:是N值，TValue:是出现次数 Dictionary<int, int> days = new Dictionary<int, int>(); //months:所有N值集合，TKey:是M值，TValue:是出现次数 Dictionary<int, int> months = new Dictionary<int, int>(); //遍历birthdays并分别对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); } //声明一个临时用的List:tempDays，用来存储N值 List<int> tempDays = new List<int>(); //声明一个临时用的List:tempMonths，用来存储M值 List<int> tempMonths = new List<int>(); //声明一个临时用的List:keys，用来存储birthdays的TKey值 List<int> keys = new List<int>(); //查找所有可能生日中N值只出现一次的对应值，并将其保存到tempDays中 //并获取到唯一N值相对应的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相应对应的TKey，存储到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中相应的值 //days出现的次数减一 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值出现过两次的日期 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值出现过两次的日期 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); } } } |
原创文章转载请注明出处：云飞扬IT的blog
