Možeš tako i ubrzat ali to više za vježbu.
Naravno da će ti proći i brute force, pa to je prvi zadatak da svak
ima nešto poslati i viditi jeli mu radi...

Učitavaj sa

Pa, nije 10 000 000 * 4, nego 1 000 000 * 4 bajta, sto je nesto manje od 4 MB, sto je verovatno prihvatljivo.

A sto se tice operacija u sekundi, zavisi sta smatras pod "operacijom". Obicno se to meri u mflops-ima (mega floating point operations per second), ali kad pricamo o operacijama u sekundi za ovakve "art of programming" probleme, ne bi trebalo racunati vise od 30 000 000 operacija u sekundi. Opet, sigurno ce x puta sporije raditi recimo deljenje ili mod, nego bitovsko and ili tako nesto, i sigurno ce mnooogo brze raditi operacije nad intovima nego nad floatima, ali ne treba probiti (po meni) taj plafon od 30M operacija. Cak, za floatove ja uzimam 10M. O 800M da ni ne govorimo ;)

A sto se feof tice, da li mislis da se to kod njih ucitava sa tastature? Naravno da ne, nego se preusmeri u fajl. Zato lepo ti stavi na pocetku 2 reda koda

pa dok radis kuci prvi red ti stoji iskomentarisan (i koristis feof normalno), a kad saljes iskomentarises drugi red, i opet ce feof kod njih lepo raditi.

Uzeo sam 10 000 000 *4 bajta zato što neki brojevi počnu prelaziti milijun(npr. 999 999 --> 2999998,a ne znam točnu granicu.No,priznajem,da,to baš i nije bilo najpametnije.

I kako mogu znati kako se zove file s ulaznim podacima?

Ma ne moras da pamtis za preko 1000000.... To ti je 2-3 koraka vise mozda za te brojeve koji budu presli 1000000... Bolje 2-3 operacije nego 10x vise memorije ;)

Pa ti i ne znas kako se zove file sa ulaznim podacima. Nego ti kad testiras kod sebe na kompu, koristi neke fileove, a za resenje koje saljes, samo ih preusmeri na stdin i stdout. Npr, pocetak koda koji koristis dok testiras kod sebe bi bio:

pa kad treba da ga posaljes:

Ovo je nevjerojatno!Sada program i radi kako treba,a na ACMovim stranicama mi stalno javlja Compile Error.Užas.

posalji kod

Pascal i Turbo Pascal se razlikuju u par detalja...

A sta je samo "pascal" ?

Na tim graderima uglavnom koriste free pascal.

Program je napisan u C-u.Prvo je kompajliran u VC6,radio,a zatim kompajliran u VS.Net 2003 i radi.Stavit ću source za koji dan,posudio sam disk nekome.
Dobro,skužio sam jednu malu manu kad je radio,tj. nije radio uopće za brojeve veće od 200 000.Mislim da odabir rekurzije nije bila greška(nema velik broj poziva),izgledala je otprilike

int cikl(int n){
if (n==1) return 1;
if (n%2) return (cikl(n*3+1)+1);
else return(cikl(n/2)+1);
}

I kao takva baš nije mogla prepuniti memorijski stog.
No dobro,kad uploadam source,vidjet ćete kako to izgleda.

Paaaa, ogranicenje za stek je dosta manje nego za heap, sto ce reci da za rekurziju verovatno nemas bas previse memorije :(

A stvarno mislim da bi bilo bolje da radis onako, da pamtis za svaki broj koliko ti koraka treba do 1....

Uostalom, pricacemo kad posaljes kod :)

Evo jednog interesantnog koda koji se lepo kompajlira i u Turbo Pascalu i u Standard Pascalu, samo što daje različite rezultate. Dva Pascala različito tretiraju ugnježdene komentare:



Ako svi koriste free pascal onda ga koristite i vi. Ako koristite različite kompajlere onda ćete stalno nailaziti na ovakve probleme.

Ovo nema toliko veze sa "umetnošću programiranja", više sa korišćenjem pravog alata. Neka je i tako, nema umetnika bez majstora

Evo i sourcea,komentirajte,je li samo katastrofa ili je totalni užas.

Hehe, pa sta moze biti tolika katastrofa u kodu od 15 reda ;)

Btw, i dalje tvrdim da je bolje da pamtis duzinu za sve brojeve....

A inace, ako vec radis ovako, ne vidim nista lose u kodu, osim sto (nema veze sa samim problemom) bi trebao da imas naviku da ti main vraca int, a ne void.

Poz

Pa koliko se često ispituje da'l je program završio svoj posao ili ne?
Modificirat ću kod,ovo je otprije par dana. Možda će ako napravim 100% promjenu prestati javljati Compile Error na ACM-u.

1.) Compile Error ti javlja zbog



to zamjeni sa



