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

Оқулықтық тірек

• Қадырқұлов Р. Ә., Нұрмұханбетова Г. К. «Информатика. ЖМБ 10-сынып», 10-сынып, Алматыкітап баспасы, 2019, 1–31-беттер (§ 1–5)
• Мұхамбетжанова С. Т., Тен А. С., Голикова Н. Г. «Информатика», 9-сынып, Атамұра, 2019, 147–155-беттер
• Қадырқұлов Р. А., Рысқұлбекова Ә. Д., Нұрмұханбетова Г. К. «Информатика», 7-сынып, Алматыкітап баспасы, 2023, 105–114-беттер
• Wikipedia, Рекурсия: https://ru.wikipedia.org/wiki/Рекурсия
• MDN, Recursion: https://developer.mozilla.org/en-US/docs/Glossary/Recursion

Негізгі ұғымдар

• Модульдік программалау — есепті шағын тәуелсіз функцияларға бөлу.
• Функция мән қайтарады (return), процедура — әрекет орындайды, мән қайтармайды (Python-да None).
• Жергілікті айнымалы функция ішінде ғана көрінеді, ауқымды — бүкіл программада.
• Жол (str) — өзгермейтін тип; индекс 0-ден (соңынан −1-ден); қию s[start:stop:step].
• Файл режимдері: 'r' — оқу, 'w' — жазу (ескісін өшіреді), 'a' — соңына қосу, 'b' — екілік, '+' — оқу/жазу.
• Қарапайым сұрыптаулар (көпіршікті, таңдау, кірістіру) — $O(n^2)$; жылдам (Хоар), біріктіру — $O(n \log n)$.
• Граф $G = (V, E)$: төбелер мен қабырғалар; BFS — кезек (FIFO), DFS — стек (LIFO) немесе рекурсия.

Теория

Функциялар. Жариялау: def name(param1, param2):, денесі шегініспен, нәтиже return арқылы қайтарылады. Функцияны шақырғанда аргументтер параметрлерге беріледі.

Жолдар. Негізгі амалдар: индекстеу s[0], s[-1]; қию s[2:5], s[::-1] (кері жол); біріктіру +; қайталау *; ұзындық len(s). Әдістер:

Әдіс	Нәтижесі
s.find(sub)	алғашқы кездескен индекс, табылмаса $-1$
s.replace(old, new)	барлық old-ты new-ге ауыстырады
s.split(sep)	жолды тізімге бөледі
sep.join(list)	тізімді жолға біріктіреді
s.upper() / s.lower()	бас / кіші әріпке түрлендіреді
s.strip()	басы мен соңындағы бос орындарды алады

Жол өзгермейтін болғандықтан s[0] = 'A' қате береді; жаңа жол құру керек.

Файлдар. Жұмыс үш қадамнан тұрады: ашу → оқу/жазу → жабу. open("data.txt", "r", encoding="utf-8"). Оқу: read() — бүкіл файл бір жол ретінде, read(n) — $n$ таңба, readline() — бір жол, readlines() — жолдар тізімі. Жазу: write(text) — тек жолды жазады, сондықтан сан str() арқылы айналдырылады; жаңа жол — '\n'. seek(n) меңзерді $n$-позицияға қояды. close() жазылмаса деректер сақталмауы мүмкін; with менеджері файлды автоматты жабады. 'r' режимінде файл жоқ болса қате шығады.

Сұрыптау — элементтерді өсу не кему ретімен орналастыру; сұрыпталған массивте екілік іздеу $O(\log n)$ уақытта жүреді.

• Көпіршікті: көршілес элементтер салыстырылып ауыстырылады; әр өтуде ең үлкені соңына «қалқып шығады»; өтулер саны $n - 1$, салыстырулар $\dfrac{n(n-1)}{2}$.
• Таңдау: реттелмеген бөліктен ең кішісін тауып, оны бөліктің басына қояды.
• Кірістіру: кезекті элемент реттелген бөліктің тиісті орнына қойылады; жартылай реттелген деректерде тиімді.
• Тез сұрыптау (Хоар) — тірек элемент (pivot), «бөліп ал да билей бер»; біріктіру — кепілді $O(n \log n)$.
• Python: a.sort() тізімнің өзін өзгертеді және None қайтарады; sorted(a) жаңа тізім қайтарады, бастапқысы өзгермейді; reverse=True — кему ретімен.

Графтар. Бағытталған (орграф), бағытталмаған, салмақты графтар. Ұсыну тәсілдері: көршілестік матрицасы ($N \times N$) және көршілестік тізімі (сөздік, жадты үнемдейді). BFS бастапқы төбенің барлық көршілерін, содан кейін келесі деңгейді аралайды — салмақсыз графта ең қысқа жолды табады. DFS бір бағытпен тұйыққа дейін барып, кейін шегінеді — байланыстылық пен циклдарды іздеуде қолданылады.

def find_max(a, b):
    if a > b:
        return a
    return b

print(find_max(15, 27))          # 27

text = "қазақ"
print(text == text[::-1])         # True — палиндром

def bubble_sort(arr):
    n = len(arr)
    for i in range(n - 1):
        for j in range(n - 1 - i):
            if arr[j] > arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]
    return arr

print(bubble_sort([64, 25, 12, 22, 11]))  # [11, 12, 22, 25, 64]

with open("Input.txt") as fin:
    a, b = map(int, fin.read().split())
with open("Output.txt", "w") as fout:
    fout.write(str(a + b) + '\n')

Рекурсия

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

• Факториал: $n!=n\cdot(n-1)!$, $0!=1$ — базалық жағдай $n=0$.
• Фибоначчи сандары: $n$-мүше үшін $(n-1)$- және $(n-2)$-мүше есептеледі, яғни бір тармақта екі шақыру болады.

Мысалдар

1. [1, 6, 9, 7, 8, 3] тізімін көпіршікпен кему ретімен сұрыптағанда 1-өтуден кейін? [6, 9, 7, 8, 3, 1] — ең кішісі соңына жылжиды. Барлық салыстыру: $5 + 4 + 3 + 2 + 1 = 15$.
2. s = "informatika"; s.find("ma"), s[2:5]? 5 және "for".
3. Input.txt-те 12 15. Жоғарыдағы код Output.txt-ке не жазады? 27.
4. Графта: A–B, A–C, B–D, C–E. A-дан BFS реті? A B C D E.

ҰБТ-дағы жиі қателер

• 'w' режимі файлды толықтырады деп ойлау: ол ескі мазмұнды өшіреді, толықтыратын — 'a'.
• a = a.sort() жазу: нәтижесі None, тізім жоғалады.
• s.find() табылмағанда қате береді деп санау: ол $-1$ қайтарады.
• write(5) жазу: тек жол жазылады, write(str(5)) керек.
• BFS пен DFS құралдарын шатастыру: BFS — кезек, DFS — стек/рекурсия.
• Қию s[2:5]-ке 5-индекс кіреді деп ойлау.

Өзіңді тексер

1. Мән қайтармайтын қосымша программа қалай аталады? — Процедура.
2. "abc" * 2 нәтижесі? — "abcabc".
3. Файл соңына дерек қосу режимі? — 'a'.
4. Таңдау арқылы сұрыптаудың күрделілігі? — $O(n^2)$.
5. Салмақсыз графта ең қысқа жолды қай алгоритм табады? — BFS (ені бойынша іздеу).