Сколькими способами можно разменять монету

Олимпиадное хобби. Размен монет

Привет. Сегодня понедельник, поэтому я решил, что стоит начать свой рабочий день с разогрева пальцев и мозга. Для тех кто не в курсе: мое олимпиадное хобби состоит в решении олимпиадных задач по программированию, которые я беру с сайта http://uva.onlinejudge.org/. Сегодня нам предстоит решить задачу о размене монет из области динамического программирования. Задача не очень сложная, но есть над чем поразмыслить, поэтому заинтересовавшихся прошу под кат. К слову, это третья наша задача, но, безусловно, из всех самая интересная.

Небольшое лирическое отступление.

Мой программистский путь начался далеко не в 3 года, когда многие будущие программисты уже разбирали калькулятор и делали из него компьютер. Я начал заниматься программированием в школе в 8 классе. К слову сказать, моя школа была далека от технического направления, поэтому в своих начинаниях я был почти одинок. Но, благодаря директору нашей школы, у нас был «кружок» по программированию, где мы готовились к школьной олимпиаде по программированию. Нас там было не более трех человек единовременно, но нашего преподавателя, к счастью, это не расстраивало. Моим преподавателем программирования был Кавокин А.А., отчасти благодаря ему я и встал на столь удивительный путь программиста. Так вот, каждый урок наш наставник начинал с логической задачки, чтобы мы расшевелили свои извилины. Это мне настолько нравилось в школе, что я решил вас тоже так помучить, поэтому сегодня мы начнем с небольшой логической задачки, которая поможет нам размяться.

Логическая задачка для разминки:

В нашем городе проезд в общественном транспорте оплачивается непосредственно во время поездки, для чего по автобусу курсирует кондуктор, собирая со всех плату за проезд. Стоимость билета составляет 20 рублей. Однажды, на одной из остановок в автобус зашли 5 человек. Один из них молча заплатил кондуктору 100 рублей, и тот, не задавая никаких вопросов, отсчитал 5 билетов и отдал платившему. Вопрос: как кондуктор догадался, что оплата происходит сразу за всех пятерых, при условии, что ничто не указывало на то, что все они были вместе?

Позволю оставить задачу без ответа, потому что уверен в вашей сообразительности. А как только в комментариях появится правильный ответ, сразу вынесу ссылку сюда.
UPD: Ответ найден в комментарии пользователя ogra

Условие

Надеюсь задачка, которую я вам подкинул для разогрева, успешно подействует на вашу мозговую активность. Сейчас мы, наконец-то займемся решением олимпиадной задачи. Наша сегодняшняя задача — это задача о размене монет.

Краткий перевод условия задачи

После закупки в большом универмаге Мелу досталась сдача в размере 17 центов. Он получил одну десятицентовую монету, одну пятицентовую и 2 монеты по 1 центу. Позже, в этот же день, он делал покупки в мини-маркете, где тоже получил сдачу в размере 17 центов. На этот раз он получил две монеты по 5 центов и 7 монет по 1 центу. Тогда Мел задался вопросом: «Как много магазинов я могу посетить и получить сдачу в 17 центов различным набором монет?» После небольшого мозгового штурма, он определил, что ответ 6. Тогда он бросил вызов вам для решения более общего случая.

Напишите программу, которая определит количество различных комбинаций американских монет(1 цент, 5 центов, 10 центов, 25 и 50 центов), которые могут сложиться в определенную сумму.

Входные данные: ввод будет состоять из множества чисел между 0 и 30000 включительно, по одному в каждой строке.

Выходные данные: на каждое входное число, нужно определить число комбинаций и вывести, как показано в примере.

Output:
There are 6 ways to produce 17 cents change.
There are 4 ways to produce 11 cents change.
There is only 1 way to produce 4 cents change.

Как обычно, рекомендую вам самим попытаться решить задачу. А как только решите, возвращайтесь к нам и хвастайтесь своим результатом.

Решение

Задача явно из области динамического программирования, а такие задачи, как правило, решаются с помощью рекурсивных зависимостей. Нам необходимо определить, какая именно рекурсивная зависимость в нашем случае.

Можно сразу заметить, что число комбинаций не отличается при сдаче от 1 цента до 4 — это 1 вариант, при сдаче от 5 центов до 9 — это 2 варианта, при сдаче от 10 центов до 14 — это 4 варианта и т.д. Это происходит потому, что внутри такой «пятерки» монеты достоинством в 1 цент невозможно ничем заменить. Таким образом мы определили, что решать задачу для каждого числа бессмысленно, поэтому мы будем решать ее для каждой «пятерки».

