سوال: جمع دو ماتریس اسپارس در حالت فشرده [بایگانی]

quiet_programmer

دوشنبه 15 فروردین 1390, 14:00 عصر

با سلام.

برای اینکه یه ماتریس اسپارس رو فشرده کنی باید از یه ماتریس که از سه تایی row و col و value تشکیل شده استفاده کنی.

کارم رو با مثال پیش میبرم.
فرض کن ماتریس خلوت زیر رو داری

1 0 0 1 0
2 0 1 0 0
0 0 5 0 8
0 0 0 9 0

میخوای فشردش کنی. n رو میگیریم تعدا عناصر غیر صفر در ماتریس خلوت. پس n برابر 7ه.
یه ماتریس n+1*3 تعریف میکنی. در این مثال 3*8
ستون اول میشه row
ستون دوم میشه col
و ستون سوم میشه value
تو سطر اول ماتریس در ستون row تعدا سطرهای ماتریس اصلی رو مینویسی. در اینجا 4
تو سطر اول ماتریس در ستون col تعداد ستونهای ماتریس اصلی رو مینویسی. در اینجا 5
و در سطر اول ستون value تعداد عناصر غیر صفر رو مینویسی در اینجا 7
بعد از سطر دوم به بعد در ستون row سطر و در ستون col ستون و در ستون value به ترتیب سطر عنصر غیر صفر، ستون عنصر غیر صفر و مقدار عنصر غیر صفر رو مینویسی.
به این شکل
Row Col Value
4 5 7
1 2 1
1 5 1
2 3 1
2 5 2
3 1 8
3 3 5
4 2 9

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

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