Zadanie 1.2, matura czerwiec 2021, informatyka rozszerzona
Darmowe konto pozwoli wrócić do niego później.
Zadanie
Zadanie 1. Sumy kwadratów
Każdą dodatnią liczbę całkowitą n można reprezentować jako sumę kwadratów dodatnich liczb całkowitych. Może istnieć wiele różnych takich sum.
Przykład:
1 = 12
9 = 32 = 22 + 22 + 12 = 22 + 12 + 12 + 12 + 12 + 12
Długością reprezentacji (kwadratowej) nazywamy liczbę składników sumy. W przykładzie liczba 9 ma trzy reprezentacje o długościach odpowiednio 1, 3 i 6. Zauważ, że suma może być jednoskładnikowa.
Jedną z metod otrzymywania krótkich reprezentacji kwadratowych jest metoda zachłanna, w której w każdym kroku jako kolejny składnik sumy bierze się największy możliwy kwadrat liczby całkowitej gwarantujący, że suma nie przekracza n. Ta metoda nie zawsze znajduje najkrótsze reprezentacje.
Polecenie
4 punktyNapisz algorytm (w postaci pseudokodu lub w wybranym języku programowania), który dla danej dodatniej liczby całkowitej n obliczy długość jej reprezentacji kwadratowej wyznaczanej metodą zachłanną. Twój algorytm powinien być zgodny z poniższą specyfikacją.
Uwaga: W zapisie algorytmu możesz korzystać tylko z instrukcji sterujących, operatorów arytmetycznych (dodawania, odejmowania, mnożenia, dzielenia, dzielenia całkowitego i reszty z dzielenia), operatorów logicznych, porównań i instrukcji przypisywania lub samodzielnie napisanych funkcji i procedur wykorzystujących powyższe operacje. Zabronione jest używanie funkcji wbudowanych, dostępnych w językach programowania, zwłaszcza funkcji pierwiastek.
Specyfikacja:
Dane
n – dodatnia liczba całkowita
Wynik
dl – długość reprezentacji kwadratowej liczby n, otrzymanej metodą zachłanną
Przykład:
Dla n = 12 wynikiem jest dl = 4.
Algorytm:
Korepetytor
Nie wiesz, jak ruszyć? Korepetytor zna to zadanie i poprowadzi Cię krok po kroku, bez gotowca.
5 rozmów · bez karty · Zaloguj się
Sprawdź się
Jak poszło?
Pokaż rozwiązanieUkryj rozwiązanie
Odpowiedź z klucza CKE
```
s ← 0
kw ← 1
dopóki kw * kw < n wykonuj
kw ← kw + 1
jeżeli kw * kw > n, to kw ← kw - 1
s ← n – kw * kw
dl ← 1
dopóki s > 0 wykonuj
jeżeli kw * kw ≤ s, to
s ← s – kw * kw
dl ← dl + 1
w przeciwnym razie
kw ← kw - 1
wypisz dl
```
Schemat punktowania
za poprawny algorytm, w tym:
za poprawne wartości początkowe zmiennych i za poprawne ustalenie największego składnika reprezentacji kwadratowej – 2 punkty,
za poprawną organizację pętli obliczającej długość reprezentacji kwadratowej – 1 punkt,
za poprawne wyznaczanie kolejnych elementów reprezentacji kwadratowej i poprawne ich zliczanie – 1 punkt.
za podanie odpowiedzi niepoprawnej albo brak odpowiedzi.
Uwaga: Akceptowane są wszystkie odpowiedzi merytorycznie poprawne, spełniające warunki zadania.
Uwaga: za każde inne niż przedstawione niżej, ale całkowicie poprawne rozwiązanie spełniające warunki zadania przyznajemy maksymalną liczbę punktów.
Komentarz. Za każde inne niż przedstawione, ale całkowicie poprawne rozwiązanie spełniające warunki zadania przyznajemy maksymalną liczbę punktów.