○ ○ ○
— ＋ — ＋ — ＝ １
○○ ○○ ○○
圈圈中填入１～９不重複...
有可能嗎...??
--
※ 發信站: 批踢踢實業坊(ptt.csie.ntu.edu.tw)
◆ From: 61.216.233.166
> -------------------------------------------------------------------------- <
作者: TKirby (做個用功乖小孩) 看板: puzzle
標題: Re: 數字問題
時間: Mon Jan 20 14:43:32 2003
※ 引述《Janifer2 (寒假愉快)》之銘言：
: ○ ○ ○
: — ＋ — ＋ — ＝ １
: ○○ ○○ ○○
: 圈圈中填入１～９不重複...
: 有可能嗎...??
5 7 9
--- + --- + --- = 1
3 4 6 8 1 2
--
╭════┬════┬════┬════┬════┬═─╭═╮╮
║████ █▋◢█│████ ███◣│███◣ █▋╯◢║│
║◤██◥│███◤╰╮██ │█◣ █ █◣ ◤│█▋◢█║│
╰╮██╭╯███◣╭╯██ ███◥│█◤ ◣│◥██◤╰╮
│║██║│█▋◥█│████│█◥█◣ ████╰╮██ ●║
╰╰══┴┴════┴════┴════┴════┴╰════╯
--
※ 發信站: 批踢踢實業坊(ptt.csie.ntu.edu.tw)
◆ From: 140.112.30.45
> -------------------------------------------------------------------------- <
作者: JinJu (Ｂａｍｂｏｏ) 看板: puzzle
標題: Re: 數字問題
時間: Tue Feb 11 16:12:41 2003
※ 引述《sfhsu (Georg Jensen)》之銘言：
: ※ 引述《andan (英雄)》之銘言：
: : 請問像上面那種input size已經固定為9的問題
: : 有可能屬於NP-Complete的問題嗎
: : 謝謝ㄛ...
: 不考慮它的input size
NO! 怎麼可以不考慮 input size.
complexity class 都是看 accept/decide/verify 所需的 time/space
相對於 input size 是 polynomial/exponential/logarithmic/..
: 這個闆題是NP-C沒錯吧
很抱歉，我還是不知道你指的是怎樣的題目是屬於 NP-Complete 呢？
可否把題目(problem)寫一下，然後給個證明呢？ 證明若不易講清楚，
麻煩簡單地說一下哪個 well-known NP-Complete problem
( eg. SAT, CLIQUE, or whatever ) 可以 reduce 到你所說的 problem
--
※ 發信站: 批踢踢實業坊(ptt.csie.ntu.edu.tw)
◆ From: 140.112.30.64
> -------------------------------------------------------------------------- <
作者: zephyr (斷了線的風箏) 看板: puzzle
標題: Re: 數字問題
時間: Tue Feb 11 21:11:35 2003
A/BC + D/EF + G/HI = 1
這種問題是屬於NP沒錯, 不過絕對不是NP-Complete
(兩者差很多, 不要搞混)
如果是 1~9 的話其實很快啊
分情況討論
1. 最大的數是 7/12
=> 其他兩個數的和是 5/12
但剩下的數最大可能為 9/34 + 8/56 < 5/12 , 所以不可能
同理, 最大的數比 7/12 小也都不可能
2. 最大的數是 8/12
=> 其他兩個數的和是 1/3
所以 EF,HI 有一個是 3 的倍數, 假設是 EF
EF = 36,39,45,54.....
(其中 7/39 + 6/45 < 1/3, 所以39以後皆不可能, 所以EF = 36)
a. EF = 9/36 , => G/HI = 1/12 (剩下457三個數,沒有可能)
b. EF = 8/36 , => G/HI = 1/9 (剩下458三個數,沒有可能)
c. EF = 7/36 , => G/HI = 5/36 (剩下459三個數,沒有可能)
......(都試完結果還是沒有)
3. 結論是最大的數是 9/12
=> 剩下兩個數的和是 1/4
.....(接下來和窮舉差不多, 就省略了, 反正只剩六個數)
就這樣
--
※ 發信站: 批踢踢實業坊(ptt.csie.ntu.edu.tw)
◆ From: 61.224.2.64