Также можно заметить, комбинации для каждой следующей «пятерки» точно повторяют комбинации предыдущей «пятерки» (с добавлением в конец комбинации нужного числа монет по 1 центу) и некоторого числа новых комбинаций. Становится понятным, что число комбинаций следующей «пятерки» имеет зависимость от числа комбинаций предыдущих «пятерок». Нарисуем таблицу, где столбцами будут «пятерки», а строками виды монет, а на пресечении будет определяться, какое количество новых комбинаций породил данных вид монет ( в комбинации со всеми более мелкими) на конкретном шаге — «пятерке»:

1	5	10	15	20	25	30	35	40	45	50	55
1	1	0	0	0	0	0	0	0	0	0	0	0
5	0	1	1	1	1	1	1	1	1	1	1	1
10	0	0	1	1	2	2	3	3	4	4	5	5
25	0	0	0	0	0	1	1	2	2	3	4	5
50	0	0	0	0	0	0	0	0	0	0	1	1
∑	1	2	4	6	9	13	18	24	31	39	50	62

В последней строке выведено число комбинаций на данной «пятерке»
К примеру: на шаге 35 (8 пятерка: 35-39)
имея только 1 центовую монету, новых комбинаций не появляется,
из монет 1 цент и 5 центов, можно выдумать 1 новую комбинацию: 5+5+5+5+5+5+5+1(от 0 до 4)
1 цент, 5 центов, 10 центов — 3 комбинации: 10+10+10+5+1(от 0 до 4), 10+10+5+5+5+1, 10+5*5+1
1, 5, 10, 25 — 2 новых комбинации: 25+10+1, 25+5+5+1

Число новых комбинаций на каждом шаге из монет 1 цент и 5 центов равняется 1, потому что это комбинация порождается добавлением 5 центовой монеты к предыдущей комбинации. Т.е. для второй пятерки 5+1, потом 5+5+1, потом 5+5+5+1 и т.д., по 1 новой комбинации на каждом шаге.
Также в этой таблице не трудно углядеть рекурсивную зависимость: число новых комбинаций на шаге i, составленных из монет 1-10 равняется числу новых комбинаций из монет 1-5 на шаге i-1 плюс число новых комбинаций из монет 1-10 на шаге i-2 (когда у нас в распоряжении было на 1 десятицентовую монету меньше). Аналогично для 25-ти центовой монеты и 50-ти центовой монеты.

В итоге мы имеем 2 формулы и 3 рекурсивных зависимости:
N(1, i) = 0, кроме N(1, 0) = 1
N(5, i) = 1
N(10, i) = N(5, i-1) + N(10, i-2)
N(25, i) = N(10, i-3) + N(25, i-5)
N(50, i) = N(25, i-5) + N(50, i-10)
S(i) = S(i-1) + N(1, i) + N(5, i) + N(10, i) + N(25, i) + N(50, i)
Где N — это матрица, определенная выше, а S — искомое число комбинаций.

Теперь нам остается лишь просчитать нужное число шагов от начала до запрашиваемой «пятерки», подсчитывая на каждом шаге общее число комбинаций (S). Учитывая тот факт, что тестов в задаче будет много, можно использовать для новых тестов, ранее просчитанный кусок матрицы и дополнять лишь ее недостающую часть. Еще очень важно понимать, что при максимальной сумме, заданной условием задачи: 30000 центов, суммарное число комбинаций перевалит за пределы int и даже long, поэтому для подсчета числа комбинаций рекомендую использовать 8 байтовые беззнаковые переменные.

Полагаю, что есть более изящное решение, чем предложенное выше, но я его пока не вижу, поэтому жду от вас интересных алгоритмов. Мое решение на C++ можно скачать тут. Проверить правильность своего решения можно здесь (требуется регистрация). Удачи, господа!

Источник

Сколькими способами можно разменять монету?

Сколькими способами можно раскрасить ребра графа
Доброго времени суток. Скоро меня настигнет дедлайн для получения зачета по алгебре, а я все никак.

Сколькими способами можно составить такую мозаику (с точностью до поворотов и осевых симметрий квадрата)?
Здравствуйте, форумчане 🙂 Столкнулся впервые с такой вот задачкой из темы «Задачи на раскраски».

