Zadanie 1

Wiązka zadań Binarny fraktal Fibonacciego

Ciąg Fibonacciego to ciąg liczb naturalnych określony rekurencyjnie w sposób następujący: ${\mathrm{F}}_1=1$, ${\mathrm{F}}_2=1$, a każdy następny element ciągu jest sumą dwóch poprzednich, czyli:

Binarny fraktal Fibonacciego to dwuwymiarowa tablicatablicatablica, zawierająca w kolejnych wierszach binarne zapisy kolejnych liczb Fibonacciego, gdzie każde zero w zapisie zastąpiono białym kwadratem, a każdą jedynkę czarnym kwadratem (Rys.1). Wszystkie binarne zapisy powinny składać się z jednakowej liczby cyfr, czyli do zapisów krótszych niż najdłuższy należy dodać zera wiodące.

Przykład binarnego fraktala dla pierwszych 10 liczb Fibonacciego:

R1IDCqbDriJlD

Ilustracja przedstawia fraktal binarny dla pierwszych dziesięciu liczb Fibonacciego. Poszczególnym pozycjom odpowiadają kolejne liczby. Na początku pierwszej kolumny po lewej stronie ilustracji jest litera n, w drugiej F indeks dolny n, w trzeciej kolumnie jest zapis: binarny F indeks dolny n. Następnie jest tabela w kształcie pionowego prostokąta z sześcioma polami na dziesięć pól. W tabeli na zielono zamalowano niektóre kwadraty, na które jest podzielona tabela. Dane są następujące: dla n=1, F indeks dolny n=1, zapis binarny F indeks dolny n to 000001, w tabeli na sześć kwadratów zamalowano na zielono ostatni kwadrat; n=2, F indeks dolny n=1, zapis binarny F indeks dolny n=000001, w tabeli na zielono zmalowano ostatni kwadrat w rzędzie sześciu kwadratów; n=3, F indeks dolny n=2, zapis binarny F indeks dolny n=000010, w tabeli zamalowano piąty, czyli przedostatni kwadrat w rzędzie sześciu kwadratów; n=4, zapis binarny F indeks dolny n=3, zapis binarny F indeks dolny n=000011, w tabeli zamalowano dwa ostatnie kwadraty; n=5, F indeks dolny n=5, zapis binarny F indeks dolny n=000101, w tabeli zamalowano czwarty i szósty kwadrat w rzędzie sześciu pól; n=6, F indeks dolny n=8, zapis binarny F indeks dolny n=001000, w tabeli zamalowano trzeci kwadrat w rzędzie sześciu pól; n=7, F indeks dolny n=13, zapis binarny F indeks dolny n=001101, w tabeli zamalowano trzeci, czwarty i szósty kwadrat; n=8, F indeks dolny n=21, zapis binarny F indeks dolny n=010101, w tabeli zamalowano drugi, czwarty i szósty kwadrat; n=9, F indeks dolny n=34, zapis binarny F indeks dolny n=100010, w tabeli zamalowano pierwszy i przedostatni, czyli piąty kwadrat; n=10, F indeks dolny n=55, zapis binarny F indeks dolny n=110111, w tabeli zamalowano pierwszy, drugi, czwarty, piąty oraz szósty kwadrat.

Napisz program komputerowy, za pomocą którego uzyskasz odpowiedzi do poniższych zadań. Rysunek fraktala (zadanie 1.3) wykonaj, wykorzystując dostępne narzędzia informatyczne. Odpowiedzi do poszczególnych zadań zapisz w pliku tekstowym o nazwie wyniki.txt, natomiast rysunek fraktala w pliku fraktal.xxx, gdzie xxx oznacza rozszerzenie pliku, w którym zapisany jest obraz fraktala.

Zadanie 1.1

Podaj wartości FIndeks dolny 10₁₀, FIndeks dolny 20₂₀, FIndeks dolny 30₃₀, FIndeks dolny 40₄₀. Zapisz każdą z liczb w osobnym wierszu.

Zadanie 1.2

Znajdź wszystkie liczby pierwsze wśród liczb FIndeks dolny 1₁, FIndeks dolny 2₂, …, FIndeks dolny 40₄₀. Zapisz każdą z liczb w osobnym wierszu.

Zadanie 1.3

Dla pierwszych 40 liczb Fibonacciego utwórz binarny fraktal Fibonacciego:

• Wypisz reprezentację binarną wszystkich liczb Fibonacciego od FIndeks dolny 1₁ do FIndeks dolny 40₄₀.

• Wyrównaj długości reprezentacji binarnych wszystkich liczb Fibonacciego od FIndeks dolny 1₁ do FIndeks dolny 40₄₀ i na ich podstawie sporządź obraz binarnego fraktala Fibonacciego.

Zadanie 1.4

