Imię	Nazwisko:	Grupa:	Data:	Rok:
	Ocena:	Uwagi:
Temat ćwiczenia: Liczby Fibonacciego / Złoty podział odcinka

Realizacja projektu laboratoryjnego:

1. Sformułowanie problemu

Celem ćwiczenia jest zaprojektowanie:

1. algorytmu wyznaczającego n liczb Fibonacciego dla określonej wartości n

2. algorytmu wyznaczającego złoty podział odcinka

3. algorytmu wyznaczającego złoty podział prostokąta

4. algorytmu znajdującego złoty punkt w prostokącie

1. Analiza matematyczna problemu

1. Ciąg Fibonacciego:

Liczby naturalne tworzące ciąg o takiej własności, że kolejny wyraz jest sumą dwóch poprzednich nazywa się liczbami Fibonacciego.

Ciąg Fibonacciego to ciąg liczb określony rekurencyjnie w sposób następujący:

F0 = 0

F1 = 1

Fn = Fn-1 + Fn-2, dla n ≥ 2

Początkowe wartości tego ciągu to:

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, ...

Podstawowy ciąg liczb Fibonacciego to: 1, 1, 2, 3, 5, 8, ... Każda liczba w ciągu jest sumą dwóch poprzednich (poza pierwszą i drugą). Mamy więc do czynienia z ciągiem rekurencyjnym. Ciąg liczbowy Fibonacciego jest pierwszym ze znanych ciągów tego rodzaju.

Liczby Fibonacciego można wyznaczyć ze wzoru:
Fn+1=n0+n−11+n−22+...
Liczby Fibonacciego są więc sumami liczb z przekątnych w trójkącie Pascala.

1. Złoty podział odcinka:

Konstrukcja geometryczna:

Jeżeli spełnione jest zależność:

$$\frac{a}{x} = \frac{x}{a - x} = \varphi \approx 1,61$$

Wtedy w odległości x od początku odcinka znajduje się punkt, który jest tzw. złotym podziałem odcinka.

1. Złoty podział prostokąta:

Konstrukcja geometryczna:

Jeżeli spełnione jest zależność:

$$\frac{a}{x} = \frac{x}{a - x} = \varphi \approx 1,61$$

Wtedy w odległości x od początku dłuższego boku znajduje się punkt, który jest tzw. złotym podziałem prostokąta.

1. Złoty punkt w prostokącie:

Konstrukcja geometryczna:

1. Formalne informatyczne rozwiązanie problemu:

1. Ciąg Fibonacciego:

Jest to rekurencyjny ciąg liczbowy gdzie:

• dla liczby n=0 przypisana jest wartość F(n)=0;

• dla liczb n=1 i n=2 przypisana jest wartość F(n)=1;

• dla liczb n>=3 wartość obliczana jest według wzoru F(n)=F(n-1)+F(n-2).

Jest to ciąg nieskończony, którego wygląd jest następujący: 0, 1, 1, 2, 3, 5, 8, 13, 21, …. Jak widać za wyjątkiem 2 pierwszych wyrazów, każdy następny wyraz jest sumą dwóch wyrazów go poprzedzających.

1. Złoty podział odcinka

W programie, który jest zamieszczony poniżej zloty podział odcinka jest rozwiązany za pomocą równania kwadratowego. Na potrzeby programu parametr a(uwzględniony poniżej) nosi nazwę dlugosc i jest on długością odcinka, a x określany w programie jako punkt jest szukanym miejscem złotego podziału odcinka.

Z zależności przedstawionej 2.2 otrzymujemy równanie postaci:

x² + ax − a² = 0

=a² + 4a²

$$x = \frac{- a + \sqrt{}}{2}$$

W programie nie uwzględniono drugiego rozwiązania równania kwadratowego, ponieważ jest on ujemny co nie jest zgodne z prawdą.

1. Złoty podział prostokąta

W programie, który jest zamieszczony poniżej zloty podział prostokąta jest rozwiązany za pomocą równania kwadratowego. Na potrzeby programu parametr a(uwzględniony poniżej) nosi nazwę dlugosc i jest on długością dłuższego boku prostokąta, a x określany w programie jako punkt jest szukanym miejscem złotego podziału prostokąta, znajdującym się na dłuższym boku.

Z zależności przedstawionej 2.4 otrzymujemy równanie postaci:

x² + ax − a² = 0

=a² + 4a²

$$x = \frac{- a + \sqrt{}}{2}$$

W programie nie uwzględniono drugiego rozwiązania równania kwadratowego, ponieważ jest on ujemny co nie jest zgodne z prawdą (jest to długość boku, a więc nie może być ujemną wartością).

1. Złoty punkt w prostokącie

Współrzędne złotego punktu znajdują się w punkcie oznaczonym jako P($\frac{2}{3}f,\frac{1}{3}e)$. W programie boki noszą nazwę dłuższy i krótszy, a wartości pierwiastków są podane w przybliżeniu.

