Informatyka 2

Nowa edycja
Zmień podręcznik

FilmProgramowanie w C++. Sortowanie przez wstawianie

Film omawia sortowanie przez wstawianie oraz procedurę wstawiania danego elementu do posortowanej tablicy i jej realizację w C++.

Ćwiczenie 0

Zdefiniuj funkcję trzy(int a, int b, int c), której wynikiem jest największa z trzech liczb podanych jako parametr. Sprawdź działanie funkcji dla podanych poniżej parametrów.

  • Wynikiem funkcji trzy(1, 9, 12) jest 12.
  • Wynikiem funkcji trzy(13, 4, 12) jest 13.

Wskazówka
Na początku za największą liczbę przyjmuje się pierwszą z trzech liczb podanych jako parametr. Następnie bada się, czy druga z liczb jest większa od niej, jeśli tak, to za największą przyjmuje się drugą liczbę. Następnie bada się, czy trzecia z liczb jest większa od niej, jeśli tak, to za największą przyjmuje się trzecią liczbę.

#include <iostream> using namespace std; // zdefiniuj funkcję int trzy(int a, int b, int c) { } int main() { // sprawdź działanie funkcji cout << trzy(1, 9, 12) << " " << trzy(13, 4, 12) << endl;     return 0; }
Wynikiem funkcji trzy(10, 10, 10) jest 10
return trzy(10, 10, 10)==10;
10
trzy(10, 10, 10)
Wynikiem funkcji trzy(112, 99, 112) jest 112
return trzy(112, 99, 112)==112;
112
trzy(112, 99, 112)
Wynikiem funkcji trzy(456, 456, 455) jest 456
return trzy(456, 456, 455)==456;
456
trzy(456, 456, 455)
Rozwiąż ćwiczenie

Ćwiczenie 1Losowa tablica liczb

Zdefiniuj funkcję losuj(int a, int b) służącą do generowania wartości losowych z podanego zakresu <a, b> i zapisywania ich w 25-elementowej tablicy oraz funkcję wypisz(), która będzie wypisywała wszystkie elementy tablicy.

#include <iostream> #include <cstdlib> #include <ctime> using namespace std; // zdefiniuj funkcję void losuj(int a, int b) { } // zdefiniuj funkcję void wypisz() { } int main() { // sprawdź działanie funkcji losuj(1, 10); wypisz();     return 0; }
Rozwiąż ćwiczenie

Ćwiczenie 2Bąbelek

Porównaj kolejne pary elementów tablicy (pierwszy z drugim, drugi z trzecim itd.). Jeśli pierwszy z nich jest większy niż drugi, to zamień je miejscami. Przeanalizuj dane (czy widzisz pewną prawidłowość w tablicy wynikowej?) i zdefiniowaną poniżej funkcję babelek(), po której wywołaniu zostanie zmodyfikowana dana tablica liczb. Następnie znajdź i popraw błąd w funkcji.

  • Wynikiem funkcji dla int tab[5] = {16, 5, 12, 3, 12} jest {5, 12, 3, 12, 16}.
  • Wynikiem funkcji dla int tab[7] = {1, 16, 18, 3, 16, 9, 9} jest {1, 16, 3, 16, 9, 9, 18}.
#include <iostream> using namespace std; const int N = 7; int tab [N] = {1, 16, 18, 3, 16, 9, 9}; // zdefiniuj funkcję void wypisz() { for (int i = 0; i < N; i++) cout << tab[i] << " "; cout << endl; } // zdefiniuj funkcję void babelek() { for (int i = 0; i < N - 1 ; i++) if (tab[i] < tab[i + 1]) swap(tab[i], tab [i + 1]); } int main() { wypisz(); babelek(); wypisz(); return 0; }
Rozwiąż ćwiczenie

Ćwiczenie 3Sortowanie bąbelkowe

Zdefiniuj funkcję sort_b(), po której wywołaniu dana tablica liczb zostanie posortowana metodą bąbelkową w porządku rosnącym. Sprawdź działanie funkcji dla podanych poniżej parametrów.

  • Wynikiem funkcji dla int tab[5] = {6, 3, 15, 9, 2} jest {2, 3, 6, 9, 15}.
  • Wynikiem funkcji dla int tab[7] = {11, 16, 8, 33, 6, 8, 1} jest {1, 6, 8, 8, 11, 16, 33}.
#include <iostream> using namespace std; // zdefiniuj funkcję void babelek() { } // zdefiniuj funkcję void wypisz() { } // zdefiniuj funkcję void sort_b() { } int main() { // sprawdź działanie funkcji sort_b(); wypisz();     return 0; }
Rozwiąż ćwiczenie

