МЕНЮ
Гостевая книга
Форум
КАК РАЗЛОЖИТЬ ЧИСЛО 100 НА ЧАСТИ
Задача №76 на сайте с задачами Projecteuler
звучит примерно так: "Сколькими способами можно записать число 100 в
виде суммы двух или более чисел, каждое из которых не меньше предыдущего
(то есть числа идут в порядке возрастания)"
Несколько способов: 100=1+99, 100=1+4+95, 100=1+1+1+1+...+1 (100 единиц)
Как я ее решал? Допустим у нас есть функция Y, принимающая на вход два
параметра: первый - минимальное слагаемое в сумме, второй - число, которое нужно разложить. Соответственно,
для нашей задачи нужно найти Y(1,100)-1. То есть разложить число 100,
и минимальное число в сумме - единица. Минус один потому что один вариант
записи числа 100 просто как 100 мы не рассматриваем. Нужно два числа как
минимум.
Для разработки алгоритма, однако, отвлечемся, и попробуем найти Y(5,1).
Это задание можно разложить на два - сначала попробовать вычесть из
5 единицу, и искать решения в виде 1+Y(4,1), где Y(4,1) - число разложений
четверки. Все остальные решения будут иметь минимальным слагаемым двойку,
поэтому можно записать их как Y(2,5) - число разложений пяти с минимальным
слагаемым "2"
Если вы не поняли, вот картинка:
Число разложений пятерки с первым слагаемым не меньше двойки будет равно
числу разложений тройки со слагаемым не меньше 2 (если представим
пятерку как 2+Y(2,3)) и плюс число разложений пятерки со слагаемым
не меньше трех - Y(3,5).
Итого мы получили:
Y(1,5) = Y(2,5) + Y(1,4)
Y(2,5) = Y(3,5) + Y(2,3)
Или, в общем виде, можно написать:
Y(A,B) = Y(A+1,B) + Y(A,B-A)
Естественно, если A=B, то Y будет единица (число сто можно записать как
сумму чисел, каждое из которых не меньше ста только одним способом),
а если A>B, то Y=0, так как, например 10 вообще нельзя записать как
сумму, если минимальное число 20.
Теперь попробуем написать первые разложения числа 100:
Y(1,100) = Y(2,100) + Y(1,99) =
= Y(3,100) + Y(2,98) + Y(2,99) + Y(1,98) =
= Y(4,100) + Y(3,97) + Y(3,98) + Y(2,96) + Y(3,99) + Y(2,97) + Y(2,98) + Y(1,97) = ...
Вот таким путем, все далее и далее, мы и решим в конце концов задачу.