Wątek przeniesiony 2014-11-14 14:50 z Kosz przez Shalom.

Brak pomysłu na optymalizacje kodu

0

Cześć. Byłbym wdzięczny za jakieś sugestie jak usprawnić program/konstruktywną krytykę. Z góry dziękuje.

#include<iostream>
using namespace std;

int main()
{
unsigned int a,b,i,N,f;

a = b = 1;

//Program ma za zadanie sprawdzic czy wczytana liczba jest suma co najwyzej 4 liczb fibonacciego

cin>>N;
if(N==1 || N ==2) {cout<<"Tak"<<endl;return 0;}

unsigned int *tablica = new unsigned int [N];

for(int k =0;k<N;k++)
tablica[k] = 0;

for(i = 0;i<N  ;i++)
{
tablica[i] = a;
a=a+b;
if(tablica[i]>N){break;}
i++;
tablica[i] = b;
b=a+b;
}

for(int k =0;k<i;k++)
cout<<tablica[k]<<endl;

for(int k = i-1;k>=3;k--)
if(N == tablica[k] || N == tablica[k]+tablica[k-1] || N == tablica[k] + tablica[k-1] + tablica[k-2] || N ==  tablica[k] + tablica[k-1] + tablica[k-2] + tablica[k-3])
{
cout<<"Tak"<<endl;f = 1;break;
}

if(f!=1) { cout<<"Nie"<<endl;}

delete [] tablica;
return 0;}
1

1+3+8=12
Wpisuję 12 do tego bubla i ... ?

  1. Brak formatowania
  2. Zacznij używać funkcji
  3. Na tablice liczb Fibbonaczego przydziel stałą pamięć 50 elementów dalej to i tak będzie przepełnienie.
1
cout<<"Tak"<<endl;f = 1;break;

Każdą instrukcję zapisuj w osobnej linii. To plus brak wcięć sprawia, że ten kod jest bardzo nieczytelny

0

Wersja sformatowana (tylko):

#include<iostream>

using namespace std;

int main()
{
  unsigned int a,b,i,N,f;
  a = b = 1;
  //Program ma za zadanie sprawdzic czy wczytana liczba jest suma co najwyzej 4 liczb fibonacciego
  cin >> N;
  if(N==1 || N ==2) {
    cout<<"Tak"<<endl;
    return 0;
  }
  unsigned int *tablica = new unsigned int [N];
  for(int k =0;k<N;k++)
    tablica[k] = 0;

  for(i = 0;i<N ;i++) {
    tablica[i] = a;
    a=a+b;
    if(tablica[i]>N){
      break;
    }
    i++;
    tablica[i] = b;
    b=a+b;
  }

  for(int k =0;k<i;k++)
    cout << tablica[k] << endl;

  for(int k = i-1; k>=3; k--)
    if(N == tablica[k] || N == tablica[k]+tablica[k-1] || N == tablica[k] + tablica[k-1] + tablica[k-2] || N == tablica[k] + tablica[k-1] + tablica[k-2] + tablica[k-3])
    {
      cout<<"Tak"<<endl;
      f = 1;
      break;
    }

  if(f!=1) {
    cout<<"Nie"<<endl;
  }

  delete [] tablica;

  return 0;
}
0

Pętla

for(int k =0;k<N;k++)

wykona się tyle samo razy co pętla for(i = 0;i<N ;i++)


.

Można je złączyć.
0

Ja bym podszedł do zadania bardziej ambitnie. Najpierw wykonałbym rozkład liczby na składniki (max 4) a następnie sprawdziłbym czy każda z nich należy do ciągu fibonacciego.
EDIT:
Oczywiście sprawdzić trza każdy możliwy rozkład

Tu jest gotowiec jak sprawdzić czy liczba należy do ciągu fibonacciego
http://www.geeksforgeeks.org/check-number-fibonacci-number/
a tutaj w rozwiązaniu zadania 6 jest gotowiec jak zrobić rozkład liczby (niestety w pascalu)
http://wazniak.mimuw.edu.pl/i[...]wania/Rekursja/%C4%86wiczenia

Nie analizowałem dokładnie tych rozwiązań, ale zakładam że są prawidłowe.

0

Przecież to zwykły bruteforce wyrabia się w rozsądnym czasie.
To cały kod:

#include<iostream>
using namespace std;

int main()
  {
   const int MaxFib=94;
   unsigned long long fib[MaxFib]={0,1,1};
   for(int i=3;i<MaxFib;++i) fib[i]=fib[i-1]+fib[i-2];
   for(unsigned long long v=0;(cin>>v)&&(v);)
     {
      unsigned long long s=0;
      int idx[]={-1,-1,-1,-1};
      for(int p=0;(s!=v)&&(p>=0);)
        {         
         for(p=4;(--p>=0)&&((++idx[p]>MaxFib)||(fib[idx[p]]>v));) idx[p]=0;
         if(p>=0) for(s=p=0;p<4;++p) if(idx[p]>=0) s+=fib[idx[p]];
        }
if(s==v) for(int p=0;p<4;++p) if(idx[p]>0) cout<<fib[idx[p]]<<' '; // To tylko pokazuj sumę można wywalić
      cout<<(s!=v?"NIE":"TAK")<<endl; 
     }
   return 0;   
  }

Owszem można trochę przyspieszyć dodając heurystykę

1

Zamiast dawać rozwiązanie, podpowiem:

Wpisz do kodu na twardo wszystkie możliwe do przetwarzania wyrazy ciągu Fibonacciego.
Następnie napisz sobie test rekurencyjny, w którym pierwszym parametrem będzie testowana liczba, a drugim ile liczb Fibonacciego może występować w tej sumie.
Zacznij tak:

#include <iostream>
#include <algorithm>

using namespace std;

const unsigned int fib[] = {
       /*0,          1, */       1,          2,          3, 
         5,          8,         13,         21,         34, 
        55,         89,        144,        233,        377, 
       610,        987,       1597,       2584,       4181, 
      6765,      10946,      17711,      28657,      46368, 
     75025,     121393,     196418,     317811,     514229, 
    832040,    1346269,    2178309,    3524578,    5702887, 
   9227465,   14930352,   24157817,   39088169,   63245986, 
 102334155,  165580141,  267914296,  433494437,  701408733, 
1134903170, 1836311903, 2971215073
};
size_t fibCount = sizeof(fib)/sizeof(fib[0]);

bool test(unsigned int x, int maxCount=4) {
      if (x==0) {
          return true;
      }
      if (maxCount==0) {
          return false;
      }
      // tu wciąłem jedynie 8 linijek
      ...
}

int main() {
    unsigned int x;
    while(cin>>x) {
        cout << (test(x)?"TAK":"NIE") << endl;
    }
    return 0;
}

Brakująca część jest naprawdę prosta do zrobienia. Dla optymalizacji można zastosować binary search.

1 użytkowników online, w tym zalogowanych: 0, gości: 1, botów: 0