Информатика

Владимир Ильин

– А мы на информатике перешли на новый level! Начали изучать Питон! — важно сказал восьмиклассник Вовка, только пришедший из школы.

– Рептилий изучают на зоологии! — ответил Андрей, младший брат Вовки, оторвавшись от компьютерной игры.

– Сам ты рептилия! — усмехнулся Вовка. — Питон — это язык программирования, и назван он так не в честь змеи, а в честь телевизионного шоу «Monty Python». Впрочем, пишется так же, как змея.

– Ну и что же такого особенного в твоём Питоне?

– Да пока не знаю, — честно признался Вовка. — Мы же его только начали. Научились устанавливать и узнали, что в нём есть длинная арифметика и нет особой разницы между строками и числами!

– Как это? — спросил Андрей. Услышанное его не очень вдохновило. Сказать по правде, он не любил арифметику, всякий там устный счёт. А тут ещё «длинная»...

– Ну смотри. На твоём калькуляторе всего 10 разрядов. Это значит, что ты можешь работать только с десятизначными числами. А Питон может вычислять хоть сто-, хоть миллион-, да хоть миллиард-секстиллионовзначные! — Как и многие дети, Вовка верил во  всемогущество компьютеров.

– Сейчас покажу, давай его установим.¹ А пока устанавливается, придумаем, что бы нам такого... длинного посчитать.

1 На сайте python.org в разделе Download (ссылка слева) скачайте инсталлятор (для Windows — вверху страницы Python Windows x86 MSI Installer) и установите.

– А, вот! Недавно читал в «Занимательной арифметике». Шах одной восточной страны пообещал изобретателю шахмат любую награду. Тот попросил... насыпать зёрен риса на каждую клетку доски. На первую клетку одно зерно, на другую — два, на третью — четыре... и так далее, каждый раз в 2 раза больше. Шах обрадовался, что просьба, как ему показалось, так ничтожна, и немедленно приказал всё выдать. Жадность подвела шаха! В книжке доказывается, что всего получается 2⁶⁴ – 1 зёрен, а это очень много. Давай посчитаем, сколько времени понадобилось бы визирям, чтобы отмерить рис точно, даже если бы у них было столько зёрен.

– Запускаем², — продолжил Вовка, у которого уже всё установилось, — можно считать!

² Пуск — Все программы — Python 3.3 — Python (command line).

Андрея несколько удивило то, что он увидел. Вместо привычных значков и кнопок в чёрном окне было что-то написано по-английски и просто мигал курсор.

– Ну вот. Сюда можем вводить команды, — пояснил Вовка.– Скажем,

>>> 2+2

нажимаем Enter и... вуаля:

4

Вовка посмотрел на Андрея с торжествующим видом, как будто сделал что-то очень важное и необычное.

– А как умножение, степень писать? — спросил Андрей.

