Sprawdź się
Zadanie 3 – Sumy wyrazów ciągu Fibonacciego
W pliku tekstowym dane3.txt
załączonym do zadania znajduje się 50 wierszy, zawierających dodatnie liczby naturalne. Wynik zapisz do pliku wynik3.txt
.
Przycisk do pobrania pliku TXT z treścią zadania. Pobierz załącznik
Używając wybranego języka programowania, napisz program, który wczyta zawartość pliku, a następnie obliczy i wypisze, ile liczb z tego pliku jest sumą dokładnie trzech różnych wyrazów ciągu Fibonacciego. Pamiętaj, że zarówno drugi, jak i trzeci wyraz mają wartość 1, jednak są różnymi wyrazami.
W ramach ćwiczenia część danych została umieszczona w formie tabeli. Pamiętaj jednak, że podczas pisania implementacji na swoim komputerze musisz się upewnić, że dane zostaną prawidłowo wczytane z pliku tekstowego do programu.
Poprawny wynik dla danych z podanego pliku tekstowego znajduje się na końcu zadania.
Do oceny oddajesz:
plik
wynik3.txt
z odpowiedzią (liczba naturalna oznaczająca to, ile liczb z plikudane3.txt
jest sumą dokładnie trzech różnych wyrazów ciągu Fibonacciego),plik(i) z komputerową realizacją zadania (kodem programu).
1 Pokaż ćwiczenia:
C++
#include <iostream>
#include <vector>
using namespace std;
void ileLiczbPotrojnych(int tab[], int n) {
int ilosc = 0;
// Szukamy maksymalnego wyrazu w tab
int max = tab[0];
for (int i = 1; i < n; i++)
if (max < tab[i])
max = tab[i];
// Obliczamy wyrazy ciagu Fibonacciego az obliczymy wiekszy od najwiekszej liczby z tablicy
vector <int> fib;
fib.push_back(0);
fib.push_back(1);
while (fib.back() < max)
fib.push_back(fib[fib.size() - 1] + fib[fib.size() - 2]);
int m = fib.size();
for (int t = 0; t < n; t++) {
bool poszukiwanie = true;
int i = 0;
while (i < m && poszukiwanie) {
int j = i + 1;
while (j < m && poszukiwanie) {
int k = j + 1;
while (k < m && poszukiwanie) {
if (tab[t] == fib[i] + fib[j] + fib[k]) {
ilosc += 1;
poszukiwanie = false;
// nalezy przerwac petle po potwierdzeniu ze liczba jest potrojna
// po to aby nie zwiekszyc kilkukrotnie "ilosc" dla jednej liczby
}
k++;
}
j++;
}
i++;
}
}
// jesli wszystkie petle przebiegalyby od 0 do n to trzeba dodac w "if" warunek
// i != j && j != k && i != k
cout << ilosc << endl;
}
int main() {
int liczby[] = { 2, 4, 11, 35, 46, 49, 51, 54 };
ileLiczbPotrojnych(liczby, 8);
return 0;
}
Java
import java.util.ArrayList;
public class Main {
public static int[] liczby = {2, 4, 11, 35, 46, 49, 51, 54};
public static void main(String[] args) {
ileLiczbPotrojnych(liczby);
}
public static void ileLiczbPotrojnych(int[] tab) {
int ilosc = 0;
ArrayList<Integer> fib = new ArrayList<>();
fib.add(0);
fib.add(1);
// Szukamy maksymalnego wyrazu w tab
int max = tab[0];
for (int x : tab)
if (max < x)
max = x;
// Obliczamy wyrazy ciagu Fibonacciego az obliczymy wiekszy od najwiekszej liczby z tablicy
while (fib.get(fib.size()-1) < max)
fib.add( fib.get(fib.size()-1) + fib.get(fib.size()-2) );
int m = fib.size();
for (int liczba : tab) {
boolean poszukiwanie = true;
int i = 0;
while (i < m && poszukiwanie) {
int j = i + 1;
while (j < m && poszukiwanie) {
int k = j + 1;
while (k < m && poszukiwanie) {
if (liczba == fib.get(i)+fib.get(j)+fib.get(k)) {
ilosc++;
poszukiwanie = false;
// nalezy przerwac petle po potwierdzeniu ze liczba jest potrojna
// po to aby nie zwiekszyc kilkukrotnie "ilosc" dla jednej liczby
}
k++;
}
j++;
}
i++;
}
}
// jesli wszystkie petle przebiegalyby od 0 do n to trzeba dodac w "if" warunek
// i != j && j != k && i != k
System.out.println(ilosc);
}
}
Python
def ileLiczbPotrojnych(tab):
ilosc = 0
fib = [0, 1]
# obliczamy wyrazy ciagu Fibonacciego az obliczymy wiekszy od najwiekszej liczby z tablicy
while fib[-1] < max(tab):
fib.append(fib[-1]+fib[-2])
n = len(fib)
for liczba in tab:
poszukiwanie = True
i = 0
while i < n and poszukiwanie:
j = i+1
while j < n and poszukiwanie:
k = j+1
while k < n and poszukiwanie:
if liczba == fib[i]+fib[j]+fib[k]:
ilosc += 1
poszukiwanie = False
# nalezy przerwac petle po potwierdzeniu ze liczba jest potrojna
# po to aby nie zwiekszyc kilkukrotnie "ilosc" dla jednej liczby
k += 1
j += 1
i += 1
# jesli wszystkie petle przebiegalyby od 0 do n to trzeba dodac w "if" warunek
# i != j and j != k and i != k
print(ilosc)
liczby = [2, 4, 11, 35, 46, 49, 51, 54]
ileLiczbPotrojnych(liczby)
Odpowiedź do zadania
Przycisk do pobrania pliku TXT z wynikiem zadania. Pobierz załącznik