20.x — podsumowanie rozdziału 20 i quiz

Pytanie nr 1

Napisz prototypy funkcji dla poniższych przypadków. Użyj const, jeśli/kiedy to konieczne.

a) Funkcja o nazwie max(), która przyjmuje dwie liczby podwójne i zwraca większą z nich.

Pokaż rozwiązanie

double max(double x, double y);

b) Funkcja o nazwie swap(), która zamienia dwie liczby całkowite.

Pokaż rozwiązanie

void swap(int& x, int& y);

c) Funkcja o nazwie getLargestElement(), która pobiera dynamicznie przydzieloną tablicę liczb całkowitych i zwraca największą liczbę w taki sposób, że osoba wywołująca może zmienić wartość zwrócony element (nie zapomnij o parametrze długości).

Pokaż rozwiązanie

// Note: array can't be const in this case, because returning a non-const reference to a const element would be a const violation.
int& getLargestElement(int* array, int length);

Pytanie nr 2

Co jest nie tak z tymi programami?

A)

int& doSomething()
{
    int array[]{ 1, 2, 3, 4, 5 };
    return array[3];
}

Pokaż rozwiązanie

B)

int sumTo(int value)
{
    return value + sumTo(value - 1);
}

Pokaż rozwiązanie

C)

float divide(float x, float y)
{
    return x / y;
}

double divide(float x, float y)
{
    return x / y;
}

Pokaż rozwiązanie

D)

#include <iostream>

int main()
{
    int array[100000000]{};

    for (auto x: array)
        std::cout << x << ' ';

    std::cout << '\n';

    return 0;
}

Pokaż rozwiązanie

mi)

#include <iostream>

int main(int argc, char* argv[])
{
    int age{ argv[1] };
    std::cout << "The user's age is " << age << '\n';

    return 0;
}

Pokaż rozwiązanie

Pytanie nr 3

Najlepszy algorytm sprawdzania, czy wartość istnieje w posortowanej tablicy, nazywa się wyszukiwaniem binarnym.

Wyszukiwanie binarne działa w następujący sposób:

• Spójrz na środkowy element tablicy (jeśli tablica ma parzystą liczbę elementów, zaokrąglij w dół).
• Jeśli środkowy element jest większy niż element docelowy, odrzuć górną połowę tablicy (lub wykonaj rekurs na dolną połowę)
• Jeśli środkowy element jest mniejszy niż element docelowy, odrzuć dolną połowę tablicy (lub powtórz operację na górnej połowie).
• Jeśli środkowy element jest równy element docelowy, zwróć indeks elementu centralnego.
• Jeśli odrzucisz całą tablicę bez znalezienia elementu docelowego, zwróć wskaźnik reprezentujący „nie znaleziono” (w tym przypadku użyjemy -1, ponieważ jest to nieprawidłowy indeks tablicy).

Ponieważ w każdej iteracji możemy wyrzucić połowę tablicy, algorytm ten jest bardzo szybki. Nawet w przypadku tablicy składającej się z miliona elementów wystarczy maksymalnie 20 iteracji, aby określić, czy wartość istnieje w tablicy, czy nie! Działa to jednak tylko na posortowanych tablicach.

Modyfikowanie tablicy (np. odrzucenie połowy elementów tablicy) jest kosztowne, dlatego zazwyczaj nie modyfikujemy tablicy. Zamiast tego używamy dwóch liczb całkowitych (min i max) do przechowywania indeksów minimalnego i maksymalnego elementu tablicy, którą chcemy zbadać.

Przyjrzyjmy się próbce działania tego algorytmu, biorąc pod uwagę tablicę { 3, 6, 7, 9, 12, 15, 18, 21, 24 } i wartość docelową 7. Na początku min = 0, max = 8, ponieważ przeszukujemy całą tablicę (tablica ma długość 9, więc indeks ostatniego elementu wynosi 8).

• Zaliczono 1) Obliczamy środek min (0) i max (8), czyli 4. Element nr 4 ma wartość 12, która jest większa niż nasza wartość docelowa. Ponieważ tablica jest posortowana, wiemy, że wszystkie elementy o indeksie równym lub większym od środka (4) muszą być za duże. Więc zostawiamy min w spokoju i ustawiamy max na 3.
• Zaliczony 2) Obliczamy punkt środkowy min (0) i max (3), czyli 1. Element nr 1 ma wartość 6, która jest mniejsza niż nasza wartość docelowa. Ponieważ tablica jest posortowana, wiemy, że wszystkie elementy o indeksie równym lub mniejszym od środka (1) muszą być za małe. Zatem ustawiamy min na 2, a max zostawiamy w spokoju.
• Zaliczono 3) Obliczamy punkt środkowy min (2) i max (3), czyli 2. Element nr 2 ma wartość 7, która jest naszą wartością docelową. Zwracamy więc 2.

