PageRank



轉移公告

計劃把 http://blog.hoamon.info/ 文章全部轉移至 http://www.hoamon.info/blog/ 這裡,而本 Blogger 站台的文章近 500 篇,我預計在 2014-12-31 前移轉完畢,完成後 http://blog.hoamon.info/ 將只作代轉服務,一律把舊連結如 http://blog.hoamon.info/index.html 轉成 http://www.hoamon.info/blog/index.html ,敬請舊雨新知互相走告。

新文章只發佈在 http://www.hoamon.info/blog/

何岳峰 敬上

2007年3月3日 星期六

微軟徵才試題

永源拿了兩個不同數字...
這兩個數字分別大於 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 原理全忘了。我還是得一次只作一件事吧!

3 則留言:

  1. 針對這個題目,我寫了一篇文章,進行推論
    http://heaven.branda.to/~thinker/GinGin_CGI.py/show_id_doc/226

    回覆刪除
  2. 我用 C 來求解 http://fourdollars.blogspot.com/2007/03/cmclass_08.html

    回覆刪除

注意:只有此網誌的成員可以留言。

Related Posts Plugin for WordPress, Blogger...