Algorithmims for student and programers Jerzy Kluczewski

Spis treści książki

1 PREFACE ................................................................................................ 13
YOUR EXPECTED SKILLS ......................................................................................... 13
ABBREVIATIONS AND MNEMONICS IN THE BOOK ....................................................... 15
OVERVIEW OF FLOWCHART PROGRAMMES .............................................................. 16
WHAT ALGORITHMS WILL YOU FIND IN THIS BOOK ..................................................... 16
ASSUMPTIONS REGARDING THE IMPLEMENTATION OF ALGORITHMS ............................. 18
WHAT ALGORITHMS YOU WON’T FIND HERE ............................................................ 19
2 INTRODUCTION ..................................................................................... 23
REQUIRED SOFTWARE .......................................................................................... 23
DOWNLOAD THE MAGIC BLOCKS PROGRAMME ..................................................... 23
INSTALLING THE MAGIC BLOCKS /MAGICZNE BLOCZKI/ PROGRAMME ..................... 25
DOWNLOAD VISUAL STUDIO ................................................................................. 33
DOWNLOAD VISUAL STUDIO ................................................................................. 42
DOWNLOAD VISUAL STUDIO INSTALLER 2022 ......................................................... 43
2.6. THE GENERAL SCHEME OF THE PROGRAMMES ADOPTED IN THE BOOK .................... 44
PROGRAM DIAGRAM REMARKS ............................................................................. 45
FILES FOR TASKS AND EXERCISES ............................................................................. 45
3 INTRODUCTION TO ALGORITHMS AND PROGRAMMING ....................... 48
EXAMPLES OF ALGORITHMS AND THEIR REPRESENTATIONS ......................................... 48
ALGORITHM DEFINITION ....................................................................................... 51
EXAMPLE ALGORITHMS......................................................................................... 51
PRINCIPLES OF DESIGNING ALGORITHMS AND PROGRAMMES ...................................... 54
FLOWCHART ELEMENTS ........................................................................................ 57
CONSTRUCT LOOPS WITH FLOWCHARTS ................................................................... 60
FLOWCHART - ADVANTAGES AND DISADVANTAGES .................................................... 64
PSEUDOCODE - ADVANTAGES AND DISADVANTAGES .................................................. 64
PROGRAMMING LANGUAGE - ADVANTAGES AND DISADVANTAGES ............................... 65
PSEUDOCODE NOTATION ...................................................................................... 66
EXAMPLES OF WRITING ALGORITHMS IN PSEUDOCODE ............................................... 70
INDEXING ARRAYS ................................................................................................ 73
DATA PROCESSING ............................................................................................... 76
VIEW RESULTS .................................................................................................... 76
ALGORITHM IMPLEMENTATION .............................................................................. 77
INPUT / OUTPUT OPERATIONS IN MAGIC BLOCKS AND C# ......................................... 77
STRUCTURES USED IN C# ...................................................................................... 87
4 CLASSIFICATION OF ALGORITHMS ......................................................... 90
CLASSIFICATION OF ALGORITHMS ACCORDING TO THEIR PURPOSE AND IMPLEMENTATION
FEATURES ........................................................................................................... 90
CLASSIFICATION ACCORDING TO THE ORDER OF OPERATIONS PERFORMED ..................... 95
CLASSIFICATION BY HOW THE OPERATION IS PERFORMED ........................................... 98
CLASSIFICATION BY AREA OF APPLICATION.............................................................. 102
CLASSIFICATION OF ALGORITHMS ADOPTED IN THE BOOK ......................................... 102
THE ALGORITHM DESCRIPTION PATTERN USED IN THE BOOK ...................................... 102
5 DATA STRUCTURES AND FUNCTIONS ................................................... 107
BASIC DATA TYPES IN C# ..................................................................................... 107
COMPLEX DATA STRUCTURES ............................................................................... 110
ARRAYS ........................................................................................................... 110
ARRAY AS ARRAY ............................................................................................... 111
BASIC METHODS OF THE ARRAY CLASS................................................................... 111
ARRAY AS A LIST ................................................................................................ 112
LIST CLASS ....................................................................................................... 116
BASIC METHODS OF THE LIST CLASS ...................................................................... 119
ARRAY AS A STACK ............................................................................................. 119
ARRAY AS A STACK – BASIC OPERATION ................................................................. 125
THE STACK CLASS .............................................................................................. 133
BASIC METHODS OF THE STACK CLASS ................................................................... 136
FUNCTIONS AS PART OF AN ALGORITHM (PROGRAM) ............................................... 136
PARAMETERLESS FUNCTIONS ............................................................................... 137
FUNCTIONS WITH PARAMETERS ........................................................................... 138
PASSING A PARAMETER BY VALUE ......................................................................... 139
PASSING A PARAMETER BY REFERENCE .................................................................. 142
PRACTICAL APPLICATION OF REFERENCES ............................................................... 145
STRUCTURE OF THE POLISH PERSONAL IDENTITY NUMBER (PESEL) ........................... 146
DIFFERENCE BETWEEN ITERATION AND RECURSION ................................................. 157
6 LINEAR ALGORITHMS .......................................................................... 164
WHAT IS A LINEAR ALGORITHM? .......................................................................... 164
SUMMING UP FOUR NUMBERS ............................................................................. 164
SUMMING UP EIGHT TEXTS .................................................................................. 166
CALCULATING THE SQUARE OF THE DIFFERENCE BETWEEN TWO NUMBERS ................... 169
CALCULATING AREA AND PERIMETER OF THE RECTANGLE .......................................... 170
CALCULATING THE PERCENTAGE ........................................................................... 172
CALCULATING THE AREA AND PERIMETER OF A RECTANGLE ....................................... 175
HERON'S FORMULA ........................................................................................... 177
CALCULATING THE VOLUME OF A CYLINDER ............................................................ 179
CALCULATING THE VOLUME OF A SPHERE ............................................................... 181
CALCULATING THE BARREL VOLUME ..................................................................... 183
CAPITALISATION OF INTEREST .............................................................................. 185
7 ARITHMETIC ALGORITHMS .................................................................. 192
CALCULATING THE ABSOLUTE VALUE ..................................................................... 192
CHECKING WHICH NUMBER IS GREATER ................................................................. 193
CHECKING IF A NUMBER IS EVEN ........................................................................... 195
VERIFY THAT A NUMBER EXISTS IN A SET ................................................................ 196
ORDERING 3 NUMBERS ...................................................................................... 198
EXPONENTIATION OF NATURAL NUMBERS .............................................................. 200
SOLVING A LINEAR EQUATION .............................................................................. 203
SOLVING A QUADRATIC EQUATION ....................................................................... 206
SOLVING A SYSTEM OF LINEAR EQUATIONS ............................................................. 209
HORNER’S SCHEME ............................................................................................ 212
DETERMINING GCD USING SUBTRACTION .............................................................. 215
EUCLID'S ALGORITHM FOR DETERMINING GCD BY DIVISION ...................................... 217
EUCLID'S ALGORITHM FOR DETERMINING GCD (RECURSIVE VERSION) ........................ 220
DETERMINATION OF LCM USING GCD ................................................................. 221
GIVING CHANGE WITH THE FEWEST DENOMINATIONS (V.1) ...................................... 226
GIVING CHANGE WITH THE FEWEST NUMBER OF DENOMINATIONS (V.2) ..................... 228
BINARY REPRESENTATION OF A DECIMAL NUMBER ................................................... 230
OCTAL REPRESENTATION OF A DECIMAL NUMBER .................................................... 232
HEXADECIMAL REPRESENTATION OF A DECIMAL NUMBER ......................................... 234
CONVERTING A BINARY NUMBER TO A DECIMAL NUMBER ......................................... 236
POSITIONAL REPRESENTATIONS OF A DECIMAL NUMBER ........................................... 238
CONVERTING NUMBER TO ROMAN NUMERALS ...................................................... 242
CONVERTING ROMAN NUMERALS TO NUMBER ...................................................... 245
SUMMING DIGITS FROM A NUMBER ...................................................................... 248
CONVERTING AN IPV4 ADDRESS TO BINARY FORM .................................................. 250
PRIME NUMBERS ............................................................................................... 253
PRIMALITY TESTING............................................................................................ 256
ARITHMETIC SEQUENCE ...................................................................................... 258
GEOMETRIC SEQUENCE ...................................................................................... 261
CALCULATING THE HARVEST AVERAGE .................................................................. 264
EXTRACTING DIGITS FROM A NATURAL NUMBER ...................................................... 266
FIBONACCI SEQUENCE (ITERATIVE METHOD) ........................................................... 268
FIBONACCI SEQUENCE (RECURSIVE METHOD) ........................................................ 270
FACTORIAL CALCULATION (ITERATIVE METHOD) ...................................................... 272
FACTORIAL CALCULATION (RECURSIVE METHOD) ..................................................... 274
DOUBLE FACTORIAL CALCULATION ........................................................................ 276
BISECTION METHOD .......................................................................................... 278
SEARCHING FOR A MINIMAL ELEMENT IN AN ARRAY ................................................. 283
SEARCHING FOR A MAXIMUM ELEMENT IN AN ARRAY ............................................... 285
SEARCHING FOR THE MINIMUM AND MAXIMUM ELEMENT IN AN ARRAY ...................... 287
GRID POINTS .................................................................................................... 290
GRID POINTS (OPTIMAL VERSION)......................................................................... 293
8 CHARACTER AND TEXT ALGORITHM .................................................... 299
WHAT IS A CHARACTER AND TEXT ALGORITHM? ...................................................... 299
ADD CHARACTERS TO THE END OF TEXT ................................................................. 299
ADDING CHARACTERS TO THE BEGINNING OF TEXT .................................................. 301
ALTERNATION OF UPPERCASE AND LOWERCASE LETTERS........................................... 302
NAIVE PATTERN SEARCH IN TEXT .......................................................................... 306
CHECKING IF A TEXT IS A PALINDROME ................................................................... 309
CHECKING IF TEXTES ARE ANAGRAMS .................................................................... 312
9 FILE OPERATIONS ................................................................................ 317
HOW CAN I PERFORM FILE OPERATIONS? ............................................................... 317
READING DATA FROM A FILE ................................................................................ 317
SAVING DATA TO A FILE ...................................................................................... 319
SIMPLE FILE OPERATIONS .................................................................................... 321
READING DATA FROM A FILE ................................................................................ 323
PREPROCESSING DATA FROM A FILE ...................................................................... 325
FLAT DATABASE ORDERING .................................................................................. 326
10 SORTING ALGORITHMS ........................................................................ 337
WHAT IS SORTING AND WHAT ARE THE ALGORITHMS FOR SORTING? .......................... 337
BOGO-SORT ..................................................................................................... 338
STUPID-SORT .................................................................................................... 342
INSERTION-SORT ........................................................................................... 345
BUBBLE-SORT ................................................................................................ 348
SELECTION-SORT ............................................................................................... 350
COUNTING-SORT ............................................................................................... 354
MERGE-SORT .................................................................................................... 357
QUICK-SORT .................................................................................................. 362
BUCKET-SORT ................................................................................................... 365
HEAP-SORT .................................................................................................... 368
11 ENCRYPTION ALGORITHMS ................................................................. 375
CAESAR CIPHER – ENCODING ............................................................................... 375
CAESAR CIPHER – DECODING ............................................................................... 379
CAESAR CIPHER – ENCODING AND DECODING ......................................................... 381
TRANSPOSITION CIPHER – ENCODING .................................................................... 383
TRANSPOSITION CIPHER – DECODING .................................................................... 385
VIGENER CIPHER – ENCODING .............................................................................. 387
VIGENER CIPHER – DECODING .............................................................................. 392
12 ADVANCED ALGORITHMS .................................................................... 398
BINARY SEARCH ................................................................................................ 398
NUMBER FACTORIZATION ................................................................................... 401
SIEVE OF ERATOSTHENES .................................................................................... 405
FAST EXPONENTIATION (ITERATIVE METHOD) ......................................................... 407
FAST EXPONENTIATION (RECURSIVE METHOD) ........................................................ 410
CALCULATING THE APPROXIMATED SQUARE ROOT ................................................... 413
REVERSE POLISH NOTATION ................................................................................ 416
PACKING A BACKPACK (GREEDY ALGORITHM) ......................................................... 421
SYMETRIC TRAVELLING SALESMAN PROBLEM .......................................................... 428
13 COMPUTATIONAL COMPLEXITY OF ALGORITHMS ................................ 441
COMPLEXITY OF SORTING ALGORITHMS ................................................................. 442
TESTING THE SPEED OF SORTING ALGORITHMS ........................................................ 442
14 EXAMPLES OF PRACTICAL TASKS.......................................................... 465
TASK 1 (SIMPLE CONSOLE MENU) ........................................................................ 465
TASK 2 (CHECK YOUR PESEL NUMBER) ................................................................. 475
TASK 3 (SORTING THE BIN WITH BALLS) ................................................................. 480
15 LIST OF SOLUTION CATALOGUES .......................................................... 494
16 BIBLIOGRAPHY AND NETOGRAPHY AND CITATIONS ............................ 504

pokaż cały spis treści

ukryj recenzje