fibonacijev niz

Teme vezane za console/GUI programiranje u C/C++ jeziku
16 post(ov)a • Stranica: 1/2.1, 2

fibonacijev niz

PostPostao/la nemesis » 30 srp 2013, 19:54

jel zna neko uraditi ovaj zadatak?

Fibonačijev niz definisan je na sljedeći način:

f1=1,f2=2
fn=fn-1+fn-2, n=3,4,5...

Napisati program u programskom jeziku C koji učitava
dva prirodna broja A i B (A<B), a zatim ispisuje sve
Fibonačijeve brojeve iz intervala <A,B> te ukupan broj
Fibonačijevih brojeva u tom intervalu.

treba da se uradi skroz pocetnicki, bez funkcija, kreiranja nizova itd, samo uslovi i petlje

Re: fibonacijev niz

PostPostao/la Armin » 30 srp 2013, 22:16

Pokušaj s ovim kodom. Ako ti nešto nije jasno pitaj me.

c code
#include<stdio.h>

void main()
{
int a,b,c;
int fib[100];
int poc,end;
poc = 0;
//ucitavanje a i b
printf("Unesite a: ");
scanf("%d",&a);
printf("Unesite b: ");
scanf("%d",&b);

//ako je a > b, obrni a i b
if(a>b)
{
c = a;
a = b;
b = c;
}

//kreiranje niza

int i = 2;
fib[0] = 1;
fib[1] = 1;
while(1)
{
if(poc==0)if((fib[i-1] + fib[i-2]) > a)poc = i;
if((fib[i-1] + fib[i-2]) > b)
{
end = i;
break;
}
fib[i] = fib[i-1] + fib[i-2];
i++;
}

// ispis
for(i=poc;i<end;i++)
{
printf("%d ",fib[i]);
}

printf("\n");
}
"Ne žalim što su drugi pokrali moje ideje. Žalim što nemaju svoje"
Nikola Tesla

Re: fibonacijev niz

PostPostao/la tomRiddle » 30 srp 2013, 22:27

nemesis je napisao/la:jel zna neko uraditi ovaj zadatak?

Fibonačijev niz definisan je na sljedeći način:

f1=1,f2=2
fn=fn-1+fn-2, n=3,4,5...

Napisati program u programskom jeziku C koji učitava
dva prirodna broja A i B (A<B), a zatim ispisuje sve
Fibonačijeve brojeve iz intervala <A,B> te ukupan broj
Fibonačijevih brojeva u tom intervalu.

treba da se uradi skroz pocetnicki, bez funkcija, kreiranja nizova itd, samo uslovi i petlje


Evo jedno rješenje od mene... Primjenio sam, ipak, osnovnu definiciju Fibonacijevog niza (f1=0, f2=1). Namjerno sam postavio dvije while petlje, a može se riješiti i sa jednom while petljom i if naredbom unutar nje, koja bi provjeravala da li je član niza unutar intervala ili ne. Za dvije while petlje sam se odlučio, jer je algoritam "malčice" brži od prethodnog (nema if uslova u svakoj iteraciji).

Evo i koda:

c code
#include<stdio.h>

int main()
{
int A, B;
int a=0, b=1; //Dva uzastopna člana Fibonačijevog niza

printf("Unesite granice intervala:\n");
scanf("%d %d", &A, &B);

if(A>=B || A<=0 || B<=0){
printf("Greska! Interval nije ispravno unesen.\n");
return 1;
}

while(a+b<=A) //Potrebno je izračunati članove niza, koji ne pripadaju intervalu
{
int c=a+b;
a=b;
b=c;
}

int n=0; //Broj članova niza koji pripadaju intervalu

while(a+b<B)
{
n++;
printf("\n%d) %d",n, a+b);

int c=a+b;
a=b;
b=c;
}

printf("\nBroj clanova niza koji pripadaju intervalu (%d,%d) je %d.\n", A, B, n);

return 0;
}


Svakako bih želio vidjeti još rješenja...

Pozdrav

Re: fibonacijev niz

PostPostao/la Armin » 30 srp 2013, 22:37

Nisam vidio da treba i ukupan broj članova. Mada mislim da to nije problem dodat na moj kod :)

