Fibonačijev podskup

Autor zadatka: Rade Radišić <radisic.rade@uns.ac.rs>

Dat je niz celobrojnih vrednosti od maksimalno 30 elemenata. Uneti n vrednosti i ispitati da li uneti niz predstavlja podskup Fibonačijevog niza na sledeći način:

  • Proveriti da li je prvi član niza pripada Fibonačijevom nizu

  • Ako pripada, proveriti da li ostatak niza prati vrednosti u odnosu na formulu Fibonačijevog niza

Prva dva člana Fibonačijevog niza imaju vrednost 1, a svaki sledeći je zbir prethodna dva člana.

Ispisati poruku da li je niz podskup Fibonačijevog niza i same vrednosti niza ukoliko jeste.

Matematička formula Fibonačijevog niza je:

\[F(n) = 1, n = 1 \wedge n = 2\]
\[F(n) = F_{n-1} + F_{n-2}, n > 2\]

Napomene

  • Nije dozvoljeno koristiti globalne promenljive

  • Računati da je uneti niz uvek u rastućem redosledu, tako da nije potrebno dodatno sortirati uneti niz!

Primer rada programa:

Unesite velicinu niza: 5
niz[0]: 1
niz[1]: 1
niz[2]: 2
niz[3]: 3
niz[4]: 5

Zadati niz je podskup Fibonacijevog niza: 1, 1, 2, 3, 5

Primer rada programa u slučaju kada niz nije podskup Fibonačijevog niza:

Unesite velicinu niza: 5
niz[0]: 1
niz[1]: 2
niz[2]: 3
niz[3]: 4
niz[4]: 5

Zadati niz nije podskup Fibonacijevog niza!

Primer rada programa u slučaju kada prvi element pripada Fibonačijevom nizu, a ostali ne:

Unesite velicinu niza: 5
niz[0]: 5
niz[1]: 7
niz[2]: 12
niz[3]: 19
niz[4]: 31

Zadati niz nije podskup Fibonacijevog niza!

Primer rada programa u slučaju niza od 1 elementa, koji pripada Fibonačijevom nizu:

Unesite velicinu niza: 1
niz[0]: 8

Zadati niz je podskup Fibonacijevog niza: 8

Primer rada programa u slučaju niza od 2 elementa, koji pripadaju Fibonačijevom nizu:

Unesite velicinu niza: 2
niz[0]: 3
niz[1]: 5

Zadati niz je podskup Fibonacijevog niza: 3, 5

Primer rešenja

 1#include <stdio.h>
 2
 3#define MAX_SIZE 30
 4
 5int main()
 6{
 7    int niz[MAX_SIZE], i, n;
 8
 9    do
10    {
11        printf("Unesite velicinu niza: ");
12        scanf("%d", &n);
13    } while (n <= 0 || n > MAX_SIZE);
14    
15    for(i = 0;i < n;i++)
16    {
17        printf("niz[%d]: ", i);
18        scanf("%d", &niz[i]);
19    }
20
21    int tekuci = 1, sledeci = 1, tmp;
22
23    while(tekuci < niz[0])
24    {
25        tmp = tekuci;
26        tekuci = sledeci;
27        sledeci += tmp;
28    }
29
30    int je_fibonacijev = 1;
31
32    if(tekuci > niz[0])
33    {
34        je_fibonacijev = 0;
35    }
36    else
37    {
38        if(n >= 2 && niz[1] != sledeci)
39        {
40            je_fibonacijev = 0;
41        }
42        else
43        {
44            for(i = 0;i < n - 2;i++)
45            {
46                if(niz[i + 2] != niz[i] + niz[i + 1])
47                {
48                    je_fibonacijev = 0;
49                    break;
50                }
51            }
52        }
53    }
54
55    if(je_fibonacijev)
56    {
57        printf("\nZadati niz je podskup Fibonacijevog niza: ");
58        for(i = 0;i < n;i++)
59        {
60            if(i > 0)
61            {
62                printf(", ");
63            }
64            printf("%d", niz[i]);
65        }
66        printf("\n");
67    }
68    else
69    {
70        printf("\nZadati niz nije podskup Fibonacijevog niza!\n");
71    }
72
73    return 0;
74}