PDA

نسخه کامل مشاهده نسخه کامل : ماتريس هاي اسپارس و نوشتن برنامه هاي آنها



array_matrix
27-10-2005, 14:13
ol: در زبان پاسکال برنامه ای بنویسید که :جمع و تفریق دو ماتریس اسپارس را انجام دهد. (باید در ابتدا ماتریس ها را از روش نامنظم تبدیل به ماتریس های بدون صفر کند و سپس اینکار را انجام دهد.)
قبلا از پاسخ سریع شما تشکر می کنم

poldarmisham
17-06-2007, 22:52
در مورد ماتریس اسپارس نیاز به مطلب دارم.
البته برنامه های این ماتریس را دارم فقط در مورد خود این ماتریس اطلاعات میخوام
ممنون میشم اگه کمک کنید

barajini
18-06-2007, 00:51
man koja chejori algoritmhaye barnamehaye sakhteman dade ro peyda konam komaaaaaaaaaaaaaaaak

rezapazahr
25-06-2007, 02:16
سلام

من تا حدودي با ماتريس اسپارس آشنايي دارم

ماتريس اسپارس ماتريسيه كه داده هاي معتبر (داده معتبر همون 1 است) در اون قرار ميگيرن

اما سئوال:

اساسا اين ماتريس بدرد چي ميخوره ؟
براي پاسخ به اين سئوال اول اين سئوال رو بايد جواب دادكه:
مگه كلا از يه ماتريس براي چه كارهايي استفاده ميكردن؟خوب معلومه براي ذخيره موقتي يه سري داده ها


داده هايي كه ازش صحبت ميكنيد چه داده هايي هستن؟
هر مجموعه داده كه قراره مورد پردازش قرار بگيرن ميتونه منظور ما باشه ولي قطعا بايد تعداد داده هاي غير معتبرش خيلي بيشتر از داده هاي معتبرش باشن تا اجازه ورود به ماتريس اسپارس رو داشته باشن.

براي اينكه مطلب بهتر جا بيفته يك مثال ميزنم :

فرض كنيد از شما بخوان اطلاعات يه برگه a4 رو كه تنها يه خط كوچيك توش كشيده شده رو وارد رايانه كنيد
قطعا شما براي اينكار از ساختمان داده ماتريس دو بعدي براي قرار دادن و ذخيره كردن اطلاعات برگه استفاده ميكنيدكه اون ماتريس بايد ماتريس اسپارس باشه

(منظور از دادههاي برگه اينه كه اگه ما صفحه برگه رو يه ماتريس دو بعدي فرض كنيم داده هاي معتبر اون نقاطي هستن كه با قلم شما سياه شدن و تشكيل به خط تو اون صفحه دادن.پس هر نقطه يه داده معتبره تو اون صفحس كه در كنار بيشمار داده غير معتبر قرار گرفته (نقاط سفيد دست نخورده)(كه تو رايانه داده معتبر 1 وداده غير معتبر0 معرفي ميشه))


اما چرا از ماتريس دو بعدي معمولي براي ذخيره سازي داده ها استفاده نميكنيم؟

چون ماتريس دو بعدي معمولي توش هم داده معتبر و هم داده غير معتبر قرار ميگيره (اگه برگرديم به همون مثالي كه زدم داده هاي بيشمار غير معتبر 0 و دادههاي اندك 1 مال برگه آ4 تو اين ماتريس قرار خواهند گرفت)كه همان طور كه ميدانيم داده هاي غير معتبر رو دليلي نداره تو پردازش هايي كه قراره بعدا با دادهاي ماتريس داريم شركت بديم(به دليل اتلاف وقت و حافظه اي كه اين داده هاي غيرمعتبر تو پردازش هامون دارن)

پس از اون جاييكه روز به روز الگوريتم هاي بهينه(الگوريتم هايي كه سريعتر اجرا ميشن و كمتر فضا اشغال ميكنن)جاي الگوريتم هاي قبلي رو ميگيرن پس به جاي نگه داري داده ها از ماتريس اسپارس به جاي ماتريس دو بعدي معمولي استفاده ميكنيم

