Zadanie 1.2, matura czerwiec 2021, informatyka rozszerzona

4 pktotwarteśrednie (szac.)Czerwiec 2021

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 punkty

Napisz 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.

Wypróbuj za darmo

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

4 pkt

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.

0 pkt

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.

Umiejętności w zadaniu

Pliki cookies

Zapisujemy na Twoim urządzeniu to, bez czego serwis nie działa, np. zalogowanie. Plików analitycznych użyjemy tylko za Twoją zgodą. Szczegóły w polityce prywatności.