Ciąg Fibonacciego zdefiniowany jest następująco:
\(\displaystyle{ Fib(n)= \begin{cases} 0 \Rightarrow n = 0 \\ 1 \Rightarrow n = 1\\ Fib(n-2)+Fib(n-1) \end{cases}}\)
Dowolną liczbę naturalną możemy przedstawić w postaci ciągu zerojedynkowego
zdefiniowanego w sposób następujący: jeżeli k-ta cyfra jest równa 1, wtedy
odpowiada wartości Fib(k), jeżeli 0 to jest równa 0 (cyfry numerujemy od prawej do
lewej zaczynając od jeden).
Przykład: \(\displaystyle{ {11011101_F_i_b= 1(21) + 1(13) + 0(8) + 1(5) + 1(3) + 1(2) + 0(1) + 1(1) =
21 + 13 + 5 + 3 + 2 + 1 = 45_1_0}\)
Napisz algorytm wyznaczający wartości dziesiętne takich ciągów zerojedynkowych.
Uwaga: elementy ciągu Fibonacciego nie mogą być stablicowane.
Napisany przeze mnie program:
Kod: Zaznacz cały
#include <iostream>
#include <string>
using namespace std;
string kb;
int i;
int licz;
int fib(int i)
{
if(i<2)
return 1;
return fib(i-2)+fib(i-1);
}
int main()
{
int i;
cout << "Wprowadz KodBin: " << endl;
cin >> kb;
for (i=0; i<=kb.size(); i++)
{
if (kb[i]=='1')
{
if (i>=2)
{
licz = licz + fib(i);
}
if (i==1)
{
licz = licz + 1;
}
if (i==0)
{
licz = licz + 1;
}
}
}
cout << "Ostateczy wynik licz = " << licz << endl;
return 0;
}
