Zadanie 2.3, matura czerwiec 2016, informatyka rozszerzona
Darmowe konto pozwoli wrócić do niego później.
Zadanie
Zadanie 2. Dziwny porządek
Na planecie X obowiązuje dziwny porządek wśród liczb całkowitych dodatnich. Każda liczba parzysta jest mniejsza od każdej liczby nieparzystej. Relację mniejszości, obowiązującą na planecie X, oznaczamy symbolem „≪”. Tak więc zachodzą np. następujące nierówności 2 ≪ 3, 2 ≪ 1, 8 ≪ 5. Ponadto wśród liczb parzystych panuje normalny porządek, taki jak u nas na Ziemi, tzn. 2 ≪ 4 ≪ 6 ≪ 8 ≪ ⋯. Natomiast wśród liczb nieparzystych jest na odwrót – największą liczbą jest 1, tzn. … ≪ 5 ≪ 3 ≪ 1.
Przykład:
Poniżej wypisane są liczby 1, 2, 3, 4, 5, 6 w kolejności od najmniejszej do największej (zgodnie z porządkiem obowiązującym na planecie X).
2 ≪ 4 ≪ 6 ≪ 5 ≪ 3 ≪ 1
Wśród tych liczb najmniejszą na planecie X jest 2, a największą jest 1.
Polecenie
4 punktyZaproponuj algorytm, który dla danego skończonego zbioru liczb całkowitych dodatnich wyznacza element największy wg porządku obowiązującego na planecie X. Algorytm zapisz w postaci pseudokodu albo w wybranym języku programowania.
Specyfikacja:
Dane: liczba całkowita dodatnia n, tablica liczb całkowitych dodatnich A[1], A[2],...,A[n]
Wynik: największa liczba (wg porządku obowiązującego na planecie X) spośród liczb w tablicy A
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
Przykład 1:
```
max ← A[1]
Dla i = 2, 3, ..., n wykonaj
x ← A[i]
Jeśli max jest nieparzyste, to wykonaj
Jeśli x jest nieparzyste oraz x < max, to max ← x
Jeśli max jest parzyste, to wykonaj
Jeśli x jest nieparzyste lub x > max, to max ← x
Zwróć max
```
Przykład 2:
```
max ← A[1]
Dla i = 2, 3, ..., n wykonaj
jeśli (max mod 2 = 1 oraz A[i] mod 2 = 1 oraz A[i] < max), to max ← A[i]
jeśli (max mod 2 = 0 oraz A[i] mod 2 = 1), to max ← A[i]
jeśli (max mod 2 = 0 oraz A[i] mod 2 = 0 oraz A[i] > max), to max ← A[i]
```
Innymi poprawnymi rozwiązaniami są: algorytm oparty na wyodrębnieniu dwóch podciągów (liczb nieparzystych i parzystych), a następnie jeśli ciąg liczb nieparzystych jest niepusty, znalezienie w nim elementu najmniejszego; w przeciwnym razie znalezienie elementu największego w ciągu liczb parzystych. Algorytm może różnić się zastosowaniem sortowania do wyszukiwania elementu najmniejszego/największego.
Schemat punktowania
poprawnie działający algorytm, w tym:
poprawne wartości początkowe zmiennych,
poprawna organizacja pętli,
poprawne porównywanie liczb wg przyjętego porządku dla co najmniej jednego przypadku,
poprawne wyznaczanie elementu maksymalnego dla każdego przypadku (niezależnie od poprawności ustalenia wartości początkowej elementu maksymalnego).
Komentarz. Algorytm musi rozróżniać między liczbami parzystymi i nieparzystymi oraz stosować odpowiednie reguły porównania.