Алгоритмдер және программалау (функция, рекурсия, жолдармен жұмыс, файлдармен жұмыс, сұрыптау, граф)

Тақырыпты талдау

Функциялар: def, параметрлер, return 10 сынып

Функция — атау берілген программа бөлігі. Бір рет жариялаймыз, қанша рет болса да шақырамыз. Үлгі: def аты(параметрлер):, одан кейін 4 бос орын шегініспен денесі жазылады. return сөзі функцияны аяқтап, нәтижені функция шақырылған жерге қайтарады.

def area(a, b=2):
    return a * b

print(area(3))        # b әдепкі мәннен алынады: 6
print(area(3, 5))     # 15
print(area(b=4, a=10))  # атаулы аргументтер: 40

Әдепкі мәні бар параметрді (b=2) бермеуге болады. Әдепкі мәнді параметрлер қарапайым параметрлерден кейін жазылады: def f(a, b=2) — дұрыс, def f(a=1, b) — қате. Шақыру кезінде аргументтерді атымен көрсетуге болады, сонда реті маңызды емес.

Функция бірден бірнеше мән қайтара алады: return a + b, a * b — кортеж шығады, оны «ашып» алу ыңғайлы: s, p = f(2, 3). return-нен кейінгі функция коды орындалмайды.

Егер return жоқ болса (немесе бос болса), функция None қайтарады. Бұл — процедура: ол бір әрекет жасайды (мысалы, басып шығарады), бірақ мән қайтармайды. ҰБТ-ның классикалық тұзағы: r = show(7) 14 шығарады, ал print(r) None шығарады.

Білу пайдалы кірістірілген функциялар: len, abs, max, min, sum, sorted, int, str, round, ord (символ коды), chr (код бойынша символ), range.

Көріну аймағы: жергілікті және глобалды айнымалылар 10 сынып

Функция ішінде жасалған айнымалы — жергілікті: ол тек шақыру кезінде өмір сүреді және сырттан көрінбейді. Негізгі программаның айнымалысы — глобалды: функция оны оқи алады, бірақ функция ішіндегі меншіктеу сол аттас жаңа жергілікті айнымалы жасайды.

x = 10

def f():
    x = 5          # жергілікті x, глобалдысына тимейді
    print(x)

def g():
    global x       # енді глобалды x-пен жұмыс істейміз
    x = x + 1

f()        # 5
print(x)   # 10
g()
print(x)   # 11

Есептерге арналған ереже: функцияда global x-сіз x = ... меншіктеуі болса — бұл басқа, жергілікті x. Егер global x болса — функция «ортақ» айнымалыны өзгертеді.

Функция параметрлері де — жергілікті айнымалылар. Сандар мен жолдарды параметр арқылы сырттан өзгерту мүмкін емес. Ал функцияға берілген тізімді әдістермен (a.append(...), a[0] = ...) өзгертуге болады — өзгерістер сыртта да көрінеді, сондықтан сұрыптауларда жиі a = a[:] көшірмесі жасалады.

Рекурсия: базалық жағдай және шақырулар стегі 10–11 сынып

Рекурсивті функция кішірек есеп үшін өзін-өзі шақырады. Міндетті екі элемент бар: базалық жағдай (бірден жауап береміз) және рекурсивті қадам (есепті кішірегіне келтіреміз). Базалық жағдай болмаса, рекурсия шексіз болып, RecursionError қатесі шығады (Python-да тереңдік шегі әдепкі бойынша шамамен 1000).

def fact(n):            # n! = 1·2·…·n
    if n <= 1:          # базалық жағдай
        return 1
    return n * fact(n - 1)

def power(a, n):        # a-ның n дәрежесі
    if n == 0:
        return 1
    return a * power(a, n - 1)

