ماتریس چند بعدی به خطی 1

[hercool]

سلام دوستان
دارم رو تمرین اخر فصل دروس ساختمان داده کار می کنم یه خورده گیج کننده است
راهنمایی می خوام
سوال :
فرض کنید یک ماتریس پایین مثلثی مثل a را بخواهیم با یک ارایه یک بعدی مثل b نمایش بدهیم اگر هر عضو A[i][J] معادل عنصر B[L]باشد بین i,j و L چه رابطه ای باید برقرار باشد.

http://www.img4up.com/up2/40493012631291.gif
حل:فرض کنید بخواهیم آرایه مثلثی A را که در زیر ارائه شده در حافظه کامپیوتر ذخیره کنیم .واضح است که ذخیره درایه های بالای قطر اصلی A کاری بیهوده است چون میدانیم تمام این عناصر صفر هستند از این رو تنها درایه های دیگر A را در ارایه خطی ذخیره می کنیم یعنی قرار می دهیم:

http://www.img4up.com/up2/8531192216401445.gif

نخست ملاحظه می کنید که B شامل:

http://www.img4up.com/up2/0165069111513145.gif

عنصر است . از انجا که در برنامه های خود مقدار http://www.img4up.com/up2/48583435413489.gif را احتیاج خواهیم داشت از این رو فرمولی را به دست می اوریم که عدد صحیح L را بر حسبب I و J معین کند که در ان :

http://www.img4up.com/up2/035031411105718.gif

ملاحظه می شود که L تعداد عناصر داخل لیست تا http://www.img4up.com/up2/48583435413489.gif و خود را نمایش میدهد اکنون تعداد :

http://www.img4up.com/up2/607260773142426.gif

عنصر در سطر بالای http://www.img4up.com/up2/48583435413489.gif وجود دارد و عنصر در سطر I وجود دارد که حداکثر تا http://www.img4up.com/up2/48583435413489.gif و خود http://www.img4up.com/up2/48583435413489.gif را شامل است .بنابراین :

http://www.img4up.com/up2/471482233447.gif


سوالاتم اینجاست که :
منظور فقط بالای قطر اصلی است که اعداد صفر هستند؟
دوم نسبت ها رو چجوری بدست اورده ؟مثلا

http://www.img4up.com/up2/607260773142426.gif

[hercool]

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

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

سلام دوستان
دارم رو تمرین اخر فصل دروس ساختمان داده کار می کنم یه خورده گیج کننده است
راهنمایی می خوام
سوال :
فرض کنید یک ماتریس پایین مثلثی مثل a را بخواهیم با یک ارایه یک بعدی مثل b نمایش بدهیم اگر هر عضو A[i][J] معادل عنصر B[L]باشد بین i,j و L چه رابطه ای باید برقرار باشد.

http://www.img4up.com/up2/40493012631291.gif
حل:فرض کنید بخواهیم آرایه مثلثی A را که در زیر ارائه شده در حافظه کامپیوتر ذخیره کنیم .واضح است که ذخیره درایه های بالای قطر اصلی A کاری بیهوده است چون میدانیم تمام این عناصر صفر هستند از این رو تنها درایه های دیگر A را در ارایه خطی ذخیره می کنیم یعنی قرار می دهیم:

http://www.img4up.com/up2/8531192216401445.gif

نخست ملاحظه می کنید که B شامل:

http://www.img4up.com/up2/0165069111513145.gif

عنصر است . از انجا که در برنامه های خود مقدار http://www.img4up.com/up2/48583435413489.gif را احتیاج خواهیم داشت از این رو فرمولی را به دست می اوریم که عدد صحیح L را بر حسبب I و J معین کند که در ان :

http://www.img4up.com/up2/035031411105718.gif

ملاحظه می شود که L تعداد عناصر داخل لیست تا http://www.img4up.com/up2/48583435413489.gif و خود را نمایش میدهد اکنون تعداد :

http://www.img4up.com/up2/607260773142426.gif

عنصر در سطر بالای http://www.img4up.com/up2/48583435413489.gif وجود دارد و عنصر در سطر I وجود دارد که حداکثر تا http://www.img4up.com/up2/48583435413489.gif و خود http://www.img4up.com/up2/48583435413489.gif را شامل است .بنابراین :

http://www.img4up.com/up2/471482233447.gif


سوالاتم اینجاست که :
منظور فقط بالای قطر اصلی است که اعداد صفر هستند؟
دوم نسبت ها رو چجوری بدست اورده ؟مثلا

http://www.img4up.com/up2/607260773142426.gif





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

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

مثال شما از حل این رابطه به دست می‌یاد:



a( i ) = a( i - 1 ) + i , a( 1 ) = 1