http://mendo.mk/jforum/posts/list/6.page JForum - http://www.jforum.net http://mendo.mk/jforum/posts/preList/701/3812.page http://mendo.mk/jforum/posts/preList/701/3812.page GMT Бидејќи постојат броеви со различен број на цифри кои би можеле да го задоволат бараното својство, ќе ја повториме техниката на броење за секоја должина на бројот посебно. Да речеме дека имаме дадна разлика S, |S| = k, и цифрите на S се s_k, s_(k-1), ..., s_1. Нека бројот кој тековно го разгледуваме е N, |N| = q, цифрите на N се n_q, n_(q-1), ..., n_1. Значајно е да спомнеме дека N > S и |N| >= |S|, инаку својството не би можело да биде исполнето. За поедноставување на проблемот, сметаме дека |S| = |N|, со тоа што S го пополнуваме со водечки нули.
За да развиеме техника за броење, треба да увидиме како можеме да ги пресметаме сите различни начини за да се добие цифрата на некоја произволна позиција (k) во бројот S. Првото нешто што би ни текнало на памет е да ги најдеме сите можни вредности на n_k и n_(q-k) за кои важи својството: s_k = n_k - n_(q+1-k). Но, тоа не е сосема точно, бидејќи кога одземаме броеви може да дојде до пренесување на десетки ако n_k < n_(q+1-k). Според тоа, нека carry е бит стринг, кај кој k-тиот бит има вредност 1 ако се пренесува десетка од k-тата во (k-1)-та позиција при одземањето. Нека valid(s, n, k, carry) е функција која враќа дали можеме да ја добиеме k-тата цифра во s од бројот n и пренесувањата carry. Тогаш, valid(s, n, k, carry) = true ако и само ако s_k = 10 * getBit(carry, k+1) + n_k - getBit(carry, k) - n_(q+1-k). Конечно, доаѓаме до следната рекурентна равенка за пресметување на сите можни броеви:

ways(k, carry, q) = cnt_k * ways(k+1, carry, q); k <= q / 2; каде што cnt_k се сите подредени парови (a, b), за кои важи valid(s, n, k, carry) и valid(s, n, q+1-k, carry).
ways(k, carry, q) = 1; k > q / 2;

Бидејќи не можеме однапред да знаеме на кои места ќе имаме пренесување на вредноста, ќе ги испробаме сите вредности на carry, кои се 2^(digitLen-1) на број, каде digitLen е бројот на цифри за кој пресметуваме. Псевдо-кодот на решението е следниот:
[code]
total = 0
for digit_len in |S|..MAX_LEN:
for carry in 0..2^(digit_len-1):
total += ways(1, carry<<1, digit_len)
[/code]

Да напоменам дека решението работи за MAX_LEN >= 19. Исто така, carry има вкупно 2^(digitLen-1) вредности, а не 2^(digitLen), поради тоа што не можеме да пренесуваме десетки од првата цифра на десно.]]> http://mendo.mk/jforum/posts/preList/701/3813.page http://mendo.mk/jforum/posts/preList/701/3813.page GMT http://mendo.mk/jforum/posts/preList/701/3814.page http://mendo.mk/jforum/posts/preList/701/3814.page GMT