Ребят, пжл, что сможете помогите решить)

+ 0 -

иван20000000

04 дек. 2014 г., 5:02:09 (9 лет назад)

Давайте рассмотрим последовательность чисел, первое из которых равно 1, а каждое последующее вдвое больше: 1, 2, 4, 8, 16, ... Используя показатели степени, ее можно записать в эквивалентном виде: 20, 21, 22, 23, 24, ... Называется она вполне ожидаемо: последовательность степеней двойки. Казалось бы, ничего выдающегося в ней нет — последовательность как последовательность, не лучше и не хуже других. Тем не менее, она обладает весьма примечательными свойствами. Несомненно, многие читатели встречали ее в классической истории об изобретателе шахмат, который попросил у правителя в награду за первую клетку шахматной доски одно пшеничное зерно, за вторую — два, за третью — четыре, и так далее, всё время удваивая число зерен. Понятно, что суммарное их количество равно S = 20 + 21 + 22 + 23 + 24 + ... + 263. (1) Но так как эта сумма неимоверно велика и во много раз превосходит годовой урожай зерновых по всему миру, вышло, что мудрец ободрал правителя как липку.1 Однако зададимся сейчас другим вопросом: как с наименьшими затратами труда подсчитать величину S? Обладатели калькулятора (или, паче того, компьютера) вполне могут за обозримое время выполнить перемножения, а затем сложить полученные 64 числа, получив ответ: 18 446 744 073 709 551 615. А поскольку объем вычислений немалый, то и вероятность ошибки весьма велика. Кто похитрей, могут углядеть в этой последовательности геометрическую прогрессию. Не знакомые же с этим понятием (или те, кто попросту забыл стандартную формулу суммы геометрической прогрессии) могут использовать следующие рассуждения. Давайте-ка умножим обе части равенства (1) на 2. Так как при удвоении степени двойки ее показатель увеличивается на 1, то получим 2S = 21 + 22 + 23 + 24 + ... + 264. (2) Теперь из (2) вычтем (1). В левой части, понятное дело, получится 2S – S = S. В правой же части произойдет массовое взаимное уничтожение почти всех степеней двойки — от 21 до 263 включительно, и останется лишь 264 – 20 = 264 – 1. Итак: S = 264 – 1. Что ж, выражение заметно упростилось, и теперь, имея калькулятор, позволяющий возводить в степень, можно найти значение этой величины без малейших проблем. А если и калькулятора нет — как быть? Перемножать в столбик 64 двойки? Еще чего не хватало! Опытный инженер или математик-прикладник, для которого главный фактор — время, сумел бы быстро оценить ответ, т.е. найти его приближенно с приемлемой точностью. Как правило, в быту (да и в большинстве естественных наук) вполне допустима погрешность в 2–3%, а если она не превосходит 1% — то это просто великолепно! Оказывается, подсчитать наши зерна с такой погрешностью можно вообще без калькулятора, и всего за несколько минут. Как? Сейчас увидите. Итак, надо возможно точней найти произведение 64 двоек (единицу в силу ее ничтожности отбросим сразу). Разобьем их на отдельную группу из 4 двоек и еще на 6 групп по 10 двоек. Произведение двоек в отдельной группе равно 24 = 16. А произведение 10 двоек в каждой из остальных групп равно 210 = 1024 (убедитесь, кто сомневается!). Но 1024 — это около 1000, т.е. 103. Поэтому S должно быть близко к произведению числа 16 на 6 чисел, каждое из которых равно 103, т.е. S ≈ 16·1018 (ибо 18 = 3·6). Правда, погрешность здесь все же великовата: ведь 6 раз при замене 1024 на 1000 мы ошибались в 1,024 раза, а всего мы ошиблись, как легко видеть, в 1,0246 раз. Так что теперь — дополнительно перемножать 1,024 шесть раз само на себя? Нет уж, обойдемся! Известно, что для числа х, которое во много раз меньше 1, с высокой точностью справедлива следующая приближенная формула: (1 + x)n ≈ 1 + xn. Поэтому 1,0246 = (1 + 0,24)6 ≈ 1 + 0,24·6 = 1,144. Посему надо найденное нами число 16·1018 умножить на число 1,144, в результате чего получится 18 304 000 000 000 000 000, а это отличается от правильного ответа менее чем на 1%. Чего мы и добивались! В данном случае нам крупно повезло: одна из степеней двойки (а именно — десятая) оказалась весьма близка к одной из степеней десятки (а именно — третьей). Это позволяет нам быстро оценивать значение любой степени двойки, не обязательно 64-й. Среди степеней других чисел подобное встречается нечасто. Например, 510 отличается от 107 также в 1,024 раза, но... в меньшую сторону.2 Впрочем, это того же поля ягода: поскольку 210·510 = 1010, то во сколько раз 210 превосходит 103, во столько же раз 510 меньше, чем 107. Другая интересная особенность рассматриваемой последовательности