Etap 7: Podstawowe algorytmy w C++ - Implementacja ręczna

Podstawowe algorytmy: Fundament logiki programowania

Na Twoim kolokwium obowiązuje zakaz korzystania z gotowych rozwiązań z biblioteki <algorithm> (takich jak std::sort czy std::copy). Oznacza to, że musisz umieć zaimplementować te mechanizmy samodzielnie, używając pętli i instrukcji warunkowych.

1. Kopiowanie tablic

Ponieważ tablic nie można kopiować operatorem przypisania (tab1 = tab2), musimy przejść przez każdy element z osobna.

cpp

void kopiujTablice(int zrodlo[], int cel[], int rozmiar) {
    for (int i = 0; i < rozmiar; i++) {
        cel[i] = zrodlo[i];
    }
}

2. Wyszukiwanie (Linear Search)

Najprostszą metodą znalezienia elementu w nieposortowanej tablicy jest przeszukiwanie liniowe. Funkcja powinna zwracać indeks znalezionego elementu lub -1, jeśli element nie istnieje.

cpp

int znajdzElement(int tab[], int rozmiar, int szukana) {
    for (int i = 0; i < rozmiar; i++) {
        if (tab[i] == szukana) return i; // Znaleziono!
    }
    return -1; // Nie ma w tablicy
}

3. Sortowanie bąbelkowe (Bubble Sort)

To najczęściej wymagany algorytm na kolokwiach wstępnych ze względu na prostotę implementacji. Polega na porównywaniu sąsiednich elementów i zamienianiu ich miejscami, jeśli są w złej kolejności.

cpp

void sortowanieBabelkowe(int tab[], int n) {
    for (int i = 0; i < n - 1; i++) {
        for (int j = 0; j < n - i - 1; j++) {
            if (tab[j] > tab[j + 1]) {
                // Zamiana (Swap)
                int temp = tab[j];
                tab[j] = tab[j + 1];
                tab[j + 1] = temp;
            }
        }
    }
}

4. Generowanie ciągów

Ciąg arytmetyczny

Każdy kolejny element różni się o stałą wartość r.

cpp

void generujArytmetyczny(int tab[], int n, int start, int r) {
    for (int i = 0; i < n; i++) {
        tab[i] = start + i * r;
    }
}

Ciąg losowy (używając <cstdlib> i <ctime>)

Pamiętaj o zainicjowaniu generatora liczb losowych za pomocą srand(time(NULL)) w funkcji main.

cpp

void generujLosowe(int tab[], int n, int max_wartosc) {
    for (int i = 0; i < n; i++) {
        tab[i] = rand() % (max_wartosc + 1);
    }
}

Kluczowe wskazówki na kolokwium

Złożoność: Sortowanie bąbelkowe ma złożoność $O(n^2)$ . Dla bardzo dużych tablic (np. 100 000 elementów) będzie bardzo wolne, ale na potrzeby kolokwium (tablice rzędu 100-1000 elementów) jest wystarczające.
Warunek wyjścia: W wyszukiwaniu liniowym zawsze pamiętaj o zwróceniu wartości sygnalizującej błąd (zazwyczaj -1), gdy pętla skończy się bez znalezienia wyniku.
Zakresy pętli: W sortowaniu bąbelkowym wewnętrzna pętla powinna kończyć się na n - i - 1, ponieważ po każdej pełnej iteracji największy element „wypływa” na koniec i nie musi być już sprawdzany.

Zadanie kontrolne:

Spróbuj napisać funkcję, która generuje ciąg Fibonacciego do tablicy o rozmiarze N. Pamiętaj: tab[i] = tab[i-1] + tab[i-2].

Podstawowe algorytmy: Fundament logiki programowania

1. Kopiowanie tablic

Ponieważ tablic nie można kopiować operatorem przypisania (tab1 = tab2), musimy przejść przez każdy element z osobna.

cpp

void kopiujTablice(int zrodlo[], int cel[], int rozmiar) {
    for (int i = 0; i < rozmiar; i++) {
        cel[i] = zrodlo[i];
    }
}

