Рекомендувати документи

даних

Структури даних, алгоритми, об'єкти

BMF-NIK-AAO Структури даних, алгоритми, об'єкти (AAO) Збірник уривків із матеріалу 2005/2006 рр. На основі лекцій Ласло Цзінка та Арпада Міклоша.

Зміст. 1. Опис алгоритму, визначення. . 4 Розв’язування квадратного рівняння. 5 Приблизне віднімання коренів (метод Ньютона). 7 2. Прості елементи програмування. 8 Послідовний розрахунок. 8 Рішення. 9 Вибір. 10 Підрахунок. 11 Пошук. 12 Максимальний пошук. 12 3. Перетворення даних, цикли, функції, масиви. 13 Перетворення даних. 13 Функції. 16 4. Сортування, сортування, двійковий пошук. 19 Відбір. 19 Сортування (на два блоки). 20 Сортування (за одним масивом). 20 Бінарний пошук. 21 5. Набір операцій. 22 Розділ. 22 Союз. 23 Відповідність. 23 6. Домовленості. 24 сортування бульбашок. 24 коктейльна лінія. 25 Розташування садового гнома. 26 Розстановка гребінця (стегновий ряд). 27 Максимальне сортування за вибором. 28 Сортування вставки. 28 Розташування голуб’ячої нори. 29

BMF-NIK-AAO 7. Швидке сортування (швидке сортування). 30 Рекурсивно. 30 Не рекурсивно. 31 8. Алгоритми ігор. 35 9. Пошук шляху лабіринту. 39 10. Слово проблема. 42 11. Алгоритми з матрицями. 45 Рідкісні матриці. 45 Ланцюжне множення матриць. 47 Множення матриці Штрассена. 47 12. Чарівний квадрат. 49 Поняття магічного квадрата. 49 Еквівалентні магічні квадрати. 50 Виведення магічної суми. 50 Метод Кокстера. 51 Пірамідальний метод. 52 13. Інші алгоритми. 53 Алгоритм Евкліда. 53 Серія Фібоначчі. 53 Схема Горнера. 54 Сито Ератостени. 54 14. Частина ООП (лекції Арпада Міклоша). 55 Обчислювальні моделі та парадигми програмування. 55 Об'єктно-орієнтована парадигма програмування. 60 Основи об’єктно-орієнтованої парадигми. 66 Розблокування, приховування даних. 74 Спадщина. 79 Різноманітність. 83 Повторне використання коду (скорочений контур). 89

2. Прості пункти програмування: Послідовний розрахунок, минулого року я відкладав рахунок за газ щомісяця. Я хочу підрахувати, скільки грошей коштує річне споживання газу ». Крок рішення: 1. Скиньте змінну агрегування. 2. Повторюю наступні два кроки 12 разів: переглядаю наступний рахунок-фактуру, додаю його до попередньої суми. 3. Я нарешті отримую результат. Псевдокод: ЗМІННІ i, сума ЦІЛЬКА, рахунок-фактура [i] РЕАЛЬНИЙ (або ЦІЛИЙ) i ← 0; сума ← 0; ПОВТОРИТИ ЯКЩО (i менше 12) < sum←sum+szamla[i]; >ПРИМІТКА (сума)

(нумерація місяців починається від 0 відповідно до маркування)

Рішення BMF-NIK-AAO Я хотів би вирішити на основі оцінок студента, чудовий він чи ні. Можливі два типи ідей: 1.

Якщо серед ваших квитків не п’ять, вони не чудові

Давайте подивимось на квитки, спочатку перший, потім решту підряд, і переконайтеся, що їх п’ять. Якщо ми знайдемо щось, що не є п’ятіркою, тоді немає необхідності дивитись на додаткові квитки, тому що оцінка не п’ятірка, тобто не відмінна. Псевдокод: ЗМІННИЙ номер_теми, i, квитки [i] ЦІЛИЙ, van_nemotos ЛОГІЧНИЙ i ← 1 ПОВТОРИТИ, ЯКЩО (i номер_теми) СУЧАСНИЙ (all_otos)

