Програмка в С++ - Компьютерный форум OSzone.net

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

Идея проста как помидор: надо найти количество всех комбинаций из N цифр соответствующих каждой из возможных сумм. Суммы будут лежать в пределах от 0 (N нулей) до 9*N (N девяток). Ответом очевидно будет являться[pre]9*N
_
\
/_  S[[N]][[i]]^2
i=0[/pre]где S[[N]][[i]] - количество комбинаций из N цифр соответствующих сумме i.

Далее, очевидно, что S[[1]][[0]] = S[[1]][[1]] = ... = S[[1]][[9]] = 1.

К любой комбинации из k-1 одной цифры можно дописать одну цифру x от 0 до 9. Она, соответственно, увуличит значение суммы этой комбинации на x.

Тогда алгоритм вычисления s[[k]] по s[[k-1]]:

Код:

// заранее обнуляем S[[k]]

Для i от 0 до 9*k:

 &nbsp; &nbsp;s[[k]][[i]] = 0

// Перебираем все цифры, которые можно дописать

Для x от 0 до 9:

 &nbsp; &nbsp;// Перебираем все возможные суммы для комбинаций из k-1 цифры

 &nbsp; &nbsp;Для i от 0 до (k-1)*9:

 &nbsp; &nbsp; &nbsp; &nbsp;// После того как допишем цифру x сумма i увеличится на x

 &nbsp; &nbsp; &nbsp; &nbsp;// значит все комбинации, которые раньше давали в сумме i

 &nbsp; &nbsp; &nbsp; &nbsp;// теперь (после того как приписали x) будут давать сумму i+x

 &nbsp; &nbsp; &nbsp; &nbsp;// Значит к количеству комбинаций длины k дающих &nbsp;в сумме i+x

 &nbsp; &nbsp; &nbsp; &nbsp;// можно добавить количество комбинаций длинны k-1,

 &nbsp; &nbsp; &nbsp; &nbsp;// сумма которых даёт i

 &nbsp; &nbsp; &nbsp; &nbsp;s[[k]][[i+x]] += s[[k-1]][[i]]

Это надо повторять до тех пор пока k не сравняется с N. А после этого уже можно вычислять конечный результат по вшеприведённой формуле.

Динамическое программирование во всей красе.

Если не понятно, прошу прощения. У меня всегда были проблемы с объяснением решений даже простых задач.