[tema] elemente termeni Fibonnaci

Scrieți o funcție care pentru un vector de lungime x verifică dacă
elementele din vector sunt primele x numere din șirul lui Fibonnaci în ordinea
apariției lor in șir.
Ex: Pentru [0,1,1,2,3,5] funcția va returna true;
Pentru [0,1,1,3,2,4] si [0,1,1,2,4] funcția va returna false.

Am scris urmatorul cod:

bool areOrderedFibonnaci(vector vec)
{ unsigned int i=3;
aux=vec.values[0];
aux2=vec.values[1];
if(aux!=0 || aux2!=1)
return 0;
while(nr!=x)
{
aux3=aux2+aux;
aux=aux2;
aux2=aux3;
if(aux3!=vec.values[i])
return 0;
i++;
x--;
}
return 1;
}

dar in main nu stiu cum ar trebui sa citesc vectorul...... ma puteti ajuta, va rog?

serios ? tu ai scris codul ala ?

 yonut_a, on 24 octombrie 2016 - 20:26, said:

da... sa inteleg ca e gresit?

Edited by hope_6, 24 October 2016 - 20:28.

pai zi ne si noua ce inseamna vector vec
cine sunt  aux, aux2 , aux3, nr, x ?

 yonut_a, on 24 octombrie 2016 - 20:28, said:

am uitat.... era data structura urmatoare intr o biblioteca k1.h
#define MAX_ARRAY_LENGTH 100
struct vector
{
unsigned int length;
int values[MAX_ARRAY_LENGTH];
};

aux, aux2 si aux3 sunt termenii fibonacci pe care i tot creez si verific daca sunt in vectorul dat

Edited by hope_6, 24 October 2016 - 20:33.

Ia mai arunca un ochi peste variabile si declararea lor

http://www.cplusplus...rial/variables/

si peste array uri

http://www.cplusplus...utorial/arrays/

yonute, daca ai ceva de spus de ce nu spui?
de tii crucis sa  faci decat pe inteligentu'?

Edited by Daniel2222, 24 October 2016 - 20:52.

 yonut_a, on 24 octombrie 2016 - 20:42, said:

nu puteti fi mai explicit, va rog?

Daniel ma bucur ca l ai lamurit tu. Eu i am pus niste intrebari la obiect. Daca vrea sa invete va incerca sa isi raspunda la ele.

Hope_6 invata sa declari variabile in primul rand

 yonut_a, on 24 octombrie 2016 - 21:13, said:

pai, tocmai, speram sa ma puteti ajuta in acest sens

pai ti am dat niste tutoriale foarte valide ....
declararea variabilelor si tipurile de date e primul pas ... apoi usor usor inveti si functiile si lucrurl cu vectori si apoi o sa le pui cap la cap si o sa iti iasa si problemele

PS: Si Daniel2222

 Daniel2222, on 24 octombrie 2016 - 20:51, said:

Edited by yonut_a, 24 October 2016 - 21:54.

morțiș nu crucis

si ce returneaza pentru [0,1,1,2,5,3] ?

 hope_6, on 24 octombrie 2016 - 20:19, said:

nici noi nu stim, citesti cum vrei, de la tastatura sau din fisier

 hope_6, on 24 octombrie 2016 - 20:27, said:

e gresit sa incerci sa ne minti

Eu as incerca astfel:

#include "stdafx.h"
#include <iostream>
#include <vector>
using namespace std;
int numar;
vector<int> vectorulCitit;
int pozitie = 0;
int calculat;

void citesteNr() {
cout << "Introduceti numerele pentru evaluare !  " << endl<<"Pentru iesire tastati un numar negativ"<<endl<<"Ex:0 1 1 2 3 5 -1"<<endl;
while ((cin >> numar)&&numar>=0) { vectorulCitit.push_back(numar);
}
}
int calculeazaF(int poz){
int nr = vectorulCitit[poz];

if (poz == 0) {  return 0; }
if (poz ==1||poz==2) {return 1; }
if (poz > 2) {
  calculat =calculeazaF(poz-1) + calculeazaF(poz - 2);
 
  return calculat;
}
}
void verificaVector() {
int marime = vectorulCitit.size()-1;
int numarPozitie=0;
while (marime>=numarPozitie)
{
  if ((marime == numarPozitie) && (vectorulCitit[numarPozitie] == calculeazaF(numarPozitie))) {
   cout << "Sir corect"<<endl;
  }
  if (vectorulCitit[numarPozitie] != calculeazaF(numarPozitie)) {
   cout << "Sir Gresit"<<endl;
   break;
  };
 
  numarPozitie++;
}

}
int main()
{
citesteNr();
verificaVector();

system("pause");
	return 0;
}

