מבני נתונים

6.1 היכרות עם המושג מבנה נתונים

בפרק 4 קראנו סדרת מדידות בלולאה וחישבנו את הממוצע שלהן. בכל סבב הקריאה החדשה החליפה את הקודמת באותו משתנה. אם נשאל אחרי הלולאה: אילו קריאות גבוהות מן הממוצע? לא תהיה לנו תשובה, כי הקריאות אבדו. את הממוצע יודעים רק בסוף, ובסוף נשארה לנו רק הקריאה האחרונה.

r1 = 12.1
r2 = 11.6
r3 = 12.4
r4 = 11.9
average = (r1 + r2 + r3 + r4) / 4
if r1 > average:
    print(r1)
if r2 > average:
    print(r2)
if r3 > average:
    print(r3)
if r4 > average:
    print(r4)

12.1
12.4

המבנה הראשון שנלמד הוא הרשימה. כותבים את הערכים בין סוגריים מרובעים, עם פסיקים ביניהם. וכל ערך במבנה נקרא איבר:

readings = [12.1, 11.6, 12.4, 11.9]
print(readings)
print(readings[0])
print(len(readings))
print(round(sum(readings) / len(readings), 2))

[12.1, 11.6, 12.4, 11.9]
12.1
4
12.0

עכשיו ארבע הקריאות נשארו שמורות תחת שם אחד. נחזור לשאלת הקריאות שגבוהות מן הממוצע בסעיף 6.7, ונפתור אותה בארבע שורות, יהיה מספרן אשר יהיה. בפרק הזה נלמד שני מבנים:

6.2 אתחול רשימה ופעולות על איבריה (list)

מאתחלים רשימה בכתיבת איבריה בין סוגריים מרובעים. האיברים יכולים להיות מספרים או מחרוזות, ואפשר גם לערבב ביניהם, אבל רשימה שכל איבריה מאותו טיפוס נוחה יותר לשימוש. הטיפוס של רשימה הוא list, והפעולה len נותנת את מספר איבריה.

volts = [12.1, 11.6, 12.4]
parts = ["R1", "C4", "D2", "LED"]
mixed = ["R1", 470, 0.25]
print(volts)
print(parts)
print(mixed)
print(type(volts), len(parts))

[12.1, 11.6, 12.4]
['R1', 'C4', 'D2', 'LED']
['R1', 470, 0.25]
<class 'list'> 4

הרשימה הריקה היא רשימה בלי איברים, ואורכה אפס. כותבים אותה [] או list(), והיא נקודת ההתחלה כשממלאים את הרשימה תוך כדי ריצה. הפעולה list ממירה לרשימה כל ערך שאפשר לעבור על חלקיו: מחרוזת, range או טאפל (Tuple), ואת שני האחרונים נכיר בפרק הזה. והפעולה split מפרק 5 נתנה לנו רשימה כבר מן ההתחלה:

log = []
print(log, len(log))
print(list())
print(list("ADC"))
print(list(range(4)))
print("BAT=12.42;TMP=31.5".split(";"))

[] 0
[]
['A', 'D', 'C']
[0, 1, 2, 3]
['BAT=12.42', 'TMP=31.5']

הפעולה print מדפיסה את כל הרשימה עם הסוגריים והפסיקים. כדי להגיע לאיבר כותבים את האינדקס שלו בסוגריים מרובעים, כמו במחרוזות. והאיבר מתנהג כמו משתנה רגיל: מציבים בו ערך חדש ומחשבים איתו. הפעולות sum, max ו-min מפרק 2 עובדות על הרשימה כולה:

loads = [60, 100, 40]
print(loads)
print(loads[0], "W and", loads[1], "W")
loads[1] = 75
loads[2] += 20
loads[0] = loads[0] * 2
print(loads)
print(sum(loads), max(loads), min(loads))

[60, 100, 40]
60 W and 100 W
[120, 75, 60]
255 120 60

כאן מופיע הבדל יסודי מן המחרוזת: הרשימה משתנה במקומה, ואילו תו במחרוזת אי אפשר לשנות.

רשימת מונים:

בפרק 4 מנינו במונה אחד. אם נרצה למנות עשרה דברים שונים נזדקק לעשרה מונים. רשימת מונים מרכזת את כולם ברשימה אחת, וכולם מתחילים מאפס. הרעיון היפה בה הוא שהערך שקוראים הוא עצמו האינדקס של המונה שלו, ולכן אין צורך בשרשרת תנאים.

