Здравствуйте, watchmaker, Вы писали:

W>Здравствуйте, Кузнец, Вы писали:

К>>>>например, если допустима длина 10, а символов 26 — все буквы английского алфавита, при этом запрещённых слов нет, то ответ будет 10^26, и мы будем его собирать по единичке, затратив на всё дело слишком много времени.

К>>Дно рекурсии — единица, ответ программа разлагает на сумму нулей и единиц и их суммирует, так что алгоритм время ест )

W>Сколько сложений делает твоя реализация на этом примере? Алгоритму, описанному в твоём же первом сообщении, достаточно 260 сложений. Если твоя реализация делает больше — то значит реализация плохая. Нужно её выкинуть и воплотить в код ровно то, что описано текстом в твоём первом сообщении. Только потом к этому имеет смысл добавлять сжатие путей и прочие оптимизации.

Либо 260 сложений этому алгоритму недостаточно, либо я его попросту неверно понял. Описанный алгоритм разлагает ответ в сумму единиц и их складывает, по-моему это в первом сообщении и описано (идёт рекурсия функцией f, рекурсивный вызов обрывается лишь если второй аргумент f равен нулю, при такой ситуации значение f будет равно 1, то есть внизу рекурсии у нас только единицы).

Моя реализация ровно это и делает. Если я неверно понял алгоритм, и всё же в каких-то случаях внизу рекурсии окажутся не единицы — прошу помочь разобраться, как именно должен выглядеть алгоритм.