Сколькими способами можно разменять
Сколькими способами можно разменять 100руб в 5,10,20 и 50 руб? решить рекурсией..помогите.

Сколькими способами можно разменять рубль?
сколькими способами можно разменять рубль на монеты достоинством в 10, 15, 20 и 50 копеек.

Иными словами, сколько есть неотрицательных решений в целых числах у уравнения x + 2y + 4z + 10w = 20

Добавлено через 4 минуты
Отсюда уже кое-что видно. Например, то, что x — четно. x = 2v
2(v+y) + 4z + 10w = 20
u + 2z + 5w = 10 (u=v+y)

Добавлено через 5 минут
Для w есть 3 варианта.
w = 2 — 1 способ
w = 1 приводит к u + 2z = 5. Возможные способы легко перебрать.
w = 0 => u + 2z = 10 — тоже можно перебрать.

Добавлено через 1 минуту
Дальше чуток усидчивости и аккуратности, и решение — вот оно!

Добавлено через 9 минут

Как-то так:
2: 50+50
3: —
4: 50+20+20+10
5: 50+20+20+5+5; 50+20+10+10+10
6: 50+20+10+10+5+5; 50+10+10+10+10+10; 20+20+20+20+10+10
. .

Добавлено через 8 минут
Пропущено:
5: 20+20+20+20+20

Но вот я не вижу схемы составления этих комбинаций. Хотя, видимо, она у вас есть. Такого алгоритма, который бы позволял гарантировать, что повторов не будет и ни одна комбинация не будет пропущена.
Я понимаю, что разбиение всего множества на классы по количеству монет гарантирует отсутствие повторов (если внутри каждого класса повторов нет, что наверное, легко проверить визуально). Но вот как внутри одного класса обеспечить все варианты?

Добавлено через 6 минут
Кстати, можно предложить легкую модификацию задачи. Добавить 3-х копеечные монеты.
Нетрудно заметить, что их число должно быть кратно 5. И можно вместо них рассматривать 15-ти копеечные.

Добавлено через 4 минуты
В общем-то понятно, что при увеличении количества номиналов комбинаторная сложность возрастает (как и у всех комбинаторных задач). И по-хорошему здесь надо программу писать.
Но мне просто любопытны, что здесь поддается «ручному» учету

На улицу не пускают. Заняться надо же чем-то

Источник

комбинаторика — Размен 110000 рублей [закрыт]

Скольким способами можно разменять 110 000 рублей монетами в 1, 2 и 5 рублей?

Как я понимаю, тут нужно использовать формулы сочетаний из комбинаторики, но я не понимаю как :\

задан 11 Янв ’15 13:57

Вопрос был закрыт. Причина — «Повтор вопроса». Закрывший — EdwardTurJ 11 Янв ’15 14:27

1 ответ

Нужно подсчитать число решений уравнения $%x+2y+5z=110000$% в целых неотрицательных числах. Здесь $%x$% — число рублёвых монет, $%y$% — число двухрублёвых, $%z$% — пятирублевых.

Придавая $%z$% различные значения от $%0$% до $%22000$%, будем получать уравнения вида $%x+2y=5(22000-z)$%. Для фиксированного $%N$% уравнение $%x+2y=N$% имеет $%[N/2]+1$% решение, где квадратные скобки означают целую часть. Действительно, $%y$% может принимать любое значение от $%0$% до $%[N/2]$% включительно, и $%x$% далее однозначно выражается из равенства $%x=N-2y$%.

Число $%N=5(22000-z)$% в правой части уравнения принимает значения $%0$%, $%5$%, $%10$%, $%15$%, . , $%110000$%. Значения $%[N/2]+1$% при этом получаются равными $%1$%, $%3$%, $%6$%, $%8$%, . , $%55001$%. Все эти числа надо сложить между собой. Закономерность тут достаточно простая: после первой 1 происходит увеличение то на 2, то на 3 — с чередованием. Если сложить числа попарно, не считая самого последнего, то получится арифметическая прогрессия $%4+14+24+\cdots+109994$%, в которой ровно 11000 членов. Применяя формулу для суммы членов прогрессии, имеем $%(4+109994)\cdot11000/2$%, к которой надо прибавить самое последнее слагаемое $%55001$%. Получится $%605044001$%, и это конечный ответ.

Источник

Зона кода

Рассмотрим следующую задачу.

Каким количеством способов можно разменять тысячерублёвую купюру монетами по 1руб., 2руб., 5руб., 10руб.?

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