Sviđa mi se pristup, tomRiddle. Pregledniji ti je kod dosta.
"Ne žalim što su drugi pokrali moje ideje. Žalim što nemaju svoje"
Nikola Tesla

Re: fibonacijev niz

PostPostao/la HepeK » 30 srp 2013, 22:55

Sviđa mi se način, nije brzi puno jer i ti imaš uslove u petljama a to je isto kao da su unutar tijela petlje ifovi.

A Armin baš nje štedio na ifovima :P
"Ko nema u glavi ima na internetu"
Što čujem - poštujem, dok ne vidim - ne vjerujem.

Re: fibonacijev niz

PostPostao/la tomRiddle » 30 srp 2013, 23:16

HepeK je napisao/la:Sviđa mi se način, nije brzi puno jer i ti imaš uslove u petljama a to je isto kao da su unutar tijela petlje ifovi.

A Armin baš nje štedio na ifovima :P


Ja razmišljam ovako: Potrebno je izračunati n članova fibonačijevog niza (neka je fn+1>B). Sa jednom while petljom imamo n puta provjeru uslova same while petlje i potrebu za if naredbom, jer trebamo brojati, a to je još n uslova. Dakle 2*n uslova (usporedbi).

Sa dvije petlje, nema if-a. Međutim, prva petlja, a samim tim i uslov iz prve petlje, će se izvršiti samo i puta (ako je fi+1>A), a uslov iz druge petlje j puta (neka je fi+j+1>B). Dakle, i + j uslova (usporedbi). Jasno je da vrijedi i + j = n, pa je to n uslova. Vođen ovom idejom, rekao sam da je algoritamski gledano, program brži...

Pozdrav

Re: fibonacijev niz

PostPostao/la HepeK » 31 srp 2013, 00:42

Pa jeste brži, ne osporavam :)

Samo sam doskočio malo sa ifovima :)

c code
#include<time.h>
#include<stdio.h>
main(){
clock_t start=clock();
/* Ovdje stavi kod */
clock_t kraj=clock();
double vrijeme=(double)(kraj-start) * 1000.0 / CLOCKS_PER_SEC;
printf("Vrijeme u ms je %f",vrijeme);
}


Ajde ako ti nije tesko stavi kod izmedju starta i kraja da izmjerimo. :)

(Ja nemam instaliran codeblocks ni visual studio)
"Ko nema u glavi ima na internetu"
Što čujem - poštujem, dok ne vidim - ne vjerujem.

Re: fibonacijev niz

PostPostao/la nemesis » 31 srp 2013, 09:00

kolege, sta mislite o mom kodu, ovo sam sinoc napravio dok sam vam pisao da mi treba pomoc, mislim da sam uspio napokon, a sad vidim da ste se i vi potrudili maksimalno, svaka cast :)

c code
#include <stdio.h>
#include <stdlib.h>
main()
{
int A,B,n,f1,f2,f3,i=0;
printf("unesi interval od A do B: ");
scanf("%d %d",&A,&B);
f1=1;
f2=1;
if (A<2 || B<2)
printf("interval mora biti veci ili jednak 2");
for(n=A;n<B;n++){

f3=f1+f2;
if(A<f3 && B>f3){


printf("%d\n",f3);
i++;}

f1=f2;
f2=f3;}

printf("%d",i);
system("pause");
}

Re: fibonacijev niz

PostPostao/la nemesis » 31 srp 2013, 09:01

Armin je napisao/la:Pokušaj s ovim kodom. Ako ti nešto nije jasno pitaj me.

c code
#include<stdio.h>

void main()
{
int a,b,c;
int fib[100];
int poc,end;
poc = 0;
//ucitavanje a i b
printf("Unesite a: ");
scanf("%d",&a);
printf("Unesite b: ");
scanf("%d",&b);

//ako je a > b, obrni a i b
if(a>b)
{
c = a;
a = b;
b = c;
}

//kreiranje niza

int i = 2;
fib[0] = 1;
fib[1] = 1;
while(1)
{
if(poc==0)if((fib[i-1] + fib[i-2]) > a)poc = i;
if((fib[i-1] + fib[i-2]) > b)
{
end = i;
break;
}
fib[i] = fib[i-1] + fib[i-2];
i++;
}

// ispis
for(i=poc;i<end;i++)
{
printf("%d ",fib[i]);
}

printf("\n");
}


