Algorytmika dla studenta i technika programisty INF.04 Jerzy Kluczewski

Spis treści ebooka

1 PRZEDMOWA ........................................................................................ 13
1.1 TWOJE OCZEKIWANE UMIEJĘTNOŚCI ............................................................ 13
1.2 FORMUŁA 2019 DLA KWALIFIKACJI INF.04 .................................................. 14
1.3 FORMUŁA 2023 DLA PRZEDMIOTU INFORMATYKA ......................................... 14
1.4 PRZYJĘTE SKRÓTY I MNEMONIKI W KSIĄŻCE ................................................... 16
1.5 PRZEGLĄD PROGRAMÓW DO TWORZENIA SCHEMATÓW BLOKOWYCH ................ 16
1.6 JAKIE ALGORYTMY ZNAJDZIESZ W TEJ KSIĄŻCE ................................................ 17
1.7 ZAŁOŻENIA DOTYCZĄCE REALIZACJI ALGORYTMÓW ......................................... 19
1.8 JAKICH ALGORYTMÓW NIE ZNAJDZIESZ TUTAJ ................................................ 19
2 WSTĘP ................................................................................................... 23
2.1 WYMAGANE OPROGRAMOWANIE ............................................................... 23
2.2 POBIERANIE PROGRAMU MAGICZNE BLOCZKI ........................................... 23
2.3 INSTALOWANIE PROGRAMU MAGICZNE BLOCZKI ....................................... 25
2.4 POBIERANIE ŚRODOWISKA VISUAL STUDIO 2022 ........................................... 31
2.5 INSTALOWANIE ŚRODOWISKA VISUAL STUDIO 2022 ....................................... 33
2.6 PIERWSZE URUCHOMIENIE ŚRODOWISKA VISUAL STUDIO 2022 ....................... 37
2.7 OGÓLNY SCHEMAT PROGRAMÓW PRZYJĘTY W KSIĄŻCE ................................... 43
2.8 UWAGI DO SCHEMATU PROGRAMU ............................................................. 44
2.9 PLIKI DO ZADAŃ I ĆWICZEŃ ......................................................................... 44
3 WPROWADZENIE DO ALGORYTMÓW I PROGRAMOWANIA ................... 47
3.1 PRZYKŁADY ALGORYTMÓW I ICH REPREZENTACJI ............................................ 47
3.2 DEFINICJA ALGORYTMU ............................................................................. 50
3.3 PRZYKŁADOWE ALGORYTMY ....................................................................... 50
3.4 ZASADY PROJEKTOWANIA ALGORYTMÓW I PROGRAMÓW ................................ 53
3.5 ELEMENTY SCHEMATU BLOKOWEGO ............................................................ 57
3.6 KONSTRUOWANIE PĘTLI ZA POMOCĄ SCHEMATÓW BLOKOWYCH ...................... 60
3.7 SCHEMAT BLOKOWY - ZALETY I WADY ........................................................... 64
3.8 PSEUDOKOD - ZALETY I WADY ..................................................................... 64
3.9 JĘZYK PROGRAMOWANIA - ZALETY I WADY .................................................... 65
3.10 NOTACJA ZAPISU W PSEUDOKODZIE ......................................................... 65
3.11 PRZYKŁADY ZAPISU ALGORYTMÓW W PSEUDOKODZIE .................................. 69
3.12 ODPOWIEDNIKI ANGIELSKIE SŁÓW KLUCZOWYCH ........................................ 71
3.13 INDEKSOWANIE TABLIC .......................................................................... 72
3.14 WCZYTYWANIE DANYCH WEJŚCIOWYCH .................................................... 74
3.15 PRZETWARZANIE DANYCH ....................................................................... 76
3.16 WYŚWIETLANIE WYNIKÓW ..................................................................... 77
3.17 IMPLEMENTACJA ALGORYTMÓW .............................................................. 78
3.18 OPERACJE WEJŚCIA/WYJŚCIA W MAGICZNYCH BLOCZKACH I C# .................... 78
3.19 STRUKTURY DANYCH STOSOWANE W JĘZYKU C# ......................................... 88
4 KLASYFIKACJA ALGORYTMÓW ............................................................... 91
4.1 KLASYFIKACJA ALGORYTMÓW ZE WZGLĘDU NA ICH CEL ORAZ CECHY
IMPLEMENTACYJNE .............................................................................................. 91
4.2 KLASYFIKACJA ZE WZGLĘDU NA KOLEJNOŚĆ WYKONYWANYCH OPERACJI ............. 96
4.3 KLASYFIKACJA ZE WZGLĘDU NA SPOSÓB WYKONYWANIA OPERACJI .................... 99
4.4 KLASYFIKACJA ZE WZGLĘDU NA OBSZAR ZASTOSOWAŃ .................................. 103
4.5 KLASYFIKACJA ALGORYTMÓW PRZYJĘTA W KSIĄŻCE ....................................... 103
4.6 WZÓR OPISU ALGORYTMU ZASTOSOWANY W KSIĄŻCE ................................... 103
5 STRUKTURY DANYCH I FUNKCJE .......................................................... 107
5.1 PODSTAWOWE TYPY DANYCH W JĘZYKU C# ................................................. 107
5.2 ZŁOŻONE STRUKTURY DANYCH .................................................................. 109
5.3 TABLICE ................................................................................................ 110
5.4 TABLICA JAKO OBIEKT ARRAY .................................................................... 111
5.5 PODSTAWOWE METODY KLASY ARRAY ....................................................... 113
5.6 TABLICA JAKO LISTA ................................................................................ 114
5.7 KLASA LIST ............................................................................................ 118
5.8 PODSTAWOWE METODY KLASY LIST ........................................................... 121
5.9 TABLICA JAKO STOS ................................................................................. 122
5.10 TABLICA JAKO STOS – PODSTAWOWA OBSŁUGA ........................................ 127
5.11 KLASA STACK...................................................................................... 131
5.12 PODSTAWOWE METODY KLASY STACK .................................................... 134
5.13 FUNKCJE JAKO CZĘŚCI ALGORYTMU (PROGRAMU) ..................................... 134
5.14 FUNKCJE BEZ PARAMETRÓW ................................................................. 136
5.15 FUNKCJE Z PARAMETRAMI .................................................................... 137
5.16 PRZEKAZYWANIE PARAMETRU PRZEZ WARTOŚĆ ........................................ 137
5.17 PRZEKAZYWANIE PARAMETRU PRZEZ REFERENCJĘ ..................................... 140
5.18 PRAKTYCZNE ZASTOSOWANIE REFERENCJI ................................................ 143
5.19 STRUKTURA NUMERU PESEL ................................................................ 144
5.20 RÓŻNICA MIĘDZY ITERACJĄ I REKURENCJĄ ................................................ 154
6 ALGORYTMY LINIOWE ......................................................................... 161
6.1 CO TO JEST ALGORYTM LINIOWY? .............................................................. 161
6.2 SUMOWANIE CZTERECH LICZB ................................................................... 161
6.3 SUMOWANIE OŚMIU TEKSTÓW ................................................................. 163
6.4 OBLICZANIE KWADRATU RÓŻNICY DWÓCH LICZB .......................................... 166
6.5 OBLICZANIE PROCENTU ............................................................................ 167
6.6 OBLICZANIE POLA I OBWODU PROSTOKĄTA ................................................. 170
6.7 WZÓR HERONA ...................................................................................... 172
6.8 OBLICZANIE OBJĘTOŚCI WALCA ................................................................. 174
6.9 OBLICZANIE OBJĘTOŚCI KULI ..................................................................... 176
6.10 OBLICZANIE OBJĘTOŚCI BECZKI .............................................................. 178
6.11 KAPITALIZACJA ODSETEK ....................................................................... 180
7 ALGORYTMY ARYTMETYCZNE .............................................................. 187
7.1 OBLICZANIE WARTOŚCI BEZWZGLĘDNEJ ...................................................... 187
7.2 SPRAWDZANIE KTÓRA LICZBA JEST WIĘKSZA ................................................ 188
7.3 SPRAWDZANIE CZY LICZBA JEST PARZYSTA ................................................... 190
7.4 SPRAWDZANIE, CZY LICZBA ISTNIEJE W ZBIORZE ............................................ 191
7.5 PORZĄDKOWANIE 3 LICZB ........................................................................ 193
7.6 POTĘGOWANIE LICZB NATURALNYCH .......................................................... 196
7.7 ROZWIĄZYWANIE RÓWNANIA LINIOWEGO .................................................. 198
7.8 ROZWIĄZYWANIE RÓWNANIA KWADRATOWEGO .......................................... 200
7.9 ROZWIĄZYWANIE UKŁADU RÓWNAŃ LINIOWYCH .......................................... 204
7.10 SCHEMAT HORNERA ............................................................................ 206
7.11 WYZNACZANIE NWD ZA POMOCĄ ODEJMOWANIA ................................... 210
7.12 ALGORYTM EUKLIDESA WYZNACZANIA NWD ZA POMOCĄ DZIELENIA ........... 211
7.13 ALGORYTM EUKLIDESA WYZNACZANIA NWD (WERSJA REKURENCYJNA) ....... 214
7.14 WYZNACZANIE NWW ZA POMOCĄ NWD .............................................. 216
7.15 WYDAWANIE RESZTY NAJMNIEJSZĄ LICZBĄ NOMINAŁÓW (V.1) ................... 219
7.16 WYDAWANIE RESZTY NAJMNIEJSZĄ LICZBĄ NOMINAŁÓW (V.2) ................... 221
7.17 DWÓJKOWA REPREZENTACJA LICZBY DZIESIĘTNEJ ...................................... 223
7.18 ÓSEMKOWA REPREZENTACJA LICZBY DZIESIĘTNEJ ...................................... 224
7.19 SZESNASTKOWA REPREZENTACJA LICZBY DZIESIĘTNEJ ................................. 226
7.20 ZAMIANA LICZBY BINARNEJ NA DZIESIĘTNĄ .............................................. 229
7.21 POZYCYJNE REPREZENTACJE LICZBY DZIESIĘTNEJ ........................................ 230
7.22 ZAMIANA LICZBY ARABSKIEJ NA RZYMSKĄ ................................................ 233
7.23 ZAMIANA LICZBY RZYMSKIEJ NA ARABSKĄ ................................................ 237
7.24 SUMOWANIE CYFR Z LICZBY .................................................................. 239
7.25 ZAMIANA ADRESU IPV4 NA POSTAĆ BINARNĄ .......................................... 241
7.26 LICZBA PIERWSZA ................................................................................ 243
7.27 BADANIE PIERWSZOŚCI LICZBY ............................................................... 246
7.28 CIĄG ARYTMETYCZNY ........................................................................... 247
7.29 CIĄG GEOMETRYCZNY .......................................................................... 249
7.30 OBLICZANIE ŚREDNIEJ ZBIORU ............................................................... 251
7.31 WYODRĘBNIANIE CYFR Z LICZBY NATURALNEJ ........................................... 253
7.32 CIĄG FIBONACCIEGO (METODA ITERACYJNA) ........................................... 255
7.33 CIĄG FIBONACCIEGO (METODA REKURENCYJNA) ....................................... 258
7.34 OBLICZANIE SILNI (METODA ITERACYJNA) ................................................ 259
7.35 OBLICZANIE SILNI (METODA REKURENCYJNA) ........................................... 261
7.36 OBLICZANIE DWUSILNI ......................................................................... 263
7.37 METODA POŁOWIENIA PRZEDZIAŁU ........................................................ 265
7.38 SZUKANIE ELEMENTU MINIMALNEGO W TABLICY ...................................... 270
7.39 SZUKANIE ELEMENTU MAKSYMALNEGO W TABLICY ................................... 271
7.40 SZUKANIE ELEMENTU MINIMALNEGO I MAKSYMALNEGO W TABLICY ............. 273
7.41 PUNKTY KRATOWE .............................................................................. 277
7.42 PUNKTY KRATOWE (WERSJA OPTYMALNA) ............................................... 279
8 ALGORYTMY ZNAKOWO-TEKSTOWE .................................................... 285
8.1 CO TO JEST ALGORYTM ZNAKOWO-TEKSTOWY? ........................................... 285
8.2 DOPISYWANIE ZNAKÓW NA KOŃCU TEKSTU ................................................. 285
8.3 DOPISYWANIE ZNAKÓW NA POCZĄTKU TEKSTU ............................................ 286
8.4 NAPRZEMIENNOŚĆ WIELKICH I MAŁYCH LITER .............................................. 288
8.5 WYSZUKIWANIE WZORCA W TEKŚCIE METODĄ NAIWNĄ ................................ 290
8.6 SPRAWDZANIE CZY TEKST JEST PALINDROMEM ............................................. 292
9 OPERACJE PLIKOWE ............................................................................. 299
9.1 JAK MOŻNA WYKONYWAĆ OPERACJE NA PLIKACH? ....................................... 299
9.2 ODCZYT DANYCH Z PLIKU ......................................................................... 299
9.3 ZAPIS DANYCH DO PLIKU .......................................................................... 301
9.4 PROSTE OPERACJE NA PLIKU ..................................................................... 303
9.5 CZYTANIE DANYCH Z PLIKU ....................................................................... 305
9.6 WSTĘPNE PRZETWARZANIE DANYCH Z PLIKU ................................................ 307
9.7 PORZĄDKOWANIE PŁASKIEJ BAZY DANYCH ................................................... 310
10 ALGORYTMY SORTUJĄCE ..................................................................... 321
10.1 CO TO JEST SORTOWANIE I JAKIE SĄ ALGORYTMY DO SORTOWANIA? ............ 321
10.2 SORTOWANIE ZWARIOWANE (BOGO-SORT) .......................................... 322
10.3 SORTOWANIE GŁUPIE (STUPID-SORT) .................................................. 325
10.4 SORTOWANIE METODĄ WSTAWIANIA (INSERTION-SORT) ...................... 328
10.5 SORTOWANIE METODĄ BĄBELKOWĄ (BUBBLE-SORT) ............................. 331
10.6 SORTOWANIE METODĄ WYMIANY (SELECTION-SORT) ........................... 334
10.7 SORTOWANIE METODĄ ZLICZANIA (COUNTING-SORT) ........................... 337
10.8 SORTOWANIE PRZEZ SCALANIE (MERGE-SORT) ..................................... 341
10.9 SORTOWANIE METODĄ SZYBKĄ (QUICK-SORT) ...................................... 345
10.10 SORTOWANIE KUBEŁKOWE (BUCKET-SORT).......................................... 349
10.11 SORTOWANIE KOPCOWE (HEAP-SORT) ................................................ 352
11 ALGORYTMY SZYFRUJĄCE .................................................................... 359
11.1 SZYFR CEZARA – KODOWANIE ............................................................... 359
11.2 SZYFR CEZARA – DEKODOWANIE ............................................................ 362
11.3 SZYFR CEZARA – KODOWANIE I DEKODOWANIE ........................................ 363
11.4 SZYFR PRZESTAWIENIOWY – KODOWANIE ................................................ 366
11.5 SZYFR PRZESTAWIENIOWY – DEKODOWANIE ............................................ 367
11.6 SZYFR VIGENERA – KODOWANIE ............................................................ 369
11.7 SZYFR VIGENERA – DEKODOWANIE ........................................................ 374
12 ALGORYTMY ZAAWANSOWANE .......................................................... 381
12.1 SZUKANIE BINARNE ............................................................................. 381
12.2 FAKTORYZACJA LICZBY .......................................................................... 384
12.3 SITO ERATOSTENESA ........................................................................... 388
12.4 SZYBKIE POTĘGOWANIE (METODA ITERACYJNA) ........................................ 392
12.5 SZYBKIE POTĘGOWANIE (METODA REKURENCYJNA) ................................... 394
12.6 OBLICZANIE PIERWIASTKA KWADRATOWEGO ........................................... 397
12.7 ODWROTNA NOTACJA POLSKA .............................................................. 400
12.8 PAKOWANIE PLECAKA (ALGORYTM ZACHŁANNY) ....................................... 404
12.9 SYMETRYCZNY PROBLEM KOMIWOJAŻERA ............................................... 411
13 ZŁOŻONOŚĆ OBLICZENIOWA ALGORYTMÓW ....................................... 423
13.1 ZŁOŻONOŚĆ ALGORYTMÓW SORTUJĄCYCH .............................................. 424
13.2 BADANIE SZYBKOŚCI ALGORYTMÓW SORTUJĄCYCH ................................... 424
14 PRZYKŁADOWE ZADANIA PRAKTYCZNE ............................................... 431
14.1 ZADANIE 1 (PROSTE MENU KONSOLOWE) ............................................... 431
14.2 ZADANIE 2 (SPRAWDŹ TWÓJ PESEL) ..................................................... 441
14.3 ZADANIE 3 (SORTOWANIE POJEMNIKA Z KULKAMI) ................................... 445
15 ALFABETYCZNY SPIS KATALOGÓW Z ROZWIĄZANIAMI ........................ 461
15.1 OBJAŚNIENIA DO SPISU KATALOGÓW ...................................................... 461
15.2 LISTA KATALOGÓW Z ROZWIĄZANIAMI .................................................... 462
16 BIBLIOGRAFIA I NETOGRAFIA ORAZ CYTOWANIE ................................. 469

pokaż cały spis treści

ukryj recenzje