تكرار ميكنم كه :
از اين ماتريس زماني استفاده ميشه كه داده هاي غير معتبرت خيلي بيشتر از داده هاي معتبرت باشن يعني اگه از ما سئوال كردن از چه ساختمان داده اي براي نگه داري داده هاي يه عكس(كه بسيار داده معتبر داره) استفاده بايد كرد ؟

ميگيم ماتريس دو بعدي نه ماتريس اسپارس چرا كه داده هاي غير معتبر يه عكس خيلي بيشتر از داده هاي معتبرش نيست كه بياييم از ماتريس اسپارس استفاده كنيم.

اما اين سئوال پيش مياد كه ساز وكار ماتريس اسپارس چيه؟
جواب:اين ماتريس مياد جاي اون داده معتبر رو پيدا ميكنه (سطر وستون داده هاي معتبر رو)به همراه مقدار داده (كه ميتونه 1 باشه يا هر عددي باشه)و سطر و ستون ومقدار اون داده رو تو خودش قرار ميده

نكته:
اين ماتريس سه ستون داره و به تعداد داده هاي معتبر سطر داره .

باز براي روشنتر شدن مطلب به مثال خودمان بر ميگرديم
براي قرار دادن داده هاي برگه آ4 ماتريس اسپارس مياد سطر و ستون داده معتبر رو پيدا ميكنه و به همراه خود داده مياد و اون ها رو به ترتيب داخل سطر اول ستون اول و سطر اول و ستون دوم و سطر اول ستون سوم خودش قرار ميدهدو باز براي داده بعدي سطر و ستون و خود داده بعدي رو به ترتيب تو سطر دوم ستون اول و سطر دوم ستون دوم و سطر دوم ستون سوم قرار ميدهد وبراي داده هاي بعدي هم همين كار ها رو انجام ميدهد تا كليه داده ها وارد رايانه شوند


اما پياده سازي الگوريتم ماتريس اسپارس:

كافيست حلقه اي در برنامه مان قرار داده وتو اون هر بار يه داده رو از ماتريس دو بعدي اي كه قبلا از كاربر گرفته شده بگيريم وسطر وستون و خود داده رو تو ماتريس اسپارسي كه از قبل به تعداد سه ستون و به تعداد مورد نظر داده ها سطردار براي سيستم تعريف كرده ايم قرار دهيم و اين حلقه رو تا زماني تكرار كنيم كه ديگر داده اي در ماتريس از قبل پر شده نداشته باشيم

اما اين سئوال پيش مياد كه اون ماتريسي اسپارسي كه قراره وسط برنامه تعداد سطراش مشخص بشه چطور اول برنامه تعداد سطراشو براي سيستم معرفي كنيم؟(نميشه بگيم ماتريسمون يه سطر يا دو و يا فلان مقدار سطر داره چرا كه برنامه مان بايد جامع باشه (نه فقط براي حالات خاص اجرا بشه) ونيز نميتونيم بگيم ماتريسمون n تا سطر داره چرا كه وقتي كامپايلر(مفسر) به n رسيد ميگه n ديگه چيه؟(چون هميشه جاي مقدار سطر عدد قرار ميگيره نه متغير))
پس براي رفع اين مشكل چه كار بايد كرد؟

كافيست از تابع malloc براي اينكار استفاده كنيد تا مشكل حل بشوديعني بنويسيم:

((new= (int*)malloc(sizeof(int* (البته در زبان c)

كه خود اين تابع مياد به تعداد سطر هاي مورد نياز برنامه از سيستم حافطه ميگيره و مشكل مشخص نبودن تعداد سطرهاي ماتريس اسپارس رو برامون حل ميكنه


انشاءالله از مطالبي كه براتون نوشتم راضي بوده باشيد.

اگه باز با مشكلي برخورديد باهام در ميون بذاريد.

ياحق.