myślenie algorytmiczne. jak rozwiązywać problemy za pomocą algorytmów cała książka.pdf

(4850 KB) Pobierz
Tytuł oryginału: Algorithmic Thinking: A Problem-Based Introduction
Tłumaczenie: Piotr Rajca
ISBN: 978-83-283-8335-7
Copyright © 2021 by Daniel Zingaro. Title of English-language original: Algorithmic Thinking: A Problem
Based Introduction, ISBN 9781718500808 published by No Starch Press Inc. 245 8th Street, San Francisco,
California United States 94103. The Polish-language edition Copyright © 2022 by Helion S.A. under license
by No Starch Press Inc. All rights reserved.
All rights reserved. No part of this book may be reproduced or transmitted in any form or by any means,
electronic or mechanical, including photocopying, recording or by any information storage retrieval
system, without permission from the Publisher.
Wszelkie prawa zastrzeżone. Nieautoryzowane rozpowszechnianie całości lub fragmentu niniejszej
publikacji w jakiejkolwiek postaci jest zabronione. Wykonywanie kopii metodą kserograficzną,
fotograficzną, a także kopiowanie książki na nośniku filmowym, magnetycznym lub innym powoduje
naruszenie praw autorskich niniejszej publikacji.
Wszystkie znaki występujące w tekście są zastrzeżonymi znakami firmowymi bądź towarowymi
ich właścicieli.
Autor oraz wydawca dołożyli wszelkich starań, by zawarte w tej książce informacje były kompletne
i rzetelne. Nie biorą jednak żadnej odpowiedzialności ani za ich wykorzystanie, ani za związane z tym
ewentualne naruszenie praw patentowych lub autorskich. Autor oraz wydawca nie ponoszą również
żadnej odpowiedzialności za ewentualne szkody wynikłe z wykorzystania informacji zawartych w książce.
Drogi Czytelniku!
Jeżeli chcesz ocenić tę książkę, zajrzyj pod adres
https://helion.pl/user/opinie/algwro
Możesz tam wpisać swoje uwagi, spostrzeżenia, recenzję.
Pliki z przykładami omawianymi w książce można znaleźć pod adresem:
https://ftp.helion.pl/przyklady/algwro.zip
Helion S.A.
ul. Kościuszki 1c, 44-100 Gliwice
tel. 32 231 22 19, 32 230 98 63
e-mail:
helion@helion.pl
WWW:
https://helion.pl
(księgarnia internetowa, katalog książek)
Printed in Poland.
•
Kup książkę
•
Poleć książkę
•
Oceń książkę
•
Księgarnia internetowa
•
Lubię to! » Nasza społeczność
Spis treści
PRZEDMOWA ...............................................................................................................................................13
PODZIĘKOWANIA .......................................................................................................................................15
WPROWADZENIE ........................................................................................................................................17
Zasoby internetowe ................................................................................................................................................ 18
Dla kogo jest przeznaczona ta książka ............................................................................................................ 18
Język programowania ............................................................................................................................................. 19
Dlaczego wybrałem język C? ................................................................................................................................... 19
Słowo kluczowe static ................................................................................................................................................ 19
Pliki nagłówkowe ......................................................................................................................................................... 20
Zwalnianie pamięci ..................................................................................................................................................... 21
Zagadnienia ............................................................................................................................................................... 21
Witryny oceniające .................................................................................................................................................. 22
Anatomia opisu problemu .................................................................................................................................... 25
Problem: Kolejki po jedzenie ............................................................................................................................... 26
Problem ........................................................................................................................................................................... 26
Rozwiązanie problemu .............................................................................................................................................. 27
Uwagi ............................................................................................................................................................................ 29
1
TABLICE MIESZAJĄCE ................................................................................................................................30
Problem 1. Płatki śniegu ....................................................................................................................................... 30
Problem ........................................................................................................................................................................... 30
Uproszczenie problemu ............................................................................................................................................. 33
Rozwiązywanie podstawowego problemu ......................................................................................................... 34
Rozwiązanie 1. Porównywanie parami ................................................................................................................ 38
Rozwiązanie 2. Zmniejszenie liczby wykonywanych operacji ..................................................................... 43
Tablice mieszające .................................................................................................................................................. 49
Projekt tablicy mieszającej ....................................................................................................................................... 49
Dlaczego warto używać tablic mieszających? .................................................................................................. 52
Kup książkę
Poleć książkę
Problem 2. Słowa złożone .................................................................................................................................... 52
Problem ........................................................................................................................................................................... 53
Wskazywanie słów złożonych ................................................................................................................................. 53
Rozwiązanie ................................................................................................................................................................... 54
Problem 3. Sprawdzanie pisowni — usuwanie litery ................................................................................ 58
Problem ........................................................................................................................................................................... 59
Rozważania o zastosowaniu tablic mieszających ............................................................................................ 60
Rozwiązanie doraźne .................................................................................................................................................. 62
Podsumowanie ......................................................................................................................................................... 65
Uwagi ............................................................................................................................................................................ 66
2
DRZEWA I REKURENCJA ...........................................................................................................................67
Problem 1. Halloweenowy łup ............................................................................................................................ 67
Problem ........................................................................................................................................................................... 68
Drzewa binarne ............................................................................................................................................................. 69
Rozwiązywanie problemu dla przykładowego drzewa ................................................................................... 71
Reprezentacja drzew binarnych ............................................................................................................................. 72
Zbieranie wszystkich cukierków ............................................................................................................................. 77
Zupełnie inne rozwiązanie ........................................................................................................................................ 84
Przechodzenie minimalnej liczby ulic .................................................................................................................. 90
Odczyt danych wejściowych .................................................................................................................................... 93
Dlaczego korzystać z rekurencji? .................................................................................................................... 100
Problem 2. Odległość pomiędzy potomkami ............................................................................................. 101
Problem ........................................................................................................................................................................ 101
Odczyt danych wejściowych ................................................................................................................................. 104
Liczba potomków w odległości d od wierzchołka ......................................................................................... 108
Liczba potomków dla wszystkich wierzchołków ............................................................................................ 110
Sortowanie wierzchołków ...................................................................................................................................... 111
Wyświetlanie wyników ........................................................................................................................................... 112
Funkcja main .............................................................................................................................................................. 113
Podsumowanie ...................................................................................................................................................... 114
Uwagi ......................................................................................................................................................................... 114
3
MEMOIZACJA I PROGRAMOWANIE DYNAMICZNE ........................................................................ 115
Problem 1. Burgerowa gorączka ..................................................................................................................... 115
Problem ........................................................................................................................................................................ 116
Określenie planu rozwiązania problemu .......................................................................................................... 116
Określanie optymalnego rozwiązania ............................................................................................................... 118
Rozwiązanie 1. Zastosowanie rekurencji .......................................................................................................... 120
Rozwiązanie 2. Memoizacja .................................................................................................................................. 126
Rozwiązanie 3. Programowanie dynamiczne ................................................................................................. 132
6
Spis tre
ś
ci
Kup książkę
Poleć książkę
Memoizacja i programowanie dynamiczne ................................................................................................ 136
Krok 1. Struktura optymalnego rozwiązania ................................................................................................... 136
Krok 2. Rozwiązanie rekurencyjne ...................................................................................................................... 137
Krok 3. Memoizacja .................................................................................................................................................. 137
Krok 4. Programowanie dynamiczne ................................................................................................................. 138
Problem 2. Skąpcy ................................................................................................................................................ 139
Problem ........................................................................................................................................................................ 139
Określanie optymalnego rozwiązania ............................................................................................................... 141
Rozwiązanie 1. Rekurencja .................................................................................................................................... 143
Funkcja main .............................................................................................................................................................. 148
Rozwiązanie 2. Memoizacja .................................................................................................................................. 149
Problem 3. Rywalizacja hokejowa .................................................................................................................. 152
Problem ........................................................................................................................................................................ 152
Rozważania dotyczące rywalizacji ...................................................................................................................... 153
Określenie optymalnego rozwiązania ............................................................................................................... 155
Rozwiązanie 1. Rekurencja .................................................................................................................................... 158
Rozwiązanie 2. Memoizacja .................................................................................................................................. 161
Rozwiązanie 3. Programowanie dynamiczne ................................................................................................. 163
Optymalizacja zużycia pamięci ........................................................................................................................... 166
Problem 4. Sposoby zaliczenia ........................................................................................................................ 167
Problem ........................................................................................................................................................................ 168
Rozwiązanie: memoizacja ..................................................................................................................................... 168
Podsumowanie ...................................................................................................................................................... 170
Uwagi ......................................................................................................................................................................... 170
4
GRAFY I PRZESZUKIWANIE WSZERZ ................................................................................................. 171
Problem 1. Pogoń skoczka ................................................................................................................................. 171
Problem ........................................................................................................................................................................ 172
Optymalne ruchy skoczka ...................................................................................................................................... 174
Najlepszy wynik skoczka ........................................................................................................................................ 184
Przesunięcie i powrót skoczka .............................................................................................................................. 186
Optymalizacja czasu działania ............................................................................................................................. 189
Grafy i przeszukiwanie wszerz ......................................................................................................................... 190
Czym są grafy? ........................................................................................................................................................... 191
Grafy a drzewa ........................................................................................................................................................... 192
Algorytm BFS na grafach ....................................................................................................................................... 194
Problem 2. Wspinaczka po linie ...................................................................................................................... 195
Problem ........................................................................................................................................................................ 195
Rozwiązanie 1. Poszukiwanie ruchów ............................................................................................................... 196
Rozwiązanie 2. Nowy model ................................................................................................................................. 202
Problem 3. Tłumaczenie książek ..................................................................................................................... 212
Problem ........................................................................................................................................................................ 212
Budowanie grafu ....................................................................................................................................................... 213
Spis tre
ś
ci
7
Kup książkę
Poleć książkę

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika:

Zgłoś jeśli naruszono regulamin