[請益] 一個數學多項式問題

看板Soft_Job作者 (hippo泡)時間9年前 (2016/08/09 16:46), 9年前編輯推噓10(13推 3噓 25→)
留言41則, 16人參與, 最新討論串1/2 (看更多)
各位大大好 最近看到一個問題 Q: 如何將所有變數的多項式組合列出來 (包含括號情況 重複意義的不需要) ex: a b c --> a + b + c (a + b) + c 重複 不用 a + b - c a - b + c a - b - c a * b * c a * b / c a / b * c a / (b * c) a / (b / c) (a / b) / c a + b * c (a + b) * c . . .etc 而輸入的變數也可能是a b c d e....etc 加入括號後 就不知道該如何做了 請問該從哪方面下手思考呢? 有沒有類似問題的關鍵字呢 謝謝m_ _m -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 1.160.93.155 ※ 文章網址: https://www.ptt.cc/bbs/Soft_Job/M.1470732404.A.86C.html
推
08/09 16:54, , 1F
作業？
08/09 16:54, 1F
不是作業..><
→
08/09 16:56, , 2F
stack?
08/09 16:56, 2F
忘了它...謝謝我上面也去問問看>< ※ 編輯: stevekevin10 (1.160.93.155), 08/09/2016 17:17:03
→
08/09 17:17, , 3F
遞迴感覺比較可以輕鬆弄，只是要額外判斷相同意義的可
08/09 17:17, 3F
→
08/09 17:17, , 4F
能要再處理
08/09 17:17, 4F
噓
08/09 17:19, , 5F
作業自己做
08/09 17:19, 5F
不是作業啦。。:"( 是跟朋友閒聊沒加括號情況下要得到所有解很簡單 但是加括號後好像難度翻了幾倍
推
08/09 17:28, , 6F
用Postfix(或Prefix)找 這樣就不用管括號 如果輸出要
08/09 17:28, 6F
→
08/09 17:28, , 7F
Infix 就Postfix再轉Infix就好
08/09 17:28, 7F
→
08/09 17:33, , 8F
好像還是會有結合律的問題....
08/09 17:33, 8F
→
08/09 17:34, , 9F
我說可以用stack做 不是stackoverflow...
08/09 17:34, 9F
XDD...抱歉我搞錯 stack有考慮過但是在括號部分還是覺得有點卡住 ※ 編輯: stevekevin10 (1.160.93.155), 08/09/2016 17:39:06
→
08/09 17:53, , 10F
個人想法如Ayu所說 最後轉Infix過程判斷一下結果
08/09 17:53, 10F
→
08/09 17:54, , 11F
是否符合結合律去做刪減？
08/09 17:54, 11F
推
08/09 18:19, , 12F
template MetaProgramming 秒解…
08/09 18:19, 12F
推
08/09 18:23, , 13F
喔～是只要列出來 不用算答案喔…
08/09 18:23, 13F
要算答案>< ※ 編輯: stevekevin10 (223.137.166.214), 08/09/2016 19:34:30
推
08/09 19:50, , 14F
那你就 1.產生依序一串運算子 2.插入 a, b, c，規則是 b
08/09 19:50, 14F
→
08/09 19:50, , 15F
不能在 a 前面，c 不能在 b 前面
08/09 19:50, 15F
推
08/09 19:53, , 16F
把產生出來的式子當作前序看待，可以產生出所有組合(包含
08/09 19:53, 16F
→
08/09 19:53, , 17F
有括號的，只是如果你要轉回中序要自己把括號加上)並且沒
08/09 19:53, 17F
→
08/09 19:53, , 18F
有重複
08/09 19:53, 18F
→
08/09 20:07, , 19F
這個該叫多變數四則運算 不是多項式
08/09 20:07, 19F
→
08/09 20:07, , 20F
多項式是有精確定義的
08/09 20:07, 20F
噓
08/09 20:23, , 21F
expression binary tree + permutation combination
08/09 20:23, 21F
→
08/09 20:23, , 22F
作業自己做
08/09 20:23, 22F
推
08/09 22:05, , 23F
就排列組合啊...
08/09 22:05, 23F
→
08/09 22:07, , 24F
看錯..
08/09 22:07, 24F
噓
08/10 06:48, , 25F
就算不使用expression binary tree
08/10 06:48, 25F
→
08/10 06:49, , 26F
窮舉所有情況再檢查相同阿
08/10 06:49, 26F
→
08/10 06:50, , 27F
作業自己做
08/10 06:50, 27F
推
08/10 10:30, , 28F
你一定沒修過資料結構.....
08/10 10:30, 28F
推
08/10 10:31, , 29F
先用BNF production rule寫出含括弧的expression 限最終
08/10 10:31, 29F
→
08/10 10:38, , 30F
terminate 出現的次數就能造出所有可能結果.
08/10 10:38, 30F
→
08/10 11:47, , 31F
如果想知道原理，去math板問會比較好
08/10 11:47, 31F
推
08/11 13:56, , 32F
我記得leetcode有這題目 可以去看看別人解法
08/11 13:56, 32F
推
08/12 01:30, , 33F
排列組合問題
08/12 01:30, 33F
推
08/18 21:38, , 34F
所以看起來 a - b + c 跟 a - (b - c) 也算重複?
08/18 21:38, 34F
→
08/18 21:41, , 35F
為什麼有 a / b * c 又有 a / (b / c)
08/18 21:41, 35F
→
08/18 21:42, , 36F
喔要括號, 所以"重複意義"僅限 infixr 或 infixl 不要囉?
08/18 21:42, 36F
推
08/19 11:26, , 37F
1.窮舉所有運算子得到所有expression
08/19 11:26, 37F
→
08/19 11:28, , 38F
2.針對1.的每個expression，窮舉所有括弧
08/19 11:28, 38F
→
08/19 11:29, , 39F
1.的解法可參考leetcode:Expression And Operators
08/19 11:29, 39F
→
08/19 11:30, , 40F
2.的解法leetcode:Different Ways To Add Parentheses
08/19 11:30, 40F
→
08/19 12:04, , 41F
其中1.的解法比leetcode那題還要簡單
08/19 12:04, 41F
‣ 更多 stevekevin10 的文章
文章代碼(AID): #1NgPXqXi (Soft_Job)
‣ 更多 stevekevin10 的文章
文章代碼(AID): #1NgPXqXi (Soft_Job)