[問題] 中介數編解碼
看板Prob_Solve (計算數學 Problem Solving)作者tropical72 (藍影)時間12年前 (2012/02/06 03:52)推噓0(0推 0噓 14→)留言14則, 3人參與討論串1/2 (看更多)
下述說明, array index start from 0.
不知道這有沒有明確定義的名詞 < 其實是在排列演算法裡面看到的 >。
現假設一 arr[] = {6,3,4,5,1,2};
中介數 n[i] 代表 arr[i] > arr[j] ( for j>i) 之個數，
白話點，就是元素 a[i] 以右，比 a[i] 還大的個數。
以 n[1] 為例，arr[1] 右邊比 arr[1] 大的數有 2 個， n[1]=2；
n[2] ,arr[2] arr[2] 1 , n[2]=1。
----
這裡做幾個前提假設
a. 假設 array 數值分佈為 [1,n] 或 [0,n-1]
b. 每個數都剛好會出現一次。
問題有三個
1. 有辦法快速知道 n[] 值嗎？ (可接受額外空間)
目前作法是
for(i=0; i<size; ++i)
for(n[i]=0, j=i+1; j<size; ++j)
n[i]+=(arr[j]>arr[i]);
因這動作非常頻繁，不知是否有其他作法？
2. 怎麼再解碼回去？ (可接受額外空間)
若 n[] = {1,0,2,1 } ; 我該怎麼解碼解成
arr[] = {4,5,3,1,2} 或 {3,4,2,0,1}？
const int size=5;
char used[size]={0};
int i, j, cnt;
for(i=0; i<size-1; ++i){
cnt = 0;
for(j=size-1; cnt!=n[i]; --j)
if(used[j]==0) ++cnt;
arr[i] = j, used[j]=1;
}
// 最後還要查一次沒用到的
for(i=0; i<size && used[i]; ++i) ;
arr[size-1] = i;
目前想法也是豬頭想法，只差無限猴子定理沒搬出來做，
不知能否有些技巧？
3. 假設不成立時，中介數之編解碼是否該重新設計？
倘若 假設 a. array 數值分佈為 [1,n] 或 [0,n-1] 不成立，
唯一確定的是 array 元素保證兩兩相異，試問還有什麼技巧可完成？
----
這篇發得很像作業文，但純粹是個人進修卡住，
希望各位先進能不吝給個意見。
懇請不吝賜教，小弟感激不盡。
--
世界上有種，
將 不可能 轉換為 無限可能 的強大力量，
我稱它為 - 信念。
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 123.195.165.40
→
02/06 03:58, , 1F
02/06 03:58, 1F
→
02/06 03:59, , 2F
02/06 03:59, 2F
→
02/06 04:02, , 3F
02/06 04:02, 3F
補上目前使用的程式碼。
※ 編輯: tropical72 來自: 123.195.165.40 (02/06 04:09)
→
02/06 22:59, , 4F
02/06 22:59, 4F
→
02/06 23:02, , 5F
02/06 23:02, 5F
→
02/06 23:02, , 6F
02/06 23:02, 6F
→
02/06 23:06, , 7F
02/06 23:06, 7F
→
02/06 23:08, , 8F
02/06 23:08, 8F
→
02/06 23:09, , 9F
02/06 23:09, 9F
→
02/06 23:13, , 10F
02/06 23:13, 10F
→
02/06 23:17, , 11F
02/06 23:17, 11F
→
02/06 23:26, , 12F
02/06 23:26, 12F
→
02/06 23:30, , 13F
02/06 23:30, 13F
→
02/07 00:12, , 14F
02/07 00:12, 14F
討論串 (同標題文章)
Prob_Solve 近期熱門文章
PTT數位生活區 即時熱門文章
