Here is the whole program for the removal of Fibonacci numbers, but a problem has arisen that the negative elements are also being output in the array, but I don’t get it .....

#include <vcl.h> #include <iostream.h> #include <stdlib.h> #include <conio.h> char* Rus(const char* text); int fibonacci (int, int [100]); int main(){ srand(time(NULL)); int a[100]; int n,i,j; int fibonacci (int, int [100]); cout <<Rus("Введите количество элементов: ") << endl; cin>>n; cout << Rus("Исходный массив: ")<< endl; for (i=0;i<n;i++) { a[i]=rand()%30+5; rand()%100-rand()%100; cout << a[i]<<" "; } fibonacci (n, a); getch(); } int fibonacci (int n, int a[100]) { int q[100]; int max, g, b,i,j,c; max=a[0]; for (i=1;i<n;i++) { if (max<a[i]) max=a[i]; } g=0; b=1; for (i=0;b<=max;i++) { c=g+b; g=b; b=c; q[i]=b; } cout << endl; cout << endl; cout << Rus("Ряд Фибоначчи: ")<< endl; for (j=0;j<i;j++) cout<< q[j] << " "; for (i=0;i<max;i++) for (j=0;j<n;j++) if (q[i]==a[j]) { for (b=j;b<n-1;b++) a[b]=a[b+1]; n=n-1; j--; } cout << endl; cout << Rus("Новый массив: ")<< endl; for (i=0;i<n;i++) cout<<a[i]<<" "; return 0; } char bufRus[256]; char* Rus(const char* text) { CharToOem(text,bufRus); return bufRus; }
  • What do you mean by removing a number from an array? Replacing it with (say 0) or shifting the numbers to the right of this one position to the left? And with the latest what to do? Array like in this program or dynamic (from the heap)? - avp
  • I mean the shift of the numbers to the right of the given one position to the left. Size of the array should be reduced after deletion (--n) Implemented as pseudo-dynamic arrays, their dimensions should be transferred as function parameters. - Neon
  • @Neon, you are halfway to the solution. See, the program calculates the Fibonacci numbers you have. It remains to convert it to a function (say, int isFibo (int num)), which checks its argument if it is a Fibonacci number. It remains to write the function void shiftarr (int a [], int asize, int from) and a trivial loop in which you iterate over the array elements, for each you call isFibo () and if you need shiftarr (), remembering to change asize, which is the loop boundary. IMHO two or three hours later you will be able to plyusovat (according to the results of the program you wrote ). - avp
  • pliz explain what void shiftarr is (int a [], int asize, int from)? I have not met this yet ... while the newcomer is Neon
  • This is the function you have to write. It should move the elements in an array asize 1 by size to the left, starting with the from index. Those. a [from] = a [from + 1], etc. Naturally, the last one being shifted is a [asize-1]. It is easy to figure out that you need to call it for those indices where the Fibonacci numbers lie. Is the isFibo () function already written? - avp

2 answers 2

Another option

 int isFibo (int k) { if (k < 0) return 0; if (k == 0) return 1; int f0 = 1, f = 1, x; while (f > 0 && f < k) { // f > 0 для проверки переполнения x = f+f0; f0 = f; f = x; } return f == k; }

I wonder in practice which one is faster?

    Well, for example. Initially, the * fib vector must contain at least two values: 0 and 1.

     int isFibo( vector<int> *fib, int k) { if(fib->back() < k) { while(fib->back() < k) { int n = fib->size(); fib->push_back((*fib)[n-1] + (*fib)[n-2]); } return k==fib->back(); } else { int i1=0, i2=fib->size() - 1; if((*fib)[i1] == k || (*fib)[i2] == k) return 1; while(i2 > i1+1) { int i=(i1+i2)/2; if((*fib)[i] == k) return 1; else if ((*fib)[i] < k) i1=i; else i2=i; } return 0; } }