[es] - Pristup 3n+1 problemu

Humanoid
Hrvatska

Član broj: 10689
Poruke: 63
*.cmu.carnet.hr.

ICQ: 170788654

Profil

Re: Pristup 3n+1 problemu

^{22.05.2005. u 20:23 - pre 230 meseci}

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

Odgovor na temu

Humanoid
Hrvatska

Član broj: 10689
Poruke: 63
*.cmu.carnet.hr.

ICQ: 170788654

Profil

Re: Pristup 3n+1 problemu

^{22.05.2005. u 21:58 - pre 230 meseci}

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.

Prikačeni fajlovi

100.c - 0.58k

Odgovor na temu

D3adly

Član broj: 43272
Poruke: 35
*.net.t-com.hr.

ICQ: 281458481

Profil

Re: Pristup 3n+1 problemu

^{23.05.2005. u 13:54 - pre 230 meseci}

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

Code:

#include <stdio.h>

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

int  main(void){

     int a,b,max,i,tmp,buff,stanje;

     while (scanf ("%d %d",&a,&b) != EOF){
       max=0;
       stanje=0;

     if (a>b) {
       buff=a;
       a=b;
       b=buff;
       stanje=10;
       }

         for (i=a;i<=b;i++){
         tmp=cikl(i);
         if (tmp>max) max = tmp;
         }

         if (stanje==10){
         buff=a;
         a=b;
         b=buff;
         }

        printf("%d %d %d\n",a,b,max);
     }

return 0;
}

#include <D3adly.h>

Odgovor na temu

Humanoid
Hrvatska

Član broj: 10689
Poruke: 63
*.cmu.carnet.hr.

ICQ: 170788654

Profil

Re: Pristup 3n+1 problemu

^{23.05.2005. u 16:31 - pre 230 meseci}

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

Odgovor na temu

djoka_l
Beograd

Član broj: 56075
Poruke: 3453

Jabber: djoka_l

+1462 Profil

Re: Pristup 3n+1 problemu

^{24.05.2005. u 16:20 - pre 230 meseci}

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

Odgovor na temu

Mihajlo Cvetanović
Beograd

Moderator
Član broj: 37636
Poruke: 1249

+96 Profil

Re: Pristup 3n+1 problemu

^{25.05.2005. u 09:24 - pre 230 meseci}

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.

Odgovor na temu

djoka_l
Beograd

Član broj: 56075
Poruke: 3453

Jabber: djoka_l

+1462 Profil

Re: Pristup 3n+1 problemu

^{25.05.2005. u 12:10 - pre 230 meseci}

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?

Odgovor na temu

djoka_l
Beograd

Član broj: 56075
Poruke: 3453

Jabber: djoka_l

+1462 Profil

Re: Pristup 3n+1 problemu

^{25.05.2005. u 13:28 - pre 230 meseci}

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.

Prikačeni fajlovi

es3n.cpp - 1.35k

Odgovor na temu

Humanoid
Hrvatska

Član broj: 10689
Poruke: 63
*.cmu.carnet.hr.

ICQ: 170788654

Profil

Re: Pristup 3n+1 problemu

^{26.05.2005. u 21:21 - pre 230 meseci}

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

Odgovor na temu

Srđan Krstić
Srđan Krstić
Princeton, NJ

Član broj: 7526
Poruke: 416
*.bankerinter.net.

Jabber: srkiboy@elitesecurity.org
ICQ: 193836365
Sajt: www.princeton.edu/~skrsti..

Profil

Re: Pristup 3n+1 problemu

^{27.05.2005. u 02:31 - pre 230 meseci}

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 ;)

I HAD A NIGHTMARE
IT ALL STARTED NORMAL
10101010
10110011
THEN ALL OF A SUDDEN
1100102
GAAAAH
_____________________________
www.princeton.edu/~skrstic
www.niwifi.co.sr

Odgovor na temu