تبدیل ماتریس به ماتریس اسپارس

[Collector]

سلام
بهترین روش برای تبدیل یک ماتریس به ماتریس اسپارس چیست؟

[مسعود اقدسی فام]

منظورتون بهترین روش ذخیره سازی هستش یا اینکه چطور به اون روش مشهور هر سطر یه عنصر غیرصفر تبدیل کنیم؟

[hafez1]

این روش مشهور کدش چطوری می شه؟

[مسعود اقدسی فام]

این روش مشهور کدش چطوری می شه؟

کدش رو که نمی‌شه بذارم. اما یه ماتریس سه ستونی با n سطر هستش که n تعداد عناصر غیر صفر ماتریسه. هر سطر ماتریس به ترتیب شماره سطر و شماره ستون و مقدار اون عنصر غیر صفر رو نگه می‌داره. در ترتیب عناصر هم اول عناصر سطر اول ماتریس درج می‌شن، بعد سطر دوم و ... یعنی این ماتریس جدید بر اساس ستون اول و بعد ستون دوم مرتب شده هستش.

[hafez1]

این درسته؟


#include<iostream>
#include<conio.h>
using namespace std;
template<class T>
void sTranspose(T b[5][3],T bt[5][3])
{
int i,j,k;
int m=b[0][1];
int t=b[0][2];
bt[0][0]=m;
bt[0][1]=b[0][0];
b[0][2]=t;
k=1;
for(int i=0;i<m;i++)
for(int j=1;j<=t;j++)
if(i==b[j][1])
{
bt[k][0]=b[j][1];
bt[k][1]=b[j][0];
b[k][2]=b[j][2];
k++;
}
}
//*************************************
int main()
{
int i,j,b[5][3],bt[5][3];
//clrscr();
for(int i=0;i<5;i++)
for(int j=0;j<3;j++)
{
cout<<"enter b["<<i<<"]["<<j<<"]";
cin>>b[i][j];
}
sTranspose(b,bt);
cout<<"Transpose of sparse matrix b:\n";
for(int i=0;i<5;i++)
{
for(int j=0;j<3;j++)
{
cout.width(5);
cout<<b[i][j];
}
cout<<"\n";
}
getch();
return 0;
}

[hafez1]

اشتبا شد این برای دترمینانشه!:لبخندساده:

[مسعود اقدسی فام]

این کد بر اساس همون ماتریسی که من گفتم ترانهاده رو حساب می‌کنم. چون وقتی جای سطر و ستون رو عوض می‌کنی اون شرط مرتب بودن عناصر به هم می‌خوره. لازمه از اول مرتب بشه. این کد این عملیات رو انجام می‌ده. یعنی اینجا ماتریس اسپارس به صورتی که من شرح دادم قبلا ساخته شده.
داخل تابع اصلی یه ماتریس پنج سطری و سه ستونی از کاربر دریافت می‌شه. در واقع از کاربر مشخصات ماتریس اسپارس با اون ساختاری که توضیح دادم دریافت می‌شه و نه به شکل ماتریس معمولی که تمامی سطر و ستونها دریافت می‌شن. این ماتریس اسپارس به تابع ارسال می‌شه تا ترانهاده محاسبه بشه.

[مسعود اقدسی فام]

یه نکته یادم رفت بگم. وقتی اونطور ماتریسی ساخته می‌شه سطر اول شامل ابعاد ماتریس و تعداد کل عناصر غیر صفر می‌شه. مثلا اگه سطر اول به صورت 3 4 2 باشه یعنی یه ماتریس دو در چهار با سه عنصر غیر صفر هستش. در ادامه هم سه سطر به صورت شماره سطر، شماره ستون و مقدار، محل و مقدار اون عناصر رو مشخص می‌کنن.


3 4 2
5 3 1
3 2 2
8 4 2


