In general, nothing serious, an entertaining task about finding the number of "happy tickets". Description of the algorithm . % Subj% :-)

recurrence formula

#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, km ); } else { sum += N( n-1, km ); } } 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; }
  • You recalculate N_i(k) many times. Try running through i and at each step remember all the N_i(k) in the array. - VladD
  • If you cheat several at once - maybe, yes. But the number of N () calls for digits = 7 and 8 differs by an order of magnitude ( 3,666,660 and 41,666,659 ) ... - user6550
  • @avp: (comments have ended there) Thank you! Flattered - VladD

2 answers 2

Something like this should roll:

 int** N = malloc(9 * sizeof(int*)); for (int i = 1; i <= 8; i++) { int length = i * 9 + 1; N[i] = malloc(length * sizeof(int)); if (i == 1) { for (int j = 0; j < length; j++) N[i][j] = 1; } else { unsigned long long runningsum = 0; int k = 0; for ( ; k <= length / 2; k++) { runningsum += N[i-1][k]; if (k >= 10) runningsum -= N[i-1][k-10]; N[i][k] = runningsum; } for ( ; k < length; k++) { N[i][k] = N[i][length - 1 - k]; } } }

It seems to work correctly: http://ideone.com/yHXArN (compared with the table in the article)

Here is the whole code: http://ideone.com/FVNJdH

  • It was wrong, corrected - VladD
  • @VladD, but where do you get the initial values ​​in N? And notice the question mark C, ane C ++. - avp
  • @avp: you are right, there were no initial values, added. Now I will translate to pure C ... - VladD
  • @avp: translated. - VladD
  • 2
    ABOUT! Initial option: 1: 10 2: 670 3: 55252 4: 4816030 5: 432457640 6: 39581170420 7: 3671331273480 8: 343900019857310 real 0m8.597s user 0m8.589s sys 0m0.008s Your: 1: 10 2: 670 3: 55252 4: 4816030 5: 432457640 6: 39581170420 7: 3671331273480 8: 343900019857310 real 0m0.007s user 0m0.004s sys 0m0.004s Gorgeous :) - user6550

Trivial replacement for (...) { ... } in N() with

 // optimize if (k < 9) { for (; m <= k; m++) sum += N(n-1, km); } else { for (; m < 10; m++) sum += N(n-1, km); }

those. removing ifs from a cycle gives 10 percent

Initial version

 real 0m4.593s user 0m4.100s sys 0m0.112s

Optimized

 real 0m4.166s user 0m3.676s sys 0m0.084s

C gcc -O3

initial

 real 0m3.659s user 0m3.148s sys 0m0.104s

optimized

 real 0m2.836s user 0m2.504s sys 0m0.080s