{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "l10_1",
   "metadata": {},
   "source": [
    "# Списки. Занятие 2.\n",
    "\n",
    "Осваиваем:\n",
    "- встроенные функции `sum`, `max`, `min`, `sorted`;\n",
    "- генераторы списков и условные генераторы;\n",
    "- функции `enumerate` и `zip`;\n",
    "- работу со строками как с последовательностями;\n",
    "- типичные математические применения: массив значений функции, фильтрация, скалярное произведение, геометрия.\n",
    "\n",
    "В конце — раздел ⭐ с задачами на классические алгоритмы."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "id": "f565d576-e998-468b-972f-de12c0b64a7e",
   "metadata": {},
   "outputs": [],
   "source": [
    "from random import randint, uniform, random"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "1a5aa086-a823-4c3f-bb93-72b25a7652a2",
   "metadata": {},
   "source": [
    "## Часть 1. Генераторы списков и встроенные функции"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "l10_12",
   "metadata": {},
   "source": [
    "**Задача 1.** Дан список. Покажите разницу между `sorted(a)` и `a.sort()`:\n",
    "- `sorted(a)` возвращает **новый** отсортированный список, исходный не меняется;\n",
    "- `a.sort()` сортирует **на месте** и возвращает `None`.\n",
    "\n",
    "Проверьте оба варианта и `reverse=True`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "id": "l10_13",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Исходный после sorted(a): [3, 1, 4, 1, 5]\n",
      "Новый: [1, 1, 3, 4, 5]\n",
      "По убыванию: [5, 4, 3, 1, 1]\n",
      "После a.sort(): [1, 1, 3, 4, 5]\n",
      "a.sort() вернул: None\n"
     ]
    }
   ],
   "source": [
    "a = [3, 1, 4, 1, 5]\n",
    "\n",
    "b = sorted(a)\n",
    "print(f'Исходный после sorted(a): {a}')\n",
    "print(f'Новый: {b}')\n",
    "print(f'По убыванию: {sorted(a, reverse=True)}')\n",
    "\n",
    "result = a.sort()\n",
    "print(f'После a.sort(): {a}')\n",
    "print(f'a.sort() вернул: {result}')"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "l10_17",
   "metadata": {},
   "source": [
    "**Задача 2.** С помощью генератора списка постройте список квадратов чисел от 1 до 20."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "id": "l10_18",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Список квадратов от 1 до 20: [1, 4, 9, 16, 25, 36, 49, 64, 81, 100, 121, 144, 169, 196, 225, 256, 289, 324, 361, 400]\n"
     ]
    }
   ],
   "source": [
    "squares = [x ** 2 for x in range(1, 21)]\n",
    "print(f'Список квадратов от 1 до 20: {squares}')"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "l10_19",
   "metadata": {},
   "source": [
    "**Задача 3.** С помощью генератора постройте список всех чисел от 1 до 30, которые одновременно чётные и делятся на 3."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "l10_20",
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "id": "l10_21",
   "metadata": {},
   "source": [
    "**Задача 4.** Дан список целых чисел. С помощью **условного** генератора постройте:\n",
    "- новый список, содержащий только положительные элементы;\n",
    "- список модулей отрицательных элементов."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "l10_22",
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "id": "l10_23",
   "metadata": {},
   "source": [
    "**Задача 5.** С помощью **вложенного** генератора постройте список всех пар `(i, j)`, где `i` и `j` пробегают от 0 до 2. Затем постройте список пар с условием `i < j`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "l10_24",
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "id": "l10_25",
   "metadata": {},
   "source": [
    "**Задача 6.** Постройте список значений аргумента на отрезке [-2, 2] с шагом 0.5, используя генератор списка. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "l10_26",
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "id": "a52",
   "metadata": {},
   "source": [
    "**Задача 7.** Дан целочисленный список $a$ размера $N$. Сформировать новый список $b$ того же размера, элементы которого определяются следующим образом:\n",
    "\n",
    "$$\n",
    "b_k = \n",
    "\\begin{cases}\n",
    "    2 \\cdot a_k, & \\text{если } a_k < 5 \\\\\n",
    "    0.5 \\cdot a_k, & \\text{в противном случае}\n",
    "\\end{cases}\n",
    "$$\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "a52c",
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "id": "a54",
   "metadata": {},
   "source": [
    "**Задача 8.** Дан целочисленный список $a$ размера $N$. Переписать в новый целочисленный список $b$ все чётные числа из исходного списка (в том же порядке) и вывести размер полученного списка $b$ и его содержимое."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "id": "a54c",
   "metadata": {},
   "outputs": [
    {
     "name": "stdin",
     "output_type": "stream",
     "text": [
      "Введите размер списка: 10\n"
     ]
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Список: [-1, -10, -10, 8, 3, 4, 5, -2, -5, -3]\n",
      "\n",
      "Список b (чётные числа, способ 1): [-10, -10, 8, 4, -2]\n",
      "Список b (чётные числа, способ 2): [-10, -10, 8, 4, -2]\n",
      "Размер списка b: 5\n"
     ]
    }
   ],
   "source": [
    "n = int(input('Введите размер списка:'))\n",
    "a = [randint(-10, 10) for _ in range(n)]\n",
    "print(f'Список: {a}\\n')\n",
    "\n",
    "b = [x for x in a if x % 2 == 0]\n",
    "print(f'Список b (чётные числа, способ 1): {b}')\n",
    "\n",
    "b = list(filter(lambda x: x % 2 == 0, a))\n",
    "print(f'Список b (чётные числа, способ 2): {b}')\n",
    "\n",
    "print(f'Размер списка b: {len(b)}')"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "l10_27",
   "metadata": {},
   "source": [
    "## Часть 2. zip и скалярное произведение"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "l10_28",
   "metadata": {},
   "source": [
    "**Задача 9.** Даны два целочисленных списка одинаковой длины. С помощью `zip` выведите их элементы парами построчно в формате `a[i] -> b[i]`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "l10_29",
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "id": "l10_30",
   "metadata": {},
   "source": [
    "**Задача 10.** Даны два вектора (целочисленные списки одинаковой длины). Вычислите их **скалярное произведение** через `zip` и `sum`:\n",
    "\n",
    "$$\\vec a \\cdot \\vec b = \\sum_i a_i \\cdot b_i$$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "l10_31",
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "id": "l10_32",
   "metadata": {},
   "source": [
    "**Задача 11.** Дан целочисленный список. Через `zip` со срезом `a[1:]` получите список всех пар соседних элементов, а затем — список их разностей `a[i+1] - a[i]` (всё через генераторы)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "l10_33",
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "id": "l10_34",
   "metadata": {},
   "source": [
    "## Часть 3. Математические приложения"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "l10_35",
   "metadata": {},
   "source": [
    "**Задача 12. Массив значений функции на сетке.** Постройте таблицу значений $f(x) = x^2 - 3x + 1$ на отрезке [-2, 2] с шагом 0.5, используя два генератора (для `x` и для `f(x)`), и выведите пары через `zip`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "l10_36",
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "id": "l10_37",
   "metadata": {},
   "source": [
    "**Задача 13. Фильтрация выбросов.** Дан список 20 случайных целых чисел от −100 до 100. С помощью условного генератора оставьте только значения в диапазоне [−50, 50], выведите их. Затем выведите, сколько значений отфильтровано."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "l10_38",
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "id": "a134",
   "metadata": {},
   "source": [
    "**Задача 14.** Дан список $A$ из $N$ точек (точки заданы своими вещественными координатами $x$, $y$). Найти пару точек этого списка с максимальным расстоянием между ними и само это расстояние (точки выводятся в том же порядке, в котором они перечислены при задании списка $A$)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "a134c",
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "id": "a138",
   "metadata": {},
   "source": [
    "**Задача 15** Дан список $A$ из $N$ точек ($N > 2$, точки заданы своими вещественными координатами $x$, $y$). Найти наименьший периметр треугольника, вершины которого принадлежат различным точкам списка $A$, и сами эти точки (точки выводятся в том же порядке, в котором они перечислены при задании списка $A$).\n",
    "\n",
    "*Подсказка:* переберите все тройки индексов $i < j < k$ и для каждой посчитайте периметр. Удобно сложить периметр и индексы в кортеж и взять `min` — кортежи сравниваются лексикографически по первому элементу."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "a138c",
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "id": "l10_42",
   "metadata": {},
   "source": [
    "## Часть 4. Работа со строками как со списками"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "s42",
   "metadata": {},
   "source": [
    "**Задача 16.** Дана строка, состоящая из русских слов, набранных заглавными буквами и разделённых пробелами (одним или несколькими). Найти количество слов, которые начинаются и заканчиваются одной и той же буквой."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "s42c",
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "id": "s43",
   "metadata": {},
   "source": [
    "**Задача 17.** Дана строка, состоящая из русских слов, набранных заглавными буквами и разделённых пробелами (одним или несколькими). Найти количество слов, которые содержат хотя бы одну букву «А»."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "s43c",
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "id": "s45",
   "metadata": {},
   "source": [
    "**Задача 18.** Дана строка, состоящая из русских слов, разделённых пробелами (одним или несколькими). Найти длину самого короткого слова."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "s45c",
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "id": "s52",
   "metadata": {},
   "source": [
    "**Задача 19.** Дана строка-предложение на русском языке. Преобразовать строку так, чтобы каждое слово начиналось с заглавной буквы. Словом считать набор символов, не содержащий пробелов и ограниченный пробелами или началом/концом строки. Слова, не начинающиеся с буквы, не изменять."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "s52c",
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "id": "l10_41",
   "metadata": {},
   "source": [
    "## Часть 5. ⭐ Задачи со звёздочкой (не обязательные, но интересные)\n",
    "\n",
    "Эти задачи — на классические алгоритмы со списками. Они выходят за рамки базовых тем лекций, но помогут глубже освоить работу со списками, циклами и указателями."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "l10_43",
   "metadata": {},
   "source": [
    "**⭐ Задача 1*. Скользящее окно.**\n",
    "\n",
    "Дан список целых чисел `a` и целое `k`. Найдите максимальную сумму `k` подряд идущих элементов и выведите её вместе с индексом начала окна. Решение за один проход (O(n)): сначала сумма первого окна, затем на каждом шаге прибавляем новый элемент справа и вычитаем старый слева.\n",
    "\n",
    "*Пример:* `a = [2, 1, 5, 1, 3, 2]`, `k = 3` → сумма 9, начало с индекса 2."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "l10_43c",
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "id": "l10_44",
   "metadata": {},
   "source": [
    "**⭐ Задача 2*. Слияние двух отсортированных списков.**\n",
    "\n",
    "Даны два отсортированных по возрастанию списка целых чисел. Получите один отсортированный, **не используя `sort`/`sorted`**. Метод двух указателей: держим индексы `i` и `j`, на каждом шаге добавляем меньший из `a[i]` и `b[j]`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "l10_45",
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "id": "l10_46",
   "metadata": {},
   "source": [
    "**⭐ Задача 3*. Пара с заданной суммой.**\n",
    "\n",
    "Дан **отсортированный** список целых чисел и число `target`. Найти индексы двух элементов, дающих в сумме `target`, за O(n) двумя указателями (`i` — с начала, `j` — с конца)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "l10_47",
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "8486be5a-431b-44bd-babf-a0827b04f313",
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python [conda env:base] *",
   "language": "python",
   "name": "conda-base-py"
  },
  "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.13.5"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}