Интересно будет проследить за тем, как, по мере перехода от «двоечника» к «троечнику» и от «троечника» к «хорошисту», объёмы предварительных математических выкладок будут расти, а программы будут становиться всё более и более эффективными.

Надеюсь, что словосочетания «математический аппарат» и «математические выкладки» не отпугнут читателя от ознакомления со статьёй. Математику мы будем использовать достаточно простую, да и программы будут простыми тоже, поэтому данный материал можно смело рекомендовать для прочтения новичкам.

Способ «двоечника»

Первое же, что может прийти на ум – это метод перебора. Ясно, что в любом размене тысячерублёвой купюры десятирублёвых монет может быть от 0 до 100, пятирублёвых – от 0 до 200, двухрублёвых – от 0 до 500 и рублёвых – от 0 до 1000. Переберём всевозможные наборы из перечисленных монет, в которых монета каждого достоинства встречается число раз, попадающее в соответствующий ей диапазон. Для каждого такого набора вычислим его рублёвый эквивалент и подсчитаем случаи, в которых он будет равен 1000р.

Программу, реализующую такой ломовой перебор, написать очень легко:

Думаю, программа проста для понимания. Переменная s – это счётчик случаев, в которых количество рублей в наборе равно 1000. Во внешнем цикле перебираем всевозможные количества «десяток», во вложенном в него – количества «пятёрок», далее – количества «двушек», наконец, в самом внутреннем цикле перебираются количества рублей.

Итак, мы имеем 4 вложенных друг в друга цикла, общее количество итераций самого внутреннего цикла – более 10,1 млрд. На моём среднем по мощности ноутбуке программа работает полминуты! Но, несмотря на свою чудовищную неэффективность, она выдаёт правильный ответ – 1712051. Задача решена!

Если мы разделим ответ на количество всех итераций и выразим частное в процентах, то получим примерно 0,017%. Этот процент можно считать «коэффициентом полезного действия» данного метода. Именно такова доля «полезных» итераций в их общем количестве. Таким образом, примерно 99,98% итераций – это условный «балласт», на который тратится компьютерное время. Давайте избавимся от этих трат.

Способ «троечника»

Изменим программу. Внешний цикл оставим нетронутым. Во вложенном в него цикле изменим верхний предел изменения переменной b . Новый предел, который мы будем хранить в переменной m , теперь будет зависеть от текущего значения переменной a . Понятно, что для любого значения a значение b должно быть таково, чтобы выполнялось неравенство 10 * a + 5 * b . Это означает, что значение m , т. е. максимально возможное значение b , должно удовлетворять равенству 10 * a + 5 * m = 1000 , откуда m = 200 — 2 * a .

Что касается третьего и четвёртого цикла, то они нам не нужны. Действительно, если фиксировано количество «десяток» ( a ) и «пятёрок» ( b ), то совсем несложно подсчитать, каким количеством способов можно представить оставшуюся сумму (т. е. 1000 — 10 * a — 5 * b ) в виде «двушек» и рублей.

Это число способов равно максимальному количеству «двушек», которое может «поместиться» в оставшейся сумме (обозначим его, например, p ), сложенному с единицей. Объясняется это тем, что любое количество двухрублёвых монет от 1 до p может быть дополнено рублёвыми монетами до оставшейся суммы, а добавляемая к p единица соответствует единственному способу представления оставшейся суммы без использования «двушек».

Для получения p нужно выполнить целочисленное деление оставшейся суммы на 2. Таким образом, количество способов представления оставшейся суммы в виде двухрублёвых и однорублёвых монет (т. е. p + 1 ) равно (1000 — 10 * a — 5 * b) / 2 + 1 (деление на 2 здесь, разумеется, целочисленное). Именно это количество мы на каждой итерации внутреннего цикла будем теперь добавлять к счётчику s .

Этих выкладок уже вполне достаточно, чтобы написать второй вариант программы:

Программа выдаёт тот же результат, что и раньше, а время её работы составляет доли секунды. Это программа уже построена на подсчёте искомого количества способов, а не на переборе огромного количества вариантов, среди которых имеется львиная доля тех, которые нас не устраивают.

Несложно подсчитать общее число итераций внутреннего цикла:

∑ a = 0 100 200 — 2 a + 1 = ∑ a = 0 100 201 — 2 ∑ a = 0 100 a = 201 · 101 — 2 · 100 · 101 2 = 101 2 = 10201 .

