Решение задачи 3.
Задача имеет очевидное решение, которое состоит в генерации всех 2*n-разрядных чисел и проверке их на требуемое свойство. Однако общее количество таких чисел равно 102n и поэтому при n>3 практически очень трудно получить результат на ЭВМ. Следовательно необходимо разработать алгоритм, не требующий генерации чисел.
Определим через S(k,i) количество k-разрядных чисел, сумма цифр которых равна i. Например, S(2,3)=4, так как существует 4 двуразрядных числа (03,12,21,30), сумма цифр которых равна 3. Легко заметить, что S(1,i)=1 при i<10 и S(1,i)=0 при i>9. Предположим теперь, что мы сумели вычислить значения величин S(n,i) для всех i от 0 до 9*n, т.е. мы знаем, сколько существует n-разрядных чисел с суммой цифр, равной 0,1,...,9*n (максимальное число цифр в n-разрядном числе). Тогда нетрудно убедиться, что общее количество 'счастливых' 2*n-разрядных чисел равно
P=S(n,0)*S(n,0)+S(n,1)*S(n,1)+...+S(n,9*n)*S(n,9*n).
Действительно, каждое 'счастливое' 2*n-разрядное число может быть получено склейкой двух произвольных n-разрядных чисел с одинаковой суммой цифр.
Таким образом, необходимо уметь вычислять значения величин S(k,i) для всех k<=n,i<=9*k. Определим способ вычисления S(k+1,i) через значения величин S(k,j), j<=i. Понятно, что любое k+1-разрядное число может быть получено из k-разрядного добавлением еще одного разряда (цифры). Следовательно
S(k+1,i) = S(k,i-ц1)+S(k,i-ц2)+...,
где ц1,ц2,... - возможные добавленные цифры. Ясно, что это 0,1,...,m где m=min(9,i). Следовательно,
S(k+1,i) = S(k,i-0)+S(k,i-1)+...+ S(k,i-m).
|
