香港三國志 · 版規 | 說明 搜尋 會員 聲望 日曆 統計 |
歡迎訪客 ( 登入 | 註冊 ) | 重寄認證電子郵件 |
分頁: (2) [1] 2 ( 前往第一篇未讀文章 ) |
Pearltea | |
四品官 發表數: 1,289 所屬群組: 太守 註冊日期: 9-22-2003 活躍:5 聲望:614 |
最近喜歡找brain teasers來玩, 看到一些很不錯的. 在這跟大家分享.
看到有一題跟之前的面試post裡相似的問題, 但是難度更高. 原來大公司如Google或投資銀行也問過面試的程序員. 我花了些時間才找到方法, 再去看其他答案後發現我的方法有些不同. 可見我是沒程序員的思考啊! 大家試試看, 說不定有一天面試時用得上. 如果有十二枚波子, 十一枚的重量一樣, 其中一枚的不同 (可以是較輕或重). 你如何用平衡秤三次來找出不同重量的一枚? 不同的一枚是較輕或較重? 已經知道答案的板友請不要回答. Edit : to add the need to find whether the unusual one is lighter or heavier. Update: pg.1&2已有答案. 想玩的不要scroll down 本篇文章已被 Pearltea 於 Aug 23 2015, 16:43 編輯過 |
XxEDxX |
發表於: Aug 23 2015, 07:25
|
||
三品官 發表數: 1,467 所屬群組: 太守 註冊日期: 8-30-2011 活躍:8 聲望:507 |
[很喜歡這種貼,謝謝分享] 我會選擇用two-split. 12->6,6 6->3,3 當然最後較難,想了一想,就1,1; 不同就知道了。[故意說亂些少,但應該明白的XD] 另外一問:有多少個solution? |
||
Pearltea | |||
四品官 發表數: 1,289 所屬群組: 太守 註冊日期: 9-22-2003 活躍:5 聲望:614 |
two-split的方法: 如果已知道不同的一枚是較輕或較重才會有用. 所以分6:6的話, 還未知道不同的一枚是在那一邊. |
||
XxEDxX |
發表於: Aug 23 2015, 07:35
|
||||
三品官 發表數: 1,467 所屬群組: 太守 註冊日期: 8-30-2011 活躍:8 聲望:507 |
謝提醒,我再想想 |
||||
XxEDxX |
發表於: Aug 23 2015, 07:57
|
||
三品官 發表數: 1,467 所屬群組: 太守 註冊日期: 8-30-2011 活躍:8 聲望:507 |
trial 2: 12->4,4,4; pick any two groups I think it should be case by case (two cases; equal or unequal) the trivial one should be easier: if equal then pick 3 marbles from the remaining group, pick any one marble from the 8 marbles as standard then 2 - 2 (with standard, WLOG) 1. if equal, then the remaining (unused) one; make a lift with standard and we can know whether it is lighter or heavier than others; 2. if unequal, see the inbalance; assume left side is lighter (WLOG, again) then one on the left is lighter; or the one on the right (not standard) is heavier; try 1-1 on the left; I think the remaining solution for this case should be trivial. [拋磚引玉,will explain the remaining cases; if the explanation above is not wrong XD] 本篇文章已被 XxEDxX 於 Aug 23 2015, 11:03 編輯過 |
||
Pearltea |
發表於: Aug 23 2015, 07:57
|
||||||
四品官 發表數: 1,289 所屬群組: 太守 註冊日期: 9-22-2003 活躍:5 聲望:614 |
好。 原題加了:不同的一枚是較輕或較重? 這樣就會減少不同的方式。我第一次看到的version只找不同的一枚所以我的方法有些少出入 |
||||||
Pearltea |
發表於: Aug 23 2015, 08:06
|
||||
四品官 發表數: 1,289 所屬群組: 太守 註冊日期: 9-22-2003 活躍:5 聲望:614 |
請繼續 |
||||
XxEDxX |
發表於: Aug 23 2015, 08:12
|
三品官 發表數: 1,467 所屬群組: 太守 註冊日期: 8-30-2011 活躍:8 聲望:507 |
[trial 2: cont]
if after the first lift, unequal; then mark the marbles as 1,2,3,4;5,6,7,8 (remaining as 9,10,11,12) [just for simpler explanation...] WLOG, assume left is lighter; then 3,4,9:1,2,5 (put 6,7,8 aside, will deal with them later) case by case again: if balance, then try 6,7,8 similar as the last step before; if not balance, then... @if the left is still lighter: then one of 3 or 4 is lighter; lift them and find the spy; @if the right is lighter: then one of 1 or 2 is lighter; lift them and find the spy; [please correct me for any mistakes...] |
Caesar |
發表於: Aug 23 2015, 08:48
|
Loop 發表數: 7,489 所屬群組: 軍團長 註冊日期: 12-18-2004 活躍:42 聲望:2218 |
I didn't read ED's solution
If mine is redundant , just tell me n ignore this So here we go. Mark 1-12 in sequence 1st : 1234 vs 5678 Two possible result , same weight (go to A)or difference ( go to B ), 2nd-A : 9,10 vs 11,12 and follow with 3rd : 9,11 vs 10,12 2nd-B: 1256vs 3478 and follow with 3rd : 1357 vs 2468 That's it. -------------------- |
Caesar |
發表於: Aug 23 2015, 09:24
|
||
Loop 發表數: 7,489 所屬群組: 軍團長 註冊日期: 12-18-2004 活躍:42 聲望:2218 |
I just read ur solution. I assumed u r right Soooooooooo, Sry for my poor comprehension. I don't really get the following . (i) 1st : 1234 vs 5678 , result : equal . 2nd : 39 vs 10,11 , result : 10,11 lighter. Now either 9 is heavier or 10,11 is lighter. With one more trial now ,from ur solution , I can't tell excatly which ball is lighter/heavier . (ii) 1st : 1234 vs 5678 , result : not equal 2nd : 349 vs 125 , result : equal Now, with one more trial .... Once again I can't excatly tell Please advise. -------------------- |
||
XxEDxX |
發表於: Aug 23 2015, 10:48
|
||
三品官 發表數: 1,467 所屬群組: 太守 註冊日期: 8-30-2011 活躍:8 聲望:507 |
I have thought around your solution. If according to your solution we have three times (left:heavier), can you tell me which marble is different? And, is it lighter or heavier than others? I think your answer looks simpler, but it seems unable to cover all possibilities. |
||
XxEDxX |
發表於: Aug 23 2015, 10:53
|
||||
三品官 發表數: 1,467 所屬群組: 太守 註冊日期: 8-30-2011 活躍:8 聲望:507 |
Maybe I write my solution unclearly, so that you seem to misunderstand my solution. Let me answer your cases one by one. *** For your case 1: I wrote: "the trivial one should be easier: if equal then pick 3 from the remaining group, pick any one marble from the 8 marbles as standard" So, if 1234:5678 is equal, then You wrote: "2nd : 39 vs 10,11 , result : 10,11 lighter." is not my solution. *** For your case 2: You wrote: "1st : 1234 vs 5678 , result : not equal 2nd : 349 vs 125 , result : equal Now, with one more trial .... Once again I can't excatly tell" You can't exactly tell, since you have one more trial Then we have 6,7,8 left, with one more trial. Please see my Part 1, last step. That's it. Thanks for your reply. |
||||
XxEDxX |
發表於: Aug 23 2015, 10:57
|
||
三品官 發表數: 1,467 所屬群組: 太守 註冊日期: 8-30-2011 活躍:8 聲望:507 |
"pick 3 from the remaining group" For this I mean pick 3 marbles. Sorry for any possible misinterpretation. Edit: I will insert the word "marbles" in my previous answer. 本篇文章已被 XxEDxX 於 Aug 23 2015, 11:02 編輯過 |
||
XxEDxX |
發表於: Aug 23 2015, 10:59
|
||||
三品官 發表數: 1,467 所屬群組: 太守 註冊日期: 8-30-2011 活躍:8 聲望:507 |
For simpler argument, After your first step, if it is unequal, then you have 8 marbles to be considered. 2-step bisection method is not enough to pick the different one and determine whether it is lighter or heavier. You need one more step, so you totally need 4 steps for your solution. |
||||
Caesar |
發表於: Aug 23 2015, 11:06
|
Loop 發表數: 7,489 所屬群組: 軍團長 註冊日期: 12-18-2004 活躍:42 聲望:2218 |
Haha i was just too confident wif my 2mins answer ,
To a point that I couldn't wait for pearltea's confirmation n google'd da answer. I guess both of us didnt hit the bell yet. ( damn my arrogant , no more chance for me ;p) Gdluck ED, enjoy the fun of getting closer to the answer. Maybe urs can be an alternative answer, But my poor comprehension seems still can't get me to the agree-side with ya solution. 本篇文章已被 Caesar 於 Aug 23 2015, 11:07 編輯過 -------------------- |
XxEDxX |
發表於: Aug 23 2015, 11:09
|
||
三品官 發表數: 1,467 所屬群組: 太守 註冊日期: 8-30-2011 活躍:8 聲望:507 |
Then please tell me where did I miss the point, thanks. You can directly point it out. |
||
Caesar |
發表於: Aug 23 2015, 11:16
|
||||
Loop 發表數: 7,489 所屬群組: 軍團長 註冊日期: 12-18-2004 活躍:42 聲望:2218 |
Hey relax. As I said I'm sorry for my poor comprehension. No offence it's truly my fault. I honestly mean it. If u said I get u wrong , I guess I basically can't understand ur solution, then how could I point it out ? From the so-called model answer I read, it's totally difference with both of us . As I said maybe urs can be an alternative answer, so dun be mad, it's just my comprehension fails. -------------------- |
||||
XxEDxX |
發表於: Aug 23 2015, 11:23
|
||||||
三品官 發表數: 1,467 所屬群組: 太守 註冊日期: 8-30-2011 活躍:8 聲望:507 |
Haha, don't get me wrong. I didn't get mad. Relax, probably I have to insert some evilgrins!! For your case 1, if you read my solution again, I said "pick 3 marbles from the remaining group". I hope you get what I mean, or I hope what I edit can make you understand my point better. For your case 2, you have one more step. It is enough for picking the different one from the 3 marbles left. |
||||||
Caesar |
發表於: Aug 23 2015, 11:30
|
Loop 發表數: 7,489 所屬群組: 軍團長 註冊日期: 12-18-2004 活躍:42 聲望:2218 |
Hey I'm dumb. ( yea sry)
For my case (ii) , I can't point it out really. 1st : 1234 vs 5678 , result : not equal 2nd : 349 vs 125 , result : equal Now ,we all know 678 is the defective group now . Please advise a detailed solution on how to figure out which one is a lighter/heavier with a final trial. This is my question 2 hours ago, and I still can't point it out. Oh please , I know I'm dumb. 本篇文章已被 Caesar 於 Aug 23 2015, 11:32 編輯過 -------------------- |
XxEDxX |
發表於: Aug 23 2015, 11:32
|
||
三品官 發表數: 1,467 所屬群組: 太守 註冊日期: 8-30-2011 活躍:8 聲望:507 |
what is your unequal in the first step? It can give you some idea for the third step bro |
||
分頁: (2) [1] 2 |