伊莉討論區

標題: JAVA新手,問一個想很久的問題 [打印本頁]

作者: 26912000 時間: 2017-1-30 06:41 PM 標題: JAVA新手,問一個想很久的問題

我是一個去年才剛學ＪＡＶＡ不到半年的新手，想問一個困惑我很久的問題.....

這個問題是我在球直上看到的，本以為自己可以輕鬆解決，結果卻解不出來！？

問題是：

８個數字相加等於１００，請把方法總數與數列列出來。（可重複）

懇請大大解惑。

作者: kyo478 時間: 2017-2-2 03:38 AM

Step.1 先用手算,理出頭緒
Step.2 開始用電腦整理
Step.3 Call out.

作者: neqkwos1003 時間: 2017-2-2 05:47 AM

我的想法是土法煉鋼，把所有組合用for跑出來，判斷<100後印出來！

作者: johnwanz 時間: 2017-2-3 11:01 AM

本帖最後由 johnwanz 於 2017-2-3 11:02 AM 編輯

首先, 先要能解; 土法煉鋼也是一種方法.

再來, 改善.
從已解出的答案或解題方式, 找出適合此題目的規律, 從規律中著手優化, 改善原本方式.

如果連土法煉鋼都解不出來, 表示還沒有辦法理解題目所想要表達的運算規則. 需求不明確就無法進行解題, 更難以說要改善.

先描述自己的想法, 解法及所得結果, 再尋求別人的建議, 經過了自己親手實作, 從錯誤中學習到經驗, 加上別人給的建議, 才能真正有效的學習, 否則只是紙上談兵, 僅用空想, 對學習的幫助很有限.

作者: owen51104 時間: 2017-3-1 10:23 PM

先在紙本上列出自己想到的可能性數列，慢慢就會規畫出規則，這時候才轉換成程式碼，如果連第一步在紙本列出可能的數列都舉不出來，是不太可能憑空編寫出程式碼的

作者: s39817072 時間: 2017-4-8 12:04 PM

當下我也是會先for去跑吧..
若時間夠的話再想優化.

作者: theloserbm 時間: 2017-4-11 12:12 PM

這問題2個月半了, 居然還只停留在for loop的階段...
這問題的解法有點像著名的[8個皇后], 只是簡單很多. 其中一種解法就是, 先列出一個已知解, 然後再慢慢改變他找出其它的解.

所以我們首先列出一個已知解
1 1 1 1 1 1 1 93

然後用最小的改變找出下一個解
1 1 1 1 1 1 2 92
1 1 1 1 1 1 3 91
...
1 1 1 1 1 1 46 48
1 1 1 1 1 1 47 47
1 1 1 1 1 1 48 46
然後我們發現從這裡開始重複了, 就不繼續了, 進入下一個數字

1 1 1 1 1 2 1 92
我們發現這行也跟上面重複了, 得出規律我們只需要列出左到右從小到大的組合就可以了

1 1 1 1 1 2 2 91
1 1 1 1 1 2 3 90
1 1 1 1 1 2 46 47
1 1 1 1 1 3 3 89

然後到中間我們會發現, 有時候位數加一會導致超過100, 如
1 1 1 1 1 31 32 32
1 1 1 1 1 32 32 32
這時候只能增加下一位了
1 1 1 1 2 2 2 90
...
12 12 12 12 12 13 14 14
12 12 12 12 13 13 13 13

然後就完成了

作者: chevylin0802 時間: 2017-4-14 05:45 PM

一般來講用土法練鋼的方式雖然也可以得到答案
但速度上就會慢了許多
八個數相加要等於100
也可以解析成兩個數字相加等於100 (假設這兩個數字各為四個數字的總合)
比如 n1+n2+n3+n4+n5+n6+n7+n8 = 100
所以設
m1 = n1+n2+n3+n4
m2 = n5+n6+n7+n8
所以 m1 >= 4 , m2 >= 4
且m1 <=96, m2 <= 96
但為了節省時間起見
所以也可以把條件改為 m1 <=50, m2 <=50
同理也可以把m1, m2拆分成 m1 = k1 + k2 (k1 = n1+n2, k2 = n3+n4)
然後再繼續取數
.................

作者: hoare 時間: 2017-6-11 12:44 AM

提示: 作者被禁止或刪除內容自動屏蔽

作者: weirdococo 時間: 2017-6-12 10:07 PM

本帖最後由 weirdococo 於 2017-6-12 10:10 PM 編輯

偷偷的先用script先寫一遍，

土法煉鋼的方法，用到了Cartesian product，folder/reduce，filter，
這樣簡化思維比較簡單(還是只有我這麼覺得?)。
再來來就是要找到java 的Cartesian product，和folder/reduce，加上filter。
題外話這是無視效率的寫法，等我有空再挑戰看看更有效的想法(演算)。

補充內容 (2017-6-12 10:26 PM):
有空用，試試看加上排容原理的想法因該會快很多。

補充內容 (2017-6-12 10:49 PM):
基本上就是 8個相同的排列，7個相同的排列.......再用排容原理的想法

作者: weirdococo 時間: 2017-6-13 11:20 AM

theloserbm 發表於 2017-4-11 12:12 PM
這問題2個月半了, 居然還只停留在for loop的階段...
這問題的解法有點像著名的[8個皇后], 只是簡單很多. 其 ...

我換個說法，基本上就是 8個相同的排列，7個相同的排列 ......再把所有的集合加起來就是了。
是不是這樣想？

歡迎光臨伊莉討論區 (http://blog.eyny.com/)