W C++20 obliczenie punktu środkowego można wykonać poprzez wywołanie std::midpoint. Przed wersją C++20 musisz samodzielnie obliczyć punkt środkowy — w tym przypadku możesz użyć min + ((max - min) / 2) aby uniknąć przepełnienia (gdy min i max są dodatnie).

Biorąc pod uwagę następujący kod:

#include <iostream>
#include <iterator>

// array is the array to search over.
// target is the value we're trying to determine exists or not.
// min is the index of the lower bounds of the array we're searching.
// max is the index of the upper bounds of the array we're searching.
// binarySearch() should return the index of the target element if the target is found, -1 otherwise
int binarySearch(const int* array, int target, int min, int max)
{

}

int main()
{
    constexpr int array[]{ 3, 6, 8, 12, 14, 17, 20, 21, 26, 32, 36, 37, 42, 44, 48 };

    // We're going to test a bunch of values to see if the algorithm returns the result we expect

    // Here are the test values
    constexpr int testValues[]{ 0, 3, 12, 13, 22, 26, 43, 44, 48, 49 };

    // And here are the results that we expect for those test values
    int expectedResult[]{ -1, 0, 3, -1, -1, 8, -1, 13, 14, -1 };

    // Make sure we have the same number of test values and expected results
    static_assert(std::size(testValues) == std::size(expectedResult));

    int numTestValues { std::size(testValues) };
    // Loop through all of the test values
    for (int count{ 0 }; count < numTestValues; ++count)
    {
        // See if our test value is in the array
        int index{ binarySearch(array, testValues[count], 0, static_cast<int>(std::size(array)) - 1) };
        // If it matches our expected value, then great!
        if (index == expectedResult[count])
             std::cout << "test value " << testValues[count] << " passed!\n";
        else // otherwise, our binarySearch() function must be broken
             std::cout << "test value " << testValues[count] << " failed.  There's something wrong with your code!\n";
    }

    return 0;
}

a) Napisz iteracyjną wersję funkcji binarySearch.

Wskazówka: możesz bezpiecznie powiedzieć, że element docelowy nie istnieje, gdy indeks min jest większy niż maksymalny indeks.

Pokaż rozwiązanie

#include <cassert>
#include <iostream>
#include <numeric> // for std::midpoint

// array is the array to search over.
// target is the value we're trying to determine exists or not.
// min is the index of the lower bounds of the array we're searching.
// max is the index of the upper bounds of the array we're searching.
// binarySearch() should return the index of the target element if the target is found, -1 otherwise
int binarySearch(const int* array, int target, int min, int max)
{
    assert(array); // make sure array exists

    while (min <= max)
    {
        // implement this iteratively
        int midpoint{ std::midpoint(min, max) };
        // Before C++20
        // int midpoint{ min + ((max-min) / 2) }; // this way of calculating midpoint avoids overflow

        if (array[midpoint] > target)
        {
            // if array[midpoint] > target, then we know the number must be in the lower half of the array
            // we can use midpoint - 1 as the upper index, since we don't need to retest the midpoint next iteration
            max = midpoint - 1;
        }
        else if (array[midpoint] < target)
        {
            // if array[midpoint] < target, then we know the number must be in the upper half of the array
            // we can use midpoint + 1 as the lower index, since we don't need to retest the midpoint next iteration
            min = midpoint + 1;
        }
        else
        {
            return midpoint;
        }
    }
    
    return -1;
}

b) Napisz rekurencyjną wersję funkcji binarySearch.

Pokaż rozwiązanie

#include <cassert>
#include <numeric> // for std::midpoint

// array is the array to search over.
// target is the value we're trying to determine exists or not.
// min is the index of the lower bounds of the array we're searching.
// max is the index of the upper bounds of the array we're searching.
// binarySearch() should return the index of the target element if the target is found, -1 otherwise
int binarySearch(const int* array, int target, int min, int max)
{
    assert(array); // make sure array exists

    // implement this recursively

    if (min > max)
        return -1;

    int midpoint{ std::midpoint(min, max) };
    // Before C++20
    // int midpoint{ min + ((max-min) / 2) }; // this way of calculating midpoint avoids overflow

    if (array[midpoint] > target)
    {
        return binarySearch(array, target, min, midpoint - 1);
    }
    else if (array[midpoint] < target)
    {
        return binarySearch(array, target, midpoint + 1, max);
    }

    return midpoint;
}