1. Schemat blokowy problemu

Schemat ogólny realizacji problemu.

1. Program komputerowy realizujący punkt 3 i 4

#include <stdafx.h>

#include <iostream>

#include <cstdlib>

using namespace std;

int main()

{

double n, pierwsza, druga, f, l, m, dlugosc, delta, pierwiastek, punkt, c, j, k, phi, dluzszy, krotszy, punkt1, punkt2, krotszy1, szerokosc;

cout << "1. Ciag Fibonacciego: " << endl << endl;

cout << "Podaj ile wyrazow ciagu mam policzyc n>=2, n=: ";

cin >> n;

pierwsza = 0;

druga = 1;

cout << "Ciag Fibonacciego ma postac: " << endl;

cout << pierwsza << ", " << druga << ", ";

for (double i = 0; i <= (n - 2); i++)

{

f = pierwsza + druga;

pierwsza = druga;

druga = f;

cout << druga << ", ";

}

cout << endl << endl << "################################################################################" << endl << endl;

cout << "2. Zloty podzial odcinka: " << endl << endl;

do{

cout << "Podaj dlugosc odcinka:";

cin >> dlugosc;

} while (dlugosc <= 0);

delta = (dlugosc * dlugosc) + (4 * dlugosc * dlugosc);

pierwiastek = sqrt(delta);

punkt = (-dlugosc + pierwiastek) / 2;

c = dlugosc / punkt;

j = punkt / (dlugosc - punkt);

phi = 1.61;

if (c = j)

{

k = c;

if (k = phi)

{

cout << "Zloty podzial odcinka znajduje sie w punkcie: " << punkt << " ." << endl;

}

}

else

cout << "Odcinek o tej dlugosci nie ma zlotego podzialu";

cout << endl << endl << "################################################################################" << endl << endl;

cout << "3. Zloty podzial prostokata:" << endl << endl;

do{

cout << "Podaj dlugosc dluzszego boku prostokata:";

cin >> dlugosc;

} while (dlugosc <= 0);

delta = (dlugosc * dlugosc) + (4 * dlugosc * dlugosc);

pierwiastek = sqrt(delta);

punkt = (-dlugosc + pierwiastek) / 2;

cout << "Krotszy bok prostokata ma dlugosc: " << punkt << endl;

c = dlugosc / punkt;

j = punkt / (dlugosc - punkt);

if (c = j)

{

k = c;

if (k = phi)

{

cout << "Zloty podzial prostokata znajduje sie na dluzszym boku prostokata w punkcie: " << punkt << endl;

}

}

else

cout << "Prostokat nie ma zlotego podzialu." << endl;

cout << endl << endl << "################################################################################" << endl << endl;

cout << "4. Zloty punkt w prostokacie:" << endl << endl;

do{

cout << "Podaj dlugosc dluzszego boku w prostokacie: ";

cin >> dluzszy;

} while (dluzszy <= 0);

do{

cout << "Podaj dlugosc krotszego boku w prostokacie: ";

cin >> krotszy;

} while (krotszy <= 0);

punkt1 = 0.67 * dluzszy;

punkt2 = 0.33 * krotszy;

cout << "Zloty punkt w prostokacie o wymiarach (" << dluzszy << "x" << krotszy << ") znajduje sie w pukcie P(" << punkt1 << " , " << punkt2 << ")." << endl;

cout << endl << endl << "################################################################################" << endl << endl;

cout << "5. Zloty punkt w prostopadloscianie: " << endl << endl;

do{

cout << "Podaj krotszy bok sciany prostopadloscianu: ";

cin >> krotszy1;

} while (krotszy1 <= 0);

do{

cout << "Podaj szerokosc prostopadloscianu: ";

cin >> szerokosc;

} while (szerokosc <= 0);

delta = (krotszy1 * krotszy1) + (4 * krotszy1 * krotszy1);

pierwiastek = sqrt(delta);

punkt = (-krotszy1 + pierwiastek) / 2;

c = dlugosc / punkt;

j = punkt / (dlugosc - punkt);

phi = 1.61;

cout << "Wymiary prostopadloscianu, dla ktorego szukam zlotego punktu: " << krotszy1 << " x " << krotszy1 + punkt << " x " << szerokosc << endl;

punkt1 = 0.67 * krotszy1;

punkt2 = 0.33 * szerokosc;

cout << "Złoty punkt w prostopadloscianie o wymiarach " << krotszy1 << " x " << krotszy1 + punkt << " x " << szerokosc << " lezy w punkcie P( " << punkt1 << " ; " << punkt2 << " )." << endl;

system("PAUSE");

return(0);

}

1. Testowanie problemu, analiza błędów zagadnienia i realizacji

Brak zależności pomiędzy następnym, a poprzednim wyrazem ciągu. Poza tym wszystko w porządku.

1. Wersja ostateczna

Wersja w podpunkcie czwartym jest niemal, że identyczna.