این ماتریس یعنی یه ماتریس خلوت دو در چهار با سه عنصر غیر صفر که در محل‌های 3 1 و 2 2 و 4 2 به ترتیب با مقادری 5 و 3 و 8 قرار دارن.

[hafez1]

:متعجب:بازم اشتباه شد منظورم ایته که این واسه ترانهادشه.

[hafez1]

ینی برای نوشتن کدش من اول باید بیام ببینم کدوم درایه ها صفر نیسن بد بذارمشون توی ماتریس اسپارس؟
سخت می شه.:افسرده:

[مسعود اقدسی فام]

ینی برای نوشتن کدش من اول باید بیام ببینم کدوم درایه ها صفر نیسن بد بذارمشون توی ماتریس اسپارس؟
سخت می شه.:افسرده:

به هر حال یه جوری باید کل ماتریس اسکن بشه که عناصر غیر صفر مشخص بشن. یه راهش می‌تونه این باشه که وقتی داری عناصر درایه رو از ورودی یا فایل می‌خونی به جای اینکه اول همه رو یه ماتریس معمولی ذخیره کنی و بعد بررسی کنی که کدوم غیر صفره، مستقیم به محض دریافت عدد با توجه به اینکه صفره یا نه ازش صرف نظر کنی یا وارد ماتریس با این فرم جدیدی که گفتیم بکنی.
البته یه روش‌های دیگه‌ای هم برای ذخیره کردن ماتریس اسپارس وجود داره. ولی این قسمت رو که باید کل ماتریس رو برای عناصر غیرصفر بگردی معمولا دارن.

[hafez1]

آخه یه مشکلی هس ما از اول نمی دونیم چند تا درایه غیر صفر داریم که از همون اول بریزیمشون توی ماتریس اسپارس.
ینی کارمون دو برابر می شه یه دور وقتی کاربر داره درایه ها رو وارد می کنه بشمریم چند تا غیر صفر داره.بدش بیایم بریزیمشون توی ماتریس اسپارس که دوباره برای این کار باید درایه ها رو باز خوانی کنیم.
این خیلی طولانیه

[hafez1]

اصلا اسپارسو در نظور نگیریم.من کدم همون اول که می خام سطر و ستون رو دلخاه وارد کنه کاربر گیر می ده.
اینم کدم:


#include<iostream>
using namespace std;
int main()
{
int m,n;
cout<<"enter m for satr,n for soton"<<endl;
cin>>m>>n;
int A[m][n]=0;
for(int i=0;i<m;i++)
for(int j=0;j<n;j++)
{
cin>>A[i][j];
}
}

[مسعود اقدسی فام]

اصلا اسپارسو در نظور نگیریم.من کدم همون اول که می خام سطر و ستون رو دلخاه وارد کنه کاربر گیر می ده.
اینم کدم:


#include<iostream>
using namespace std;
int main()
{
int m,n;
cout<<"enter m for satr,n for soton"<<endl;
cin>>m>>n;
int A[m][n]=0;
for(int i=0;i<m;i++)
for(int j=0;j<n;j++)
{
cin>>A[i][j];
}
}


اولا اکثر کامپایلرها اجازه نمی دن اندیس آرایه در زمان تعریف یه متغیر باشه. ثانیا یعنی برابر صفر قرار دادنش معنی نداره. باید {0} باشه که تمام عناصر رو صفر می کنه.

[Collector]

این برنامه برای تولید ماتریس اسپارس درسته؟

void SetRandomSparse()
{
//***** Set Random Sparse ***********************
for (i=0; i<Num; i++)
{
for (j=0; j<Num; j++)
{
Sparse[i][j]= 0;
}
}

for (i=0; i<Num; i++)
{
Sparse[rand()%Num][rand()%Num]= rand()%10;
}
return;
}

[مسعود اقدسی فام]