def digsum(n):          # цифрлар қосындысы
    if n < 10:
        return n
    return n % 10 + digsum(n // 10)

def fib(n):             # 1, 1, 2, 3, 5, 8, 13, ...
    if n <= 2:
        return 1
    return fib(n - 1) + fib(n - 2)

Қалай жұмыс істейді: әр шақыру шақырулар стегіне (тәрелкелер бумасы сияқты) салынады және кішірек шақыру қайтқанша күтеді. fact(4) fact(3)-ті күтеді, ол fact(2)-ні, ол — fact(1)-ді. fact(1) бірден 1 қайтарады, сосын стек кері «тарқатылады»: $2\cdot1=2$, $3\cdot2=6$, $4\cdot6=24$.

Егер функция ішінде екі рекурсивті шақыру болса (fib-тегідей), шақырулар ағаш сияқты тармақталады және олардың саны өте тез өседі: fib(6) функцияны 15 рет, fib(7) — 25 рет шақырады. Шақыруларды $C(n)=C(n-1)+C(n-2)+1$, $C(1)=C(2)=1$ формуласымен санау ыңғайлы.

Шығару реті. Егер print рекурсивті шақырудан БҰРЫН тұрса, сандар «түсу кезінде» (тура ретпен) басылады; КЕЙІН тұрса — «көтерілу кезінде» (кері ретпен). Мысал: def g(n): print(n); if n > 1: g(n // 2); print(n) функциясы g(10) кезінде 10 5 2 1 1 2 5 10 шығарады.

Кез келген рекурсияны циклмен (итерациямен) алмастыруға болады және керісінше. Цикл әдетте жылдамырақ және стекті жұмсамайды; рекурсия «өзіне ұқсас» есептерде — ағаштар мен графтарды аралауда (DFS), жылдам сұрыптауда, рекурренттік формула бойынша есептеуде қысқа жазылады.

Жолдар: индекстер, кесінділер, аралау 10 сынып

Жол — символдар тізбегі. Нөмірлеу солдан 0-ден, оңнан −1-ден басталады. s = "informatika" (11 символ) үшін: s[0] = i, s[4] = r, s[-1] = a, len(s) = 11. Жол шегінен тыс индекс (мысалы s[11]) IndexError қатесін береді.

s[start:stop:step] кесіндісі start нөмірінен stop-қа дейінгі символдарды, stop-ты ҚОСПАЙ, step қадамымен алады. start жазылмаса — басынан, stop жазылмаса — соңына дейін. s[2:5] = for, s[:4] = info, s[7:] = tika, s[-3:] = ika, s[::2] = ifraia, s[1::3] = nrta, s[::-1] = akitamrofni (жол кері ретпен). Жол шегінен тыс кесінді қате бермейді — бар бөлігін ғана қайтарады.

Жолдар өзгермейді: s[0] = "I" — қате. Жолды «өзгерту» үшін жаңасын құрады: s = "I" + s[1:]. Амалдар: + біріктіреді, * қайталайды ("ab" * 3 = ababab), in ішінде бар-жоғын тексереді ("for" in s → True), жолдар символ кодтары бойынша символдап салыстырылады ("apple" < "banana", бірақ "Z" < "a", себебі бас әріптердің коды кішірек).

Жолды аралау: for ch in s: — символдар бойынша; for i in range(len(s)): — индекстер бойынша (орны маңызды болғанда керек, мысалы s[i] мен s[i+1]-ді салыстыру). Символ кодтары: ord("A") = 65, ord("a") = 97, chr(66) = B.

Жол әдістері, палиндромдар, символдарды санау, сөздіктер мен жиындар 10 сынып

Әдістер жолды өзгертпейді, жаңа жол қайтарады: s.upper() / s.lower() — әріп регистрі; s.strip() — шеттеріндегі бос орындарды алып тастау; s.replace(a, b) — барлық a-ны b-ға ауыстыру (s.replace(a, b, 1) — тек біріншісін); s.find(x) — бірінші кездесу индексі, жоқ болса −1; s.count(x) — қиылыспайтын кездесулер саны; s.split(sep) — тізімге бөлу; sep.join(тізім) — жолдар тізімін біріктіру; s.isdigit() / s.isalpha() — жол тек цифрлардан / әріптерден тұра ма.

t = "Astana, Almaty, Shymkent"
parts = t.split(", ")     # ['Astana', 'Almaty', 'Shymkent']
print("-".join(parts))     # Astana-Almaty-Shymkent
print(t.find("Almaty"))    # 8
print(t.lower().count("a")) # 5
print("aaaa".count("aa"))  # 2 (3 емес!)

Палиндром — солдан оңға және оңнан солға бірдей оқылатын жол: level, kazak, 12321. Бір жолмен тексеру: s == s[::-1]. Егер регистр маңызды болмаса, алдымен s = s.lower(); бос орындарды елемеу керек болса — s.replace(" ", "").

Символдарды санау. Цифрлар: if ch.isdigit(): total += int(ch). Әріптердің жиілігін сөздікте сақтау ыңғайлы: freq[ch] = freq.get(ch, 0) + 1; "banana" үшін {'b': 1, 'a': 3, 'n': 2} шығады. Сөздік (dict) «кілт: мән» жұптарын сақтайды, кілт бойынша қатынау d["a"], len(d) — кілттер саны.

Жиын (set) тек қайталанбайтын элементтерді ретсіз сақтайды: set("banana") = {'a', 'b', 'n'}, len(set(s)) — әртүрлі символдар саны. Амалдар: | біріктіру, & қиылысу, - айырма.

Файлдармен жұмыс 7, 10 сынып

Файл open(аты, режим) функциясымен ашылады. Режимдер: "r" — оқу (әдепкі; файл жоқ болса — қате), "w" — жазу (файл жасалады, ал бұрын болса — толығымен ТАЗАЛАНАДЫ), "a" — соңына қосып жазу (ескі мазмұны сақталады). with open(...) as f: құрылымы блоктан кейін файлды өзі жабады — f.close()-ты қолмен шақырғаннан гөрі осылай жазған дұрыс.

Оқу: f.read() — бүкіл файл бір жол болып; f.readline() — соңындағы \n символымен бірге келесі бір жол; f.readlines() — барлық (қалған) жолдар тізімі; for line in f: — жолдарды бір-бірлеп аралау. Жазу: f.write(мәтін) тек жол жазады және жаңа жолға көшуді ӨЗІ ҚОСПАЙДЫ — \n-ді анық жазу керек; сандарды жазар алдында жолға айналдырады: f.write(str(x) + "\n").

with open("data.txt", "w") as f:
    f.write("5\n12\n7\n20\n3\n")

with open("data.txt") as f:
    nums = [int(line) for line in f]   # int \n-ді өзі алып тастайды

print(sum(nums), max(nums))   # 47 20

Типтік есеп: «файлда әр жолға бір саннан жазылған, қосындысын / жұп сандар санын / ең үлкенін табыңыз». Үлгі: жолдарды оқу, әрқайсысын санға айналдыру (int(line) немесе int(line.strip())), әрі қарай санауышы бар кәдімгі цикл. Егер сандар бір жолда бос орын арқылы жазылса: nums = list(map(int, f.read().split())).

Файл магнитофон сияқты тізбектей оқылады: readline()-нан кейін «көрсеткіш» келесі жолда тұрады, ал readlines() тек қалған жолдарды қайтарады. Басынан қайта оқу үшін файлды қайта ашу керек.

Сұрыптау және іздеу 9–10 сынып

Көпіршікті сұрыптау: массивті аралап, көршілерді салыстырамыз және сол жақтағысы үлкен болса, орындарын ауыстырамыз. Бірінші өтуден кейін ең үлкен элемент соңына «қалқып шығады»; $k$-өтуден кейін соңғы $k$ элемент өз орнында тұрады. $n$ элемент үшін: $n-1$ өту, салыстырулар саны $(n-1)+(n-2)+\dots+1=\frac{n(n-1)}{2}$. Алмастырулар саны «инверсиялар» санына — дұрыс емес ретте тұрған жұптар санына тең.

Таңдау арқылы сұрыптау: $i$-қадамда $i$-элементтен соңына дейінгі элементтердің ең кішісін тауып, оны $i$-элементпен алмастырамыз. Салыстырулар саны да $\frac{n(n-1)}{2}$, бірақ алмастырулар $n-1$-ден аспайды. Кірістіру арқылы сұрыптау: кезекті элементті алып, сол жағында үлкені тұрғанша оны солға жылжытамыз — қолдағы карталарды осылай реттейді; дерлік сұрыпталған деректерде өте тез жұмыс істейді.

for i in range(n - 1):              # көпіршік
    for j in range(n - 1 - i):
        if a[j] > a[j + 1]:
            a[j], a[j + 1] = a[j + 1], a[j]

Кірістірілген құралдар: sorted(a) ЖАҢА сұрыпталған тізім қайтарады, a.sort() тізімнің өзін сұрыптайды және None қайтарады. Параметрлер: reverse=True — кему бойынша; key=функция — белгі бойынша сұрыптау: sorted(words, key=len) — ұзындығы бойынша, a.sort(key=abs) — модулі бойынша. Python-дағы сұрыптау орнықты: кілті бойынша тең элементтер бастапқы ретін сақтайды.

Сызықтық іздеу — элементтерді ретімен қараймыз; ең нашар жағдайда $n$ салыстыру, кез келген массивте жұмыс істейді. Екілік (бинарлық) іздеу — тек СҰРЫПТАЛҒАН массив үшін: ортаңғы mid = (lo + hi) // 2 элементпен салыстырып, ізделетін сан бола алмайтын жартысын тастаймыз; қадамдар саны $\lceil\log_2(n+1)\rceil$-ден аспайды (1000 элемент үшін — 10, миллион үшін — 20).

Графтар: берілуі, аралау, ең қысқа жол, ағаштар 10 сынып

Граф — төбелер мен қабырғалар. Бағытталмаған граф: A–B қабырғасы бойынша екі жаққа да жүруге болады (жолдар). Бағытталған граф: A→B доғасы тек бір жаққа апарады (бір бағытты көшелер, жазылулар). Салмақты граф: әр қабырғаның саны — салмағы бар (қашықтық, уақыт, құн). Жол — қабырғалармен қосылған төбелер тізбегі; жолдың ұзындығы — қабырғалар саны немесе салмақтар қосындысы; цикл — бастапқы төбеге қайта оралатын жол.

Төбенің дәрежесі — одан шығатын қабырғалар саны (тұзақ 2 береді). Барлық төбелер дәрежелерінің қосындысы $2|E|$-ге тең, сондықтан тақ дәрежелі төбелер саны әрқашан жұп. Бағытталған графта кіру және шығу жарты дәрежелері ажыратылады.

Сыбайластық матрицасы — $n\times n$ кесте: A–B қабырғасы болса, [A][B] ұяшығында 1 (немесе салмақ), болмаса 0 немесе сызықша тұрады. Бағытталмаған графтың матрицасы бас диагональға қатысты симметриялы; төбенің дәрежесі = оның жолының қосындысы. Сыбайластық тізімі — әр төбе үшін көршілерін тізіп шығамыз; Python-да сөздікпен ыңғайлы: g = {"A": ["B", "C"], "B": ["A", "D"], ...}.

Ені бойынша аралау (BFS) — «толқынмен»: алдымен бастапқы төбенің барлық көршілері, сосын олардың көршілері т.с.с. Кезекті пайдаланады; қабырғалар саны ең аз жолды табады. Тереңдігі бойынша аралау (DFS) — бір тармақпен мүмкіндігінше алысқа барамыз, тірелсек — артқа қайтамыз; рекурсиямен жазу ыңғайлы.

Салмақты графтағы ең қысқа жол (Дейкстра алгоритмі, кесте бойынша қолмен шешіледі): 1) бастапқы төбеге 0, қалғандарына ∞ белгісін қоямыз; 2) белгісі ең кіші, әлі бекітілмеген төбені таңдап, оны «бекітеміз»; 3) оның әр көршісінің белгісін жақсартып көреміз: жаңа белгі = ағымдағы төбенің белгісі + қабырға салмағы, ескісінен кіші болса — ауыстырамыз; 4) соңғы төбеге дейін қайталаймыз. Басты ереже: тура қабырға міндетті түрде ең қысқасы емес — басқа төбелер арқылы айналма жол арзанырақ болуы мүмкін.

Ағаш — циклсіз байланысқан граф; $n$ төбелі ағашта дәл $n-1$ қабырға бар және кез келген екі төбе арасында дәл бір жол бар. Тамырлы ағаш: тамыр, ата-аналар, ұрпақтар, жапырақтар (ұрпағы жоқ төбелер). Ағаш түрінде бумалар құрылымын, шежірені, рекурсивті шақырулар ағашын бейнелейді. Циклсіз бағытталған графтағы жолдар саны былай есептеледі: төбеге апаратын жолдар саны = оған доға кіретін барлық төбелерге апаратын жолдар сандарының қосындысы.