A pomógłby mi ktoś napisać algorytm na znalezienie rozwiązania takiego problemu:
Ile jest liczb naturalnych mniejszych od 10^15, których suma cyfr jest równa 16?
Mój algorytm znajdywał poszczególne cyfry tej liczby, a potem sprawdzał poprawność sumy, ale sypnął się przy miliardzie bo wykonywał pętlę ok. 3 minut... :/
suma czego? cyfr?
tak mały bład....
79
88 //79 + 9
97 //88 + 9
169
178 //169 + 9
187 //178+ 9
196 //187 + 9
Jak widać...jakaś zależność jest...musisz tylko wyłapać jaka dokładnie (wydaje mi się, że po prostu początkowe liczby(79, 169, 259...) powstają przez dodanie do siebie 90... no a kolejne przez dodanie 9...tyle, że ilość tych kolejnych też jest na pewno od czegoś zależna...np. za pierwszym razem są dwie..za drugim trzy... no i pewnie etc. ;] ... przyznaję, że po prostu mi się nie chce sprawdzać/szukać tej zależności ;-P ) ... no a wtedy(jeśli moja teoria się okaże prawdziwa) na pewno zaoszczędzisz sporo czasu ... bo w pewnych momentach będziesz mógł opuścić sprawdzanie wielu liczb :)
//mam nadzięję, że się nie pomyliłem z tą zależnością..jeśli tak, to sorki.
pzdr.
Rozwiązać można to w sekundę (lub mniej), przy okazji znajdując liczbę wszystkich rozwiązań od zera do 135 (15*9).
Szkoda, że [tex] taki kulawy.
http://4programmers.net/cgi-bin/mimetex.cgi?%5Cleft(%5Csum_{i=0}^9x_i%5Cright)^{15}=
http://4programmers.net/cgi-bin/mimetex.cgi?%5Cleft(1+x+x^2+x^3+x^4+x^5+x^6+x^7+x^8+x^9%5Cright)^{15}
Liczba rozwiązań to współczynnik występujący przy odpowiedniej potędze iksa.
Program to mniej niż 20 wierszy.
Rozwiązanie to 144841275.
A moglbyś go tutaj przedstawic??
Jakąs czesc główną kodu tego programu...
Bo troszke nie jasne jest to dla mnie...
const max=644;
var
t,z:array[0..max] of qword;
procedure moneta(k, p,n:dword);
var i,j:dword;
begin
write('\left(\sum_{i=',p,'}');
if n<max then write('^{',n,'}');
write('x^'); if k>1 then write('{',k,'i}') else write('i');
write('\right\)');
z:=t;
for i:=0 to max do z[i]:=0;
i:=p;
while (i<=max) and (i div k<=n) do begin
for j:=max-i downto 0 do
z[i+j] += t[j];
i+=k
end;
t:=z;
end;
var i:dword; s:qword;
begin
for i:=1 to max do t[i]:=0; t[0]:=1; //x^0
for i:=1 to 15 do
moneta(1, 0, 9);
writeln('=');
s:=t[0];
if t[0]>0 then write(t[0]);
for i:=1 to max do begin
s+=t[i];
if t[i]>0 then begin
write(' +');
if t[i]>1 then write(t[i]);
write('x^{',i,'}');
end
end;
writeln; writeln('\sum=',s);
end;
Jeżeli zsumujemy cyfry [u]dowolnej[/u] liczby (całkowitej), następnie zsumujemy cyfry sumy itd aż do chwili gdy uzyskamy jedną cyfrę, otrzymamy to samo co licząc (liczba-1) mod 9 + 1.
Wszystkie liczby (o odpowiedniej sumie cyfr) dadzą resztę z dzielenia przez 9 równą 7 (1+6).
Z tego wynika pomysł Wędrowca, możemy więc sprawdzać co 9 liczbę, czyli o tyle przyśpieszymy przeszukiwanie całego zakresu, ale i tak 10^15/9 do olbrzymia liczba.
Kłopot z moim rozwiązaniem polega na tym, że trzeba się spodziewać pytania: "A czy potrafisz udowodnić, że tak można?". I co wtedy?
Można podejść do tego inaczej.
Wszystkich sposobów na jakie można zapisać 16 jako sumę jest tylko 231, cześć nie będzie poprawna, ponieważ składniki nie mogą być większe od 9 oraz liczba składników nie może być większa od 15.
Np. 16=7+9, 7 możemy umieścić na dowolnej z 15 pozycji, 9 już tylko na 14 (albo odwrotnie), czyli liczb składających się z 7, 9 i 13 zer będzie 1514=210
16=7+5+4, takich liczb będzie 1514*13=2730
Tyle czynników ile składników, suma tych iloczynów to właśnie rozwiązanie.
Program, który znajdzie te 231 "rozkładów" będzie działał z pewnością szybciej niż sprawdzanie sumy cyfr wszystkich liczb aż do 10^15.
Poprawka!!!!!
16=9+5+1+1, liczba liczb to nie będzie 15141312, bo kolejność jedynek przecie NIE MA znaczenia.
Liczymy to tak (15 po 1)(14 po 1)(13 po 2)
(x po y) to x!/y!/(x-y)! (<url= http://pl.wikipedia.org/wiki/Symbol_Newtona>Symbol Newtona</url>)
x to kolejne liczby, od 15 w dół, y to liczba takich samych cyfr.
(15 po 1) to 15
(13 po 2) to 1312/2
"Rozkłady" można znaleźć zadziwiająco zwięzłą procedurą procedure pp(n,k,t:longint);
var j:longint;
begin
p[t]:=k;
if n=k then printit(t);
for j:=min(k, n-k) downto 1 do
pp(n-k, j, t+1);
end;
Zawołane n:=16; pp(2*n, n, 0), zawoła 231 razy procedurę printit(T); składniki znajdują się w tablicy P[1..T].
Trzeba sprawdzić czy T<16 oraz czy żaden składnik nie jest większy od 9.
Jest 200 takich przypadków.