Edited by Daniel2222, 25 October 2016 - 22:14.

Pentru fiecare element din vector o iei de la capat cu functia calculeazaF.

Da, stiu asta.
As fi putut numara elementele din vectorul introdus si sa creez un alt vector sau o matrice cu acel numar de elemente si sa compar sirurile. In acest fel se executa o de mult mai putine ori.
Il modific cand am timp...

 hope_6, on 24 octombrie 2016 - 20:19, said:

Adica doresti practic sa compari doi vectori: cel citit si cel al numerelor lui Fibonacci. Presupunand ca ai un vector cu numere lui Fibonacci, compari x[i] cu y[i] pana nu mai sunt egale sau ajungi la final.

Dar poate nu vrei sa generezi 100 de elemente ale sirului lui Fibonacci ca apoi sa vezi ca defapt prima valoare din vectorul de verificat e deja diferita => munca in zadar. Asadar folosesti un generator

template <typename TIterator1, typename TIterator2>
bool comparaSecvente(TIterator1 begin1, TIterator1 end1, TIterator2 begin2, TIterator2 end2)
{
   do
   {
	  if ((begin1 == end1) || (begin2 == end2))
	  {
		 //comparam doar elementele pe lungimea comuna
		 return true;
	  }
	  if (*begin1 != *begin2)
	  {
		 //valorile curente nu sunt egale 
		 return false;
	  }
	  ++begin1;
	  ++begin2;
   } while (true);
}

int main()
{
   int deTestat[] = { 0, 1, 1, 2, 3, 5 };

   std::cout << comparaSecvente(std::begin(deTestat), std::end(deTestat), FibonacciGenerator(), FibonacciGenerator::end());
}

Se intelege intentia codului dintr-o privire? Se intelege, ca-s doar doua randuri.



Hai sa si comparam complexitatea solutiei curente cu cea a celei prezentata anterior in topic:

Prima solutie e usor mai rapida pentru primii termeni ai sirului (n-au fost aplicate optimizari la compilare), iar apoi o ia razna, crescand exponential.
A doua solutie creste usor, liniar cu numarul de elemente din sir. La compararea a 15 elemente din sir, prima varianta executa deja de 24x mai multe instructiuni fata de a 2-a.

 Untitled.png   34.34K   14 downloads

De notat la solutia lui dani.user e ca vorbeste despre complexitatea algoritmica amortizata: daca ultimul numar e cel deviant, tot aceeasi complexitate o va avea ca atunci cand generezi toate numerele apriori.

INSA solutia lui dani.user e optima la consumul de memorie, deoarece consuma constant O(1).

Acesta e in opinia mea adevarajul avantaj, la care se adauga si eleganta in modularizare a codului: daca apelantul vrea sa memoizeze sirul generat, o poate face, sau nu - ceea ce face algoritmul reutilizabil.

Aceasta ar trebui sa fie mult mai rapida decat prima mea solutie.

#include "stdafx.h"
#include <iostream>
#include <vector>
using namespace std;
int numar;
vector<int> vectorulCitit;
vector<int> vectorulCalculat;
int pozitie = 0;
int calculat;

void citesteNr() {
cout << "Introduceti numerele pentru evaluare !  " << endl<<"Pentru iesire tastati un numar negativ"<<endl<<"Ex:0 1 1 2 3 5 -1"<<endl;
while ((cin >> numar)&&numar>=0) { vectorulCitit.push_back(numar);
}
}
/*
int calculeazaF(int poz){
int nr = vectorulCitit[poz];

if (poz == 0) {  return 0; }
if (poz ==1||poz==2) {return 1; }
if (poz > 2) {
  calculat =calculeazaF(poz-1) + calculeazaF(poz - 2);
 
  return calculat;
}
}
*/
void genereazaV() {
int marimeVectorCitit = vectorulCitit.size()-1;
int pozitie = 0;
int calculat =0;
while (pozitie<=marimeVectorCitit) {

  if (pozitie == 0) { vectorulCalculat.push_back(0); }
  if (pozitie == 1 || pozitie == 2) { vectorulCalculat.push_back(1); }
  if (pozitie > 2) { calculat = vectorulCalculat[pozitie - 1] + vectorulCalculat[pozitie - 2]; vectorulCalculat.push_back(calculat); }
  pozitie++;
}
}
void verificaVector() {
if (equal(vectorulCitit.begin(),vectorulCitit.end(),vectorulCalculat.begin()))
{
  cout << "sir corect"<<endl;
 
}
else
{
  cout << "sir gresit " << endl;
}

}
int main()
{
citesteNr();
genereazaV();
verificaVector();
system("pause");
	return 0;
}