שינויים
יצירת דף עם התוכן "[[תקציר שימושי מחשב, סמסטר ב תשעג, גיא בלשר|חזרה לקישורים לתקצירים]] '''המטרה: לכתוב פונקציות..."
[[תקציר שימושי מחשב, סמסטר ב תשעג, גיא בלשר|חזרה לקישורים לתקצירים]]
'''המטרה: לכתוב פונקציות להוספה, למחיקה, לחיפוש ולמיון במערך'''. נחלק את הפעולות לשני מקרים: המערך אינו ממוין והמערך ממוין.
==מערך שאינו ממוין==
נגדיר איזשהו מערך:
<div align="left">
;[v=[79,100,31,5,84
<div align="right">
ונבצע עליו את הפעולות הבאות:
===הוספה===
<div align="left">
(function [u] = add2array (v,k
הפונקציה מוסיפה איבר k למערך v ומחזירה u %
;u=v
;u(end+1)=k
end
<div align="right">
===מחיקה===
אפשרות 1:
<div align="left">
(function [u] = deleteFromArray (v,p
הפונקציה מוחקת את האיבר ה־p־י במערך ומחזירה u %
;(u=zeros(length(v)-1,1
;(u(1:p-1)=v(1:p-1
;(u(p:length(v)-1)=v(p+1:end
end
<div align="right">
אפשרות 2:
<div align="left">
(function [u] = deleteFromArray2 (v,p
הפונקציה מוחקת את האיבר ה־p־י במערך ומחזירה u %
;(u=zeros(length(v)-1,1
for i=1:p-1
;(u(i)=v(i
end
(for i=p+1:length(v
;(u(i-1)=v(i
end
end
<div align="right">
===חיפוש===
<div align="left">
(function [p] = findInArray (v,x
הפונקציה מחזירה את המקום במערך שבו x נמצא או אפס אם x אינו במערך %
;k=1
;p=0
;(n=length(v
while p==0 && k<=n
if v(k)==x
;p=k
else
;k=k+1
end
end
end
<div align="right">
==מערך ממוין==
כעת נניח שיש לנו מערך ממוין v, למשל מהקטן לגדול.
===מחיקה===
בדיוק כמו במערך שאינו ממוין.
===חיפוש===
ישנן שתי שיטות חיפוש: חיפוש בינארי ואריה במדבר.
חיפוש בינארי:
<div align="left">
(function [p] = binarySearch (v,x
;(n=length(v
;L=1
;H=n
while L<H-1
;(M=floor((L+H)/2
(if x<v(M
;H=M
else
;L=M
end
end
(if x==v(H
;p=H
else
;p=L
end
end
<div align="right">
מספר הפעולות בחיפוש בינארי: <math>\log_2 n</math>
===הוספה===
אם x קטן מ־(v(1, נכניס אותו בהתחלה. אחרת נחפש את x ונכניס אותו אחרי L.
===מיון פשוט===
ראשית, נכתוב פונקציית עזר:
<div align="left">
(function [m,p] = findSmallest (v,k
הפונקציה מוצאת את המקום p ואת הערך m הנמצא במערך v והמינימלי מהמקום ה־k־י והלאה %
;p=k
;(m=v(k
;(n=length(v
for i=k+1:n
if v(i)<m
;p=i
;(m=v(i
end
end
end
<div align="right">
כעת, נכתוב את התוכנית למיון:
<div align="left">
for i=1:n-1
;(m,p]=findSmallest(v,i]
;(v(p)=v(i
;v(i)=m
end
<div align="right">
'''המטרה: לכתוב פונקציות להוספה, למחיקה, לחיפוש ולמיון במערך'''. נחלק את הפעולות לשני מקרים: המערך אינו ממוין והמערך ממוין.
==מערך שאינו ממוין==
נגדיר איזשהו מערך:
<div align="left">
;[v=[79,100,31,5,84
<div align="right">
ונבצע עליו את הפעולות הבאות:
===הוספה===
<div align="left">
(function [u] = add2array (v,k
הפונקציה מוסיפה איבר k למערך v ומחזירה u %
;u=v
;u(end+1)=k
end
<div align="right">
===מחיקה===
אפשרות 1:
<div align="left">
(function [u] = deleteFromArray (v,p
הפונקציה מוחקת את האיבר ה־p־י במערך ומחזירה u %
;(u=zeros(length(v)-1,1
;(u(1:p-1)=v(1:p-1
;(u(p:length(v)-1)=v(p+1:end
end
<div align="right">
אפשרות 2:
<div align="left">
(function [u] = deleteFromArray2 (v,p
הפונקציה מוחקת את האיבר ה־p־י במערך ומחזירה u %
;(u=zeros(length(v)-1,1
for i=1:p-1
;(u(i)=v(i
end
(for i=p+1:length(v
;(u(i-1)=v(i
end
end
<div align="right">
===חיפוש===
<div align="left">
(function [p] = findInArray (v,x
הפונקציה מחזירה את המקום במערך שבו x נמצא או אפס אם x אינו במערך %
;k=1
;p=0
;(n=length(v
while p==0 && k<=n
if v(k)==x
;p=k
else
;k=k+1
end
end
end
<div align="right">
==מערך ממוין==
כעת נניח שיש לנו מערך ממוין v, למשל מהקטן לגדול.
===מחיקה===
בדיוק כמו במערך שאינו ממוין.
===חיפוש===
ישנן שתי שיטות חיפוש: חיפוש בינארי ואריה במדבר.
חיפוש בינארי:
<div align="left">
(function [p] = binarySearch (v,x
;(n=length(v
;L=1
;H=n
while L<H-1
;(M=floor((L+H)/2
(if x<v(M
;H=M
else
;L=M
end
end
(if x==v(H
;p=H
else
;p=L
end
end
<div align="right">
מספר הפעולות בחיפוש בינארי: <math>\log_2 n</math>
===הוספה===
אם x קטן מ־(v(1, נכניס אותו בהתחלה. אחרת נחפש את x ונכניס אותו אחרי L.
===מיון פשוט===
ראשית, נכתוב פונקציית עזר:
<div align="left">
(function [m,p] = findSmallest (v,k
הפונקציה מוצאת את המקום p ואת הערך m הנמצא במערך v והמינימלי מהמקום ה־k־י והלאה %
;p=k
;(m=v(k
;(n=length(v
for i=k+1:n
if v(i)<m
;p=i
;(m=v(i
end
end
end
<div align="right">
כעת, נכתוב את התוכנית למיון:
<div align="left">
for i=1:n-1
;(m,p]=findSmallest(v,i]
;(v(p)=v(i
;v(i)=m
end
<div align="right">