آره تولید می‌کنه. واسه یه ماتریس n‌ در n فقط n تا عنصر غیر صفر داری. البته اون یاقیمانده رندم بر ده رو با یک جمع کن. چون ممکنه خود رندم صفر بشه. با یک جمعش کن که مطمئن شی صفر نیست نتیجه. مگه اینکه بحث حداکثر n عنصر باشه که همین کد درسته.
برای تولید رندوم درست هم srand فراموش نشه.

[Collector]

آره تولید می‌کنه. واسه یه ماتریس n‌ در n فقط n تا عنصر غیر صفر داری. البته اون یاقیمانده رندم بر ده رو با یک جمع کن. چون ممکنه خود رندم صفر بشه. با یک جمعش کن که مطمئن شی صفر نیست نتیجه. مگه اینکه بحث حداکثر n عنصر باشه که همین کد درسته.
برای تولید رندوم درست هم srand فراموش نشه.

این دو برنامه برای این دو تا سوال درسته؟
1- یک ماتریس دلخواه بسازد و نمایش دهد.
2- ماتریس ذخیره سازی اسپارس را نمایش دهد.

سوال اول:

void SetRandomSparse()
{
//***** Set Random Sparse ***********************
for (i=0; i<Num; i++)
{
for (j=0; j<Num; j++)
{
Sparse[i][j]= 0;
}
}

for (i=0; i<Num; i++)
{
Sparse[rand()%Num][rand()%Num]= rand()%10+1;
}

//***** Print Sparse ******************************
cout<<endl<<"Print Sparse:"<<endl<<endl;

for (i=0; i<Num; i++)
{
for (j=0; j<Num; j++)
{
cout<<" "<<Sparse[i][j];
}
cout<<endl<<endl;
}
return;
}


سوال دوم:
برای سوال دوم از همان روش که سطر اول برای تعداد سطر و ستون و تعداد غیر صفرها
و بقیه سطر ها مختصات و مقدار غیر صفر را نمایش میدهد استفاده کردم.

void PrintStoreSparse()
{
for (i=0; i<Num+1; i++)
{
for (j=0; j<Num; j++)
{
StoreSparse[i][j]= 0;
}
}

int r = 0;
StoreSparse[r][0] = Num;
StoreSparse[r][1] = Num;
StoreSparse[r][2] = Num;

for(int i=0; i<Num; i++)
{
for(int j=0; j<Num; j++)
{
if(Sparse[i][j] != 0)
{
r++;
StoreSparse[r][0] = i;
StoreSparse[r][1] = j;
StoreSparse[r][2] = Sparse[i][j];
}
}
}

//***** Print Store Sparse ***********************
cout<<endl<<"Print Store Sparse:"<<endl<<endl;

for (i=0; i<Num+1; i++)
{
for (j=0; j<Num-1; j++)
{
cout<<" "<<StoreSparse[i][j];
}
cout<<endl<<endl;
}
}

[مسعود اقدسی فام]

در کل درسته. فقط اجرا کردی برنامه‌ها رو؟

مثلا دو حلقه آخر که اسپارس رو جاپ می‌کنه j فقط صفر و یک و دو می‌تونه باشه. وابسته به Num نیست.

[Collector]

در کل درسته. فقط اجرا کردی برنامه‌ها رو؟

مثلا دو حلقه آخر که اسپارس رو جاپ می‌کنه j فقط صفر و یک و دو می‌تونه باشه. وابسته به Num نیست.

خوب اگر بیام شرط حلقه را کوچکتر از 3 قرار بدم درسته؟
بله برنامه را اجرا کردم فقط میخوام ببنیم منطق برنامه درسته؟ و بعدا مشکل پیش نمیاد؟

[مسعود اقدسی فام]

خوب اگر بیام شرط حلقه را کوچکتر از 3 قرار بدم درسته؟
بله برنامه را اجرا کردم فقط میخوام ببنیم منطق برنامه درسته؟ و بعدا مشکل پیش نمیاد؟

آره درست می شه.

وقتی برنامه رو نوشتید، چند بار با ورودی های مختلف اجرا کنید و ببینید خروجی مطلوب می ده یا نه.