Zadanie 1. Trójkąty i kwadraty

Dana jest dwuwymiarowa tablica dodatnich liczb naturalnych. Tablica składa się z n wierszy, w każdym wierszu podane są trzy liczby naturalne dodatnie. Każda liczba w tablicy reprezentuje pole kwadratu.

Wyznacz długości boków kwadratów z dokładnością do dwóch miejsc po przecinku i sprawdź, czy z boków kolejnych kwadratów w wierszu można zbudować trójkąt. Oblicz, ile trójkątów możesz zbudować.

Napisz algorytm (w postaci pseudokodu lub w wybranym języku programowania) sprawdzania, czy z długości boków kwadratów można zbudować trójkąty.

17 19 21

4,12 4,35 4,58

W zapisie algorytmu możesz wykorzystać tylko operacje arytmetyczne (dodawanie, odejmowanie, mnożenie, dzielenie, dzielenie całkowite, reszta z dzielenia), instrukcje porównania, instrukcje sterujące i przypisania do zmiennych, samodzielnie napisane funkcje, wykorzystujące wymienione wyżej operacje lub funkcje wbudowane.

Specyfikacja problemu:

Dane:

• tablica[0..n - 1][0..2] – tablica liczb naturalnych

• n – liczba naturalna; liczba wierszy

Wynik:

• liczbaTrojkatow – liczba naturalna; liczba trójkątów, które można zbudować z odcinków, które są długościami boków kwadratów

Rozwiązanie

Zauważmy, że algorytm bazuje na algorytmie Newtona‑Raphsonametoda Newtona‑RaphsonaNewtona‑Raphsona.

W metodzie tej wykorzystywany jest fakt, że jeśli pierwiastkowana liczba oznacza pole powierzchni kwadratu, to długość jego boku będzie wynikiem pierwiastkowania badanej liczby. Algorytm polega na modyfikowaniu przyjętej długości boków prostokąta o polu równym pierwiastkowanej liczbie do momentu, w którym różnica między ich długościami będzie mniejsza niż zadany próg (zakładamy, że przy różnicy długości boków poniżej tego progu przybliżoną wartością pierwiastka tej liczby jest długość jednego z boków prostokąta).

R1ECNCjtaoDAe

Ilustracja przedstawia prostokąt. Krótszy bok oznaczono małą literą c, dłuższy b, w środku prostokąta jest litera a. Strzałka w prawo. Kwadrat o bokach pierwiastek z a, w środku kwadratu jest litera a.

Wiemy, na czym polega działanie algorytmu Newtona‑Raphsona. Algorytm ten zapisany za pomocą pseudokodu wygląda następująco:

funkcja oblicz_pierwiastek(a, epsilon)
	b ← a / 2
    c ← a / b
    
    dopóki | b - c | > epsilon wykonuj
    	b ← ( b + c ) / 2
        c ← a / b
	
    zwróć b

Naszym zadaniem jest wyznaczenie wartości pierwiastka w zaokrągleniu do dwóch miejsc po przecinku, z tego względu wykorzystamy również funkcję zaokr().

Zmiennej epsilon przypisujemy wartość $0,001$.

Ustalając wartość parametru epsilon, należy wziąć pod uwagę dokładność obliczeń komputerowych. Więcej na ten temat znajdziesz w e‑materiale Błędy obliczeń numerycznychP90lYs0bMBłędy obliczeń numerycznych.

funkcja oblicz_pierwiastek(a)
	epsilon ← 0.001
    b ← a / 2
    c ← a / b
    
    dopóki | b - c | > epsilon wykonuj
    	b ← ( b + c ) / 2
        c ← a / b
    
    b ← zaokr(b)
	zwróć b

Gdy już przygotowaliśmy funkcję obliczającą pierwiastek kwadratowy, przejdźmy do zapisania algorytmu sprawdzania, czy z trzech danych w każdym wierszu można zbudować trójkąt.

funkcja czyTrojkat(a, b, c)
	jeżeli (a + b > c) ORAZ (b + c > a) ORAZ (a + c > b)
		zwróć 1
	w przeciwnym razie        
		zwróć 0

Zapiszmy również właściwą część programu.

Wczytujemy do programu dwuwymiarową tablicę liczby, tworzymy również pustą dwuwymiarową tablicę wyniki[0..n - 1][0..2].

W pętli dla każdej liczby z tablicy liczby dodajemy nową pustą tablicę do tablicy wyniki, a następnie obliczamy pierwiastki dla każdej liczby i przypisujemy je do kolejnych indeksów w wewnętrznej tablicy wyniki[i].

Tworzymy zmienną licznikTrojkatow; przypisujemy jej wartość 0.

W pętli dla każdej liczby z tablicy liczby przypisujemy wartości pierwiastków z wewnętrznej tablicy wyniki[i] do zmiennych a, b, i c.

Wywołujemy funkcję czyTrojkat(a, b, c) i sprawdzamy, czy zwrócona wartość jest równa 1, co oznacza, że odcinki, których długości są pierwiastkami liczb naturalnych, tworzą trójkąt.

Jeśli wartość zwrócona przez funkcję czyTrojkat(a, b, c) jest równa 1, wartość zmiennej licznikTrojkatow zostanie zwiększona o 1.

Po tym, jak program przeiteruje po wszystkich wierszach tablicy liczby, wypisana zostanie wartość zmiennej licznikTrojkatow.

wczytaj tablicę liczby[][]
utwórz tablicę wyniki[][]

dla i od 0 do długość(liczby) - 1 wykonuj:
	dodaj pustą tablicę w tablicy wyniki
    dla j od 0 do 2 wykonuj:
    	wyniki[i][j] ← oblicz_pierwiastek(liczby[i][j])
    
licznikTrojkatow ← 0    

dla i od 0 do długość(liczby) wykonuj:
    a ← wyniki[i][0]
    b ← wyniki[i][1]
    c ← wyniki[i][2]
    jeżeli czyTrojkat(a, b, c) == 1
        licznikTrojkatow =+ 1

wypisz licznikTrojkatow

Słownik