Хотябы алгоритм... но лучше сразу код... прога для вас гуру простенькая... ,а я тупой не шарю...
вот текст задания(сори если коряво - переводил с украинского)
Написать програму для опредиления количества 2*N -значных билетов, у которых
сума первых N десятичных цифр равняется суме N последних цифр; N –
произвольное натуральное число.
Програмка в С++
-
ivank
Re: Програмка в С++
Вообще говоря, не хорошо просить написать программу других людей. Я даже подумывал вчера закрыть тему... Но сегодня я ехал в метро и всё равно не о чем было думать, так что вот результат моих теоретических изысканий.
Идея проста как помидор: надо найти количество всех комбинаций из N цифр соответствующих каждой из возможных сумм. Суммы будут лежать в пределах от 0 (N нулей) до 9*N (N девяток). Ответом очевидно будет являться[pre]9*N
_
\
/_ S[[N]][]^2
i=0[/pre]где S[[N]][] - количество комбинаций из N цифр соответствующих сумме i.
Далее, очевидно, что S[[1]][[0]] = S[[1]][[1]] = ... = S[[1]][[9]] = 1.
К любой комбинации из k-1 одной цифры можно дописать одну цифру x от 0 до 9. Она, соответственно, увуличит значение суммы этой комбинации на x.
Тогда алгоритм вычисления s[[k]] по s[[k-1]]:
Код:
Это надо повторять до тех пор пока k не сравняется с N. А после этого уже можно вычислять конечный результат по вшеприведённой формуле.
Динамическое программирование во всей красе.
Если не понятно, прошу прощения. У меня всегда были проблемы с объяснением решений даже простых задач.
Идея проста как помидор: надо найти количество всех комбинаций из N цифр соответствующих каждой из возможных сумм. Суммы будут лежать в пределах от 0 (N нулей) до 9*N (N девяток). Ответом очевидно будет являться[pre]9*N
_
\
/_ S[[N]][]^2
i=0[/pre]где S[[N]][] - количество комбинаций из 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:
s[[k]][[i]] = 0
// Перебираем все цифры, которые можно дописать
Для x от 0 до 9:
// Перебираем все возможные суммы для комбинаций из k-1 цифры
Для i от 0 до (k-1)*9:
// После того как допишем цифру x сумма i увеличится на x
// значит все комбинации, которые раньше давали в сумме i
// теперь (после того как приписали x) будут давать сумму i+x
// Значит к количеству комбинаций длины k дающих в сумме i+x
// можно добавить количество комбинаций длинны k-1,
// сумма которых даёт i
s[[k]][[i+x]] += s[[k-1]][[i]]Это надо повторять до тех пор пока k не сравняется с N. А после этого уже можно вычислять конечный результат по вшеприведённой формуле.
Динамическое программирование во всей красе.
Если не понятно, прошу прощения. У меня всегда были проблемы с объяснением решений даже простых задач.
-
ivank
да действительно не понятно...-
ivank
Re: Програмка в С++
А что конкретно непонятно? Откуда взялась формула для результата, как считается s[[k]][] или что-то ещё?