Модул 10. Алгоритми и структури от данни

Материали | Задачи | Решения | Видео

Съдържание

  1. Алчни алгоритми

  2. Рекурсия и връщане назад

  3. Комбинаторика

  4. Динамично програмиране

  5. Дървета

  6. Хеширане и хеш таблици

  7. Графи и алгоритми с графи

  8. Подготовка за изпит

Алчни алгоритми

Алчен алгоритъм е всеки алгоритъм, който следва евристиката за решаване на проблеми при вземането на локално оптимален избор на всеки етап. В много проблеми алчната стратегия не води до оптимално решение, но алчната евристика може да доведе до локално оптимални решения, които се доближават до глобално оптимално решение за разумен период от време.

Например, алчната стратегия за проблема с пътуващия продавач (която е с висока изчислителна сложност) е следната евристика: "На всяка стъпка от пътуването посетете най-близкия непосетен град". Тази евристика не възнамерява да намери най-доброто решение, но завършва с разумен брой стъпки; Намирането на оптимално решение на такъв сложен проблем обикновено изисква необосновано много стъпки. В математическата оптимизация алчните алгоритми оптимално решават комбинаторни задачи, имащи свойствата на матроиди, и дават приближения с постоянен фактор на оптимизационни проблеми със субмодулната структура.

Източник: https://en.wikipedia.org/wiki/Greedy_algorithm

Рекурсия и връщане назад

Рекурсия

Рекурсията възниква, когато дефиницията на концепция или процес зависи от по-проста версия на себе си. Рекурсията се използва в различни дисциплини, вариращи от лингвистика до логика. Най-често срещаното приложение на рекурсията е в математиката и компютърните науки, където дефинираната функция се прилага в рамките на собствената си дефиниция. Въпреки че това очевидно определя безкраен брой инстанции (стойности на функциите), често се прави по такъв начин, че не може да възникне безкраен цикъл или безкрайна верига от препратки ("рекурсия на глинения съд").

Процес, който проявява рекурсия, е рекурсивен.

Източник: https://en.wikipedia.org/wiki/Recursion

Връщане назад

Връщане назад е клас алгоритми за намиране на решения на някои изчислителни проблеми, по-специално проблеми с удовлетворението от ограниченията, които постепенно изграждат кандидати за решенията и изоставят кандидат веднага щом преценят, че кандидатът не може да бъде завършен до валидно решение.

Класическият учебникарски пример за използването на връщане назад е пъзелът на осемте кралици, който изисква всички подредби на осем шахматни кралици на стандартна шахматна дъска, така че никоя кралица да не атакува друга. В общия подход за връщане назад, частичните кандидати са подредби на k царици в първите k редове на дъската, всички в различни редове и колони. Всяко частично решение, което съдържа две взаимно атакуващи се кралици, може да бъде изоставено.

Източник: https://en.wikipedia.org/wiki/Backtracking

Комбинаторика

Комбинаториката е област на математиката, която се занимава предимно с броенето, както като средство, така и като цел за получаване на резултати, както и определени свойства на крайните структури. Той е тясно свързан с много други области на математиката и има много приложения, вариращи от логика до статистическа физика и от еволюционна биология до компютърни науки.

Източник: https://en.wikipedia.org/wiki/Combinatorics

В математиката комбинацията е селекция от елементи от множество, което има отделни членове, така че редът на подбор няма значение (за разлика от пермутациите). Например, като се имат предвид три плода, да речем ябълка, портокал и круша, има три комбинации от две, които могат да бъдат извлечени от този комплект: ябълка и круша; ябълка и портокал; или круша и портокал.

Източник: https://en.wikipedia.org/wiki/Combination

Сложност при комбинаторни Алгоритми

  • Permutation = Пермутации = O(N!)

  • Permutation by Swapping = Пермутация чрез размяна = O(N!)

  • Permutation with Repetition = Пермутации с повторения = O(N!)

  • Variation = Вариации = O(N!/(N-K)!)

  • Combination = Комбинации = O(N!/K!(N-K)!)

  • Combination with Repetition = Комбинации с повторения = O(N!/K!(N-K)!)

  • Binomial Coefficients = Биномни коефициенти = C[n|k] = N!/(N-K)!K!

