Многоразрядные числа и длинная арифметика
11 класс, углублённый уровень. Обзорный практикум к шестнадцатой паре: шесть задач — длинное число в списке, сложение и умножение столбиком на бумаге и в программе, сколько цифр у результата, вычисления с числами в тысячи цифр.
- Что нужно сделать
- Шесть задач — по одной на каждый вопрос темы, и все сразу на странице: решай в любом порядке. Ответил верно — вопрос закрыт. Ошибся — сразу видно, как это решается, а вопрос остаётся открытым: кнопка «Новые числа» даёт ту же задачу с другими данными. Времени нужно минут тридцать: столбики удобно писать на черновике, как на слайдах.
- Программы — картинкой, последняя — своя
- Код в задачах нарисован картинкой: его читают, а не запускают. Шестой вопрос — практическая работа: число в сотни и тысячи цифр вручную не сосчитать, программу для него пишешь сам в IDLE — на длинном int Python или своим списком цифр. Образец — в «Подсказке».
- Отметка
- Закрыто 6 из 6 — «5», 5 — «4», 3 или 4 — «3». Исправленная задача не засчитывается — за ошибку приходит новая, без ограничений: добирать можно до пятёрки. Кнопка «Получить код» появляется, как только закрыто три вопроса.
- Короткий ответ — знак в знак
- Ответ везде — целое число:
25, а не25 цифр, без пробелов между разрядами и без нулей впереди. На КЕГЭ ответ читает машина, и здесь так же. - Как сдать
- В конце появится код работы и кнопка «Сдать работу»: впишешь код ученика, кнопка сама откроет форму с уже вписанным кодом. Переписывать код руками не надо — на этом чаще всего и ошибаются.
- Не успел на уроке
- Открой эту же страницу дома и пройди целиком: вариант будет другой, а сдаётся всё так же — одним кодом.
Вопросы темы
Подсказка: многоразрядные числа и длинная арифметика
Зачем длинная арифметика
Целый тип в C++, Java, Паскале — 64 бита: наибольшее число 263 − 1 = 9 223 372 036 854 775 807, 19 цифр. Уже 21! и 264 туда не помещаются. Числа в сотни цифр нужны в криптографии (ключ RSA на 2048 бит — 617 цифр) и в точных вычислениях. Длинная арифметика — хранить число по частям и считать столбиком, как на бумаге. В Python тип int длинный сам: внутри он тоже хранит число частями.
Как хранить
Список цифр младшими вперёд: 8497 → 
,
a[i] — цифра при 10i. Перенос в новый старший разряд —
просто 
.
Блоками по три цифры (основание 1000): 3 120 045 007 →
. Блок внутри числа при выводе дополняют
нулями: 45 → 045. Элементов в три раза меньше, чем цифр, — и действий
тоже.
Столбиком
- Сложение: x = a[i] + b[i] + p, в разряд пишем x % 10, перенос p = x // 10 — только 0 или 1. Последний перенос — новая цифра.
- Вычитание: если цифра меньше вычитаемой — занимаем единицу у старшего разряда и прибавляем 10.
- Умножение на однозначное d: x = a[i]·d + p, перенос бывает до 8.
- Сколько стоит: сложение n-значных — порядка n действий, умножение m-значного на n-значное столбиком — порядка m·n.
Сколько цифр
У натурального x цифр ⌊lg x⌋ + 1, у mn — ⌊n·lg m⌋ + 1 (lg 2 ≈ 0,30103, lg 3 ≈ 0,47712, lg 7 ≈ 0,84510). Сумма двух n-значных — n или n + 1 цифр. Произведение m-значного и n-значного — m + n − 1 или m + n цифр.
Программа: сложение столбиком
Практическая работа: числа в тысячи цифр
len(s) — сколько цифр, s[:5] — первые пять, s.count('0') — сколько нулей. Сначала проверь программу на маленьком числе, где ответ знаешь: 2 ** 10 = 1024 — четыре цифры, сумма 7.