2. Wyszukiwanie (Linear Search)

Najprostszą metodą znalezienia elementu w nieposortowanej tablicy jest przeszukiwanie liniowe. Funkcja powinna zwracać indeks znalezionego elementu lub -1, jeśli element nie istnieje.

cpp

int znajdzElement(int tab[], int rozmiar, int szukana) {
    for (int i = 0; i < rozmiar; i++) {
        if (tab[i] == szukana) return i; // Znaleziono!
    }
    return -1; // Nie ma w tablicy
}

3. Sortowanie bąbelkowe (Bubble Sort)

cpp

void sortowanieBabelkowe(int tab[], int n) {
    for (int i = 0; i < n - 1; i++) {
        for (int j = 0; j < n - i - 1; j++) {
            if (tab[j] > tab[j + 1]) {
                // Zamiana (Swap)
                int temp = tab[j];
                tab[j] = tab[j + 1];
                tab[j + 1] = temp;
            }
        }
    }
}

4. Generowanie ciągów

Ciąg arytmetyczny

Każdy kolejny element różni się o stałą wartość r.

cpp

void generujArytmetyczny(int tab[], int n, int start, int r) {
    for (int i = 0; i < n; i++) {
        tab[i] = start + i * r;
    }
}

Ciąg losowy (używając <cstdlib> i <ctime>)

Pamiętaj o zainicjowaniu generatora liczb losowych za pomocą srand(time(NULL)) w funkcji main.

cpp

void generujLosowe(int tab[], int n, int max_wartosc) {
    for (int i = 0; i < n; i++) {
        tab[i] = rand() % (max_wartosc + 1);
    }
}

Kluczowe wskazówki na kolokwium

Złożoność: Sortowanie bąbelkowe ma złożoność $O(n^2)$ . Dla bardzo dużych tablic (np. 100 000 elementów) będzie bardzo wolne, ale na potrzeby kolokwium (tablice rzędu 100-1000 elementów) jest wystarczające.
Warunek wyjścia: W wyszukiwaniu liniowym zawsze pamiętaj o zwróceniu wartości sygnalizującej błąd (zazwyczaj -1), gdy pętla skończy się bez znalezienia wyniku.
Zakresy pętli: W sortowaniu bąbelkowym wewnętrzna pętla powinna kończyć się na n - i - 1, ponieważ po każdej pełnej iteracji największy element „wypływa” na koniec i nie musi być już sprawdzany.

Zadanie kontrolne:

Spróbuj napisać funkcję, która generuje ciąg Fibonacciego do tablicy o rozmiarze N. Pamiętaj: tab[i] = tab[i-1] + tab[i-2].

Etap 7: Podstawowe algorytmy w C++ - Implementacja ręczna

Podstawowe algorytmy: Fundament logiki programowania

1. Kopiowanie tablic

2. Wyszukiwanie (Linear Search)

3. Sortowanie bąbelkowe (Bubble Sort)

4. Generowanie ciągów

Ciąg arytmetyczny

Ciąg losowy (używając <cstdlib> i <ctime>)

Kluczowe wskazówki na kolokwium

Zadanie kontrolne:

Może Cię zainteresować

Etap 8: Podstawowe funkcje matematyczne z biblioteki <cmath>

Etap 5: Referencje i referencje jako parametry funkcji

Etap 1: Podstawowe typy danych w C++ - Kompendium

Etap 7: Podstawowe algorytmy w C++ - Implementacja ręczna

Podstawowe algorytmy: Fundament logiki programowania

1. Kopiowanie tablic

2. Wyszukiwanie (Linear Search)

3. Sortowanie bąbelkowe (Bubble Sort)

4. Generowanie ciągów

Ciąg arytmetyczny

Ciąg losowy (używając <cstdlib> i <ctime>)

Kluczowe wskazówki na kolokwium

Zadanie kontrolne:

Może Cię zainteresować

Etap 8: Podstawowe funkcje matematyczne z biblioteki <cmath>

Etap 5: Referencje i referencje jako parametry funkcji

Etap 1: Podstawowe typy danych w C++ - Kompendium