Динамично програмиране

Динамичното програмиране е както математически метод за оптимизация, така и метод за компютърно програмиране. Методът е разработен от Ричард Белман през 50-те години на миналия век и е намерил приложение в множество области, от аерокосмическото инженерство до икономиката.

И в двата контекста тя се отнася до опростяване на сложен проблем, като го разбива на по-прости под-проблеми по рекурсивен начин. Докато някои проблеми с решенията не могат да бъдат разделени по този начин, решенията, които обхващат няколко точки във времето, често се разпадат рекурсивно. По същия начин, в компютърните науки, ако даден проблем може да бъде решен оптимално чрез разбиването му на подзадачи и след това рекурсивно намиране на оптималните решения на подзадачите, тогава се казва, че има оптимална подструктура.

Източник: https://en.wikipedia.org/wiki/Dynamic_programming

Сложност при динамично оптимиране

  • Memoization = Save/Cache Sub-Problem Solutions for Later Use

  • Fibonacci Sequence = Редицата на Фибоначи = O(N)

  • 0/1 Knapsack Problem = Задача за раницата = O(N*C)

    • where: N = number of items, C = the knapsack capacity

Дървета

В компютърните науки дървото е широко използван абстрактен тип данни, който представлява йерархична дървовидна структура с набор от свързани възли. Всеки възел в дървото може да бъде свързан с много деца (в зависимост от вида на дървото), но трябва да бъде свързан точно с един родител, с изключение на коренния възел, който няма родител. Тези ограничения означават, че няма цикли или "цикли" (никой възел не може да бъде свой собствен прародител), а също и че всяко дете може да бъде третирано като коренния възел на собственото си поддърво, което прави рекурсията полезна техника за преминаване на дървета. За разлика от линейните структури от данни, много дървета не могат да бъдат представени чрез връзки между съседни възли в една права линия.

Двоичните дървета са често използван тип, който ограничава броя на децата за всеки родител до най-много две. Когато е посочен редът на децата, тази структура от данни съответства на подредено дърво в теорията на графите. Стойност или указател към други данни може да бъде свързан с всеки възел в дървото или понякога само с листните възли, които нямат деца.

Абстрактният тип данни може да бъде представен по няколко начина, включително списък на родителите с указатели към деца, списък на децата с указатели към родителите или списък с възли и отделен списък на отношенията родител-дете (специфичен тип съседен списък). Представянията също могат да бъдат по-сложни, например използването на индекси или списъци с предци за ефективност.

Източник: https://en.wikipedia.org/wiki/Tree_(data_structure)

Хеширане и хеш таблици

Хеш функция е всяка функция, която може да се използва за картографиране на данни с произволен размер към стойности с фиксиран размер, въпреки че има някои хеш функции, които поддържат изход с променлива дължина. Стойностите, върнати от хеш функция, се наричат хеш стойности, хеш кодове, дайджести или просто хешове. Стойностите обикновено се използват за индексиране на таблица с фиксиран размер, наречена хеш таблица. Използването на хеш функция за индексиране на хеш таблица се нарича хеширане или адресиране на точково съхранение.

Източник: https://en.wikipedia.org/wiki/Hash_function

В изчислителната техника хеш таблицата, е структура от данни, която реализира асоциативен масив или речник. Това е абстрактен тип данни, който съпоставя ключовете със стойностите. Хеш таблицата използва хеш функция, за да изчисли индекс, наричан още хеш код, в масив от кофи или слотове, от които може да се намери желаната стойност. По време на търсенето ключът се хешира и полученият хеш показва къде се съхранява съответната стойност.

