Pristup 3n+1 problemu

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:

Potpis

#include <D3adly.h>

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?