Здесь мы использовали хорошо известные формулы для нахождения сумм:

∑ k = 0 n c = n + 1 c , ∑ k = 0 n k = n n + 1 2 .

Как мы видим, общее число итераций внутреннего цикла, по сравнению с предыдущим вариантом, снизилось на 6 порядков!

Заметим, что если бы мы решали задачу, в которой размен тысячи необходимо было осуществлять с помощью монет достоинством 1руб., 5руб., 10руб., то на каждой внутренней итерации нужно было бы увеличивать счётчик на 1. Это означает, что окончательное его значение совпало бы с общим числом внутренних итераций, т. е. с числом 10201. Таким, образом, мы, в качестве побочного эффекта, получили аналитическое решение задачи о количестве способов, которым можно осуществить описанный в начале абзаца обмен. Это число равно 10201.

Дальнейшие усовершенствования программы уже не приведут к хоть сколько-нибудь заметному увеличению производительности, поскольку программа уже выполняется почти мгновенно. Однако, из любви к искусству программирования, останавливаться мы не будем.

Способ «хорошиста»

В этом разделе мы получим выражение искомого количества способов размена в виде суммы, поле чего напишем программу для её вычисления.

Каждому способу размена тысячерублёвой купюры, удовлетворяющему условию нашей задачи, можно поставить в соответствие число t – суммарный рублёвый эквивалент всех однорублёвых и двухрублёвых монет, использующихся при размене данным способом. Для каждого t создадим группу, содержащую все способы размена, соответствующие t. Таким образом, каждой группе способов будет соответствовать своё t.

Несложно заметить, что t может принимать значения 0, 5, 10, . 1000. Таким образом, количество групп равно 201. Пусть s_k – число способов размена, содержащихся в группе, соответствующей значению t, равному 5k. Тогда S – искомое количество способов размена тысячерублёвой купюры, можно представить в виде:

S = ∑ k = 0 200 s k .

Выразим s_k через k. Для этого представим s_k в виде u_kv_k, где u_k – число способов, которыми можно набрать 5k рублей однорублёвыми и двухрублёвыми монетами, а v_k – число способов, которыми можно набрать оставшиеся 1000-5k рублей пятирублёвыми и десятирублёвыми монетами.

Найдём u_k. Воспользуемся способом, уже применявшимся нами в предыдущем разделе: разделим 5k на 2 «нацело» и добавим единицу:

Квадратные скобки здесь обозначают целую часть заключённого в них числа.

Теперь найдём v_k. Задача о нахождении количества способов набора 1000-5k рублей пятирублёвыми и десятирублёвыми монетами эквивалентна задачи о нахождении количества способов набора однорублёвыми и двухрублёвыми монетами суммы в 5 раз меньшей, т. е. 200-k рублей. Снова делим на 2 «нацело» и добавляем единицу:

v k = 200 — k 2 + 1 = 100 — k 2 + 1 = 101 — k 2 .

В итоге, получаем:

s k = u k · v k = 5 k 2 + 1 · 101 — k 2 ,

S = ∑ k = 0 200 5 k 2 + 1 · 101 — k 2 .

Формула получена, теперь можно составлять программу:

Заметим, что при написании программы выражение 101 — k 2 было закодировано как (202 — k) / 2 .

Программа выдаёт всё тот же результат – 1712051, используя при этом один-единственный цикл, в ходе которого выполняется 201 итерация.

Способ «отличника»

А теперь давайте решим задачу без использования программирования. Частью нашего решения являются математические выкладки, уже выполненные в предыдущем разделе. Нам остаётся лишь найти число S, воспользовавшись последней формулой предыдущего раздела.

Индекс k, принимающий все целые чётные значения от 0 до 200 включительно, можно представить в виде 2m, где новый индекс m принимает все целые значения от 0 до 100 включительно. Воспользовавшись заменой k=2m, запишем S₀ в виде суммы и найдём её:

S 0 = ∑ m = 0 100 5 · 2 m 2 + 1 · 101 — 2 m 2 = ∑ m = 0 100 5 m + 1 · 101 — m =
= ∑ m = 0 100 — 5 m 2 + 504 m + 101 = — 5 ∑ m = 0 100 m 2 + 504 ∑ m = 0 100 m + ∑ m = 0 100 101 = — 5 · 100 · 101 · 201 6 +
+ 504 · 100 · 101 2 + 101 2 = — 1691750 + 2545200 + 10201 = 863651 .