В идеалния случай хеш функцията ще присвои всеки ключ на уникална кофа, но повечето дизайни на хеш таблици използват несъвършена хеш функция, която може да причини хеш сблъсъци, при които хеш функцията генерира един и същ индекс за повече от един ключ. Такива сблъсъци обикновено се приспособяват по някакъв начин.

В добре оразмерена хеш-таблица средната времева сложност за всяка справка е независима от броя на елементите, съхранени в таблицата. Много дизайни на хеш-таблици също позволяват произволни вмъквания и изтривания на двойки ключ-стойност, при амортизирана постоянна средна цена на операция.

Хеширането е пример за пространствено-времеви компромис. Ако паметта е безкрайна, целият ключ може да се използва директно като индекс, за да се намери стойността му с един достъп до паметта. От друга страна, ако е налично безкрайно време, стойностите могат да се съхраняват без оглед на техните ключове и за извличане на елемента може да се използва двоично търсене или линейно търсене.

В много ситуации хеш таблиците се оказват средно по-ефективни от дърветата за търсене или всяка друга структура за търсене на таблици. Поради тази причина те се използват широко в много видове компютърен софтуер, особено за асоциативни масиви, индексиране на бази данни, кешове и набори.

Източник: https://en.wikipedia.org/wiki/Hash_table

Графи и алгоритми с графи

Графът е структура, възлизаща на набор от обекти, в който някои двойки от обектите са в някакъв смисъл "свързани". Обектите съответстват на математически абстракции, наречени върхове и всяка от свързаните двойки върхове се нарича ребра. Обикновено графът се изобразява в схематична форма като набор от кръгове за върховете, съединени с линии или криви за ребрата. Графите са един от обектите на изследване в дискретната математика.

Ребрата могат да бъдат насочени или ненасочени. Например, ако върховете представляват хора на парти, а ребрата между двама души представим с ръкостискане, то тази графика е ненасочена, защото всеки човек А може да се ръкува с човек Б само ако Б също се ръкува с А. Обаче ако човек А дължи пари на човек Б, тогава тази графика е насочена, защото дължимите пари не са непременно реципрочни.

Източник: https://en.wikipedia.org/wiki/Graph_(discrete_mathematics)

Задачи

VertexDistances

Даден е ориентиран граф и съответните свързващи двойки върхове. Да се намери най-краткото разстояние между двойките върхове или -1, ако няма път, който ги свързва. На първия ред се въвежда N - броя на върховете на графа. На втория ред се въвежда едно цяло число P - броя на двойките върхове, между които ще се търси минималното разстояние. На следващите N реда върховете на графа, а на следващите P реда - двойките върхове.

Вход
Изход

2 2 1:2 2: 1-2 2-1

{1, 2} -> 1 {2, 1} -> -1

8 4 1:4 2:4 3:4 5 4:6 5:3 7 8 6: 7:8 8: 1-6 1-5 5-6 5-8

{1, 6} -> 2 {1, 5} -> -1 {5, 6} -> 3 {5, 8} -> 1

9 8 11:4 4:12 1 1:12 21 7 7:21 12:4 19 19:1 21 21:14 31 14:14 31: 11-7 11-21 21-4 19-14 1-4 1-11 31-21 11-14

{11, 7} -> 3 {11, 21} -> 3 {21, 4} -> -1 {19, 14} -> 2 {1, 4} -> 2 {1, 11} -> -1 {31, 21} -> -1 {11, 14} -> 4

MatrixRegions

Дадена е матрица с размери NxM, чиито стойности са малки латински букви. Две клетки са съседни, ако те имат обща стена. Напишете програма, която намира свързаните области на съседните клетки, съдържащи една и съща буква. Програмата да извежда общия брой области и броя на зоните за всяка латинска буква, подредени лексикографски. На първия ред се посочва броят на редовете.

Вход
Изход

6 aacccaac baaaaccc baabaccc bbdaaccc ccdccccc ccdccccc

Области: 8 Буква 'a' -> 2 Буква 'b' -> 2 Буква 'c' -> 3 Буква 'd' -> 1

3 aaa aaa aaa

