a[5][4]={{1,2,3,6},
{4,3,1},
{5,4,1,2},
{3,5},
{3,4}};
要怎麼壓縮各列的矩陣變為
b[3][4]={{1,2,3,6},
{4,3,1,5},
{5,4,1,2}};
我們要將原陣列壓縮
第一行為1236
第二行為431發現無法存到1236裡，
所以431再存一列，而發現它還有一個空位可以放一個元素
第三行為5412但上面任一列都沒有5412可以納入所以再開一列
第四行為35，發現第二行可以存變為4315所以跟第二行合併
第五行為34 ，發現4315有了，所以又跟第二行合併
就是該怎麼比較一列一列的陣列呢?
想很久還是想不太出來..
已邀請的邦友 {{ invite_list.length }}/5
如果數字是 0 到 9 ，或是有限的
那麼集合的判斷可以用這個方法
if
#include <stdio.h>
#include <string.h>
#include <stdarg.h>
#include <stdint.h>
#define DATA_LENGTH 5
typedef struct{
int length; //儲存幾個數字
int buf[4];
unsigned mask;
} set;
void setDatas(set* p, int n, ...);
void showSetArray(int n,set **arr);
int main()
{
set database[DATA_LENGTH];
set *arr[DATA_LENGTH];
int i,j,n=DATA_LENGTH,k,count;
unsigned mask;
//因為最多只有 1024 種組合，可以利用查表加速
//下面這個陣列可以查 mask 位元不為 0 的數量是否 <= 4
//即(bit_count[mask/32]&1<<mask%32)若為 true 代表可合併
uint32_t bit_count[]={
0x7fffffff,0x177fffff,0x177f7fff,0x01571fff,
0x177f7fff,0x77d77f7f,0x01d73fff,0x0061ffdf,
0x77ff7fff,0x77df577f,0x0177ff7f,0x76c7639f,
0x0117177f,0x76c76bd7,0x76c76bbf,0xb86d0d85,
0x177f7fff,0x015717ff,0x0117177f,0x004119f7,
0x0177ffff,0x0061ff1f,0x0061ffdf,0x76c6ca21,
0xcfd77fff,0xffffffff,0x76c76bbf,0x76c66cad,
0x004119f7,0x0060ff95,0x00401a4b,0x004019f0
};
//測試資料
setDatas(database+0,4,1,2,3,6);
setDatas(database+1,3,4,3,1);
setDatas(database+2,4,5,4,1,2);
setDatas(database+3,2,3,5);
setDatas(database+4,2,3,4);
//用指標指向每一列，方便操作
//(刪除、移動時減少記憶體的讀寫量)
for(i=0;i<DATA_LENGTH;++i)
arr[i]=database+i;
//顯示測試資料(初始狀態)
printf("initial:\n");
showSetArray(n,arr);
printf("-------------\n\n");
//開始壓縮
for(i=1;i<n;++i)
{
//子集合處理
k=0;
for(j=0;j<i;++j)
{
//利用位元運算判斷誰是誰的子集合
mask=arr[i]->mask|arr[j]->mask;
if(mask==arr[j]->mask)
{// i 為 j 的子集, 刪除 i
memmove(arr+i,arr+i+1,(--n-i)*sizeof(*arr));
--i;
k=1;
break;
}
if(mask==arr[i]->mask)
{// j 為 i 的子集, 用 i 取代 j
arr[j]=arr[i];
memmove(arr+i,arr+i+1,(--n-i)*sizeof(*arr));
--i;
k=1;
break;
}
}
if(k)
continue;
//如果不存在子集合關係，嘗試合併集合
for(j=0;j<i;++j)
{
if(arr[j]->length>=4)
continue;
//聯集後，計算有幾個不為0的位元，即為合併後所需空間
mask=arr[i]->mask|arr[j]->mask;
/*
for(count=k=0;k<10;++k)
if(1<<k&mask)
++count;
if(count>4)//合併後會超過
continue;
*/
//查表加速，等同於上面註解掉的程式碼
if(~bit_count[mask/32]>>mask%32&1) //合併後會超過
continue;
//合併後不會超過的話執行以下程序合併
for(k=0;k<arr[i]->length;++k)
{
mask=1<<arr[i]->buf[k];
if(!(mask&arr[j]->mask))
{
arr[j]->mask|=mask;
arr[j]->buf[arr[j]->length++]=arr[i]->buf[k];
}
}
memmove(arr+i,arr+i+1,(--n-i)*sizeof(*arr));
--i;
break;
}
}
//顯示結果
printf("result:\n");
showSetArray(n,arr);
printf("-------------\n\n");
return 0;
}
void setDatas(set* p, int n, ...)
{
int x;
p->length=0;
va_list args;
va_start(args,n);
p->mask=0;
while(n--)
{
x=va_arg(args,int);
p->buf[p->length++]=x;
p->mask|=1<<x;
}
va_end(args);
}
void showSetArray(int n,set **arr)
{
int i,j;
for(i=0;i<n;++i)
{
printf("%02X ",arr[i]->mask);
for(j=0;j<arr[i]->length;++j)
printf(" %d%c",arr[i]->buf[j],arr[i]->length-1==j?'\n':',');
}
}
不過他的資料是 {4,3,1} {3,5}
所以其實 SetB 不屬於 SetA
如果不存在子集合的關係
就判斷 SetA | SetB 不為 0 的位元數
如果在 4 以內，則表示可以合併
程式碼補上了
你的程式唯一的問題是
使用了許多老師還沒教到的進階語法
沒法子跟老師解釋
您的解法好厲害
for(count=k=0;k<10;++k)
if(1<<k&mask)
++count;
if(count>4)//合併後會超過
continue;
這段程式看懂了，但查表的地方不太清楚邏輯，可以解說嗎 >"<?
因為 mask 全部的狀況是 1024 種
可以事先計算每種狀況是否不超過 4 個 bit 被設為 1
一開始直觀的想法是用 int bit_array[1024]; 去儲存這1024種狀況
int bit_array[1024],i;
for(i=0;i<1024;++i)
if(i 不超過 4 個 bit 是 1)
bit_array[i]=1;
else
bit_array[i]=0;
但是每個整數只會儲存 0 跟 1 而已
因此為了避免浪費空間，可以以一個 bit 代表一組資料
這時需要 1024 位元的儲存空間
(每個 uint32_t 有 32 個位元，共有 32 個 uint32_t，合計 1024 bit)
這是目前想到的直覺想法
如果有更好的方法再請求各路大神提供了 > <
表達能力還有待加強請見諒 
方法：
除第一列外的每一列都從第一列開始比對元素
如果第一列不包含的該列元素個數多於第一列的空位數，就再往下一列去做比對
如果第一列不包含的該列元素<=第一列的空位數，
就將第一列原本不包含的那幾個元素加入第一列，並移除已經合併的該列
如果在找到該列位置之前都沒有符合條件可以塞進去的列
那就表示該列會自成一列，那就接著將下一列從第一列開始比對，再重複上面的比對動作
column = 4
for (i = 1 ~ (Array.size - 1)){
for ( j = 0 ~ (i - 1)){
if ((num of elements that not in Array[j]) > (column-Array[j].size)){
j++
if (j = i) i++
}
else {
add (elements that not in Array[j]) to Array[j]
remove Array[i]
Array.size - 1
break
}
}
}
以你的例子來說就是
從第一列開始找，找到第 2 列發現元素不滿 4 個
就將第 2 列 {4,3,1} 從第一列 {1,2,3,6} 開始比對元素
發現不包含的元素(也就是 4)個數是 1 > 第一列的空位個數 0，
因此在第 2 列之前沒找到符合條件可以塞進去的，所以自成一列，
接著將第 3 列 {5,4,1,2} 從第一列 {1,2,3,6} 開始比對，
發現不包含的元素(5,4)個數 2 > 第一列空位 0，
因此往下跟第 2 列 {4,3,1} 做比對，發現不包含的元素(5,2)個數 2 > 第2列的空位數 1 ，
因此在第 3 列之前沒有符合的，所以自成一列
接著將第 4 列 {3,5} 從第一列 {1,2,3,6} 開始比對，
發現不包含的元素(5)個數是 1 > 第一列的空位個數 0，
因此往下跟第 2 列 {4,3,1} 做比對，發現不包含的元素(5)個數 1 = 第2列的空位數 1 ，
因此將 5 加入第 2 列，並且移除第 4 列。
接著將現在的第 4 列 (也就是原本的第 5 列) {3,4} 從第一列 {1,2,3,6} 開始比對，
發現不包含的元素(4)個數是 1 > 第一列的空位個數 0，
因此往下跟第 2 列 {4,3,1,5} 做比對，發現不包含的元素個數 0 = 第2列的空位數 0 ，
將不包含的元素加入(這次沒有不包含的元素)，移除第 4 列。
我去下載了
Pelles C (http://www.pellesc.de/)
同大家的想法,只是純C寫要寫比較多而已...
寫一個比較蠢的實例供參考
#include <stdio.h>
int InList(char a, char x[4])
{
int k;
for (k = 0; k < 4; k++)
{
if (a == x[k])
return 1;
}
return 0;
}
int GetCount(char x[4])
{
int k;
for (k = 0; k < 4; k++)
{
if (x[k] == 0)
return k;
}
return 4;
}
int GetSpace(char x[4])
{
return (4 - GetCount(x));
}
void Compress(char t[4], char x[4])
{
int i, k;
for (i =0; i < 4; i++)
{
if (t[i] == 0)
break;
if (InList(t[i], x))
t[i] = 0;
else
{
x[GetCount(x)] = t[i];
for (k = i; ++k < 4;)
{
t[k-1] = t[k];
if (t[k] == 0)
break;
}
i--;
}
}
}
void ShowArray(char a[5][4])
{
int i, j;
for (i = 0; i < 5; i++)
{
printf("a[%d]=", i);
for (j = 0; j < 4; j++)
printf("%c%d", (j==0)?'{':',', a[i][j]);
printf("}\n");
}
}
int main(int argc, char *argv[])
{
char a[5][4]={
{1,2,3,6},
{4,3,1,0},
{5,4,1,2},
{3,5,0,0},
{3,4,0,0}
};
int i, j, k;
int count, need;
printf("Origin:\n");
ShowArray(a);
for (i = 1; i < 5; i++)
{
for (j = 0; j < i; j++)
{
k = 0;
need = 0;
count = 0;
for (k = 0; k < 4; k++)
{
if (a[i][k] == 0)
break;
if (InList(a[i][k], a[j]))
count++;
else
need++;
}
if (need > 0)
{
if (need <= GetSpace(a[j]))
{
Compress(a[i], a[j]);
}
}
else if (count == GetCount(a[i]))
{
while (k > 0)
a[i][--k] =0;
}
}
}
printf("Compressd:\n");
ShowArray(a);
return 0;
}
請不要選我正解
用C寫的，我的做法比較直覺，二維轉一維，再轉回二維。
arr1即是答案
#include<stdio.h>
#include<stdlib.h>
int main()
{
char temp[100] = {'\0'};
int arr1[5][4];
int arr2[5][4] = {
{ 1,2,3,6 },
{ 4,3,1 },
{ 5,4,1,2 },
{ 3,5 },
{ 3,4 }
};
for (int i = 0; i < 5; i++)
{
for (int j = 0; j < 4; j++)
{
if(arr2[i][j]==0)
sprintf_s(temp, "%s%c", temp, 'x');
else
sprintf_s(temp, "%s%d", temp, arr2[i][j]);
}
}
int row = 0, column = 0;
for (int count = 0; count < 100; count++)
{
if (temp[count] != 'x')
{
if (column == 4)
{
column = 0; row++;
}
if (row == 5)
break;
arr1[row][column] = temp[count] - 48; //char to int
column++;
}
}
system("pause");
return 0;
}
iThome鐵人賽
看影片追技術