Вибір BMF-NIK-AAO З закритих паперів круга резервуара виберіть один із достатньої кількості паперів. Рішення: давайте розглянемо дисертації, спочатку перші, потім інші по черзі, поки не знайдемо достатньо дисертацій. Коли ми знайдемо достатньо, він буде обраний. Псевдокод: ЗМІННІ i, кількість, кількість робочих місць, документи [i] WHOLE i ← 1 REPEAT IF ((кількість днів) Console.WriteLine (“Немає рішення”); ще Console.Write (i + “день!”);

Підрахунок BMF-NIK-AAO Попередня проблема дещо змінена. Порахуйте, за скільки днів (якщо такі були) дохід бізнесу перевищив 20 000 форинтів? Код підрахунку: int штука = 0; для (i = 1; i 20) штук ++; Console.WriteLine (штука + “дохід за день становив понад 20 тисяч форинтів”);

Максимальний вибір Я дивився на карту вчора ввечері. Я написав собі висоту 10 високих гір над рівнем моря. Введіть найвищу вершину! Рішення: Я відзначаю висоту першої гори. Я вважаю це найвищим. Я дивлюсь через інші гори одну за одною: якщо одна є вищою за найвищу досі, я забуваю найвищу за всю історію і зазначаю нову. В кінці буде відзначена найвища гора. Код: int номер гори = 10; int [] висока = нова int [гора номер + 1]; // тому що ми індексуємо з 1 int i; Random RandomClass = new Random (); для (i = 1; i max) < max=magas[i]; eddigi=i; >Console.WriteLine ("найбільша кількість (одна):" + попередня + "висота:" + макс.);

Якщо, скажімо, гора 2 і гора 7 мають однакову висоту, а решта - всі менші, результат буде 2 або сім? Буде 2. Однак, якщо замість> вставлено> =, то 7.

3. Перетворення даних, цикли, функції, масиви Перетворення даних Перетворення в C # може бути неявним або явним. Якщо перетворення відбувається автоматично, ми говоримо про неявне перетворення, і в цьому випадку не відбувається втрати даних. Явне перетворення примусово, і в цьому випадку може відбутися втрата даних. Перетворення найчастіше відбувається під час передачі параметрів виклику функції або для числових обчислень із змішаними даними. Стрілки показують неявні параметри перетворення:

Неявне числове перетворення: довгий x1; int y1 = 25; x1 = y1; Console.WriteLine (x1); int x1; довгий y1 = 25; x1 = y1;

// неявне числове перетворення int → long

// довга → стрілка int відсутня: повідомлення про помилку…; // але добре, бо можлива втрата даних!

BMF-NIK-AAO Рішення з відливанням (явне): int x1, x2; довгий y1 = 2147483647, y2 = 21474836470; // y1 "вписується" в int, y2 не може поміститися x1 = (int) y1; x2 = (int) y2; // (int) cast Console.WriteLine (x1 + ”” + x2); // x1 = 2147483647, x2 = -10 // x2 втратив дані

Цілий або реальний поділ? int i = 13, j = 7; int k = i/j; Console.WriteLine (k); плаваючий k1 = i/j; Console.WriteLine (k1); float k2 = (float) i/j; Console.WriteLine (k2); Console.WriteLine (55/7); Console.WriteLine (55.0/7); float i = 13; int j = 7; Console.WriteLine (i/j); Console.WriteLine ((int) i/j); подвійний i1 = 13,15; int j = 7; Console.WriteLine (i1/j); Console.WriteLine ((int) i1/j); float i2 = 13,15; int j = 7; Console.WriteLine ((int) i2/j);

// обидва аргументи спочатку цілі числа // PRINT: 1 // PRINT: 1 //1.857143 // (float) i/(float) j або i/(float) j також добре! // 7 //7.8571 . // i реальний, але з цілим числом //1.85 . // 1 // i1 подвійний, неціле значення //1.87 . // 1 // i2 реальний нецілий значення // ПОМИЛКА: float неможливо перетворити

Перетворити змінну з подвійною крапкою у ціле число з втратою даних: подвійний i2 = 13,83; Console.WriteLine ((int) i2);

Приклад логічного виразу: int a = 7; журнал bool; log = a% 2 == 0; // журнал = (a% 2 == 0); if (log) Console.WriteLine (“even”); ще Console.WriteLine ("непарна");

BMF-NIK-AAO Рядок → числове (ціле) значення рядок sz = ”123”; int sz1 = Int32.Parse (sz); int sz2 = Перетворити.ToInt32 (sz);

Рядок → числове (дійсне) значення рядок myDoubleStr = ”- 12,2”; double x = Double.Parse (myDoubleStr) +5,3; подвійний y = Convert.ToDouble (myDoubleStr) +1,1; Console.WriteLine (x); // - 6.9 Console.WriteLine (y); // - 11.1 // варто звернути увагу на вживання десяткових крапок або коми

Розбийте текст на слова string s = "Одного разу # де # не існувало" char [] seps = new char [] foreach (рядок ss sin s.Split (seps)) Console.WriteLine (ss);

// Це потрібно розібрати // символи-роздільники // ss результат

Результат: Колись давно не було

Функції BMF-NIK-AAO Використання функцій без повернення значення public static void change (int b) < b=5; >статична порожнеча Головна ()

Повернути значення від імені методу public static int change (int b) < b=5; return b; >статична порожнеча Головна ()

// буде дорівнює 5

Передача параметрів за адресою (вихід) загальнодоступна статична зміна порожнечі (вихід int b) < b=5; >статична порожнеча Головна ()

// вам не потрібно отримувати значення

BMF-NIK-AAO Список змінних аргументів Використання масиву параметрів дозволяє використовувати змінну кількість параметрів одного типу. Ключове слово params повинно бути включене у визначення, але не при виклику. За списком параметрів у визначенні слідує одновимірний масив, за викликом може бути включена будь-яка кількість параметрів (до нуля), за умови, що тип сумісний. Приклад використання params: static void ShowNumbers (params int [] numbers) < foreach (int x in numbers)< Console.Write(x+” ”); >Console.WriteLine (); > статична порожнеча Main ()< int[] x=; ShowNumbers(x); ShowNumbers(4, 5); Console.ReadKey(); >

Результатів: 123 45

BMF-NIK-AAO Одновимірний масив int [] itomb; itomb = new int [3]; для (int i = 0; i 0) < p[pdb]=t[i]; pdb++; >ще < np[npdb]=t[i]; npdb++; >i ++; >

// індекс від 0 до n-1

Розділення (на один масив) Що стосується розподілу пам'яті, попередній алгоритм, що використовує два масиви, неефективний: обидва масиви p і np повинні бути оголошені як n елементів, але загалом у двох масивах є лише n елементів. Ви також можете використовувати масив, потім помістіть додатні числа в першу його половину, а решту - у другу половину (починаючи із зворотного боку). Цей алгоритм розміщує позитивні елементи масиву t (індекси від 0 до n-1) на початку масиву p, негативні елементи в кінці масиву p. Код C #: i = 0; pdb = 0; veg = n-1; в той час як (i 0) p [pdb ++] = t [i]; інакше p [veg -] = t [i]; i ++; >

BMF-NIK-AAO Двійковий пошук Ви можете здійснювати пошук за ним лише в упорядкованій послідовності. k = вимагає кроків log2n. (n кількість елементів) Принцип роботи: Завжди зменшує список даних удвічі та розглядає, яку частину даних ви шукаєте. Тоді загляньте далі. Код C # int також, top, center, space, n; // n = кількість елементів elementtype data = new elementtype (); // тип елемента даних для пошуку [] a = новий тип елемента []; // список, який ми шукаємо; також = 1; felso = n; посередині = (також + верх)/2; while ((також = n) c [k ++] = a [j]; // якщо такий був, поставте c>> k; // встановіть кінець c для (i = 0; ia [i + 1 ])) < //ha rossz a sorrend cserélünk int cs; cs=a[i]; a[i]=a[i+1]; a[i+1]=cs; csere_volt=1; //még nem biztos hogy jó a sorrend >>

Коли цикл while запускається один раз, найбільший елемент буде останнім. Якщо послідовність (випадково) відсортована заздалегідь, ми готові, якщо відбулася хоча б одна заміна, то час буде працювати знову, а наступним за величиною елементом буде передостанній. Елемент замінюється на кожному кроці, тому поки він не може виконуватися більше n разів. Найгірший випадок: сортування бульбашок вимагає найгіршого кроку O (n * n). Кожен предмет може переміститися в одну позицію за рахунок порівняння (сусідні елементи порівнюються). Елемент може знаходитись на відстані не більше n-1 від його послідовно відповідного розташування, тому його можна відновити щонайбільше n-1 = O (n) операціями, так що при (n-1) * (n-1 ) = O (n * n) операцій може бути не більше, ніж для повного сортування.

Експерименти на масиві з 10000 елементів показали, що розчісування було трохи гіршим, ніж швидке сортування (10%); зміна не є великою порівняно з міхуром. Однак не потрібно турбуватися про заздалегідь підготовлену справу, яка дуже уповільнює швидкий сорт. Встановивши зазор, ми спочатку сортуємо відсутні елементи. Потім щілина звужується, поки остаточно не стане. У цьому випадку програма така ж, як міхур; відповідно правильний. Лейсі та Річард Бокс показали, що розрив ділиться на 1,3 при кожному русі. Крім того, було виявлено, що 9 і 10 не підходять для пропусків і їх потрібно замінити на 11.

BMF-NIK-AAO Maximum Select Sort Сортувати масив, використовуючи найбільший елемент. Виберіть найбільший і замініть його останнім. (n - довжина масиву) C # код int max, cs; для (int i = n; i> 1; i--)< max=i; for(int j=i-1; j>0; j--) if (a [j]> a [max]) max = j; cs = a [i]; a [i] = a [max]; a [максимум] = cs; >

Вставлення сортування Візьміть наступний предмет і знайдіть його місце у вже відсортованій частині ліворуч. Паралельно з пошуком більші елементи переміщуються відповідно на один праворуч. C # тип елемента коду x = новий тип елемента (); тип елемента [] a = новий тип елемента []; int i, j; для (i = 2; i = 1) && (x
28

// скинути піраміду

// виробляємо чарівний квадрат

// якщо зелений // якщо фіолетовий // якщо червоний // якщо синій

13. Інші алгоритми Евклідовий алгоритм gcd = найбільший спільний дільник = найбільший спільний дільник Ми хочемо визначити найбільший спільний дільник чисел A і B. Нехай Т - залишок, отриманий діленням А на В. Отже: A = qB + T, де q - частка ділення. Будь-який спільний дільник A і B ділить T (оскільки T = A-qB). Так само будь-який спільний дільник B і T ділить A. Найбільший спільний дільник A і B дорівнює найбільшому спільному дільнику B і T. Отже, достатньо, якщо ми продовжимо процедуру з B і T. Оскільки | T | б) a = a-b; інакше b = b-a; повернути a; >

// завжди віднімаємо менше від більшого

Серія Фібоначчі - це серія чисел Фібоначчі: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946, ... Один член серії отримується додаванням двох попередніх. (однак, якщо n = 0, тоді значення елемента дорівнює 0, якщо n = 1, тоді значення елемента дорівнює 1). Код C # // ця функція повертає x-те число Фібоначчі. unsigned int f (int x)< return x