Области: 1 Буква 'a' -> 1

5 asssaadas adsdasdad sdsdadsas sdasdsdsa ssssasddd

Области: 21 Буква 'a' -> 6 Буква 'd' -> 7 Буква 's' -> 8

GraphCycle

Напишете програма, която проверява дали даден неориентиран граф съдържа цикли или е ацикличен.

Вход
Изход

1 C–G

Yes

3 A–F F–D D–A

No

3 E–Q Q–P P–B

Yes

5 K–J J–N N–L N–M M–I

Yes

14 K–X X–Y X–N N–J M–N A–Z B–P I–F A–Y Y–L M–I F–P Z–E P–E

No

Salary

Между служителите в фирма Х има йерархия. Служителите могат да имат един или няколко преки началника. Хората, които не управляват никой, се наричат редовни служители и заплатата им е 1. Хората, които управляват поне един служител, се наричат мениджъри. Всеки мениджър взима заплата, равна на сумата от заплатите на своите пряко управлявани служители. Мениджърите не могат управляват пряко или косвено себе си . Някои служители може да нямат мениджър (като големия шеф). Вижте примерна йерархия във фирма, заедно с изчислените заплати, следвайки гореописаното правило:

И така: служителите 0 и 3 са редовни служители и взимат заплата 1. Всички останали са мениджъри и вземат сумата от заплатите на своите пряко управлявани служители. Например, мениджър 1 взема заплата 3 + 2 + 1 = 6 (сума от заплатите на служителите 2, 5 и 0). Служителите 4 и 1 нямат мениджър. В задачата се знаят броя на служителите - N на брой, те са с индекси от 0 до N - 1. За всеки служител има информация във вид на низ от символите „Y“ или „N“ в зависимост от това дали настоящият служител е пряк мениджър на служителя i или не. Съвет: намерете връх, който няма родител и стартирайте DFS, за да изчислите заплатите по дървото рекурсивно.

Вход

  • Входните данни се въвеждат в конзолата

  • На първия ред се въвежда стойността на N - цяло число

  • На следващите N реда се въвеждат низове от двата символа 'Y' или 'N' с дължина N.

Изход

  • Изходните данни се извеждат в конзолата на един ред.

  • На изхода се извежда едно число - сумата от заплатите на всички служители

Ограничения

  • N = цяло число в интервала [1 ... 50].

  • За всеки i-ти ред, i-тия символ е 'N'.

  • Ако служител А е мениджър на служител В, В не може да бъде мениджър на А.

  • Време за работа на програмата (time limit): 0.1 секунди. Използвана памет:(memory limit) 16 MB.

Вход
Изход

1 N

1

4 NNYN NNYN NNNN NYYN

5

6 NNNNNN YNYNNY YNNNNY NNNNNN YNYNNN YNNYNN

17

CyclesBreaker

Даден е неориентиран мултиграф. Задачата да отстраните минимален брой ръбове, така, че да направите графа ацикличен. (т.е. Трябва да прекъснете всички цикли). На изхода е необходимо да отпечатате броя на отстранените ръбове и кои точно са те. Ако няколко ръба могат да бъдат премахнати, за да се прекъсне определен цикъл, премахнете най-малкия от тях по азбучен ред (най-малкият начален връх и най-малкият краен връх по лексикографска наредба).

Вход
Изход

1 -> 2 5 4 2 -> 1 3 3 -> 2 5 4 -> 1 5 -> 1 3 6 -> 7 8 7 -> 6 8 8 -> 6 7

Брой на премахнатите ребра: 2 1 - 2 6 - 7

K -> X J J -> K N N -> J X L M X -> K N Y M -> N I Y -> X L L -> N I Y I -> M L A -> Z Z Z Z -> A A A F -> E B P E -> F P P -> B F E B -> F P

Брой на премахнатите ребра: 7 A - Z A - Z B - F E - F I - L J - K L - N

Подготовка за изпит

2023.10.15