counts = [0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
digit = int(input("Digit (-1 to stop): "))
while digit != -1:
    counts[digit] += 1
    digit = int(input("Digit (-1 to stop): "))
print(counts)
print("Red bands:", counts[2])

Digit (-1 to stop): 2
Digit (-1 to stop): 7
Digit (-1 to stop): 2
Digit (-1 to stop): 1
Digit (-1 to stop): 0
Digit (-1 to stop): 2
Digit (-1 to stop): -1
[1, 1, 3, 0, 0, 0, 0, 1, 0, 0]
Red bands: 3

presses = [0, 0, 0, 0]
button = int(input("Button: "))
while button != 0:
    presses[button - 1] += 1
    button = int(input("Button: "))
print(presses)

רשימת צוברים:

רשימת צוברים דומה לרשימת מונים, אבל מוסיפים לתא כמות כלשהי במקום 1. האינדקס קובע לאן מוסיפים, והקלט השני קובע כמה מוסיפים.

hours = [0, 0, 0]
tech = int(input("Technician (-1 to stop): "))
while tech != -1:
    hours[tech] += float(input("Hours: "))
    tech = int(input("Technician (-1 to stop): "))
print(hours)
print("Total:", sum(hours))

Technician (-1 to stop): 0
Hours: 6.5
Technician (-1 to stop): 2
Hours: 8
Technician (-1 to stop): 0
Hours: 3
Technician (-1 to stop): -1
[9.5, 0, 8.0]
Total: 17.5

6.3 המבנה הסידורי של רשימה (List), גישה לאיבר באמצעות אינדקס

איברי הרשימה מסודרים, ולכל איבר מספר שמציין את מקומו: האינדקס. הספירה מתחילה מאפס, כמו במחרוזות, ולכן האינדקס של האיבר הראשון הוא 0, ושל האחרון קטן באחד מן האורך. אפשר גם לספור מן הסוף באינדקס שלילי: [-1] הוא האיבר האחרון, ו-[-2] זה שלפניו.

samples = [0.2, 1.4, 3.1, 4.8, 2.6]
print(samples[0], samples[2], samples[4])
print(samples[-1], samples[-5])
samples[-1] = 0.0
print(samples)

0.2 3.1 2.6
2.6 0.2
[0.2, 1.4, 3.1, 4.8, 0.0]

האינדקס השלילי פוטר אותנו מלכתוב samples[len(samples) - 1], עובד בכל אורך של רשימה, ומתאים גם לשינוי.

samples = [0.2, 1.4, 3.1, 4.8, 2.6]
print(samples[5])

IndexError: list index out of range

samples = [0.2, 1.4, 3.1, 4.8, 2.6]
high = 0
i = 0
while i < len(samples):
    if samples[i] > 2.5:
        high += 1
    i += 1
print("Above 2.5 V:", high)

Above 2.5 V: 3

6.4 חיתוך רשימות (slicing)

חיתוך נותן לנו חלק מן הרשימה כרשימה חדשה. כותבים s[start:stop:step]: מתחילים מן האינדקס start, עוצרים לפני האינדקס stop, ומתקדמים בצעד step. אלה אותם כללים שהכרנו במחרוזות:

s = [10, 20, 30, 40, 50, 60]
print(s[1:4])
print(s[:3], s[3:])
print(s[-2:])
print(s[::2])
print(s[::-1])
print(s[2:100])
print(s[4:2])
print(s)

[20, 30, 40]
[10, 20, 30] [40, 50, 60]
[50, 60]
[10, 30, 50]
[60, 50, 40, 30, 20, 10]
[30, 40, 50, 60]
[]
[10, 20, 30, 40, 50, 60]

• אם משמיטים את ההתחלה מתחילים מתחילת הרשימה, ואם משמיטים את הסוף מגיעים לסופה. והצעד -1 הופך את הסדר.
• חיתוך אינו נעצר בשגיאה: הגבול 100 מחוץ לרשימה ובכל זאת זה עובד, ו-[4:2] נותן רשימה ריקה.
• השורה האחרונה מראה שחיתוך אינו משנה את הרשימה המקורית.

samples = [0.1, 0.9, 2.4, 2.5, 2.6, 2.4, 2.5]
stable = samples[2:]
print(stable)
print(round(sum(stable) / len(stable), 2))
print(stable[::2])

[2.4, 2.5, 2.6, 2.4, 2.5]
2.48
[2.4, 2.6, 2.5]

השמה אינה מעתיקה רשימה:

a = [12, 9, 5]
b = a
b[0] = 99
print(a)
print(b)

[99, 9, 5]
[99, 9, 5]

כשרוצים העתק אמיתי משתמשים בחיתוך a[:], או בפעולה list(a), ונוצרת רשימה חדשה בזיכרון:

a = [12, 9, 5]
b = a[:]
b[0] = 99
print(a)
print(b)

[12, 9, 5]
[99, 9, 5]

a = [1, 2, 3]
b = a
c = a[:]
a[0] = 7
b[1] = 8
c[2] = 9
print(a)
print(b)
print(c)

6.5 הוספת איברים לרשימה

הרשימה גדלה תוך כדי ריצת התוכנית. הפעולה append מוסיפה איבר אחד לסוף, וזו הדרך שמשתמשים בה רוב הזמן. האופרטור + משרשר שתי רשימות ויוצר רשימה חדשה, ו-+= מוסיף רשימה לסוף אותה רשימה. והאופרטור * משכפל את הרשימה, וזו הדרך הקצרה ביותר לאתחל רשימת מונים: במקום עשרת האפסים שבסעיף 6.2 כותבים [0] * 10.

log = [12.1]
log.append(11.8)
print(log)
log = log + [11.9, 12.0]
print(log)
log += [12.2]
print(log)
print([0] * 5)

[12.1, 11.8]
[12.1, 11.8, 11.9, 12.0]
[12.1, 11.8, 11.9, 12.0, 12.2]
[0, 0, 0, 0, 0]

loads = []
watts = float(input("Load W (0 to stop): "))
while watts != 0:
    loads.append(watts)
    watts = float(input("Load W (0 to stop): "))
print(loads)
print("Count:", len(loads))
print("Total:", sum(loads))

Load W (0 to stop): 60
Load W (0 to stop): 100
Load W (0 to stop): 40.5
Load W (0 to stop): 0
[60.0, 100.0, 40.5]
Count: 3
Total: 200.5

a = [1]
a.append(2)
b = a + [3]
a += [4, 5]
print(a)
print(b)
print([7] * 2 + [8])

6.6 שימוש ב-range לאתחול רשימה

הפעולה range מייצרת סדרת מספרים שלמים. ממירים אותה לרשימה בפעולה list, ומקבלים רשימה ארוכה בלי לכתוב את איבריה. יש לה שלוש צורות:

print(list(range(5)))
print(list(range(2, 8)))
print(list(range(0, 50, 10)))
print(list(range(5, 0, -1)))
print(range(5))

[0, 1, 2, 3, 4]
[2, 3, 4, 5, 6, 7]
[0, 10, 20, 30, 40]
[5, 4, 3, 2, 1]
range(0, 5)

הגבול stop לעולם אינו נכנס לסדרה, כמו בחיתוך. והשורה האחרונה מראה ש-range לבדה אינה רשימה, אלא תיאור של סדרת מספרים שנוצרת לפי הצורך, ולכן כתבנו list כדי לראות אותה.

freqs = list(range(100, 1100, 100))
print(freqs)
channels = list(range(1, 9))
print(channels)

[100, 200, 300, 400, 500, 600, 700, 800, 900, 1000]
[1, 2, 3, 4, 5, 6, 7, 8]

6.7 לולאת for העוברת על איברי רשימה (for)

בסעיף 6.3 עברנו על הרשימה בלולאת while: אתחלנו אינדקס, בדקנו אותו והגדלנו אותו בכל סבב. המעבר הזה נפוץ מאוד, ולכן יש לו לולאה מיוחדת: for. כותבים אותה כך:

for item in sequence:
    statement
    statement
next_statement

• בכל סבב המשתנה item מקבל את האיבר הבא של sequence, לפי הסדר, מן הראשון עד האחרון.
• לא כותבים אינדקס, תנאי או הגדלה: הלולאה נעצרת לבדה כשהאיברים נגמרים.
• אחרי השורה הראשונה באות נקודתיים, וגוף הלולאה מוזח פנימה, כמו ב-if וב-while.
• את שם המשתנה בוחרים בעצמנו, ובוחרים שם שמתאר איבר אחד: v או score.

volts = [12.1, 11.6, 12.4]
for v in volts:
    print("Reading:", v)
print("Done")

Reading: 12.1
Reading: 11.6
Reading: 12.4
Done

השורה for הופיעה בטבלה ארבע פעמים עבור רשימה של שלושה איברים: בפעם הרביעית לא נשאר איבר, והלולאה יצאה אל הפקודה הבאה.

readings = [12.1, 11.6, 12.4, 11.9]
average = sum(readings) / len(readings)
for r in readings:
    if r > average:
        print(r)

12.1
12.4

volts = [12, 9, 5]
for v in volts:
    v = v * 2
print(volts)
print(v)

[12, 9, 5]
10

לולאת for עובדת גם על כל מה שאפשר לעבור על חלקיו, למשל מחרוזת: for ch in "ADC":. ועל רשימה ריקה הגוף שלה אינו מתבצע אף פעם, ואין שום שגיאה.

items = [4, 7, 2, 9]
s = 0
for x in items:
    if x % 2 == 1:
        s += x
    print(s)

6.8 שילוב של לולאת for עם range

הפעולה range נותנת סדרת מספרים, ולולאת for עוברת על הסדרה. כשמשלבים אותן מתקבל מונה מוכן, וזו החזרה הפשוטה ביותר למספר ידוע של סבבים. כך גם קוראים מספר ידוע של ערכים, בלי זקיף:

for i in range(4):
    print(i, i * 5)

0 0
1 5
2 10
3 15

currents = []
for k in range(3):
    currents.append(float(input("Current: ")))
print(currents)
print(max(currents))

Current: 1.5
Current: 0.75
Current: 2.25
[1.5, 0.75, 2.25]
2.25

השימוש החשוב ביותר הוא מעבר על האינדקסים של הרשימה: for i in range(len(v)): נותן 0, אחר כך 1 וכן הלאה עד האינדקס האחרון, בכל אורך של רשימה. זה נחוץ בשלושה מצבים, ולולאה על האיברים אינה מספיקה באף אחד מהם.

adc = [0, 256, 512, 1023]
for i in range(len(adc)):
    adc[i] = round(adc[i] * 5 / 1023, 2)
print(adc)

[0.0, 1.25, 2.5, 5.0]

volts = [12, 5, 3.3]
amps = [0.5, 0.2, 0.1]
power = []
for i in range(len(volts)):
    power.append(round(volts[i] * amps[i], 2))
print(power)
print("Total:", round(sum(power), 2))

[6.0, 1.0, 0.33]
Total: 7.33

samples = [0.1, 0.2, 3.2, 3.3, 3.2, 0.2, 0.1]
for i in range(1, len(samples)):
    step = samples[i] - samples[i - 1]
    if abs(step) > 1:
        print("Edge at index", i)

Edge at index 2
Edge at index 5

הפקודות break ו-continue מפרק 4 עובדות גם ב-for: כשמחפשים את האיבר הראשון שמקיים תנאי, כותבים break מיד כשמוצאים אותו, ולא ממשיכים במעבר.

a = [2, 5, 1, 8]
t = 0
for i in range(1, len(a)):
    if a[i] > a[i - 1]:
        t += 1
print(t)
for i in range(0, len(a), 2):
    print(a[i])

6.9 אופרטור היחס in (in)

הביטוי x in values שואל: האם הערך הזה הוא איבר ברשימה? התוצאה היא ערך בוליאני, וההפך שלו הוא x not in values. הכרנו את האופרטור הזה במחרוזות, וכאן הוא משווה איבר שלם. בדוגמה הבאה הרשימה היא סדרת E12, כלומר הערכים התקניים של נגדים. המספר 47 והמחרוזת "47" אינם אותו ערך, ולכן בשורה האחרונה יצא False.

e12 = [10, 12, 15, 18, 22, 27, 33, 39, 47, 56, 68, 82]
print(47 in e12)
print(50 in e12)
print(50 not in e12)
print("47" in e12)

True
False
True
False

codes = ["R1", "C4", "R1", "D2", "C4"]
unique = []
for code in codes:
    if code not in unique:
        unique.append(code)
print(unique)

['R1', 'C4', 'D2']

a = [1, 3, 5]
b = [3, 4, 5, 6]
for x in b:
    if x in a:
        print(x)
print(2 in a or 4 in b)
print([3] in a)

6.10 עבודה עם פעולות של המחלקה list

הרשימה היא עצם של המחלקה list, ולמחלקה הזאת יש פעולות מוכנות שמזמנים בנקודה אחרי שם הרשימה, כפי שזימנו את פעולות המחרוזת בפרק 5. ההבדל החשוב מן המחרוזת הוא שהפעולות האלה משנות את הרשימה עצמה, ואינן נותנות רשימה חדשה.

parts = ["R1", "C4", "D2", "C4"]
parts.append("LED")
print(parts)
parts.remove("C4")
print(parts)
print(parts.count("C4"))
parts.insert(1, "Q1")
print(parts)
parts.extend(["U1", "U2"])
print(parts)
parts.clear()
print(parts)

['R1', 'C4', 'D2', 'C4', 'LED']
['R1', 'D2', 'C4', 'LED']
1
['R1', 'Q1', 'D2', 'C4', 'LED']
['R1', 'Q1', 'D2', 'C4', 'LED', 'U1', 'U2']
[]

הפעולה remove מחקה רק את ההופעה הראשונה של הרכיב C4, ולכן נשאר אחד, וזה מה ש-count אישרה. הפעולה append מוסיפה איבר אחד גם אם הוא רשימה, ואילו extend מוסיפה את איברי הרשימה אחד אחד.

הפעולה sort:

הפעולה sort ממיינת מספרים לפי ערכם, ומחרוזות לפי סדר מילוני, כלומר תו אחרי תו כמו במילון. ואם כותבים reverse=True המיון הוא בסדר יורד:

r = [470, 10, 220, 1000, 47]
r.sort()
print(r)
r.sort(reverse=True)
print(r)
names = ["diode", "LED", "resistor", "Capacitor"]
names.sort()
print(names)
codes = ["100", "47", "9"]
codes.sort()
print(codes)

[10, 47, 220, 470, 1000]
[1000, 470, 220, 47, 10]
['Capacitor', 'LED', 'diode', 'resistor']
['100', '47', '9']

ההשוואה בין תווים נעשית לפי המספר של כל תו בטבלת הקידוד, שאותו נותנת ord מפרק 2. בטבלה הזאת כל האותיות הגדולות באות לפני כל האותיות הקטנות, ולכן LED הגיעה לפני diode. גם ספרות במחרוזת הן תווים, ולכן המחרוזת "100" הגיעה לפני המחרוזת "9", אף שהמספר 100 גדול מ-9.

r = [470, 10, 220]
r = r.sort()
print(r)
print(r[0])

None
TypeError: 'NoneType' object is not subscriptable

samples = [2.5, 2.6, 9.9, 2.4, 2.5]
ordered = samples[:]
ordered.sort()
print(ordered)
print("Median:", ordered[len(ordered) // 2])
print("Average:", round(sum(samples) / len(samples), 2))

[2.4, 2.5, 2.5, 2.6, 9.9]
Median: 2.5
Average: 3.98

הפעולה remove:

parts = ["R1", "C4"]
parts.remove("D2")

ValueError: list.remove(x): x not in list

לכן בודקים באופרטור in לפני המחיקה. וכדי למחוק את כל ההופעות חוזרים על הבדיקה בלולאת while:

parts = ["R1", "C4", "R1", "D2", "R1"]
name = "Q7"
if name in parts:
    parts.remove(name)
else:
    print(name, "not found")
while "R1" in parts:
    parts.remove("R1")
print(parts)

Q7 not found
['C4', 'D2']

samples = [5, 0, 0, 7, 0, 3]
for s in samples:
    if s == 0:
        samples.remove(s)
print(samples)

[5, 7, 0, 3]

הפתרון הברור ביותר הוא לבנות רשימה חדשה עם האיברים שרוצים להשאיר. פתרון אחר הוא לעבור על העתק ולמחוק מן המקורית: for s in samples[:]:.

samples = [5, 0, 0, 7, 0, 3]
clean = []
for s in samples:
    if s != 0:
        clean.append(s)
print(clean)

[5, 7, 3]

a = [8, 2, 6]
a.insert(0, 2)
a.append(4)
a.remove(2)
print(a)
a.sort()
print(a)
print(a.count(2))
a.extend([1, 1])
print(len(a))

6.11 רשימה של רשימות

גם איבר של רשימה יכול להיות רשימה. רשימה של רשימות היא הדרך הטבעית לייצג טבלה: כל רשימה פנימית היא שורה, האינדקס הראשון בוחר את השורה, והשני בוחר את העמודה.

grid = [[10, 20, 30],
        [40, 50, 60]]
print(grid[1])
print(grid[1][2])
print(len(grid), len(grid[0]))
grid[0][1] = 25
print(grid)

[40, 50, 60]
60
2 3
[[10, 25, 30], [40, 50, 60]]

קוראים את grid[1][2] משמאל לימין: grid[1] הוא רשימה, ומתוכה לוקחים את האיבר [2]. len(grid) הוא מספר השורות, ו-len(grid[0]) הוא מספר העמודות. בתוכנית כותבים את הטבלה על כמה שורות כדי שתיראה כמו טבלה אמיתית, ופייתון מאפשרת זאת בתוך סוגריים.

כדי לעבור על הטבלה כותבים לולאה בתוך לולאה. הלולאה החיצונית עוברת על השורות, הפנימית על איברי השורה, והפקודה print() אחרי הפנימית עוברת לשורה חדשה:

grid = [[5, 1, 0],
        [2, 8, 4]]
for r in range(len(grid)):
    for c in range(len(grid[r])):
        print(grid[r][c], end=" ")
    print()

5 1 0 
2 8 4 

lab = [[78, 85, 90],
       [60, 72, 64],
       [95, 88, 91]]
for row in lab:
    print(row, round(sum(row) / len(row), 1))
for c in range(len(lab[0])):
    total = 0
    for r in range(len(lab)):
        total += lab[r][c]
    print("Experiment", c, round(total / len(lab), 1))

[78, 85, 90] 84.3
[60, 72, 64] 65.3
[95, 88, 91] 91.3
Experiment 0 77.7
Experiment 1 81.7
Experiment 2 81.7

בונים טבלה באותה דרך: רשימה חיצונית ריקה, ובכל סבב בונים שורה ומוסיפים אותה:

rows = 2
cols = 3
grid = []
for r in range(rows):
    row = []
    for c in range(cols):
        row.append(r * 10 + c)
    grid.append(row)
print(grid)

[[0, 1, 2], [10, 11, 12]]

grid = [[0] * 3] * 2
grid[0][0] = 7
print(grid)

[[7, 0, 0], [7, 0, 0]]

m = [[1, 2, 3],
     [4, 5, 6],
     [7, 8, 9]]
print(m[2][0], m[0][2])
d = 0
for i in range(len(m)):
    d += m[i][i]
print(d)
print(m[1][1:])

6.12 כתיבת אלגוריתמים (שאינם מובנים בשפה)

הפעולות max, min ו-sort עושות הרבה ממה שנכתוב כאן. אז למה לכתוב בעצמנו? כי האלגוריתמים האלה הם הבסיס של החשיבה התכנותית, כי בחינת הבגרות דורשת אותם, וכי לעתים קרובות צריך שינוי קטן שהכלים המוכנים אינם נותנים, כמו מקומו של האיבר הגדול ביותר ולא רק ערכו.

(א) האיבר הגדול ביותר:

הרעיון שהכרנו בפרק 4 הוא ערך קיצון: מניחים שהאיבר הראשון הוא הגדול ביותר, עוברים על השאר, וכל איבר גדול יותר ממה שמצאנו תופס את מקומו.

ולעתים קרובות צריך את מקומו של האיבר ולא רק את ערכו, למשל את מספר הערוץ עם המתח הגבוה ביותר. אז שומרים את האינדקס שלו, והערך נמצא ברשימה:

volts = [12.1, 11.6, 12.9, 11.9]
pos = 0
for i in range(1, len(volts)):
    if volts[i] > volts[pos]:
        pos = i
print("Highest:", volts[pos], "at index", pos)

Highest: 12.9 at index 2

temps = [-4, -9, -2]
top = 0
for t in temps:
    if t > top:
        top = t
print(top)

0

אותו אלגוריתם עובד גם על מחרוזות, כי האופרטורים < ו-> משווים ביניהן לפי סדר מילוני:

print("diode" < "resistor")
print("diode" < "diodes")
print("Zener" < "diode")
print("100" < "9")
print(100 < 9)

True
True
True
True
False

(ב) האיבר הקטן ביותר:

הופכים רק את כיוון ההשוואה: < במקום >. וכשהאיבר הקטן ביותר חוזר, ההשוואה < נשארת על ההופעה הראשונה, ואילו כתבנו <= היינו מגיעים לאחרונה.

parts = ["resistor", "diode", "capacitor", "zener"]
first = parts[0]
last = parts[0]
for name in parts:
    if name < first:
        first = name
    if name > last:
        last = name
print(first)
print(last)

capacitor
zener

(ג) מיזוג שתי רשימות:

מיזוג פירושו לבנות משתי רשימות ממוינות רשימה אחת ממוינת. למשל שני יומני אירועים משני מכשירים, כשכל יומן מסודר לפי הזמן. מחזיקים אינדקס בכל רשימה, ומשווים בין שני האיברים שהם מצביעים עליהם. הקטן עובר לתוצאה, והאינדקס שלו מתקדם צעד.

a = [3, 8, 15]
b = [1, 9, 11, 20]
merged = []
i = 0
j = 0
while i < len(a) and j < len(b):
    if a[i] <= b[j]:
        merged.append(a[i])
        i += 1
    else:
        merged.append(b[j])
        j += 1
merged += a[i:]
merged += b[j:]
print(merged)

[1, 3, 8, 9, 11, 15, 20]

הלולאה מסתיימת כשאחת הרשימות נגמרת. מה שנשאר באחרת גדול מכל מה שכבר עבר, ולכן הוא מתווסף כפי שהוא. אחד החיתוכים a[i:] ו-b[j:] ריק בוודאות, ואין צורך לבדוק איזה מהם.

(ד-1) מיון בועות:

הרעיון במיון בועות פשוט: משווים כל איבר לשכנו, ואם הם בסדר הלא נכון מחליפים ביניהם. אחרי מעבר אחד על הרשימה האיבר הגדול ביותר כבר הגיע לסופה, כמו בועה שעולה אל פני המים. נעקוב קודם אחר מעבר אחד:

וזה המעבר בתוכנית, על רשימה קצרה יותר. ההחלפה בשורה אחת, כפי שלמדנו בסעיף 2.6, כי כל הצד הימני מחושב לפני ההשמה:

nums = [7, 3, 9, 1]
for j in range(3):
    if nums[j] > nums[j + 1]:
        nums[j], nums[j + 1] = nums[j + 1], nums[j]
print(nums)

האיבר הגדול ביותר הגיע למקומו, אבל השאר עדיין לא ממוין. לכן חוזרים על המעבר. בכל מעבר חדש נכנס עוד איבר למקומו בסוף, ומקצרים את התחום באחד. רשימה של n איברים זקוקה ל-n−1 מעברים:

nums = [7, 3, 9, 1, 5]
n = len(nums)
for i in range(n - 1):
    for j in range(n - 1 - i):
        if nums[j] > nums[j + 1]:
            nums[j], nums[j + 1] = nums[j + 1], nums[j]
print(nums)

[1, 3, 5, 7, 9]

התנאי nums[j] > nums[j + 1] קובע את הכיוון, ולמיון בסדר יורד כותבים <. ומכיוון שהאופרטור > עובד גם על מחרוזות, אותה תוכנית ממיינת אותן לפי סדר מילוני.

v = [4, 2, 5, 1]
for j in range(3):
    if v[j] > v[j + 1]:
        v[j], v[j + 1] = v[j + 1], v[j]
print(v)

(ד-2) מיון החלפה:

במיון החלפה בונים את האזור הממוין מן ההתחלה: מציבים בתא הראשון את האיבר הקטן ביותר. משווים את התא לכל תא שאחריו, וכל פעם שמוצאים איבר קטן יותר מחליפים ביניהם. אחר כך עוברים לתא השני, וכן הלאה.

nums = [7, 3, 9, 1, 5]
n = len(nums)
for i in range(n - 1):
    for j in range(i + 1, n):
        if nums[j] < nums[i]:
            nums[i], nums[j] = nums[j], nums[i]
print(nums)

[1, 3, 5, 7, 9]

ההבדל בין שני המיונים: במיון בועות משווים כל איבר לשכנו והגדול ביותר מגיע לסוף, ובמיון החלפה משווים תא קבוע לכל מה שאחריו והקטן ביותר מגיע להתחלה. שניהם בשתי לולאות מקוננות. כמה השוואות דורש המיון? נמנה אותן:

for n in [5, 10, 100, 1000]:
    count = 0
    for i in range(n - 1):
        for j in range(n - 1 - i):
            count += 1
    print(n, count)

5 10
10 45
100 4950
1000 499500

פי עשרה איברים פירושו בערך פי מאה השוואות, כי המספר שווה ל-n(n−1)/2. לכן האלגוריתמים האלה אינם מתאימים למיליוני איברים, והפעולה sort המוכנה משתמשת באלגוריתם יעיל יותר. כותבים מיון בעצמנו כדי להבין איך הוא עובד, ובתוכנית רגילה משתמשים ב-sort.

6.13 אתחול טאפל, הפעולה tuple, הדפסה (tuple)

כותבים את איבריו בין סוגריים עגולים. טאפל מתאים לערכים ששייכים זה לזה, כמו שעת המדידה והמתח שלה, או לנתונים שאסור שישתנו, כמו הגדרות של הדק בבקר.

reading = (8, 12.4)
pin = ("A0", "input", 5)
empty = ()
one = (5,)
print(reading, pin)
print(empty, one, len(pin))
print(type(reading))

(8, 12.4) ('A0', 'input', 5)
() (5,) 3
<class 'tuple'>

הפעולה tuple ממירה לטאפל כפי ש-list ממירה לרשימה. הסוגריים אינם הכרחיים ביצירה: הפסיק הוא שיוצר את הטאפל. כבר פגשנו אותו בלי לקרוא לו בשם: הפעולה divmod בפרק 2 נותנת טאפל, וההשמה v, i = 12, 0.5 בונה אחד ואז מפרקת אותו:

print(tuple([1, 2, 3]))
print(tuple("ADC"))
print(tuple(range(4)))
pair = 12, 0.5
print(pair)
print(divmod(17, 5))

(1, 2, 3)
('A', 'D', 'C')
(0, 1, 2, 3)
(12, 0.5)
(3, 2)

reading = (8, 12.4)
reading[1] = 12.0

TypeError: 'tuple' object does not support item assignment

reading = (8, 12.4)
temp = list(reading)
temp[1] = 12.0
reading = tuple(temp)
print(reading)

(8, 12.0)

6.14 המבנה הסידורי של טאפל, אינדקס וחיתוך

אינדקס וחיתוך עובדים בדיוק כמו ברשימה, חיוביים ושליליים, והחיתוך נותן טאפל חדש. גם כאן אינדקס מחוץ לתחום עוצר את התוכנית. ואפשר לפרק טאפל למשתנים בפקודה אחת, בתנאי שמספרם שווה למספר האיברים:

rec = (14, 12.6, "OK")
print(rec[0], rec[-1])
print(rec[1:])
hour, volts, status = rec
print(hour, volts, status)

14 OK
(12.6, 'OK')
14 12.6 OK

colors = ("black", "brown", "red", "orange", "yellow",
          "green", "blue", "violet", "gray", "white")
first = 4
second = 7
power = 2
print(colors[first], colors[second], colors[power])
print((first * 10 + second) * 10 ** power, "ohm")

yellow violet red
4700 ohm

t = (2, 4, 6, 8, 10)
print(t[1], t[-1])
print(t[1:3])
print(t[::2])
a, b = t[:2]
print(a + b)

6.15 לולאת for העוברת על איברי טאפל

log = [(8, 12.4), (10, 12.7), (12, 13.1)]
print(log[1], log[1][0])
for hour, volts in log:
    print("Hour", hour, ":", volts, "V")

(10, 12.7) 10
Hour 8 : 12.4 V
Hour 10 : 12.7 V
Hour 12 : 13.1 V

log = [(1, 5), (2, 9), (3, 4)]
s = 0
for a, b in log:
    if a != 2:
        s += b
print(s)

6.16 עבודה עם פעולות המחלקה: count, index

מכיוון שטאפל אינו משתנה, יש לו רק שתי פעולות, ושתיהן שואלות ואינן משנות. הפעולה count נותנת כמה פעמים הערך מופיע, והפעולה index נותנת את האינדקס של ההופעה הראשונה שלו, ואפשר לקבוע לה מהיכן להתחיל לחפש.

bits = (1, 0, 1, 1, 0, 1)
print(bits.count(1))
print(bits.index(0), bits.index(0, 2))
print(bits.count(1) % 2)

4
1 4
0

השורה האחרונה מחשבת את סיבית הזוגיות: השארית של מספר הסיביות שערכן 1 בחלוקה ב-2. נחזור לסיבית הזאת בתקשורת טורית בפרק 10. הפעולה index קיימת גם ברשימה, ועובדת באותה דרך.

rails = (3.3, 5, 12, 5)
wanted = 5
if wanted in rails:
    print(rails.index(wanted), rails.count(wanted))
else:
    print("No such rail")

1 2

days = (0, 2, 2, 5, 2, 0)
print(days.count(2))
print(days.index(2))
print(days.index(0, 1))

log = []
counts = [0, 0, 0]
hour = int(input("Hour (-1 to stop): "))
while hour != -1:
    volts = float(input("Battery V: "))
    log.append((hour, volts))
    if volts < 11.8:
        counts[0] += 1
    elif volts <= 12.6:
        counts[1] += 1
    else:
        counts[2] += 1
    hour = int(input("Hour (-1 to stop): "))
print(log)
print("Low, OK, High:", counts)

Hour (-1 to stop): 8
Battery V: 12.4
Hour (-1 to stop): 12
Battery V: 13.1
Hour (-1 to stop): 18
Battery V: 11.6
Hour (-1 to stop): -1
[(8, 12.4), (12, 13.1), (18, 11.6)]
Low, OK, High: [1, 1, 1]

log = [(8, 12.4), (12, 13.1), (18, 11.6)]
best = log[0]
readings = []
for rec in log:
    readings.append(rec[1])
    if rec[1] > best[1]:
        best = rec
print("Highest:", best[1], "V at hour", best[0])
readings.sort()
print("Sorted:", readings)

Highest: 13.1 V at hour 12
Sorted: [11.6, 12.4, 13.1]

עיקרי הפרק:

• מבנה נתונים שומר הרבה ערכים תחת שם אחד, והם אינם אובדים אחרי הלולאה.
• האינדקס מתחיל מ-0, האינדקס האחרון קטן באחד מן האורך, ואינדקס שלילי סופר מן הסוף.
• ברשימת מונים הערך עצמו הופך לאינדקס של המונה שלו, ואין צורך בשרשרת תנאים.
• ההשמה b = a אינה מעתיקה רשימה, אלא נותנת לה שם שני. העתק כותבים a[:].
• הלולאה for v in a נותנת את הערך של כל איבר. כדי לשנות איברים עוברים על האינדקסים בעזרת range(len(a)).
• לא מוחקים מרשימה תוך כדי מעבר עליה, ו-sort אינה מחזירה רשימה.
• מחפשים ערך קיצון החל מאיבר של הרשימה, ולא מאפס.
• רשימה משתנה וטאפל אינו משתנה. יומן הקריאות הוא רשימה, והקריאה האחת היא טאפל.

סיכום פקודות הפרק:

מילון מונחים:

שאלות לתרגול:

v = [4, 8, 15, 16, 23, 42]
print(v[2], v[-2])
print(v[1:3])
print(v[::3])
print(len(v[2:]))

currents = []
for k in range(4):
    currents.append(float(input("Current: ")))
print("Total:", sum(currents))
print("Largest:", max(currents))

volts = [12, 5, 3]
for i in range(len(volts) + 1):
    print(volts[i])
volts = volts.sort()
print(volts[0])

volts = [12, 5, 3]
for i in range(len(volts)):
    print(volts[i])
volts.sort()
print(volts[0])

samples = [0.4, 1.2, 1.9, 3.3, 4.8, 1.1, 0.7, 3.9]
counts = [0, 0, 0, 0, 0]
for v in samples:
    counts[int(v)] += 1
print(counts)

samples = [2, 4, 9, 4, 2, 6]
smooth = []
for i in range(len(samples) - 2):
    window = samples[i:i + 3]
    smooth.append(round(sum(window) / 3, 2))
print(smooth)

levels = [2, 7, 3, 4, 9, 1, 5, 2]
for i in range(1, len(levels) - 1):
    if levels[i - 1] < levels[i] > levels[i + 1]:
        print("Peak at index", i, "level", levels[i])

a = [6, 3, 8]
b = []
for x in a:
    if x > 4:
        b.append(x - 4)
a[0] = len(b)
print(a, b)

nums = [3, 8, 2, 9, 4, 7]
n = len(nums)
passes = 0
swapped = True
while swapped:
    swapped = False
    passes += 1
    for j in range(n - 1):
        if nums[j] < nums[j + 1]:
            nums[j], nums[j + 1] = nums[j + 1], nums[j]
            swapped = True
print(nums)
print("Passes:", passes)

data = [[1.2, 1.4, 1.1, 1.3],
        [3.0, 3.3, 3.1, 3.2],
        [0.5, 4.9, 0.4, 0.6]]
best = 0
top = sum(data[0]) / len(data[0])
for ch in range(len(data)):
    average = sum(data[ch]) / len(data[ch])
    print("Channel", ch, round(average, 2), max(data[ch]))
    if average > top:
        top = average
        best = ch
print("Highest average: channel", best)

bits = (1, 0, 1, 1, 0, 0, 1, 0)
value = 0
for b in bits:
    value = value * 2 + b
print(value)
print("Parity bit:", bits.count(1) % 2)

reg = [1, 0, 0, 1, 1, 0]
k = int(input("Shift: "))
k = k % len(reg)
reg = reg[-k:] + reg[:-k]
print(reg)

שאלות בגרות לפרק 6

בגרות 2026 שאלה 11 — הצבעה לחמישים שירים

סעיף	המבוקש	תשובה
(א)	קולטים בלולאה מספר שיר עד שנקלט מספר מחוץ לטווח, ומונים את ההצבעות ברשימת מונים.	למטה
(ב)	מציגים את מספר השיר שקיבל את מספר הקולות הגבוה ביותר, ואחד מהם אם יש כמה.	למטה
(ג)	מחשבים את ממוצע ההצבעות, ומציגים את מספרי השירים שקיבלו פחות ממנו.	למטה

הפתרון המלא: fahed-lab.com/exams/electronics-815381/815381/solutions/solution-2026

(א) השירים ממוספרים מ-1 עד 50 והאינדקסים מ-0 עד 49, ולכן המונה של השיר נמצא בתא song - 1. תנאי הלולאה הוא הטווח עצמו, וכל מספר מחוץ לו מסיים אותה. (ב) מחפשים את האינדקס של הגדול ביותר כמו בסעיף 6.12, ומדפיסים את האינדקס ועוד 1. (ג) מחשבים את הממוצע מסכום ההצבעות, ואז עוברים על הרשימה שוב. זה בדיוק מה שאי אפשר לעשות בלי רשימה.

songs = 50
votes = [0] * songs
song = int(input("Song number: "))
while 1 <= song <= songs:
    votes[song - 1] += 1
    song = int(input("Song number: "))
best = 0
for i in range(1, songs):
    if votes[i] > votes[best]:
        best = i
print("Most votes: song", best + 1)
average = sum(votes) / songs
print("Average:", average)
print("Below average:")
for i in range(songs):
    if votes[i] < average:
        print(i + 1, end=" ")

חמישים שירים פירושם פלט ארוך שאי אפשר לבדוק בעין. לכן נשנה זמנית את השורה הראשונה ל-songs = 5, ונקליד 2, 3, 2, 1, 2, 3, 5, 4, 2, 3, 6. המספר 6 מחוץ לטווח ומסיים את הקליטה. התוכנית מדפיסה: Most votes: song 2 , Average: 2.0 , Below average: , 1 4 5

וכשיש שוויון, ההשוואה > בוחרת את השיר הראשון, כי השני אינו גדול ממנו, והשאלה מקבלת כל אחד מהם:

בגרות 2025 שאלה 11 — חברת השליחויות

סעיף	המבוקש	תשובה
קליטה	קולטים בלולאה מספר שליח, מידת שביעות רצון וטיפ, ועוצרים במספר שליח לא חוקי.	למטה
טיפים	מציגים כמה כסף קיבלו שני השליחים יחד כטיפים.	למטה
הטוב ביותר	מציגים את מספר השליח שקיבל את הדירוג הגבוה ביותר.	למטה
בונוס	מציגים 20% מן הטיפים של השליח הטוב ביותר.	למטה

הפתרון המלא: fahed-lab.com/exams/electronics-815381/815381/solutions/solution-2025

לכל שליח שני ערכים שנצברים, ולכן בונים שתי רשימות צוברים מקבילות, והאינדקס courier - 1 מציין את אותו שליח בשתיהן. התנאי courier in [1, 2] מבטא את סוף הקליטה במקום שני תנאים שמחוברים באופרטור or.

tips = [0, 0]
ratings = [0, 0]
courier = int(input("Courier: "))
while courier in [1, 2]:
    ratings[courier - 1] += int(input("Rating (1-5): "))
    tips[courier - 1] += float(input("Tip: "))
    courier = int(input("Courier: "))
print("Total tips:", sum(tips))
if ratings[0] >= ratings[1]:
    best = 0
else:
    best = 1
print("Best courier:", best + 1)
print("Bonus:", tips[best] * 20 / 100)

Courier: 1
Rating (1-5): 5
Tip: 20
Courier: 2
Rating (1-5): 4
Tip: 30
Courier: 1
Rating (1-5): 2
Tip: 10
Courier: 0
Total tips: 60.0
Best courier: 1
Bonus: 6.0