Podaj w zapisie binarnym wyrazy ciągu Fibonacciego z zakresu od FIndeks dolny 1₁ do FIndeks dolny 40₄₀, które w tym zapisie mają dokładnie 6 jedynek.

Rozwiązanie

Zadanie 1.1

Rozwiązanie pierwszego podpunktu sprowadza się do zapisania algorytmu wyznaczania kolejnych wyrazów ciągu Fibonacciego. Skorzystamy z iteracyjnej wersji algorytmu, używającej pomocniczych zmiennych, przechowujących dwa wcześniejsze wyrazy ciągu. Jednak nic nie stoi na przeszkodzie, by wykorzystać wersję rekurencyjną algorytmu.

F1 ← 1
F2 ← 1
dla i = 3, 4, ..., 40 wykonuj:
	pom ← F1
	F1 ← F2
	F2 ← pom + F1

	jeżeli i mod 10 = 0:
		wypisz F2

1. Inicjujemy dwa pierwsze wyrazy ciągu Fibonacciego. [linie kodu 1, 2]

2. Zapisujemy pętlę dlainstrukcja dlapętlę dla, wyliczającą kolejne wyrazy ciągu, aż do czterdziestego. [linie kodu 3‑6]

3. Jeżeli właśnie obliczyliśmy wyraz ciągu, którego numer jest podzielny przez 10, to wypisujemy go. [linie kodu 8, 9]

Zadanie 1.2

Zmodyfikujemy rozwiązanie pierwszego podpunktu – zamiast wypisywania wyrazów ciągu o konkretnych numerach, każdy z obliczonych wyrazów będziemy sprawdzać pod kątem „bycia na pierwszym miejscu”. Zapiszmy funkcjęfunkcjafunkcję stwierdzającą, czy liczba podana jako argumentargument funkcjiargument jest liczbą pierwszą:

funkcja czyPierwsza(liczba)
	jeżeli liczba < 2:
    	zwróć fałsz
	dla i = 2, 3, ..., pierwiastekCałkowity(liczba):
		jeżeli liczba mod i = 0:
        	zwróć fałsz
	zwróć prawdę

1. Zapisujemy nagłówek funkcji. [linia kodu 1]

2. Jeżeli liczba jest mniejsza od 2 (0 lub 1), nie jest liczbą pierwszą, zatem zwracamy fałsz. [linie kodu 2, 3]

3. Sprawdzamy podzielność argumentu funkcji przez kolejne liczby, aż do jego pierwiastka. W przypadku wystąpienia podzielności, zwracamy fałsz. [linie kodu 4‑6]

4. Jeżeli pętlą zakończyła się bez zwrócenia fałszu, liczba dzieli się tylko przez 1 i samą siebie, zatem jest liczbą pierwszą i możemy zwrócić prawdę. [linia kodu 7]

F1 ← 1
F2 ← 1
dla i = 3, 4, ..., 40 wykonuj:
	pom ← F1
	F1 ← F2
	F2 ← pom + F1

	jeżeli czyPierwsza(F2):
		wypisz F2

Przedstawiona funkcja jest analogiczna do rozwiązania pierwszego podpunktu zadania. W linii 8 zamiast sprawdzania, czy dany numer wyrazu ciągu jest podzielny przez 10, sprawdzamy, czy jest liczbą pierwszą.

Zadanie 1.3

Podpunkt trzeci zadania podzielimy na dwie części. W pierwszej, korzystając z rozwiązania pierwszego podpunktu, wyliczymy pierwsze 40 wyrazów ciągu Fibonacciego, przekonwertujemy je do postaci binarnej i zapiszemy w tablicy. W drugiej, znając długość najdłuższego obliczonego wyrazu zapisanego binarnie, dopełnimy krótsze od niego wyrazy zerami z przodu i wypiszemy poprawione wyrazy.

Zapiszmy funkcję konwertującą wyrazy ciągu Fibonacciego do postaci binarnej. W związku z koniecznością dopisywania zer na początek krótszych liczb w dalszej części zadania, przekonwertowane liczby zapiszemy jako łańcuchy znaków:

funkcja konwertuj(liczba):
	postacBinarna ← ""
	dopóki liczba > 0, wykonuj:
		jeżeli liczba mod 2 = 0:
			postacBinarna ← "0" + postacBinarna
		w przeciwnym wypadku:
        	postacBinarna ← "1" + postacBinarna
		liczba ← liczba div 2
	zwróć postacBinarna

1. Zapisujemy nagłówek funkcji oraz pusty łańcuch znaków, do którego będziemy dopisywać kolejne cyfry w trakcie konwersji. [linie 1, 2]

2. Dopóki argument funkcji jest większy od 0, dzielimy go całkowitoliczbowo przez 2, za każdym razem dopisując resztę z dzielenia na początek postaci binarnej. [linie kodu 3‑8]

3. Zbudowany łańcuch znaków zwracamy. [linia kodu 9]