Available from: Sunday, 15 October 2023, 10:00
Due date: Sunday, 15 October 2023, 15:00
Type of work: Individual work

Задача 1. Елементи

Експеримент с интегритета между химични елементи, чрез поставянето им в ограничено затворено пространство води до ключови открития. Вие сте част от софтуерния екип зад този сложен секретен интернационален проект с интергалактическо значение!

Ще получите колекция от елементи, на един ред, разделени с интервал. Това са елементите, с които ще направите експериментите си. На следващия ред ще получите размера на ограниченото пространството – цяло число N, оказващо с колко елемента трябва да изпълнявате един експеримент.

На последния ред ще получите колекция от приоритетни елементи, на един ред, разделени с интервал.

Вашата задача е да генерирате всички възможни експерименти с елементите, започвайки по реда им на въвеждане във входа на данни, използвайки по N елемента на експеримент, без да използвате един и същи набор от елементи в различни експерименти.

  • Ако в определен експеримент присъства приоритетен елемент, той трябва да е изведен пръв, в изхода на данни.

  • Ако в определен експеримент присъства повече от един приоритетен елемент, то те трябва да бъдат изведени в зависимост от индекса им в колекцията с приоритетни елементи.

Вход

  • На първия ред от входа на данни ще получите колекция от всичките елементи – низове, разделени с интервал.

  • На втория ред ще получите N – цяло число, определящо, по колко елемента трябва да бъдат използвани на всеки експеримент.

  • На последния ред ще получите колекция от приоритетни елементи – низове, разделени с интервал.

Изход

  • Като изход, трябва да принтирате всички експерименти – набор от N елемента, разделени с интервал.

Ограничения

  • Броя на елементите ще е в интервал [0 ... 20].

  • Броя на елементите, които трябва да използвате в експериментите – N ще бъде в интервал [0 ... 20].

  • Елементите ще бъдат винаги уникални низове.

Примери

Input
Output
Comment

Hydrogen Oxygen Helium Carbon

Hydrogen Oxygen

Коментар 1: След като вече веднъж сме използвали "Hydrogen" и "Oxygen" в един експеримент (експериментът: "Hydrogen Oxygen"), не ги използваме пак.

2

Hydrogen Helium

Коментар 2: Тъй като "Hydrogen" е приоритетен елемент, той е изведен пръв в изхода на данни, в експериментите, в които е използван.

Hydrogen

Hydrogen Carbon

Oxygen Helium

Oxygen Carbon

Helium Carbon

Input
Output
Comment

Lithium Sulfur Lead

Lithium Sulfur

Коментар 3: По реда на въвеждане, 4-ия експеримент трябва да е – "Iron Carbon Sodium". Поради факта, че 2 от елементите са приоритетни, те се подреждат първи, и по индекс на въвеждане в приоритетната листа, тоест Sodium – Index 0, Carbon – Index 1.

2

Lead Lithium

Lead

Lead Sulfur

Iron Gold Carbon Sodium Silver

Carbon Iron Gold

Sodium Carbon

Sodium Iron Gold

3

Iron Gold Silver

Sodium Carbon Iron

Carbon Iron Silver

Sodium Iron Silver

Sodium Carbon Gold

Carbon Gold Silver

Sodium Gold Silver

Sodium Carbon Silver

Задача 2. Градска търговия

Дени е търговски представител на фирма. Тя има за задача да посещава различни градове и да извършва сделки в тях. При посещението на даден град, тя има определени разходи. От даден град, тя може да отиде до следващия или до по-следващия. По-далечни пътувания не са разрешени, тъй като ще изтърве твърде много бизнес възможности!

Понеже Дени е ваша страхотна представителка и фирмата ѝ се занимава с търговия на хардуерни компоненти, а вие много искате тя да ви даде далаверка за нова видео карта, трябва да ѝ помогнете!

Целта на задачата е започвайки от града с индекс 0 или от индекс 1 да стигнете до края на списъка с градове с възможно най-малко разходи.

