Matura 2016 (maj). Zadanie 2. Przestawienia w tablicy

Parametrem podanej poniżej funkcji przestaw jest tablica A o długości n, indeksowana od 1, w której znajdują się liczby całkowite. Niech klucz będzie wartością pierwszego elementu tablicy A. Funkcja przestawia (zamienia wzajemnie) elementy tablicy A tak, aby po jej wykonaniu w lewej części tablicy były wszystkie elementy tablicy mniejsze od klucza, natomiast w prawej części – wszystkie większe lub równe kluczowi.

Specyfikacja:

Dane:

n – liczba całkowita dodatnia
A[1..n] – tablica liczb całkowitych

Wynik:

A[1..n] – tablica liczb całkowitych ułożona według podanej reguły

funkcja przestaw(A)
  klucz ← A[1]
  w ← 1
  dla k = 2, 3, ..., n wykonaj
    jeśli A[k] < klucz
      zamień(A[w], A[k])
      w ← w + 1

Uwaga:
Funkcja zamień(x,y) zamienia wzajemnie wartości zmiennych x i y – w powyższym przypadku zamienia wzajemnie dwa elementy tablicy A.

Zadanie 2.1. (0–2)
Dana jest liczba n = 6 oraz tablica A = [4,6,3,5,2,1]. Podaj kolejność elementów w tablicy A po wykonaniu funkcji przestaw(A).

Krok 1.
Podstawiamy pod klucz = A[1], czyli klucz = 4. Zmienna w = 1, w to jest nr elementu w tablicy, z którym będziemy zamieniać element mniejszy od klucza.

Krok 2.
Sprawdzamy czy A[2] < klucza, czyli czy 6<4, tu odpowiedź brzmi nie. Nie wykonujemy zamiany. Sprawdzamy kolejny element tablicy. Po wykonaniu tej czynności nasz tablica A = [4,6,3,5,2,1].

Krok 3.
Sprawdzamy czy A[3] < klucza, czyli czy 3<4, tu odpowiedź brzmi tak. Zamieniamy element tablicy A[1] z A[3], czyli 3 z 4. Po wykonaniu tej czynności nasz tablica A = [3,6,4,5,2,1]. Zwiększamy o 1 wartość zmiennej w, tj. w = 2. Sprawdzamy kolejny element tablicy.

Krok 4.
Sprawdzamy czy A[4] < klucz, czyli czy 5<4, tu odpowiedź brzmi nie. Nie wykonujemy zamiany. Sprawdzamy kolejny element tablicy.Po wykonaniu tej czynności nasz tablica A = [3,6,4,5,2,1].

Krok 5.
Sprawdzamy czy A[5] < klucza, czyli czy 2<4, tu odpowiedź brzmi tak. Zamieniamy element tablicy A[2] z A[5], czyli 6 z 2. Po wykonaniu tej czynności nasz tablica A = [3,2,4,5,6,1]. Zwiększamy o 1 wartość zmiennej w, tj. w = 3. Sprawdzamy kolejny element tablicy.

Krok 6.
Sprawdzamy czy A[6] < klucza, czyli czy 1<4, tu odpowiedź brzmi tak. Zamieniamy element tablicy A[3] z A[6], czyli 4 z 1. Po wykonaniu tej czynności nasz tablica A = [3,2,1,5,6,4]. Zwiększamy o 1 wartość zmiennej w, tj. w = 4. Koniec naszej tablicy.

Odpowiedź:
Tablica A = [3,2,1,5,6,4].

Kod w C++ sprawdzający poprawność działania algorytmu:

#include <iostream>
using namespace std;
int main()
{
 int n = 6;
 int A[n] = {4,6,3,5,2,1};
 int klucz = A[0];
 int w = 0;
 for (int k=1; k<n; k++)
 if (A[k] < klucz) {
 swap(A[w], A[k]);
 w++;
 }
 for (int i=0; i<n; i++)
 cout << A[i] << " ";
 cout << endl;
 cout << "Zamian = " << w << endl;
 return 0;
}

Zadanie 2.2. (0–1)
Podaj przykład siedmioelementowej tablicy A, dla której funkcja przestaw(A) dokładnie 5 razy wykona zamień.

Musi to być taka tablica, gdzie dokładnie 5 elementów będzie mniejszych od klucza. Kluczem jest pierwszy element tablicy. Przykładowa tablica to: A = [6,5,4,3,2,1,7].

Odpowiedź:
Tablica A = [5,4,3,2,1,6,7].

Zadanie 2.3. (0–3)
Tablica A[1..100] zawiera wszystkie liczby całkowite z przedziału <1, 100> w następującej kolejności:
A = [10, 20, 30, …, 100, 9, 19, 29, …, 99, 8, 18, 28, …, 98, …., 1, 11, 21, …, 91].
(najpierw rosnąco wszystkie liczby kończące się na 0, potem rosnąco liczby kończące się na 9, potem na 8 itd.)
Podaj wartość zmiennej w oraz wartości trzech pierwszych elementów tablicy A (A[1], A[2], A[3]), po wykonaniu funkcji przestaw(A).

Wartość zmiennej w jest równa ilości wykonanych zamian liczb, czyli tu będzie to 9 zmian, tak więc w = 9, ponieważ mniejszych liczb od klucz (A[1] = 10) jest 9 (tj. 9,8,7,6,5,4,3,2,1).  Jeśli chodzi o elementy to w zależności, który element jest pierwszy mniejszy od klucza, który jest równy 10. W podanym zapisie mamy że najpierw napotykamy 9, potem 8 itd. do 1.

Odpowiedź:
w = 10.
A[1] = 9, A[2] = 8, A[3] = 7.