| Я уже пыталась поднять тут такой вопрос: как бы в хаскеле хранить результаты предыдущих вычислений, чтобы не делать все подряд вычисления экспоненциально длинными? Первое, что выяснилось, сам хаскель этого «волшебно» не делает, так что надо как-то заботиться об этом самостоятельно. Пример с числами Фибоначчи был не лучшим, ибо для него надо всего-то хранить два последних значения, и можно выкрутиться всякими хитростями. А что если их надо знать аж целых N? Вот сейчас я опишу некую задачу и прошу знатоков хаскеля мне объяснить: как её следует образцово-показательно решать на хаскеле? Итак, залезая в Ленинграде в трамвай, следует кинуть три копейки в кассу-копилку и выкрутить себе из неё билетик. На нём стоит шестизначный номер. Билетик считается «счастливым», если сумма первых трёх цифр номера равняется сумме трёх последних (оставшихся) цифр. Для наступления счастья, такой билет необходимо немедленно засунуть в рот, прожевать и проглотить (а потом заесть булкой сидя на поребрике у парадной). Задача такая: сколько существует обобщённых счастливых билетиков заданного порядка n, то есть последовательностей цифр длины 2n, у которых сумма первой половины цифр равна сумме второй половины цифр (таким образом стандартный трёхкопеечный билет с шестизначным номером является обобщённым порядка 3). Есть два подхода к вычислению этого числа, которые дают алгоритмы одинаковой временной сложности — O(n²), если мы говорим о машине RAM и O(n³) если мы говорим об «обычном компьютере», который складывает и вычитает длинные числа за линейное в длине время. Оба подхода основываются на том, что достаточно лишь подсчитать, сколько существует билетиков заданной длины с заданной суммой цифр, а количество счастливых билетиков порядка n оказывается равным числу билетов длины 2n с суммой цифр 9n (что бы это увидеть, нужно представить себе, что во всех билетах заменили вторую половину цифр по формуле x↦9-x). Таким образом, всё сводится к вычислению функции B(n,s) числа билетов длины n с суммой цифр s. Дальше можно действовать по разному. Вот здесь описано как свести вычисление функции B(·,·) к вычислению нескольких биномиальных коэффициентов и их сумм. Таким образом получается простая программа на хаскеле, но не она меня сегодня интересует. ( Кому интересно, билетики можно считать такCollapse ) А интересно мне вот что: как выразить на хаскеле «алгоритм считания в лоб»? В лоб считают так: предположим, что мы знаем все значения B(n-1,·). Тогда для вычисления B(n,s) нужно просто по очереди предположить, что билетик начинается на 0, 1, 2, 3, 4, 5, 6, 7, 8 и 9, и получится, что B(n,s)=Σ B(n-1, s-i) по всем i=0,…,9. То есть, для вычисления следующих 9n+1 значений нужно знать все 9(n-1)+1 предыдущих — похитрее чем у чисел Фибоначчи. ( Вот, чисто для иллюстрации, этот алгоритм на перлеCollapse ) |
|