PTT數位生活區 / Prob_Solve (計算數學 Problem Solving)

Re: [問題] 長方形與正方形

看板Prob_Solve (計算數學 Problem Solving)作者yoco315 (眠月)時間18年前 (2006/11/16 10:03)推噓2(2推 0噓 0→)

留言2則, 1人參與討論串11/15 (看更多)

※ 引述《march20 ()》之銘言： : ※ 引述《willieliao (Willie Liao)》之銘言： : : 眾版友好 : : 三年前我去紐約的花旗銀行面試，有一題我到現在還想不出來，無意間看到這個版， : : 就寫出來讓眾高手笑笑了： : : 假設現在有一個長方形mn，m＞n，mn均為整數，題目問最少要多少個正方形可以填滿 : : 這個長方形？正方形大小不限，但是邊長要整數。 : 銀行面試應該不會考這麼難的題目, 我猜他其實是問 : "最少要用多少個大小相同的正方形填滿, 其中正方形大小不很, 邊長為整數" 我想到《約耳談軟體》裡面談到... ============================================== 現在我們談談清單上的第三款，無法回答的問題。這很有趣。這個主意的關鍵在於問一些不可能有答案的問題，就是想看一下應試者怎麼辦。「西雅圖有多少眼科醫生？」「華盛頓紀念碑有多重？」「洛杉機有多少加油站？」「紐約有多少鋼琴調音師？」。聰明的應試者猜到你不是要測驗他們的專業知識，他們會積極地給出一個估計。「嗯，洛杉機的人口是七百萬；每個人平均擁有2.5輛轎車...」當然如果他們的估計完全錯誤了也沒有關係。重要的是他們能積極地試著回答問題。他們可能會試著搞清楚每個加油站的儲量。「嗯，需要四分鐘給一個儲油罐加滿油，一個加油站有十個油泵每天運行十八個小時 ...」他們也可能試著從占地面積來估計。有時，他們的想法的創造力讓你吃驚。而有時，他們直接要一個LA的黃頁去查。這都是好跡像。 =============================================== 換言之，也許這個時候考的是你的反應。所以當你遇到這個問題，如果你很快的反應出來這是一個 NP，(當然我不知道是不是XD) 並且很積極的想辦法給出一個 DP 或是 greedy 的近似解，那這樣的反應就是對的了。 -- To iterate is human, to recurse is divine. 遞迴只應天上有, 凡人該當用迴圈. 　 L. Peter Deutsch -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 61.31.171.248