پاورپوینت پردازش زیر آرایه ها

بخشی از پاورپوینت

اسلاید 1 :

پردازش زیر آرایه ها

اسلاید 2 :

مروری بر مطالب
از آرایه برای نگهداری مجموعه ای از داده های به هم وابسته استفاده می کنیم
برای استفاده از آرایه لازم است قبل از شروع برنامه، حداکثر اندازه آرایه را مشخص نماییم و در طول برنامه اندازه آرایه را بدست آوریم.
ماشین حساب 30 رقمی
با تغییر اندیس آرایه می توانیم به صورت ترتیبی به آن دسترسی پیدا کنیم

اسلاید 3 :

پردازش زیر آرایه ها
در بعضی از الگوریتم ها لازم است محاسبات را بر روی قسمتی از آرایه از اندیس شروع تا اندیس پایان انجام دهیم.

اسلاید 4 :

مثال : پیدا کردن اندیس کوچکترین عضو زیر آرایه
Const MaxSize = 100;
Var
startIndex, endIndex,minIndex: Integer;
nums : array [1..MaxSize] of Integer;
Begin
….
readln(startIndex,endIndex);
minIndex:= startIndex;
for i:=startIndex+1 to endIndex do
if nums[minIndex]>nums[i] then minIndex:=i;
writeln(minIndex);
End.

اسلاید 5 :

جستجوی یک آرایه
آرایه ای را برای رسیدن به عددی خاص مورد جستجو قرار می دهیم.
از عنصر اول آرایه جستجو را شروع کرده، آن را با عنصر مورد نظر مقایسه می کنیم و این عمل را تا پیدا شدن داده مورد نظر ادامه می دهیم.

اسلاید 6 :

مثال : جستجوی نام دانشجو با استفاده از شماره دانشجویی
Var
ID : array[1..Max] of Integer;
names : array[1..Max] of string;
Begin
…
readln(sid);
for i:=1 to max do
if ID[i]=sid then break;
if i>max then writeln(‘not found’)
else writeln(names[i]);
End.

اسلاید 7 :

مرتب سازی یک آرایه
مرتب سازی انتخابی : برای اجرای مرتب سازی انتخابی روی آرایه ای که دارای N عضو است (اندیس 1..N)، کوچکترین عنصر آرایه را پیدا کرده و آن را با اولین عنصر آرایه جایگزین می کنیم.
کوچکترین عنصر در اندیس 1 قرار دارد
کوچکترین عنصر از آرایه باقیمانده را (اندیس 2..N) در اندیس 2 قرار می دهیم.
کوچکترین عنصر از آرایه باقیمانده را (اندیس 3..N) در اندیس 3 قرار می دهیم.
.

اسلاید 8 :

الگوریتم مرتب سازی انتخابی
برای Fill برابر با 1 تا N-1 انجام بده
در زیر آرایه nums[Fill..N]، موقعیت کوچکترین عنصر را پیدا کن
اگر Fill در موقعیت کوچکترین عنصر قرار نگرفته، آنگاه
کوچکترین عنصر را با عنصری که در موقعیت Fill قرار گرفته است، تعویض کن.

اسلاید 9 :

مثال اجرایی از الگوریتم مرتب سازی انتخابی
Fill
Min

اسلاید 10 :

پیاده سازی مرتب سازی انتخابی
Var
nums : array[1..max] of Integer; …
Begin
…
for Fill:=1 to max do
begin
min := Fill;
for j:=Fill+1 to max do
if nums[j] if (Fill<>min) then
begin
temp:=nums[Fill];
nums[Fill]:=nums[min];
nums[min]:=temp;
end;
end;
End.

اسلاید 11 :

تحلیل الگوریتم : نماد Oی بزرگ
الگوریتم های مختلفی برای حل مساله وجود دارد
معیار انتخاب
بهترین راه حل کم ترین زمان اجرا را داشته باشد
بهترین راه حل کم ترین میزان حافظه را مصرف کرده باشد.
.
زمان اجرای الگوریتم ها (برنامه ها) را روی N داده تخمین می زنیم و با یکدیگر مقایسه می کنیم.
رابطه میان زمان پردازش و N را با O نشان می دهیم.

اسلاید 12 :

تحلیل الگوریتم : نماد Oی بزرگ (ادامه)
زمان اجرای هر دستور را O(1) در نظر می گیریم.
زمان اجرای هر حلقه = زمان اجرای بدنه حلقه * تعداد تکرار حلقه
For i:= 1 to N do
nums[i]:=I;
For i:= 1 to N do
for j:= 1 to N do
k:= k+i*j;
O(N*1)
O(N*N)

اسلاید 13 :

تحلیل الگوریتم : نماد Oی بزرگ (ادامه)
O(3N)=O(N)
O(2N*N-3N) =O(N2)
O(4)=O(1)
جمله ای که بیشترین توان را دارد، از سایر جملات سریع تر رشد می کند، بنابراین از ثوابت و جملات با توان کمتر چشم پوشی می کنیم.

اسلاید 14 :

تحلیل زمان اجرای الگوریتم مرتب سازی انتخابی