Программирование для начинающих - CodeChick

Нужно перемножить числа в списке: факториал по частям, произведение простых, масштаб коэффициентов. Ручной цикл с acc = 1 легко забыть инициализировать — особенно когда список может быть пустым. С Python 3.8 есть prod в модуле math. Он берёт iterable и перемножает элементы. Пустой iterable даёт 1 — это математически верный «пустой продукт», как sum([]) даёт 0. from math import prod print(prod([2, 3, 5, 7])) # 210 print(prod(range(1, 6))) # 120, то есть 5! print(prod([])) # 1 print(prod([2, 3], start=10)) # 60 Аргумент start — начальное значение (по умолчанию 1). Удобно, когда произведение уже начато с константы. В нашем запуске на Python 3.13 prod([0.5] * 20) вернул около 9,5e-7: мно…

Сегодня Шведская королевская академия наук присудила премию Банка Швеции по экономическим наукам Роберту Холлу (Стэнфорд) и Майклу Вудфорду (Колумбийский университет) — «за микроэкономические основания макроэкономической стабилизации». Зачем сглаживать циклы. Экономика ходит волнами: спады с безработицей и подъёмы с перегревом. Со времён Кейнса идея простая: в спад снижать ставки и наращивать дефицит, на подъёме — наоборот. Цель — срезать пики и ямы, особенно для тех, у кого нет запаса. Почему старые модели сломались. В 1970-е нефтяные кризисы дали стагфляцию: и инфляция вверх, и безработица вверх. Статистические связи «инфляция ↔ безработица» и «доход → потребление» перестали держаться. К…

В олимпиадных задачах ответ часто просят «по модулю 10^9 + 7». Писать 3 ** n % M — плохая идея: Python сначала честно построит всё 3 в степени n и лишь потом возьмёт остаток. У встроенной pow есть третий аргумент — модуль. Тогда остаток берётся после каждого умножения, и промежуточные числа не растут. M = 10**9 + 7 print(pow(3, 10**18, M)) # 246336683 print(pow(3, -1, M)) # 333333336, ведь 3 * 333333336 % M == 1 Внутри — бинарное возведение в степень: основание каждый шаг возводится в квадрат и домножается в ответ, когда очередной бит показателя равен 1. Шагов около log2(b): для 10^18 это примерно 60, а не 10^18. В нашем запуске на Python 3.13 pow(3, 10**6, M) занял порядка микросекунд…

Нужно разбить список на пачки по N элементов: батчи API, строки таблицы, чанки для обработки. Ручной цикл с шагом N и срезами легко ошибается на «хвосте». С Python 3.12 есть готовый способ — batched из itertools. Он берёт iterable и размер n, отдаёт кортежи длины n. Последний кусок может быть короче, если элементов не хватило — без IndexError. from itertools import batched print(list(batched(range(1, 11), 3))) # [(1, 2, 3), (4, 5, 6), (7, 8, 9), (10,)] print(list(batched("abcdefg", 2))) # [('a', 'b'), ('c', 'd'), ('e', 'f'), ('g',)] Важно: n должен быть не меньше 1, иначе ValueError. Это итератор — если пачки нужны дважды, оберни в list. Когда брать: непересекающиеся окна фиксированной…

Код почти как днём: expand around centers, лучший полуинтервал обновляем по длине. Ошибка в цикле по центрам: вызывается только разворот из одной буквы (нечётный центр). Чётный разворот из щели между соседями не запускают. Три теста: «babad», «cbbd», «abba». Печатают длины найденных кусков. Код с отступами — на картинке. Что выведет print? A) 3 2 4 B) 3 1 1 C) 1 1 1 D) 3 2 1 Подсказка: без чётных центров все палиндромы длины 2, 4, 6... пропадают. «bb» и «abba» как раз чётные — остаются одиночные буквы, а «bab» (длина 3) находится как обычно. Ответ с разбором — в комментарии позже вечером. #задачка

