標題: 此文章來自奇摩知識+如有不便請留言告知
c語言 求所有解和複雜度
發問:
170*v3 + 217*v4 + 264*v5 + 311*v6 + 358*v7 +405*v8 +452*v9 + 499*v10 + 546*v11 + 593*v12 = 15608求v3~v12的所有解和複雜度(總共的計算次數)用巢狀for迴圈寫的似乎是計算量過大 執行後等了20分鐘都沒跑出甚麼請高手幫忙看一下#include
最佳解答:
其他解答:
我有個疑問... 我用 gcc 在 -O1 以上, 他就自動會做 Jacob 的程式碼裡面的事情 (用暫存變數來儲存運算結果, 這應該是 CSE 範疇). 所以我在原 po 的程式也加上了類似 if (v3 * 170 = 14 2*v5+3*v6+4*v7+5*v8+6*v9+7*v10+8*v11+9*v12 = 14)*-1 就-v5-2*v6-3*v7-4*v8-5*v9-6*v10-7*v11-8*v12 27/2=13.5 =13 027/3=9 027/4=6 027/5=5 027/6=4 027/7=3 , 027/8=3 ,027/9=3 ,0= 0 v4 = 0？這樣和其他變數的值域比較一致？ ====== 假定 v4 >= 0，那麼 2*v5+3*v6+4*v7+5*v8+6*v9+7*v10+8*v11+9*v12 = -27 但這樣推演下去， v5+v6+v7+v8+v9+v10+v11+v12 >= -41 顯然又有點矛盾？ 2011-05-11 12:11:38 補充： 綜合林林總總的意見， 你這個問題是否該界定各個變數的值域，才不會空忙一場？ 2011-05-11 13:01:21 補充： 若 v3~v12皆為正整數，那麼依所列出的初始式： v3 = -14+(v5+2*v6+3*v7+4*v8+5*v9+6*v10+7*v11+8*v12) ----(1) v4 = 27+(2*v5+3*v6+4*v7+5*v8+6*v9+7*v10+8*v11+9*v12) ----(2) 應界定 v4 >= 27 建議你重新檢視你在推演的過程中是否有 BUG？ 2011-05-11 17:06:25 補充： 以意見039的程式數據為本， 程式修改後的執行結果如下： total: 114106 match: 1498 unmatch: 112608 這樣是否正確？是否有降低複雜度？ 2011-05-11 18:18:27 補充： v4 = 27+(2*v5+3*v6+4*v7+5*v8+6*v9+7*v10+8*v11+9*v12) 因 v3～v12皆 ＞＝0, 故 v4必＞＝27 但你程式運算結果 match的數據中，v4絕大多數未＞＝27。 因此，程式邏輯與數學式明顯無法密合，應重新檢討程式邏輯。 ====== 此外，意見014提及： 4個鐘頭後終於跑完..... 複雜度2106785854 答案也是27318619 複雜度的數據實際已超過 UINT的極限，已失真不可用。 有必要把程式裡的計數變數改用 long long 才行。 2011-05-11 19:08:10 補充： b - (2*v5 + 3*v6 + 4*v7 + 5*v8 + 6*v9 + 7*v10 + 8*v11 + 9*v12) b=27 若是這樣，便與你程式的邏輯相符了。 ====== 我剛以 a=92, b=144 去跑， 結果是： total: 2225869700 match: 27318619 unmatch: 2198551081 spend 1780.156 seconds 程式計數是用unsigned long long ，因此，數據是可信的。 2011-05-11 19:25:14 補充： v3 = a + (1*v5 + 2*v6 + 3*v7 + 4*v8 + 5*v9 + 6*v10 + 7*v11 + 8*v12) >= 0 v4 = b - (2*v5 + 3*v6 + 4*v7 + 5*v8 + 6*v9 + 7*v10 + 8*v11 + 9*v12) >= 0 令 k1 = v5 + v6 + v7 + v8 + v9 + v10 + v11 + v12) 令 k2 = v5 + 2*v6 + 3*v7 + 4*v8 + 5*v9 + 6*v10 + 7*v11 + 8*v12 2011-05-11 19:25:34 補充： 則 a + k2 >= 0 ---(1) b - (k2 + k1) >= 0 ---(2) (1)+(2）得 a+b >= k1 ---(3) (3)在程式演算中，對縮短複雜度占舉足輕重的角色。 2011-05-11 19:25:50 補充： 你的程式中， a 明明是負數，卻改用正數， 雖在配套上並無不可，但與數學式違逆，略失人性的順勢。 我將它改成直接套用原值，並以稍前導出的（3）佐助， a=-92, b=144 total: 2225869700 match: 27318619 unmatch: 2198551081 spend 1780.156 seconds 2011-05-11 19:38:23 補充： 若非你給的數學式有誤， 早在意見023 已指引出縮減複雜度的方向， 而現在，也以實作證明這個方向是正確的。6524A8F25B63629D
留言列表