2.) Ako tako izmjeniš kod javljat će ti WA (Wrong Answer). Gledaj zašto:
input:


output mora biti:


Dakle, u zadatku nije navedeno da prvi broj može biti veći od drugog.

Ako to sve središ dobit ćeš Accepted! ;-)

Napravio sam kako si rekao,no još uvijek javlja isti tip greške.A ništa,vraćam se ja Pascalu,što će mi C,C++ i te gluposti :-)

Posalji kao C++, ne kao C (provereno radi, slao sam tvoj kod ;))

Oprosti što gnjavim,ali da'l bi mogao pojasniti zašto je to tako?

Evo i moj novi kod,koji,da,pogodili ste,ne radi(Wrong Answer).Odnosno radi za jednostavne slučajeve,a nije mi pao na pamet neki slučaj za koji ne radi.

Evo ti kod koji radi. Zapravo to je onaj tvoj kod , ali malo izmjenjeni:

Koji sam ja idiot!!!
Ovakvu glupost ne bih napravio ni u trećem razredu srednje.Zbilja sam zahrđao.
Hvala na uvidu u grešku

Program je školski primer zloupotrebe rekurzije. Jeste, rekurzivni programi izgledaju elegantno, ali retko kad rade dobro. Primer koji je okačen na sajt, ne radi za ceo interval [1,999999]. Evo iste te rekurzivne funkcije, napisane kako treba (nerekurzivno):

int cikl(int n) {
int x, result;

result=1;
for (x=n; x>1; ) {
if (x & 1) {
x+=(x>>1)+1;
result+=2; }
else {
x>>=1;
result++; }
if (x<0) {printf("Integer overflow error: i=%d, x=%d\n", n, x); x=1; result=-1;}
}
return result;
}

Za neke brojeve u datom opsegu DOLAZI do prekoračenja vrednosti koja može u int, kao na primer, za brojeve: 159487, 212649 (ukupno za 109 mogućih vrednosti).

Uzgred, izraze sam malo optimizovao, pa je uslov
if ( x % 2 )
postao
if ( x & 1 )

x=x/2
je postao
x>>=1

a
x = x*3 + 1
sam malo razbio. Naime, neprani brojevi su oblika n=2k+1. Kada to pomnožiš sa 3 pa dodaš jedan, dobiješ broj 6k+4. Ovaj broj je uvek paran. Kada ga podeliš sa 2 dobiješ 3k+2 koji se može napisati i kao 2k + 1 + k + 1. E, sada je 2k+1 početni broj n, k je pola od tog n (celobrojno pola). Dakle, neparni broj ti dodaje 2 koraka, a ako zanemariš međurezultat dobiješ
x=x+x/2+1 ili bez deljenja:
x+=(x>>1)+1
a rezultat (broj ciklusa uvećavaš za 2.

Pozdrav

Grozno! Cak i u ovakvim akademskim problemima ovim sitnim optimizacijama

se nista ne postize (uporedite vremena izvrsavanja), ali zato kod

postaje nerazumljiviji. U realnom programiranju situacija je jos

izrazenija. Highly unrecommended.

Slažem se sa primedbom u vezi optimizacije. Čisto sam je stavio da bih proverio da li će brže raditi i ubrzanje je skoro nikakvo. Ono što je u prvom, rekurzivnom, programu bilo loše je to što za neke brojeve (onih 109) program puca jer prepuni stek.

I dalje mislim da rekurzija treba da se primenjuje samo kada je neophodna, a kad god je primenjlivo, treba koristiti petlju. Jeste, rekurzivni programi deluju lepše, ali staviti vrednosti na stek 300 miliona puta, pa ih odatle skidati, sigurno nije zanemarljivo.

Lično, uvek bih radije stavio if ( x % 2 ) nego if ( x & 1 ) u program koji bih radio u komercijalen svrhe, a čak kada bih morao da koristim drugi izraz, obavezno bi išao komentar:
if ( x & 1 ) // da li je x neparan?

Još nešto, što se tiče vremena izvršavanja:

za optimizovan program i opseg 1,999999 je 1,7s
za program sa celobrojnim deljenjem i isti opseg je 2,8s

Program je radio na Windows XP mašini sa Pentium IV procesorom na 1,6 GHz, kompajliran bez optimizacija mingw kompajlerom.

A,znači,by default,trebao bih uzimati 10MFlops kad se pitam da'l je program dovoljno brz?

Paaa, u zivotu (kad pravis nesto ozbiljnije) uglavnom ti i nije bitno da li ce nesto da se odradi za jednu ili dve sekunde... Ali kad pricamo o ovakvim "takmicarskim" zadacima, ja sam uvek uzimao ~10M floating point, tj. ~30M operacija sa integerima, i uglavnom nisam imao problema sto se toga tice ;)