Вход

  • На единствения ред от входа на данни ще получите колекция от всичките градове –цели числа, разделени с интервал, които представляват разходите при посещение на даден град.

Изход

  • Като изход, трябва да принтирате минималното нужно гориво за да стигнете до края.

Ограничения

  • Броя на градовете ще е в интервал [0 ... 10000].

  • Самите градове ще представляват цели числа в интервал [0 ... 10000].

Пример

Вход
Изход
Коментар

13 18 23

18

Коментар 1: Ще започнем от индекс 1, и ще направим 2 стъпки, излизайки от списъка. Тогава единственият разход, който трябва да направим е в град 1 – 18.

3 101 3 3 3 101 3 3 101 3

18

Коментар 2:

Започваме от индекс 0.

Имаме разход 3 там, а след това правим 2 стъпки до индекс 2.

Отново вземайки град с разход 3, правим 2 стъпки до индекс 4.

След това правим още 2 стъпки до индекс 6.

След това правим една стъпка до индекс 7.

След това правим още 2 стъпки до индекс 9.

И накрая правим 1 последна стъпка излизайки от колекцията.

2020.10.04

Avaliable from: Sunday, 4 October 2020, 10:00
Due date: Sunday, 4 October 2020, 15:00
Type of work: Individual work

Задaча 1. Банкомат

Държавната банка иска софтуерът на банкоматите им да работи така, че при теглене, гражданите да получават парите си с възможно най-малко банкноти. Банкнотите, с които банкоматите се разплащат са с номинали от по 1лв, 2лв, 5лв, 10лв, 20лв, 50лв и 100лв.

Напишете програма, която прочита от клавиатурата цяло число N - колко пари картодържателят желае да изтегли от банкомата и връща цяло число M - минималния брой банкноти, с които може да се изплати сумата.

И така ако картодържател тегли 88 лева от банкомат на държавната банка, то той трябва да получи:

  • 1 банкнота от 50лв

  • 1 банкнота от 20лв

  • 1 банкнота от 10лв

  • 1 банкнота от 5лв

  • 1 банкнота от 2лв

  • 1 банкнота от 1лв.

На стандартния вход се въвежда цяло число N – сумата за теглене. На стандартния изход се извежда цяло число – минималния брой банкноти, с които може да се изплати сумата.

Ограничения: 1<=N<=1000

Пример:

Вход
Изход

88

6

Задача 2. Пермутации

Да се състави програма, която генерира всички пермутации на първите N естествени числа. На стандартния вход се въвежда цяло число N. На стандартния изход се извежда списък от пермутациите на първите N естествени числа.

Ограничения: 1<=N<=100

Пример:

Вход
Изход

3

1 2 3

1 3 2

2 1 3

2 3 1

3 1 2

3 2 1

2019.06.16

SoftUni Judje Algorithms Exam (16 June 2019) https://judge.softuni.bg/Contests/1700/Algorithms-Exam-16-June-2019

1. Monkey Business

https://judge.softuni.bg/Contests/Practice/Index/1700#0

2. Lost Devices

https://judge.softuni.bg/Contests/Practice/Index/1700#1

3. The Mad Gardener

https://judge.softuni.bg/Contests/Practice/Index/1700#2

4. Good Omens

https://judge.softuni.bg/Contests/Practice/Index/1700#3

2019.09.21

SoftUni Judje Algorithms Exam (21 Sept 2019) https://judge.softuni.bg/Contests/1817/CSharp-Algorithms-Exam-21-Sept-2019

1. Cinema

https://judge.softuni.bg/Contests/Practice/Index/1817#0

2. Word Cruncher

https://judge.softuni.bg/Contests/Practice/Index/1817#1

3.Word Differences

https://judge.softuni.bg/Contests/Practice/Index/1817#2

4. Road Reconstruction

https://judge.softuni.bg/Contests/Practice/Index/1817#3

PreviousМодул 8. Въведение в операционни и вградени системиNextМодул 11. Функционално програмиране

Last updated

Was this helpful?