[ stalker @ 21.07.2004. 23:24 ] @
Radeci pascal naisao sam na jako zanimljivu "pojavu". Pretpostavljam da ce interesovati i vas. Zadatak je glasio ovako:
Code:

U nizu 19886138... svaka cifra pocev od pete, jednaka je poslednjoj cifri
od sume cetiri prethodne cifre. Napisati program
kojim se odredjuje od koje cifre ce se ponovo naici na pocetnu kombinaciju 1988?


Pretpostavljam, inace, da je zadatak bio 1988. godine na nekom takmicenju:)

E, sad da se ne bi mucili, evo programa koji to resava
Code:

program cudan_niz(input, output);
const
    pattern=1988;
var
    broj, cifra:integer;

{na osnovu 4-cifrenog broja trazi sledecu cifru}
{primer: novacifra(1988)=6}
function novacifra(broj:integer):integer;
begin
    novacifra:=0;
    repeat
        novacifra:=novacifra+broj mod 10;
        broj:=broj div 10;
    until broj=0;
    novacifra:=novacifra mod 10;
end;

begin
    cifra:=0;
    broj:=pattern;
    repeat
        {pravimo novi 4-cifreni broj}
        {od 1988 nastaje 9886}
        broj:=(broj mod 1000)*10+novacifra(broj);
        cifra:=cifra+1;
    until broj=pattern;
    writeln('Od ',cifra,'. cifre');
    readln;
end.


Verovatno znate output po imenu teme:) Ali sad meni djavo ne da mira, moram ja da se igram sa konstantnom pattern za 2004. godinu, i zacudih se rezultatom! Napravih ja tu jednu petlju gde vrti pattern, kad se jos vise zacudih!!! Provalio sam semu kako izlazi rezultat, ali ne razumem zasto?

Evo, nisam bas sve hteo da vam otkrijem, igrajte se i vi, prepravite program, provalite semu kako rezultat izlazi (ovo je lako, castim pice) i objasnite mi zasto je bas tako (ovo je tesko, bar meni). Sad sam se nalozio, i neki linkovi o ovome ne bi bili losi takodje.
[ stalker @ 23.07.2004. 16:37 ] @
U bre sto ste stidljivi. Evo da vas podstaknem
[ neor @ 23.07.2004. 19:40 ] @
Ne mogu da ti kazem konkretno u ovom slucaju zasto bas ta dva broja (u stvari tri, moze da se dobije i petica) ali ako ti nesto znaci evo malo uopsteno.
Stvar je u tome da je ta operacija definisana u zadatku ciklicna.
Na primer kad samo imas obicno sabiranje po modulu 10 onda nula ima ciklus 1, petica 2, svaki paran broj ima ciklus 5 a svaki neparan osim petice ima ciklus 10.
Znaci ako bilo koji paran broj saberes sa samim sobom 5 puta dobices isti broj.
Slicno je i sa mnozenjem po modulu. To moze cak da se koristi kao vrlo jednostavan nacin za dobijanje pseudo slucajnih brojeva.

U ovom tvom slucaju operacija je malo komplikovanija i zavisi od 4 cifre ali ocigledno i ona ima takve cikluse. Ako malo modifikujes operaciju mozes da dobijes neke druge brojeve ali se moze desiti i da neki brojevi nikad nece da se ponove, zavisi od operacije.
U tvom zadatku ciklus 5 imaju brojevi koji sadrze samo cifre 0 i 5, ciklus 312 imaju ako sadrze samo parne cifre a 1560 ako imaju i neparne.
Ako je A1 pocetni broj i njegove cifre a1,a2,a3 i a4 onda je
An = F(n,A1) = F1(n)a1+F2(n)a2+F3(n)a3+F4(n)a4 (sabiranje po modulu 10)
gde su Fi(n) funkcije koje preslikavaju N u {0..9}.
Koga ne mrzi neka proba da odredi te funkcije pa ce verovatno videti i zasto se kao ciklusi jaljaju bas ovi brojevi.Mozda ima i neki brzi nacin ali mi ne pada na pamet.
[ stalker @ 23.07.2004. 21:21 ] @
Pice, nista manje:) Bravo, nisam ni znao za 3. ciklus (ovaj sa samo 5), za njega imas jos jedno pice cim se vratim sa odmora