Ćwiczenie 4Wstawianie elementów

Zdefiniuj funkcję wstawianie(int x) wstawiającą odpowiednio parametr x będący liczbą całkowitą do posortowanej tablicy. Sprawdź działanie funkcji dla podanych poniżej parametrów.

  • Wynikiem funkcji dla
    int tab[6] = {6, 13, 15, 19, 22, 0} i wstawianie(18)  jest {6, 13, 15, 18, 19, 22}.
  • Wynikiem funkcji dla
    int tab[6] = {1, 9, 12, 33, 46, 0} i wstawianie(57) jest [1, 9, 12, 33, 46, 57].
#include <iostream> using namespace std; // zdefiniuj funkcję void wstawianie(int x) { } // zdefiniuj funkcję void wypisz() { } int main() { // sprawdź działanie funkcji wstawianie(18); wypisz();     return 0; }
Rozwiąż ćwiczenie

Ćwiczenie 5Sortowanie przez wstawianie

Uzupełnij definicję funkcji sort_w(), po której uruchomieniu tablica tab zostanie posortowana metodą przez wstawianie w porządku rosnącym. Sprawdź działanie funkcji dla podanych poniżej parametrów.

  • Wynikiem funkcji dla int tab[5] = {6, 3, 15, 9, 2} jest {2, 3, 6, 9, 15}.
  • Wynikiem funkcji dla int tab[7] = {11, 16, 8, 33, 6, 8, 1} jest {1, 6, 8, 8, 11, 16, 33}.
#include <iostream> using namespace std; const int N = 7; int tab[N] = {11, 16, 8, 33, 6, 8, 1}; void sort_w() { for(int j = N - 2; j >= 0; j--) { int x = tab[j]; int i = j + 1; while((i < N) and (x > tab[i])) { tab[i - 1] = tab[i]; i++; } tab[i - 1] = x; } } // zdefiniuj funkcję void wypisz() { } int main() { // sprawdź działanie funkcji wypisz(); sort_w(); wypisz(); return 0; }
Rozwiąż ćwiczenie

Ćwiczenie dodatkowe 1

Zdefiniuj funkcję minimum(int liczba), której wynikiem będzie najmniejsza cyfra liczby podanej jako parametr. Parametrem jest co najmniej dwucyfrowa liczba całkowita dodatnia. Sprawdź działanie funkcji dla podanych poniżej parametrów.

  • Wynikiem minimum(19) jest 1.
  • Wynikiem minimum(98989) jest 8.
#include <iostream> using namespace std; // zdefiniuj funkcję int minimum(int liczba) { } int main() { // sprawdź działanie funkcji cout << minimum(19) << " " << minimum(98989) << endl;     return 0; }
Wynikiem funkcji minimum(777777777) jest 7
return minimum(777777777)==7;
7
minimum(777777777)
Wynikiem funkcji minimum(9876543210) jest 0
return minimum(9876543210)==0;
0
minimum(9876543210)
Wynikiem funkcji minimum(12345678987654321) jest 1
return minimum(12345678987654321)==1;
1
minimum(12345678987654321)
Rozwiąż ćwiczenie

Zadanie 1Zliczanie

Zdefiniuj funkcję ile_liczb(), której wynikiem jest liczba różnych liczb w tablicy podanej jako parametr. Parametrem jest niepusta tablica co najwyżej 100 liczb z zakresu od 0 do 10. Sprawdź działanie funkcji dla podanych poniżej parametrów.

  • Wynikiem funkcji ile_liczb() dla tablicy {4, 1, 1, 4} jest 2.
  • Wynikiem funkcji ile_liczb() dla tablicy {6, 6, 3, 7, 1, 7, 4, 4, 0, 3} jest 6.
#include <iostream> using namespace std; // zdefiniuj funkcję int ile_liczb() { } int main() { // sprawdź działanie funkcji cout << ile_liczb();     return 0; }
Rozwiąż ćwiczenie

Pytania quizoweSortowanie bąbelkowe i przez wstawianie

Twój wynik to: /3
  • W programie zadeklarowano tablicę int tab[5] = {-3, 4, -12, 0, 3}. Jaką wartość ma element o indeksie 3?
  • W programie wykonano poniższe operacje.

    int x, y;
    x = 5; y = 3;
    x = y; y = x;
    Ile wynoszą wartości zmiennych x i y ?

  • W programie zadeklarowano tablicę int tab[5] = {-3, 4, -12, 0, 3} oraz wykonano operację tab[1] = tab[0]. Jaką wartość ma pierwszy element tablicy?
Sprawdź wynik