{ "cells": [ { "cell_type": "markdown", "metadata": {}, "source": [ "# Лекция 1. Введение. Алгоритм и язык Python\n", "\n", "Курс **«Алгоритмы и структуры данных»** (факультет искусственного интеллекта МГУ). Два рабочих критерия качества алгоритма:\n", "\n", "- **корректность** — на всех допустимых входах ответ верный;\n", "- **эффективность** — время и память растут приемлемо с размером входа.\n", "\n", "Python 3 здесь — язык *записи и реализации*. Где задание требует свою реализацию, встроенными аналогами пользоваться нельзя.\n", "\n", "Сегодня: как записать алгоритм и обработать поток чисел, не складывая вход в память.\n", "\n", "## План\n", "\n", "1. Алгоритм. Псевдокод, блок-схема, Python.\n", "2. Основы языка Python.\n", "3. Функции: капсула, чистая функция, контракт.\n", "4. Потоки чисел и память $O(1)$." ], "id": "intro" }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Алгоритм\n", "\n", "**Алгоритм** — это\n", "\n", "1. последовательность команд\n", "2. на формальном языке исполнителя,\n", "3. приводящая к цели\n", "4. за конечное время.\n", "\n", "Исполнитель действует формально: не «додумывает» шаг, если выбор не прописан в самом алгоритме. Это **детерминированность**. Конечность тоже обязательна: зацикливание без достижения цели — не алгоритм." ], "id": "algorithm" }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Языки описания\n", "\n", "Один и тот же алгоритм можно записать псевдокодом, блок-схемой и на Python. Задача: по натуральному $n$ вычислить сумму $1 + 2 + \\ldots + n$.\n", "\n", "**Псевдокод.**\n", "\n", "```\n", "ввести n\n", "s ← 0\n", "для x от 1 до n:\n", " s ← s + x\n", "вывести s\n", "```" ], "id": "languages" }, { "cell_type": "markdown", "metadata": {}, "source": [ "**Блок-схема.**\n", "\n", "\n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " начало\n", " \n", " \n", " ввести n\n", " \n", " \n", " s ← 0\n", " \n", " \n", " x ← 1\n", " \n", " \n", " x ≤ n?\n", " \n", " \n", " \n", " нет\n", " \n", " да\n", " \n", " s ← s + x\n", " \n", " \n", " x ← x + 1\n", " \n", " \n", " \n", " \n", " \n", " вывести s\n", " \n", " \n", " конец\n", "" ], "id": "flowchart" }, { "cell_type": "markdown", "metadata": {}, "source": [ "**Python.** Исполнитель курса — интерпретатор Python: те же шаги, формальный синтаксис." ], "id": "python-sum-md" }, { "cell_type": "code", "metadata": {}, "source": [ "n = 5\n", "s = 0\n", "x = 1\n", "while x <= n:\n", " s = s + x\n", " x = x + 1\n", "print(s)" ], "execution_count": 1, "outputs": [ { "output_type": "stream", "text": [ "15\n" ], "name": "stdout" } ], "id": "python-sum" }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Основы языка Python\n", "\n", "Напоминание конструкций, без которых алгоритм не записать. Списков на этой лекции нет.\n", "\n", "### Операции с целыми\n", "\n", "| Операция | Действие |\n", "| --- | --- |\n", "| `A + B`, `A - B`, `A * B` | сумма, разность, произведение |\n", "| `A / B` | частное (вещественное) |\n", "| `A // B` | частное нацело |\n", "| `A % B` | остаток |\n", "| `A ** B` | степень |\n", "\n", "`//` и `%` разбирают число по разрядам: последняя цифра — `n % 10`, без последней — `n // 10`.\n", "\n", "Имя можно заставить обозначать новый объект: `s = s + x` или короче `s += x`." ], "id": "python-basics" }, { "cell_type": "code", "metadata": {}, "source": [ "n = 179\n", "print(n // 100, n // 10 % 10, n % 10)\n", "print(n // 100 + n // 10 % 10 + n % 10)" ], "execution_count": 2, "outputs": [ { "output_type": "stream", "text": [ "1 7 9\n", "17\n" ], "name": "stdout" } ], "id": "int-ops" }, { "cell_type": "code", "metadata": {}, "source": [ "1 - 3 - 7" ], "execution_count": 4, "outputs": [ { "output_type": "execute_result", "data": { "text/plain": [ "-9" ] }, "metadata": {}, "execution_count": 4 } ], "id": "a2b36859-3fd4-4112-8fb8-21236ba14cbe" }, { "cell_type": "code", "metadata": {}, "source": [ "1 / 2 / 2" ], "execution_count": 5, "outputs": [ { "output_type": "execute_result", "data": { "text/plain": [ "0.25" ] }, "metadata": {}, "execution_count": 5 } ], "id": "e37f92c3-fdfa-41ab-8b0c-4ad15eb8eba6" }, { "cell_type": "code", "metadata": {}, "source": [ "(3 ** 3) ** 3 == 3 ** (3*3)" ], "execution_count": 11, "outputs": [ { "output_type": "execute_result", "data": { "text/plain": [ "True" ] }, "metadata": {}, "execution_count": 11 } ], "id": "f5299ef2-8b42-4f41-8910-097badb2249f" }, { "cell_type": "code", "metadata": {}, "source": [ "-1 // 10" ], "execution_count": 15, "outputs": [ { "output_type": "execute_result", "data": { "text/plain": [ "-1" ] }, "metadata": {}, "execution_count": 15 } ], "id": "75ccb49a-6abd-42e6-8090-1f48e5f978c8" }, { "cell_type": "code", "metadata": {}, "source": [ "-1 % 10" ], "execution_count": 16, "outputs": [ { "output_type": "execute_result", "data": { "text/plain": [ "9" ] }, "metadata": {}, "execution_count": 16 } ], "id": "3ffebf0a-7807-45d0-b809-eb2f674377c1" }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Строки: `+` и `*`\n", "\n", "Сложение строк — конкатенация, умножение на целое — повтор." ], "id": "str-ops-md" }, { "cell_type": "code", "metadata": {}, "source": [ "a = \"алго\"\n", "b = \"ритм\"\n", "print(a + b)" ], "execution_count": 18, "outputs": [ { "output_type": "stream", "text": [ "алгоритм\n" ], "name": "stdout" } ], "id": "d814fb06-b922-4a94-9306-dd332a13bf0d" }, { "cell_type": "code", "metadata": {}, "source": [ "a + b == b + a" ], "execution_count": 19, "outputs": [ { "output_type": "execute_result", "data": { "text/plain": [ "False" ] }, "metadata": {}, "execution_count": 19 } ], "id": "4d90890d-3a64-4e0a-aab8-2fa271c8c0d3" }, { "cell_type": "code", "metadata": {}, "source": [ "print(\"-\" * 8)" ], "execution_count": 20, "outputs": [ { "output_type": "stream", "text": [ "--------\n" ], "name": "stdout" } ], "id": "str-ops" }, { "cell_type": "code", "metadata": {}, "source": [ "a * b" ], "execution_count": 21, "outputs": [ { "output_type": "error", "ename": "TypeError", "evalue": "can't multiply sequence by non-int of type 'str'", "traceback": [ "\u001b[31m---------------------------------------------------------------------------\u001b[39m", "\u001b[31mTypeError\u001b[39m Traceback (most recent call last)", "\u001b[36mCell\u001b[39m\u001b[36m \u001b[39m\u001b[32mIn[21]\u001b[39m\u001b[32m, line 1\u001b[39m\n\u001b[32m----> \u001b[39m\u001b[32m1\u001b[39m a * b\n", "\u001b[31mTypeError\u001b[39m: can't multiply sequence by non-int of type 'str'" ] } ], "id": "0c3fcc6f-c7f5-4c1e-a97f-03a0df91c0b7" }, { "cell_type": "code", "metadata": {}, "source": [ "2 ** 10000" ], "execution_count": 25, "outputs": [ { "output_type": "execute_result", "data": { "text/plain": [ "19950631168807583848837421626835850838234968318861924548520089498529438830221946631919961684036194597899331129423209124271556491349413781117593785932096323957855730046793794526765246551266059895520550086918193311542508608460618104685509074866089624888090489894838009253941633257850621568309473902556912388065225096643874441046759871626985453222868538161694315775629640762836880760732228535091641476183956381458969463899410840960536267821064621427333394036525565649530603142680234969400335934316651459297773279665775606172582031407994198179607378245683762280037302885487251900834464581454650557929601414833921615734588139257095379769119277800826957735674444123062018757836325502728323789270710373802866393031428133241401624195671690574061419654342324638801248856147305207431992259611796250130992860241708340807605932320161268492288496255841312844061536738951487114256315111089745514203313820202931640957596464756010405845841566072044962867016515061920631004186422275908670900574606417856951911456055068251250406007519842261898059237118054444788072906395242548339221982707404473162376760846613033778706039803413197133493654622700563169937455508241780972810983291314403571877524768509857276937926433221599399876886660808368837838027643282775172273657572744784112294389733810861607423253291974813120197604178281965697475898164531258434135959862784130128185406283476649088690521047580882615823961985770122407044330583075869039319604603404973156583208672105913300903752823415539745394397715257455290510212310947321610753474825740775273986348298498340756937955646638621874569499279016572103701364433135817214311791398222983845847334440270964182851005072927748364550578634501100852987812389473928699540834346158807043959118985815145779177143619698728131459483783202081474982171858011389071228250905826817436220577475921417653715687725614904582904992461028630081535583308130101987675856234343538955409175623400844887526162643568648833519463720377293240094456246923254350400678027273837755376406726898636241037491410966718557050759098100246789880178271925953381282421954028302759408448955014676668389697996886241636313376393903373455801407636741877711055384225739499110186468219696581651485130494222369947714763069155468217682876200362777257723781365331611196811280792669481887201298643660768551639860534602297871557517947385246369446923087894265948217008051120322365496288169035739121368338393591756418733850510970271613915439590991598154654417336311656936031122249937969999226781732358023111862644575299135758175008199839236284615249881088960232244362173771618086357015468484058622329792853875623486556440536962622018963571028812361567512543338303270029097668650568557157505516727518899194129711337690149916181315171544007728650573189557450920330185304847113818315407324053319038462084036421763703911550639789000742853672196280903477974533320468368795868580237952218629120080742819551317948157624448298518461509704888027274721574688131594750409732115080498190455803416826949787141316063210686391511681774304792596709376" ] }, "metadata": {}, "execution_count": 25 } ], "id": "0a037596-6817-47cb-bcad-5b5565a67283" }, { "cell_type": "code", "metadata": {}, "source": [ "x = 2 ** 10000" ], "execution_count": 26, "outputs": [], "id": "318511c0-02d4-4365-b7b8-9214c0a81ef0" }, { "cell_type": "code", "metadata": {}, "source": [ "print(x)" ], "execution_count": 27, "outputs": [ { "output_type": "stream", "text": [ "19950631168807583848837421626835850838234968318861924548520089498529438830221946631919961684036194597899331129423209124271556491349413781117593785932096323957855730046793794526765246551266059895520550086918193311542508608460618104685509074866089624888090489894838009253941633257850621568309473902556912388065225096643874441046759871626985453222868538161694315775629640762836880760732228535091641476183956381458969463899410840960536267821064621427333394036525565649530603142680234969400335934316651459297773279665775606172582031407994198179607378245683762280037302885487251900834464581454650557929601414833921615734588139257095379769119277800826957735674444123062018757836325502728323789270710373802866393031428133241401624195671690574061419654342324638801248856147305207431992259611796250130992860241708340807605932320161268492288496255841312844061536738951487114256315111089745514203313820202931640957596464756010405845841566072044962867016515061920631004186422275908670900574606417856951911456055068251250406007519842261898059237118054444788072906395242548339221982707404473162376760846613033778706039803413197133493654622700563169937455508241780972810983291314403571877524768509857276937926433221599399876886660808368837838027643282775172273657572744784112294389733810861607423253291974813120197604178281965697475898164531258434135959862784130128185406283476649088690521047580882615823961985770122407044330583075869039319604603404973156583208672105913300903752823415539745394397715257455290510212310947321610753474825740775273986348298498340756937955646638621874569499279016572103701364433135817214311791398222983845847334440270964182851005072927748364550578634501100852987812389473928699540834346158807043959118985815145779177143619698728131459483783202081474982171858011389071228250905826817436220577475921417653715687725614904582904992461028630081535583308130101987675856234343538955409175623400844887526162643568648833519463720377293240094456246923254350400678027273837755376406726898636241037491410966718557050759098100246789880178271925953381282421954028302759408448955014676668389697996886241636313376393903373455801407636741877711055384225739499110186468219696581651485130494222369947714763069155468217682876200362777257723781365331611196811280792669481887201298643660768551639860534602297871557517947385246369446923087894265948217008051120322365496288169035739121368338393591756418733850510970271613915439590991598154654417336311656936031122249937969999226781732358023111862644575299135758175008199839236284615249881088960232244362173771618086357015468484058622329792853875623486556440536962622018963571028812361567512543338303270029097668650568557157505516727518899194129711337690149916181315171544007728650573189557450920330185304847113818315407324053319038462084036421763703911550639789000742853672196280903477974533320468368795868580237952218629120080742819551317948157624448298518461509704888027274721574688131594750409732115080498190455803416826949787141316063210686391511681774304792596709376\n" ], "name": "stdout" } ], "id": "f73a36bb-68a9-4010-839a-b86bed3cd627" }, { "cell_type": "code", "metadata": {}, "source": [ "s = str(x)" ], "execution_count": 29, "outputs": [], "id": "5209d9d6-6bc5-48a5-be4f-58f2e53a028f" }, { "cell_type": "code", "metadata": {}, "source": [ "s.count()" ], "execution_count": 32, "outputs": [ { "output_type": "error", "ename": "TypeError", "evalue": "count expected at least 1 argument, got 0", "traceback": [ "\u001b[31m---------------------------------------------------------------------------\u001b[39m", "\u001b[31mTypeError\u001b[39m Traceback (most recent call last)", "\u001b[36mCell\u001b[39m\u001b[36m \u001b[39m\u001b[32mIn[32]\u001b[39m\u001b[32m, line 1\u001b[39m\n\u001b[32m----> \u001b[39m\u001b[32m1\u001b[39m s.count()\n", "\u001b[31mTypeError\u001b[39m: count expected at least 1 argument, got 0" ] } ], "id": "a17c7e24-056a-49af-9640-6ae31b75ac91" }, { "cell_type": "code", "metadata": {}, "source": [ "help(s.count)" ], "execution_count": 33, "outputs": [ { "output_type": "stream", "text": [ "Help on built-in function count:\n", "\n", "count(sub[, start[, end]], /) method of builtins.str instance\n", " Return the number of non-overlapping occurrences of substring sub in string S[start:end].\n", "\n", " Optional arguments start and end are interpreted as in slice notation.\n", "\n" ], "name": "stdout" } ], "id": "0ac2c0f5-1530-448c-8727-02f01b92124b" }, { "cell_type": "code", "metadata": {}, "source": [ "s.count(\"2\")" ], "execution_count": 34, "outputs": [ { "output_type": "execute_result", "data": { "text/plain": [ "287" ] }, "metadata": {}, "execution_count": 34 } ], "id": "daa882cb-da41-4347-a8ef-e320ecb2bc26" }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Индекс и срез\n", "\n", "Символы нумеруются с нуля: `s[i]`, последний — `s[-1]`. Срез `s[a:b]` берёт индексы $a, a+1, \\ldots, b-1$ (правая граница не входит). У `str` нет отдельного типа «символ»: и `s[i]`, и срез — снова строка. Присваивать в `s[i]` нельзя: строки неизменяемы." ], "id": "str-index-md" }, { "cell_type": "code", "metadata": {}, "source": [ "s = \"алгоритм\"\n", "print(s[0], s[2], s[-1])\n", "print(s[0:4], s[4:])" ], "execution_count": 35, "outputs": [ { "output_type": "stream", "text": [ "а г м\n", "алго ритм\n" ], "name": "stdout" } ], "id": "str-index" }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Ветвления\n", "\n", "Сравнения `==`, `!=`, `<`, `>`, `<=`, `>=` дают `True` или `False`. Команды, сдвинутые на 4 пробела под `if`, выполняются только при истинном условии. Первая несдвинутая строка после блока идёт уже безусловно.\n", "\n", "Вложенный `if` — проверка внутри другой проверки." ], "id": "branching" }, { "cell_type": "code", "metadata": {}, "source": [ "x = 2 ** 100\n", "if isinstance(x, int) and x > 0:\n", " s = str(x)\n", " if s.count('2') > 0:\n", " print(\"Двоек в числе\", x, s.count('2'))" ], "execution_count": 38, "outputs": [ { "output_type": "stream", "text": [ "Двоек в числе 1267650600228229401496703205376 6\n" ], "name": "stdout" } ], "id": "nested-if" }, { "cell_type": "markdown", "metadata": {}, "source": [ "Каскад `if` / `elif` / `else` выбирает **один** из взаимоисключающих исходов. Год високосный, если кратен 4, но не кратен 100, либо кратен 400." ], "id": "cascade-md" }, { "cell_type": "code", "metadata": {}, "source": [ "year = 2000\n", "if year % 400 == 0:\n", " print(\"YES\")\n", "elif year % 100 == 0:\n", " print(\"NO\")\n", "elif year % 4 == 0:\n", " print(\"YES\")\n", "else:\n", " print(\"NO\")" ], "execution_count": 39, "outputs": [ { "output_type": "stream", "text": [ "YES\n" ], "name": "stdout" } ], "id": "leap-year" }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Циклы `for` и `while`\n", "\n", "`range(n)` даёт $0, 1, \\ldots, n-1$. Цикл `for` — когда число шагов известно. Цикл `while` повторяет тело, пока условие истинно; переменную условия нужно менять в теле, иначе цикл не остановится." ], "id": "loops-md" }, { "cell_type": "code", "metadata": {}, "source": [ "s = 0\n", "for x in range(1, 6):\n", " s += x\n", "print(s)" ], "execution_count": 40, "outputs": [ { "output_type": "stream", "text": [ "15\n" ], "name": "stdout" } ], "id": "for-range" }, { "cell_type": "code", "metadata": {}, "source": [ "x = 1\n", "while x < 100:\n", " print(x)\n", " x *= 2" ], "execution_count": 43, "outputs": [ { "output_type": "stream", "text": [ "1\n", "2\n", "4\n", "8\n", "16\n", "32\n", "64\n" ], "name": "stdout" } ], "id": "while-loop" }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Функции\n", "\n", "Повторяющийся фрагмент алгоритма выносят в **функцию** — капсулу: описали один раз, вызываем сколько нужно.\n", "\n", "Заголовок — строка `def имя(параметры):`. Тело сдвинуто на 4 пробела. Имена в скобках — **формальные параметры**; при вызове им подставляют **фактические** значения. `return` возвращает значение и заканчивает выполнение тела." ], "id": "functions" }, { "cell_type": "code", "metadata": {}, "source": [ "def maximum(a, b):\n", " if a >= b:\n", " return a\n", " return b\n", "\n", "print(maximum(3, 8), maximum(10, 2))" ], "execution_count": 44, "outputs": [ { "output_type": "stream", "text": [ "8 10\n" ], "name": "stdout" } ], "id": "maximum" }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Чистая функция\n", "\n", "Если кроме вычисления значения функция ещё читает клавиатуру, печатает, меняет объекты снаружи — у неё есть **побочные эффекты**.\n", "\n", "**Чистая функция** побочных эффектов не имеет: результат зависит *только* от значений параметров. Её можно вызывать в любом месте, где нужно значение, и подставлять результат в выражения." ], "id": "pure-md" }, { "cell_type": "code", "metadata": {}, "source": [ "def is_leap(year):\n", " \"\"\"Високосный ли год year (натуральное число).\"\"\"\n", " if year % 400 == 0:\n", " return True\n", " if year % 100 == 0:\n", " return False\n", " return year % 4 == 0\n", "\n", "print(is_leap(2000), is_leap(1900), is_leap(2024))" ], "execution_count": 45, "outputs": [ { "output_type": "stream", "text": [ "True False True\n" ], "name": "stdout" } ], "id": "is-leap" }, { "cell_type": "code", "metadata": {}, "source": [ "help(is_leap)" ], "execution_count": 46, "outputs": [ { "output_type": "stream", "text": [ "Help on function is_leap in module __main__:\n", "\n", "is_leap(year)\n", " Високосный ли год year (натуральное число).\n", "\n" ], "name": "stdout" } ], "id": "80a29e6c-7f70-460d-b463-2c5aadaed876" }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Контракт и документ-строка\n", "\n", "Вызов функции — контакт **заказчика** и **поставщика**. Заказчик обещает допустимый вход (здесь — натуральный номер года). Поставщик обещает результат, соответствующий условию (истинность «год високосный»). Нарушение договорённости на входе снимает ответственность за выход.\n", "\n", "Минимум документации контракта — **документ-строка**: первая строка в теле, в тройных кавычках. Она описывает, что делает функция, что принимает и что возвращает. В примере выше это строка сразу под `def`.\n", "\n", "### Ввод и вывод на семинаре\n", "\n", "В контесте программа — не чистая функция, а процедура: читает вход и печатает ответ. Так будут устроены задачи семинара. Это формат проверки, а не обычный стиль прикладного кода, где функция принимает аргументы и возвращает значение, а печать оставляют вызывающему коду.\n", "\n", "```python\n", "year = int(input())\n", "if is_leap(year):\n", " print(\"YES\")\n", "else:\n", " print(\"NO\")\n", "```\n", "\n", "`input()` даёт строку до конца строки, `int(...)` делает из неё целое, `print(...)` пишет ответ." ], "id": "contract" }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Потоки чисел и память $O(1)$\n", "\n", "Последовательность можно обработать, **не запоминая её целиком**: прочитали (или породили) очередное число, обновили несколько переменных, само число забыли. Число дополнительных ячеек не растёт с длиной входа — это и есть память $O(1)$ на этой лекции (без формального определения нотации).\n", "\n", "Складывать члены в список нельзя: для суммы, произведения и максимума он не нужен.\n", "\n", "Свёртка последовательности в одно число — **редукция**. Аккумулятор суммы инициализируют нулём, произведение — **единицей** (иначе всё занулится)." ], "id": "streams" }, { "cell_type": "code", "metadata": {}, "source": [ "s = 0\n", "p = 1\n", "for x in range(1, 6):\n", " s += x\n", " p *= x\n", "print(s, p)" ], "execution_count": null, "outputs": [], "id": "sum-prod" }, { "cell_type": "markdown", "metadata": {}, "source": [ "Максимум: помним текущий лучший, сравниваем с очередным. Ниже поток — остатки `(k * 7) % 10` при $k = 0, 1, \\ldots, 7$; в памяти только `k`, `x` и `m`." ], "id": "max-md" }, { "cell_type": "code", "metadata": {}, "source": [ "m = None\n", "for k in range(8):\n", " x = (k * 7) % 10\n", " if m is None or x > m:\n", " m = x\n", "print(m)" ], "execution_count": null, "outputs": [], "id": "maximum-stream" }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Генерация прогрессий\n", "\n", "Член печатают сразу, последовательность не собирают. Арифметическая: постоянная разность. Геометрическая: постоянный множитель." ], "id": "progressions-md" }, { "cell_type": "code", "metadata": {}, "source": [ "x = 10\n", "while x < 50:\n", " print(x)\n", " x += 5" ], "execution_count": null, "outputs": [], "id": "ap" }, { "cell_type": "code", "metadata": {}, "source": [ "x = 1\n", "while x < 100:\n", " print(x)\n", " x *= 2" ], "execution_count": null, "outputs": [], "id": "gp" }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Фильтрация\n", "\n", "Редукция только по членам, прошедшим условие: учёт очередного числа ставят под `if`. Список отобранных не нужен, если ответ — одно число (здесь — сколько чётных)." ], "id": "filter-md" }, { "cell_type": "code", "metadata": {}, "source": [ "count = 0\n", "for x in range(1, 11):\n", " if x % 2 == 0:\n", " count += 1\n", "print(count)" ], "execution_count": null, "outputs": [], "id": "filter-count" }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Поэлементная обработка\n", "\n", "Для каждого члена сразу печатают преобразование. Пример: квадраты, не превосходящие $n$." ], "id": "map-md" }, { "cell_type": "code", "metadata": {}, "source": [ "n = 20\n", "k = 1\n", "while k * k <= n:\n", " print(k * k)\n", " k += 1" ], "execution_count": null, "outputs": [], "id": "squares" }, { "cell_type": "markdown", "metadata": {}, "source": [ "На семинаре те же приёмы: разряды через `//` и `%`, ветвления, циклы, поток без списка.\n", "\n", "Модель вычислений и нотации роста времени и памяти — на следующей лекции." ], "id": "closing" } ], "metadata": { "kernelspec": { "display_name": "Python 3 (ipykernel)", "language": "python", "name": "python3" }, "language_info": { "codemirror_mode": { "name": "ipython", "version": 3 }, "file_extension": ".py", "mimetype": "text/x-python", "name": "python", "nbconvert_exporter": "python", "pygments_lexer": "ipython3", "version": "3.14.5" } }, "nbformat": 4, "nbformat_minor": 5 }