PTT數位生活區 / Prob_Solve (計算數學 Problem Solving)

Re: [問題] N數列插隊的問題

看板Prob_Solve (計算數學 Problem Solving)作者 (喲)時間14年前 (2010/04/04 01:14), 編輯推噓3(3推 0噓 27→)
留言30則, 3人參與, 最新討論串2/2 (看更多)
※ 引述《ptthidebear (= =)》之銘言： : 其實我也不知道標題打這樣對不對...Orz : 我的問題如下 : 假設有兩個數列 A = {a1, a2} : B = {b1, b2} : 如果我要數列A不動，數列B插入到數列A裡面 : 且插入後B原本的順序不會改變，即： : 可能的數列為 {b1, b2, a1, a2} : {b1, a1, b2, a2} : {b1, a1, a2, b2} : {a1, b1, b2, a2} : {a1, b1, a2, b2} : {a1, a2, b1, b2} : 以上簡單舉的範例，實際上數列的數目，甚至數列內的元素都可能更多 : 我有點卡關了關於這個問題， : 不知道板上的大大有沒有辦法幫忙我...Orz : 順便一問，這個問題算是排列問題還是組合問題呀@@? 看解題方式決定是排列問題或組合問題. 看起來是排列問題, 但若我先看 A 間隙構成的一系列位置為 {1,2,3}, 將 B 兩個元素放在 1 2 3 三個位置的其中兩個,並且 B 兩個元素保持順序, 則可以將問題看成是從 {1,2,3} 中取出兩項的組合. 這樣就是組合問題了. 並且是取重覆數字的組合. 重覆數字表示兩個以上的元素插入同一間隙位置. 而處理這個組合問題,程式就是算盤移珠式的處理法了. -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 59.112.228.65 ※ 編輯: yauhh 來自: 59.112.228.65 (04/04 01:16)
推
04/04 14:18, , 1F
我想請問一下如果元素個數和數列個數都是變數要怎處理
04/04 14:18, 1F
→
04/04 14:19, , 2F
感謝大大願意回我的問題Orz
04/04 14:19, 2F
用快一點的講法回答這個問題,先想有一個函數處理插入幾個元素到一個數列: insert(B[n], A[m]) 這是把 n 個 B 項目插入 A 數列, A 數列有 m 個項目. 函數輸出是一大堆組合情況: insert(B[2], A[2]) ==> { b1, b2, a1, a2 }, { b1, a1, b2, a2 }, { a1, b1, b2, a2 }, { b1, a1, a2, b2 }, { a1, b1, a2, b2 }, { a1, a2, b1, b2 } 這個函數做法用 {1,2,3} 取其中兩項並可重覆的組合,依序將 b1 b2 填入兩項位置, 例如,取出的其中一種組合是 {1,3}, 就把 b1 放在 {1} 位置, b2 放在 {3} 位置. 然後把 a1 放在 {1} {2} 位置中間, a2 放在 {2} {3} 位置中間. 哎呀,講得很模糊,看個意思就好. 已知有這個 insert 函數,要把幾個數列合併,就是下列遞迴規則: combine(L[s]) // L[s] = L1, L2, L3,... , Ls 1. if s = 1, result = L1 2. Else, // s > 1 3. R[k] = insert(L2, L1) // R[k] = R1, R2, R3,... , Rk 4. T3[?] = combine(M3[s-1]) // M3[s-1] = R1, L3, L4,... , Ls 5. T4[?] = combine(M4[s-1]) // M4[s-1] = R2, L3, L4,... , Ls 6. T5[?] = combine(M5[s-1]) // M5[s-1] = R3, L3, L4,... , Ls ... ... 3+k. Tk[?] = combine(Ms[s-1]) // Ms[s-1] = Rk, L3, L4,... , Ls 4+k. result = T[k-2] // T[k-2] = T3[?], T4[?], T5[?],... , Tk[?] 符號系統是我自己定的,慢慢看. ※ 編輯: yauhh 來自: 59.112.230.231 (04/04 17:58)
推
04/04 18:10, , 3F
感謝您!!! 我會好好消化一下的!!!
04/04 18:10, 3F
→
04/04 18:15, , 4F
我想請問一下,如果只有s=2的話 應該也只要insert即可?
04/04 18:15, 4F
→
04/04 18:16, , 5F
那這樣我可以把s=2列為終止條件嗎@@?
04/04 18:16, 5F
→
04/04 19:16, , 6F
s=2是只做一步insert就好. 嗯,這也是遞迴的一個底.
04/04 19:16, 6F
→
04/04 21:05, , 7F
是不是處理這類的問題記憶體的loading都會必然的重呀?
04/04 21:05, 7F
→
04/04 21:08, , 8F
用loading形容記憶體? 我假設你是說需要大量記憶體好了:不會
04/04 21:08, 8F
→
04/04 21:25, , 9F
假設要排的單位是一個結構 且要排的數列一多呢...@@?
04/04 21:25, 9F
→
04/04 21:26, , 10F
因為感覺排出來的可能結果會很多 每種結果都要存
04/04 21:26, 10F
→
04/04 21:51, , 11F
loading看情況吧,如果你要抓所有的排列放在一組資料結構,
04/04 21:51, 11F
→
04/04 21:51, , 12F
當然要用到空間. 如果只是印出來當然會省空間.
04/04 21:51, 12F
→
04/04 21:53, , 13F
聰明一點做個graph減少複製許多重複的數值空間.
04/04 21:53, 13F
→
04/04 22:02, , 14F
我想不到什麼情況非把所有組合留在記憶體裡，能舉例一下嗎?
04/04 22:02, 14F
→
04/04 22:04, , 15F
喔喔~我是指運算的過程中@@" 最後印出來前應該都要先
04/04 22:04, 15F
→
04/04 22:05, , 16F
放在記憶體內吧~ 我的意思是這樣
04/04 22:05, 16F
→
04/04 22:06, , 17F
另外我說的結構是指 每個元素都是結構 @@"
04/04 22:06, 17F
→
04/04 22:38, , 18F
所以反過來說，如果能夠立刻印出來，就可以省下記憶體囉 :p
04/04 22:38, 18F
→
04/04 22:49, , 19F
嗯嗯...Orz 我想請教insert()裡面是C的m+1取n的問題嗎
04/04 22:49, 19F
→
04/04 23:54, , 20F
我現在是insert()有點卡關了orz...它應該也是遞迴吧?
04/04 23:54, 20F
→
04/04 23:57, , 21F
其實我覺得換個方式比較好寫，準備一個 m+n 的陣列，把 A 所
04/04 23:57, 21F
→
04/04 23:58, , 22F
有組合放進去，空白的補上 B
04/04 23:58, 22F
→
04/05 00:26, , 23F
yauhh大大講的insert方法我大致了解 只是不太懂實做
04/05 00:26, 23F
→
04/05 00:27, , 24F
它跟tkcn大您說的方法 有差嗎@@?
04/05 00:27, 24F
→
04/05 00:32, , 25F
我說的方法是只管把 A 插入空白陣列
04/05 00:32, 25F
→
04/05 09:48, , 26F
ok,一般語言真是不好寫,如果用Prolog就很普通...
04/05 09:48, 26F
→
04/05 09:49, , 27F
想不到什麼情況要把組合留在記憶體?一般函數語言就是這樣啊
04/05 09:49, 27F
→
04/05 09:49, , 28F
並不是所有的程式只是像練習題那樣印一印就算了
04/05 09:49, 28F
→
04/05 09:50, , 29F
物件導向語言做起來是把資料留在物件實體中,這也是.
04/05 09:50, 29F
insert(B[3],A[2])是先準備k個長度5陣列,k是重覆的C(3,3)扣除後項數字小於前項 的數目,5是A,B項目總數. B三項要填到哪些位置也是要做一下C(3,3),從{1,2,3}取 可重覆的三個數字並扣除後項數字小於前項的情況. 在寫insert函數之前,要先寫C(M,N)的組合與總數,扣掉後項數字小於前項,並檢查 M<N時也得到正確結果. 接下來的問題是把B,A填入長度5陣列,程序是先看B有哪些填入{1}位置,都一個一個填 入長度5陣列,然後把A第一項加在之前填入項的後面,然後看B有哪些填入{2}位置, 一個一個填入,然後把A第二項加在之前填入項的後面,然後把B填入{3}位置的項目填入. insert函數會由C(3,3)產生k個B填入的組合,例如{1,1,1},{1,1,2},{1,1,3},{1,2,2}, {1,2,3},... 根據k種組合不同的情況,把A[2],B[3]混合複製到k個長度5陣列. ※ 編輯: yauhh 來自: 59.112.230.231 (04/05 10:22)
推
04/05 16:48, , 30F
Thanks~ 待我好好消化 XD
04/05 16:48, 30F
‣ 更多 yauhh 的文章
文章代碼(AID): #1BjtThIm (Prob_Solve)
討論串 (同標題文章)
本文引述了以下文章的的內容：
完整討論串 (本文為第 2 之 2 篇)：
排序： 最舊先 | 最新先 | 留言數
在新視窗開啟完整討論串 (共2篇)
Prob_Solve 近期熱門文章
更多 近期熱門文章 >>
PTT數位生活區 即時熱門文章
更多 即時熱門文章 >>
‣ 更多 yauhh 的文章
文章代碼(AID): #1BjtThIm (Prob_Solve)