В общем-то ничего серьёзного, развлекательная задача про поиск количества "счастливых билетов". Описание алгоритма. %Subj% :-)
#include <stdio.h>
static unsigned long long
N( size_t n, size_t k )
{
unsigned long long sum = 0;
size_t m = 0;
if( !n ) return 0;
if( n == 1 ) return (k <= 9);
for( ; m <= 9; m++ )
{
if( k < 9 )
{
if( m <= k ) sum += N( n-1, k-m );
}
else
{
sum += N( n-1, k-m );
}
}
return sum;
}
static unsigned long long
l_t( size_t digits )
{
unsigned long long tickets = 0;
size_t i = 0;
for( ; i <= (digits*9); i++ )
{
unsigned long long n = N( digits, i );
tickets += n*n;
}
return tickets;
}
int main()
{
printf
(
"1: %llu\n2: %llu\n3: %llu\n4: %llu\n5: %llu\n6: %llu\n7: %llu\n8: %llu\n",
l_t(1),l_t(2),l_t(3),l_t(4),l_t(5),l_t(6),l_t(7),l_t(8)
);
return 0;
}
N_i(k)
. Попробуйте пробежаться по i и на каждом шаге запомнить всеN_i(k)
в массиве.