微軟徵才試題

永源拿了兩個不同數字...
這兩個數字分別大於 1 ,也分別小於 50
永源只把這兩個數字的乘積告訴了亞譚 ...
永源再只把這兩個數字的和告訴了明歆 ...
永源問, 這兩個數字是什麼 ?

以下是亞譚和明歆的對話... (小強, 小毛, 小燕在旁坐陪)
亞譚: 我不知道這兩個數字是什麼！
明歆: 但我也還是不知道這兩個數字是什麼！
亞譚: 喔！那我知道那兩個數字是什麼了 !
明歆: 喔！那我也知道那兩個數字是什麼了 !
突然間 ....聰明的三位陪客同時也說: 我們也知道那兩個數字是什麼了 !
聰明的你, 告訴我....那兩個數字是什麼 ?

原文應是英文，翻成中文後，求解卻有多組，所以上文已有作過部份修改。

之前聽到這個題目時，是用質數的概念來解的，這方法不對。今天聽了老師的講法，才知道應是用集合的方式。

求解的邏輯如下：

找出兩個數字「積」的集合，把只出現1次的全部刪除，針對剩下數字對，把「和」的集合中，只出現1次的刪除。

這樣留下來的數字對只剩下638對。然後我們針對638對所產生的「積」，去找出對應數字對的「和」出現有幾次。如：
1344的積有兩個數字對(28，48)及(32，42)，所以「和」為76及74，再去對應638對中的「和」是76的有幾次，74的有幾次。最後我們得到1344的「和」次數集合為(2，3)。

這一定不是我們要的答案，因為亞潭知道但明韶不知道的原因，在於只能有一個次數大於2的「和」次數集合，而上述的1344共有2個大於2的集合。

所以我們所要找尋的「和」次數集合應為(2,1,1,1,1)、(3,1,1,1)或是(6,1)之類的。

程式邏輯如下：

利用 dictionary(hash) 的特性，把「積」集合放在 times 變數，key為積值，value為對應的數字對陣列;「和」集合放在 plus 變數，key為和值，value為對應的數字對陣列。

刪完了只出現1次的數字對後，把剩下的「積」集合放到 s_times 變數;「和」集合放到 s_plus 變數中。

最後一個迴圈，則是把剩下的「積」集合中，所對應數字對的「和」次數集合(放到 a 陣列)找出來，並找出其次數只有1個大於2的 a 陣列，而 a陣列中惟一大於2的「和」其數字對即是解答。

Python 程式碼：

#!/usr/bin/python

(times, plus) = ({}, {})
for i in xrange(2, 50):
----for j in xrange(i + 1, 50):
--------if(times.has_key(i * j)):
------------times[i*j].append((i, j))
--------else:
------------times[i*j] = [(i, j)]
--------if(plus.has_key(i + j)):
------------plus[i+j].append((i, j))
--------else:
------------plus[i+j] = [(i, j)]
--------
(s_times, s_plus) = ({}, {})
for (t_k, t_v) in times.items():
----if(len(t_v) >= 2):
--------for (i, j) in t_v:
------------if(len(plus[i+j]) >= 2):
----------------if(s_times.has_key(i * j)):
--------------------s_times[i*j].append((i, j))
----------------else:
--------------------s_times[i*j] = [(i, j)]
----------------if(s_plus.has_key(i + j)):
--------------------s_plus[i+j].append((i, j))
----------------else:
--------------------s_plus[i+j] = [(i, j)]

for (t_k , t_v) in s_times.items():
----(a, b) = ([], 0)
----for (t_i, t_j) in t_v:
--------a.append(len(s_plus[t_i+t_j]))
----for a_i in a:
--------if(a_i >= 2): b += 1
----if(b == 1): print str(t_i) + ', ' + str(t_j)

後記：

老師講解這題的時候，是用 Matlab 程式求解的。我在課堂上，嘗試用 Python 求解，怎麼想都想不出來，直到回家路上，才發現看了 Matlab 程式後，一直把矩陣觀念放在腦中，而基本的 hash 原理全忘了。我還是得一次只作一件事吧!