![>](style_images/1/nav_m.gif)
香港三國志 · 版規 |
![]() ![]() ![]() ![]() ![]() ![]() |
歡迎訪客 ( 登入 | 註冊 ) | 重寄認證電子郵件 |
分頁: (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 ![]() |
||
![]() |
![]() ![]() ![]() |