Здесь мы использовали три формулы, позволяющие вычислять суммы. Две из них мы приводили ранее, а третью приведём сейчас:

∑ k = 0 n k 2 = n n + 1 2 n + 1 6 .

Эти же три формулы понадобятся нам и для нахождения S₁.

Индекс k, принимающий все целые нечётные значения от 1 до 199 включительно, можно представить в виде 2m+1, где новый индекс m принимает все целые значения от 0 до 99 включительно. Воспользовавшись заменой k=2m+1, запишем S₁ в виде суммы и найдём её:

S 1 = ∑ m = 0 99 5 · 2 m + 1 2 + 1 · 101 — 2 m + 1 2 = ∑ m = 0 99 5 m + 3 + 1 2 · 100 + 1 2 — m =
= ∑ m = 0 99 5 m + 3 · 100 — m = ∑ m = 0 99 — 5 m 2 + 497 m + 300 = — 5 ∑ m = 0 99 m 2 + 497 ∑ m = 0 99 m + ∑ m = 0 99 300 =
= — 5 · 99 · 100 · 199 6 + 497 · 99 · 100 2 + 100 · 300 = — 1641750 + 2460150 + 30000 = 848400 .

S = S 1 + S 2 = 863651 + 848400 = 1712051 .

Выводы

Итак, мы решили задачу 4-мя способами. Первые 3 из них включали в себя написание программ. Для каждой из них было указано число итераций внутреннего цикла. Данная информация позволяет приближённо сравнить программы по производительности. Однако сравнение будет более точным, если в нём будут участвовать количества операций умножения и деления, задействованных в программах. Известно, что эти 2 операции требуют для своего выполнения значительно большего количества процессорного времени, чем операции сложения и вычитания, поэтому последними двумя мы пренебрежём.

Соберём в таблицу информацию о количествах циклов, итераций внутреннего цикла и числе операций умножения и деления.

Программа	Количество циклов	Количество итераций внутреннего цикла	Количество операций умножения и деления
«двоечника»	4	10 180 971 801	30 542 915 403
«троечника»	2	10 201	30 704
«хорошиста»	1	201	804

Как мы видим, информация, приведённая в последнем столбце, не вносит существенных корректив в результаты сравнений производительности программ. В соответствии с ней, вторая программа превосходит по производительности первую почти в 10 6 раз, а третья вторую – почти в 40 раз. В первом случае разрыв гигантский, а во втором – небольшой. «На глаз» заметить разницу во временах выполнения второй и третьей программ невозможно.

В заключение статьи проведём забавный мысленный эксперимент. Представим, что 4-м человекам предоставили в распоряжение компьютеры, бумагу, ручки и предложили решить нашу задачу. Предположим, что каждый из них выбрал один из способов, приведённых в статье, причём все выбрали разные способы. Будем считать, что способности этих людей примерно равны, тем не менее, назовём их условно «двоечником», «троечником», «хорошистом» и «отличником» в соответствии с выбранными ими способами. Зададимся вопросом: кто из них быстрее всех справится с задачей, а кто – медленнее?

Как мне представляется, «двоечник» решит задачу достаточно быстро. Например, за минуту придумает алгоритм, за минуту его реализует на компьютере, через полминуты работы программы ответ будет готов. «Троечник» будет возиться с алгоритмом на несколько минут дольше «двоечника», и, хоть его программа выполнится за доли секунды, по общему количеству времени «двоечнику» он уступит.

«Хорошисту» придётся разрабатывать алгоритм ещё дольше, и «троечнику» он проиграет. А вот отличник может в своих выкладках вообще увязнуть и потратить на решение полчаса или даже больше. Таким образом, он, скорее всего, «с треском» проиграет всем остальным.

Результаты могут показаться парадоксальными: интеллект проигрывает грубой ломовой силе. Означает ли это, что особого смысла в оптимизации программ может и не быть?

Вопрос очень простой, и я думаю, что ответ читателю известен. Если программа используется однократно, то, действительно, нет особой разницы в том, работает она полминуты или тысячную долю секунды. Но такие программы – редкость. В подавляющем большинстве случаев программное обеспечение рассчитано на многократное применение. И если на одном компьютере программа запускается на выполнение пару сотен тысяч раз, то снижение времени её работы даже на полсекунды весьма существенно! Ведь в данном примере суммарный выигрыш по времени превысит сутки! В таких случаях уместность оптимизации очевидна.

Источник