– Очень просто — смотри! Плюс как +, минус как –, умножение — звёздочкой *(Shift 8), степень двумя звёздочками (**), деление — прямым слешем (/). Можно делить нацело (//). Например, 29/10 — это две целых девять десятых, а 29//10 — ровно 2. И ещё брать остаток от деления (%). У нас получается...

>>> 2**64 — 1

– ввёл Вовка и нажал Enter, — 18446744073709551615 зёрен!

– Немало! — сказал Андрей. — Предположим, что они считали вдесятером и каждый отсчитывал 100 зёрен в секунду... В минуте 60  секунд, в часе 60 минут... в тысячелетии 1000 лет... Готово. Давай не будем считать доли тысячелетий, разделим нацело. И Андрей набрал:

>>> 2**64-1//100*60*60*24*365*1000

18446744073709551616

– Ерунда какая-то!

– Конечно, — сказал Вовка, — как и в математике, в Питоне можно и нужно ставить скобки.

>>> (2**64-1)//(100*60*60*24*365*1000)

Компьютер ответил:

5849424

– Пять миллионов восемьсот сорок девять тысяч четыреста двадцать четыре тысячелетия и ещё немного. Изобретатель шахмат, наверное, изобрёл ещё и эликсир бессмертия, если собирался столько ждать! — засмеялся Андрей.

– Слушай! На маткружке мы придумали преотличное число: 5⁵⁰ — это произведение пятидесяти пятёрок, а Мёбиус — так называли учителя информатики — дал нам задачу:

Доказать, что существует число без нулей, которое делится на преотличное.

Самый простой способ доказать, что что-то существует, — это просто найти его! Вперёд, Питон!

>>> 5**50

88817841970012523233890533447265625

Сначала Андрей очень обрадовался, потому что ему первому из всего класса удалось «вживую» увидеть преотличное число. Но радость была недолгой. В самом преотличном оказалось целых три нуля...

– Ничего, продолжим! — сказал Андрей и начал умножать преотличное на два, семь... Ничего не помогло, даже возведение в квадрат. Везде оказывались нули...

– Мы можем попробовать «выгнать» нули из преотличного, — предложил Вовка. Возьмём, допустим, 1023. Умножим на 101 — ноль исчезнет или хотя бы переедет левее: 1023•101 = 102300 + 1023 = 103323.

Теперь его можно умножить на 10001 (или 1023 сразу на 10101, это одно и то же).

– А, понял! — сказал Андрей и быстро умножил 550 на 1000000000001:

88817841970101341075860545970499515533447265625

Последний ноль «переместился» на 19-е место справа.

– Попробуем умножить на 1000001000000000001...

Число стало значительно длиннее, но ноль переехал левее — на 26-ю позицию. Потом на 32-ю, 49-ю. Умножение преотличного на 10000000000000000100000100 00001000001000000000001 «сдвинуло» последний ноль на 63-е место справа. Но левее него всё равно оставалось несколько нулей! Андрей устал.

– А что, если нули никогда не «выгонятся»? — спросил он.

Вопрос Вовку поставил в тупик. Действительно, даже на примере 1023 при таких умножениях ноль останется всегда! Ребята приуныли. Но тут вмешался папа.

– Какие признаки делимости вы знаете? — спросил папа.

– На 2, 3, 4, 5, 9, 10... При чём здесь это?

– На 4 — это хорошо! А на 8?

– Ну, последние три цифры должны делиться на 8. Это элементарно, потому что если их «откинуть», будет число, заканчивающееся тремя нулями, а тысяча делится на 8.

– Замечательно, а на преотличное?

– Такого мы не проходили, — обиженно ответил Андрей, подозревая, что папа просто издевается.

– ...Может, если последние 50 цифр числа делятся на преотличное, то и само число делится! Ну и что?.. — задумался Вовка.

– А вот что! — радостно продолжил он. — Ноль у нас сейчас на 63-й позиции. Возьмём последние 50 цифр числа — это и будет ответ!

– Сам отсчитывай, — огрызнулся всё ещё расстроенный Андрей.

– А вот и не буду! Питон — сила! Просто найдём остаток от деления нашего монстра на один с  пятьюдесятью нулями. Строки в Питоне записываются в кавычках. Их тоже можно складывать и даже умножать, при этом они «склеиваются». Смотри, — Вовка набрал:

>>> «Вовка–молодец!» *100

На экране высветилось ещё сто надписей «Вовка–молодец!».

– «Соберём» наше число:

>>> int("1"+"0"*50)

Тут int для того, чтобы со строкой как с числом производить арифметические действия. Можно, конечно, и просто 10**50 написать, но со строками интереснее! Обратно — функция str. Она переводит число в  строку. Это чтобы можно было действовать с числом как со строкой. Например:

>>> len(str(5**50))

35

– Функция len ищет длину строки. Значит, в твоём преотличном — 35 знаков! Посчитай! — съехидничал Вовка.

Таким образом...

>>> 5**50*1000000000000000010000010000001000001000000000001 % int("1"+ "0"*50)

– Ну вот и ответ:

75394925527871325954265557811595499515533447265625

– Проверим, — сказал Андрей, который к этому времени немного успокоился.

>>> 75394925527871325954265557811595499515533447265625 % (5**50)

0

– Точно! Остаток равен нулю, значит делится! И нулей нет!

– А вот здесь, кстати, скобки необязательны, — заметил Вовка. — Потому что в Питоне, как в  математике, — если без скобок, то сначала степень (**), потом умножение и деление (*, /, //), а потом сложение и вычитание.

Андрей вывел число на принтер — то-то Мёбиус удивится!

«Длинные» задачи

1. Профессор Бурик не верит, что число возможных различных состояний кубика Рубика равно 43 252 003 274 489 856 000. 1 января 2014 года в полночь он запустил для проверки свой компьютер, который проверяет миллиард состояний в секунду. Во сколько Бурику надо быть дома, чтобы увидеть результат?

2. Докажите признак делимости на преотличное.

3. Сколько среди первой тысячи степеней двойки, считая с первой, начинаются с единицы?

Подсказка: поможет определение длины строки, функции len и str.

Художник Артём Костюкевич

elementy.ru