عضو سایت
v پياده سازي آرايه هاي دو بعدي
آرايه هاي دوبعدي مي توانند به صورت سطري ياستوني ذخيره شوند. در روش سطري، ابتداعناصر سطر اول، سپس عناصر سطردوم و غيره ذخيره مي شوند.در روش ستوني، ابتدا عناصر ستون اول، سپس عناصر ستون دوم و غيره ذخيره مي شوند. در C آرايه ها به صورت سطري ذخيره مي شوند.آريه زير را درنظر بگيريد:
int a[3][5];
[دل خوش از آنیم که حج میرویم؟ ..]غافل از آنیم که کج میرویم
[SIGPIC][/SIGPIC]
عضو سایت
اكنون فرض كنيد آرايه a با m سطر و n ستون تعريف شده است كه m و n از قبل مشخص هستند:
int a[m][n];
براي رسيدن به اولين عنصر سطر iﭐم (يعني عنصر a[i][0] ) بايد از i سطر كامل بگذريم كه هر سطر آن داراي n عنصر است. لذا آدرس عنصر سطر i برابر است با:
= base(a) + i * n * size آدرس اولين عنصر سطر i
فاصله اولين عنصر سطر i تا ستون j برابر با j * size است. بنابراين آدرس عنصر a[i][j] به صورت زير است:
= base(a) + i * n * size + j * size آدرس عنصر a[i][j]
= base(a) + (j * n + j) * size
[دل خوش از آنیم که حج میرویم؟ ..]غافل از آنیم که کج میرویم
[SIGPIC][/SIGPIC]
عضو سایت
كاربرد آرايه هاي دو بعدي
نام ديگر آرايه هاي دو بعدي، ماتريس است كه كاربردهاي فراواني در حل مسئله دارد. نمونه هايي از ماتريس ها در زير مشاهده مي شوند كه ماتريس a را
و به صورتa3*4مي نويسيم و ماتريس b را5*2مي گوييم و به صورت b2*5
[دل خوش از آنیم که حج میرویم؟ ..]غافل از آنیم که کج میرویم
[SIGPIC][/SIGPIC]
عضو سایت
ماتريس هاي اسپارس
ماتريسي كه تعداد زيادي از عناصر آن صفر باشند، ماتريس اسپارسناميده ميشود.
[دل خوش از آنیم که حج میرویم؟ ..]غافل از آنیم که کج میرویم
[SIGPIC][/SIGPIC]
عضو سایت
الگوريتم تعيين ترانهاده ماتريس اسپارسدريافتي:نمايش ماتريس اسپارسبرگشتي: ترانهاده ماتريس اسپارس1.تعداد ستون هاي ماتريس اسپارس را برابر با تعداد سطرهاي ماتريس ترانهاده قرار مي دهيم.2.تعداد سطرهاي ماتريس اسپارس را برابر با تعداد ستون هاي ماتريس ترانهاده قرار مي دهيم.3.تعداد عناصر مخالف صفر ماتريس اسپارس را برابر با تعداد عناصر مخالف صفر ماتريس ترانهاده قرار مي دهيم.4.براي قرار دادن مقادير مخالف صفردر ماتريس ترانهاده، درستون دوم نمايش ماتريس اسپارس به دنبال كوچك ترين انديس (يعني صفر) مي گرديم و پس از پيدا كردن اين انديس، جاي سطر و ستون آن را عوض كرده، به همراه مقدار آن سطر و ستون، در ابتداي ماتريس ترانهاده قرار مي دهيم. به همين ترتيب، در ستون دوم نمايش ماتريس اسپارس به دنبال انديس هاي 1، 2،... و n - 1 مي گرديم. پس از جابه جايي سطر و ستون، به ترتيب در ترانهاده ماتريس اسپارس قرار مي دهيم.
اگرستون دوم نمايش ماتريس اسپارس به طور صعودي مرتب باشند،مرحله 4به اين صورت انجام مي شودكه،جاي سطر و ستون ماتريس اسپارس عوض مي شود و به همراه مقدار آن سطر و ستون به ترتيب در ماتريس ترانهاده قرار مي گيرد.
[دل خوش از آنیم که حج میرویم؟ ..]غافل از آنیم که کج میرویم
[SIGPIC][/SIGPIC]
عضو سایت
جمع دو ماتريس اسپارس
در جمع دو ماتريس اسپارس، فقط عناصر متناظر، در صورت وجود با هم جمع مي شوند و چنانچه نتيجه جمع صفر نباشد، در ماتريس حاصل قرار مي گيرد. الگوريتم آن به شرح زير است:
الگوريتم جمع دو ماتريس اسپارسدريافتي: سه ماتريس اسپارس a ،b و cبرگشتي: حاصل جمع دو ماتريس اسپارس (c)1.شماره سطر اولين عنصر مخالف صفر ماتريس aرا با شماره سطر اولين عنصر مخالف صفر از ماتريس b مقايسه كن. سه حالت ممكن است رخ دهد:الف. اگرشماره سطرماتريس aكمتر از شماره سطر ماتريس bباشد، با توجه به اين كه شماره سطرها صعودي مي باشند، آنگاه شماره سطر aاز تمام شماره سطرهاي b كمتر است. نتيجه مي گيريم كه عنصر متناظر با اين موقعيت در ماتريس b وجود ندارد(صفر است). اين عنصر را در ماتريس cقرار دهيد.ب. اگر شماره سطر ماتريس b كمتر از شماره سطر ماتريس aباشد، مشخصات عنصر ماتريس b در ماتريس c قرار مي گيرد.ج. اگر شماره سطرها برابر باشند، شماره ستون ها را باهم مقايسه كنيد. در اين جا نيز سه حالت ممكن است رخ دهد. درحالت كوچك تر يا بزرگ تر بودن، مثل سطرها عمل كنيد. در حالت تساوي(چون سطرها برابر بودند)،مقادير دوعنصر را جمع كنيد و اگرحاصل جمع مخالف صفر بود، به همراه مشخصات آن عنصر در آرايهc قرار دهيد. اگر حاصل جمع دو عنصر صفر بود، مشخصات آن عنصر در cقرار نمي گيرد. زيرا نمايش ماتريس اسپارس فقط عناصر غير صفر را دربرمي گيرد.
[دل خوش از آنیم که حج میرویم؟ ..]غافل از آنیم که کج میرویم
[SIGPIC][/SIGPIC]
عضو سایت
مشكلات آرايه
آرايه ها چند مشكل دارند كه در هنگام استفاده از آن ها بايد در نظر گرفته شوند:
• حد و مرز آرايه ها در c كنترل نمي شود.
• ظرفيت آرايه در طول اجراي برنامه تغيير نمي كند.
• درج كردن مقداري در بين مقادير ديگر در آرايه، مستلزم جابه جايي عناصر است.
• حذف مقداري از آرايه نيز مستلزم جابه جايي عناصر است.
[دل خوش از آنیم که حج میرویم؟ ..]غافل از آنیم که کج میرویم
[SIGPIC][/SIGPIC]
عضو سایت
نشانه گذاري O بزرگ
عوامل متعددي در زمان اجراي الگوريتم موثر هستند،ولي آنچه كه به عنوان كارايي الگوريتم مطرح است،تعداد دفعات اجراي دستورات مي باشد. اين نوع تحليل، در توسعه نرم افزار كارآمد، مهم تر از اندازه گيري مدت زمان اجراي يك الگوريتم بر روي كامپيوتر خاص، برحسب واحدهاي زماني مثل"ثانيه" است.
دانشمندان كامپيوتر، نشانه گذاري ها و اصطلاحات زيادي را براي درك ارتباط بين اندازهوروديو زمان اجرا مطرح كردند. به عنوان مثال، اگر با دو برابر شدن اندازه ورودي (n)، زمان اجراي الگوريتم نيز دوبرابر شود،آن گاه زمان اجراي الگوريتم به طور خطي رشد مي كند. به اين ترتيب، مي گوييم نرخ رشد، مرتبه n است.
ازطرف ديگر، اگر با دو برابر شدن اندازه ورودي، زمان اجراي الگوريتم چهار برابر شود، آن گاه الگوريتم با نرخ توان دوم رشد مي كند. در اين مورد مي گوييم نرخ رشد آن، مرتبه است
[دل خوش از آنیم که حج میرویم؟ ..]غافل از آنیم که کج میرویم
[SIGPIC][/SIGPIC]
عضو سایت
ساده ترين روش محاسبه ي O مربوط به الگوريتم يا برنامه، در نظرگرفتن حلقه هاي تكرار و تودرتو بودن آن ها است.اگر فرض كنيم بدنه حلقه فقط حاوي دستورات ساده است، يك حلقه از O(n)، حلقه تودرتو از o(n) به توان سه استو غيره. علاوه براين، بايد تعداد دفعات تكرار اجراي حلقه را تعيين كنيد.
[دل خوش از آنیم که حج میرویم؟ ..]غافل از آنیم که کج میرویم
[SIGPIC][/SIGPIC]
عضو سایت
حلقه زير را در نظربگيريد:
for(int i = 1; i < x_length; i*= 2)
{
process x[i];
}
بدنه حلقه k-1 بار اجرا مي شود كه i داراي مقادير 1، 2، 4، 8، 16، 32، ... و
است، به طوري كه 2 به توان kكوچك تر از x_length مي باشد. لذا مي گوييم اين حلقه از Oلگاریتم n است
[دل خوش از آنیم که حج میرویم؟ ..]غافل از آنیم که کج میرویم
[SIGPIC][/SIGPIC]
پاسخ با نقل قول
علاقه مندی ها (بوک مارک ها)