zabranjena je upotreba niza

Re: fibonacijev niz

PostPostao/la tomRiddle » 31 srp 2013, 11:23

HepeK je napisao/la:Pa jeste brži, ne osporavam :)

Samo sam doskočio malo sa ifovima :)

c code
#include<time.h>
#include<stdio.h>
main(){
clock_t start=clock();
/* Ovdje stavi kod */
clock_t kraj=clock();
double vrijeme=(double)(kraj-start) * 1000.0 / CLOCKS_PER_SEC;
printf("Vrijeme u ms je %f",vrijeme);
}


Ajde ako ti nije tesko stavi kod izmedju starta i kraja da izmjerimo. :)

(Ja nemam instaliran codeblocks ni visual studio)


S obzirom da koristim Linux na raspolaganju imam komandu time, koja mi vraća vrijeme izvršenja nekog programa. Tako da sam najprije toj komandi podvrgao osnovna dva koda o kojima smo diskutovali, u oba slučaja je bilo vrijeme izvršenja 0.002 s, zbog nepreciznosti mjerenja, a i operacije koje smo koristili su same po sebi, izuzetno brze...

Kako bih doveo do neke "vidljive" razlike, prepravio sam malo kodove. Naime, dodao sam dvije for petlje, tako da se naš kod obavlja 100 000 000 puta, kako bih došao do neke vremenske razlike. Ovo su kodovi:

c code
#include<stdio.h> 

main(){

int A=1, B=30000;
int a=0, b=1; //Dva uzastopna člana Fibonačijevog niza

// printf("Unesite granice intervala:\n");
// scanf("%d %d", &A, &B);

if(A>=B || A<=0 || B<=0){
printf("Greska! Interval nije ispravno unesen.\n");
return 1;
}

int i;
int j;

for(j=0; j<10000; j++)
{

for(i=0; i<10000; i++)
{
a=0;
b=1;

while(a+b<=A) //Potrebno je izračunati članove niza, koji ne pripadaju intervalu
{
int c=a+b;
a=b;
b=c;
}

int n=0; //Broj članova niza koji pripadaju intervalu

while(a+b<B)
{
n++;
// printf("\n%d) %d",n, a+b);

int c=a+b;
a=b;
b=c;
}

// printf("\nBroj clanova niza koji pripadaju intervalu (%d,%d) je %d.\n", A, B, n);
}

}
return 0;
}


c code
#include<stdio.h> 

main(){

int A=1, B=30000;
int a=0, b=1; //Dva uzastopna člana Fibonačijevog niza

// printf("Unesite granice intervala:\n");
// scanf("%d %d", &A, &B);

if(A>=B || A<=0 || B<=0){
printf("Greska! Interval nije ispravno unesen.\n");
return 1;
}

int n=0;
int i;
int j;

for(j=0; j<10000; j++)
{

for(i=0; i<10000; i++)
{
a=0;
b=1;

while(a+b<B)
{
int c=a+b;
a=b;
b=c;

if(c>A)
n++;
// printf("\n%d) %d", n, c);
}

// printf("\nBroj clanova niza koji pripadaju intervalu (%d,%d) je %d.\n", A, B, n);

}

}

return 0;
}


Rezultati dobiveni komandom time su:
./a.out 11.81s user 0.06s system 99% cpu 11.881 total
./b.out 13.70s user 0.06s system 99% cpu 13.771 total

Zaključak:
Program sa dvije while petlje je brži. Ali to ne znači da ga trebate koristiti :-) . U pisanju koda nije važna samo brzina već i preglednost, kao i mnoge druge stvari. Mnogo je osobina programskog koda koje su važnije od brzine. Ovakva testiranja su pogodna samo za provjeru brzine algoritama. Ovi programi nikada neće biti korišteni na 100 000 000 brojeva Fibonacijevog niza, a sa nekom "normalnom" količinom podataka, programi su iste brzine...

Dakle, kod sa jednom while petljom i jednim if-om je pravo riješenje pri ovom algoritmu... :-)

Pozdrav


16 post(ov)a • Stranica: 1/2.1, 2

Na mreži

Trenutno korisnika/ca: / i 1 gost.