Możemy zapisać główną część kodu. Modyfikujemy rozwiązanie z podpunktu pierwszego, zapisując każdą przekonwertowaną liczbę w pomocniczej tablicy. Na koniec sprawdzamy długość ostatniego zapisanego w tablicy wyrazu i dla krótszych wyrazów dopisujemy z przodu 0, a następnie zapisujemy wyrazy do pliku wynikowego.

F1 ← 1
F2 ← 1

Binarne[0] ← "1"
Binarne[1] ← "1"
dla i = 2, 3, ..., 39 wykonuj:
	pom ← F1
	F1 ← F2
	F2 ← pom + F1
	Binarne[i] ← konwertuj(F2)
dla i = 0, 1, ..., 39 wykonuj:
	różnica ← długość(Binarne[39]) - długość(Binarne[i])
	jeżeli różnica > 0:
		dla j = 0, 1, ..., różnica:
			Binarne[i] ← "0" + Binarne[i]
    wypisz Binarne[i]

1. Oprócz pierwszych wyrazów ciągu Fibonacciego deklarujemy tablicę łańcuchów znaków, która będzie przechowywać wyrazy w postaci binarnej. Dwa pierwsze elementy tablicy wypełniamy od razu, gdyż nie ma dla nich różnicy między systemem binarnym oraz dziesiętnym. [linie kodu 1‑5]

2. W pierwszej pętli obliczamy kolejne wyrazy ciągu Fibonacciego oraz zapisujemy ich postać binarną do tablicy Binarne[]. [linie kodu 6‑10]

3. Następnie, dla każdego z wyrazów w postaci binarnej, dopisujemy zera z przodu, aby zrównały się długością z najdłuższym obliczonym wyrazem, a następnie zapisujemy je do pliku wynikowego. [linie kodu 11‑16]

Zadanie 1.4

W ostatnim podpunkcie zadania wykorzystamy zmodyfikowaną funkcję konwertującą z podpunktu trzeciego, przy okazji sprawdzając liczbę jedynek w postaci binarnej.

funkcja konwertuj(liczba):
	postacBinarna ← ""
	liczbaJedynek ← 0
	dopóki liczba > 0, wykonuj:
		jeżeli liczba mod 2 = 0:
			postacBinarna ← "0" + postacBinarna
		w przeciwnym wypadku:
			postacBinarna ← "1" + postacBinarna
			liczbaJedynek ← liczbaJedynek + 1      
		liczba ← liczba div 2
	jeżeli liczbaJedynek = 6:
		wypisz postacBinarna

Do funkcji wykorzystanej we wcześniejszym poleceniu dodajemy zmienną liczbaJedynek, zwiększaną za każdym razem, gdy w postaci binarnej liczby pojawi się jedynka. Na koniec konwersji sprawdzamy, czy jej wartość jest równa 6. Jeśli tak, wypisujemy postać binarną liczby. W przeciwnym wypadku funkcja kończy się bez żadnego skutku.

F1 ← 1
F2 ← 1
dla i ← 3, 4, ..., 40 wykonuj:
	pom ← F1
	F1 ← F2
	F2 ← pom + F1
	konwertuj(F2)

1. Inicjujemy dwa pierwsze wyrazy ciągu Fibonacciego. [linie kodu 1, 2]

2. Zapisujemy pętlę dla, wyliczającą kolejne wyrazy ciągu, aż do czterdziestego. [linie kodu 3‑6]

3. Wywołujemy zmodyfikowaną funkcję konwertującą, która wypisuje liczby w postaci binarnej, tylko jeżeli mają 6 jedynek. [linia kodu 9]

Odpowiedzi do zadania

Zadanie 1.1

55
6765
832040
102334155

Zadanie 1.2

2
3
5
13
89
233
1597
28657
514229

Zadanie 1.3

000000000000000000000000001
000000000000000000000000001
000000000000000000000000010
000000000000000000000000011
000000000000000000000000101
000000000000000000000001000
000000000000000000000001101
000000000000000000000010101
000000000000000000000100010
000000000000000000000110111
000000000000000000001011001
000000000000000000010010000
000000000000000000011101001
000000000000000000101111001
000000000000000001001100010
000000000000000001111011011
000000000000000011000111101
000000000000000101000011000
000000000000001000001010101
000000000000001101001101101
000000000000010101011000010
000000000000100010100101111
000000000000110111111110001
000000000001011010100100000
000000000010010010100010001
000000000011101101000110001
000000000101111111101000010
000000001001101100101110011
000000001111101100010110101
000000011001011001000101000
000000101001000101011011101
000001000010011110100000101
000001101011100011111100010
000010101110000010011100111
000100011001100110011001001
000111000111101000110110000
001011100001001111001111001
010010101000111000000101001
011110001010000111010100010
110000110010111111011001011

Zadanie 1.4

101111001
10101011000010
1011010100100000
10010010100010001

Słownik