Вчера искали палиндром-подпоследовательность: буквы можно было пропускать. Сегодня жёстче — нужна непрерывная подстрока. В «babad» ответ «bab» (или «aba»): три буквы подряд, читаются одинаково в обе стороны. Вчерашний «BBBAB» тут дал бы только «BBB» или одиночную «A» — середину уже не выкинешь. Подстрока = сплошной кусок; подпоследовательность = можно прыгать по индексам. Это разные задачи, путать их на собеседовании дорого. Идея: expand around centers. У палиндрома есть центр. Для нечётной длины это буква (как «a» в «bab»), для чётной — щель между двумя одинаковыми (как между «b» и «b» в «bb»). Всего 2n−1 таких центров: n нечётных и n−1 чётных. Из каждого тянем указатели влево и вправо, по…

n писем и n конвертов. Сколько писем попадут «своему» адресату, если разложить наугад? Интуиция шепчет: чем больше n, тем больше совпадений. На деле среднее число неподвижных точек равно 1 — и для 5, и для 20, и для миллиона. Неподвижная точка перестановки π — позиция i, где π(i) = i. Пусть I_i = 1, если письмо i на своём месте, иначе 0. Тогда P(I_i = 1) = 1/n. Число совпадений X = I_1 + ... + I_n. Индикаторы зависимы: если 19 из 20 писем уже на местах, двадцатое тоже. Кажется, складывать нельзя. Но линейность матожидания не требует независимости: E[X] = E[I_1] + ... + E[I_n] = n · (1/n) = 1. Мы проверили на Python 3.13 (seed 20261012, 50 000 случайных перестановок): — при n = 20 средне…

Вечерняя задачка — продолжение урока про наибольшую палиндромную подпоследовательность. Код почти как днём: таблица dp по длине отрезка, при совпадении краёв берём внутренний ответ. Ошибка в одной цифре: к внутреннему прибавляют 1, а не 2. Три теста: «BBBAB», «CHARACTER», «ABA». Код с отступами — на картинке. Что выведет print? A) 4 5 3 B) 2 3 2 C) 1 1 1 D) 4 3 2 Подсказка: когда s[i] совпал с s[j], в ответ входят обе буквы. Если плюсовать только единицу, длина растёт вдвое медленнее на каждой паре краёв — и короткие совпадения вроде «AA» уже дают 1 вместо 2. Ответ с разбором — в комментарии позже вечером. #задачка

Вчера собирали возрастающую цепочку (НВП). Сегодня сосед по семейству подпоследовательностей: наибольшая палиндромная подпоследовательность (НПП, по-английски LPS). Дана строка — нужно найти самую длинную цепочку букв, которая читается одинаково слева направо и справа налево, а порядок индексов сохраняется. Буквы не обязаны стоять рядом: в «BBBAB» ответ BBBB длины 4 (пропускаем A). Это снова не подстрока: подстрока непрерывна, подпоследовательность — нет. Базовый способ — двумерная динамика O(n2). Пусть dp[i][j] — длина НПП на отрезке от i до j включительно. Тогда: — одна буква: dp[i][i] = 1; пустой отрезок даёт 0; — если s[i] совпадает с s[j]: берём внутренний ответ dp[i+1][j−1] и плюс две…

Ждёшь автобус — интервалы сильно скошены вправо: чаще короткие, иногда очень длинные. Кажется, из такого распределения «нормальный колокол» не получится. Центральная предельная теорема говорит иначе: среднее многих независимых одинаковых величин с конечной дисперсией всё равно становится примерно нормальным. Возьми экспоненциальное с средним 1 (дисперсия тоже 1). Медиана ≈ 0,693: больше половины значений меньше среднего. Скошенность равна 2 — хвост вправо заметный. Мы проверили на Python 3.13 (seed 20261011, по 20 000 прогонов): — одиночные числа: среднее ≈ 1,00, но ниже 1 лежит ≈ 63%; — средние из 30 независимых: среднее ≈ 1,00, стандартное отклонение ≈ 0,182 (теория: 1/√30 ≈ 0,183); — в…