Arkusz
Rozwiązanie
Zasady oceniania i sprawozdanie
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) - poziom wykonania: 36%
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).
Pseudokod po poprawieniu
Wersja I
A ← [4, 6, 3, 5, 2, 1]
n ← 6
funkcja przestaw(A)
klucz ← A[1]
w ← 1
dla k = 2, 3, ..., n
jeśli A[k] < klucz
pom ← A[w]
A[w] ← A[k]
A[k] ← pom
w ← w+1
przestaw(A)
wypisz "A = [" + A + "]"
Wersja II
A ← [4, 6, 3, 5, 2, 1]
n ← 6
funkcja zamien(x, y)
pom ← A[w]
A[w] ← A[k]
A[k] ← pom
funkcja przestaw(A)
klucz ← A[1]
w ← 1
dla k = 2, 3, ..., n
jeśli A[k] < klucz
zamien(A[w], A[k])
w ← w+1
przestaw(A)
wypisz "A = [" + A + "]"
A=[3,2,1,5,6,4]
Zapis w C++
#include <iostream>
using namespace std;
void zamien(int A[], int w, int k) {
int pom = A[w];
A[w] = A[k];
A[k] = pom;
}
void przestaw(int A[], int length) {
int klucz = A[0];
int w = 0;
for (int k = 1; k < length; ++k) {
if (A[k] < klucz) {
zamien(A, w, k);
w += 1;
}
}
}
int main() {
int A[] = {4, 6, 3, 5, 2, 1};
int length = sizeof(A) / sizeof(A[0]);
przestaw(A, length);
cout << "A = [";
for (int i = 0; i < length; ++i) {
cout << A[i];
if (i < length - 1) {
cout << ", ";
}
}
cout << "]" << endl;
return 0;
}
Zapis w Python
def zamien(A, w, k):
pom = A[w]
A[w] = A[k]
A[k] = pom
def przestaw(A):
klucz = A[0] # W Python, tablice indeksujemy od 0
w = 0
n = len(A)
for k in range(1, n):
if A[k] < klucz:
zamien(A, w, k)
w += 1
return A
A = [4, 6, 3, 5, 2, 1]
przestaw(A)
print("A =", A)
Zapis w Java
Zapis w Java
public class Main {
public static void zamien(int[] A, int w, int k) {
int pom = A[w];
A[w] = A[k];
A[k] = pom;
}
public static void przestaw(int[] A) {
int klucz = A[0];
int w = 0;
int n = A.length;
for (int k = 1; k < n; ++k) {
if (A[k] < klucz) {
zamien(A, w, k);
w += 1;
}
}
}
public static void main(String[] args) {
int[] A = {4, 6, 3, 5, 2, 1};
przestaw(A);
System.out.print("A = [");
for (int i = 0; i < A.length; ++i) {
System.out.print(A[i]);
if (i < A.length - 1) {
System.out.print(", ");
}
}
System.out.println("]");
}
}