Проучване - Дев, блог архив, структури от данни и алгоритми

структури от данни и алгоритми. Теория. Класически програмиране проблем

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

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

Рекурсия и проблеми с търсенето

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

Пример: При един шахматна дъска размер N * N. Всяка клетка на борда е номериран за от 1 до N ^ 2. Конят се движи в правилата за обичайните шах. Трябва да намерим начин през всички клетки, в които ние ще го посетят всички полета, и само веднъж. Размерите на борда са на коня и изходно положение (координати си по двете оси) първоначалните данни. Разтворът трябва да бъде просто рекурсивно.

Изображението за пример в центъра на дъската е много кон. Цифрите показват възможни около клетките за първия ход. За да имате по стандартизиран метод за изчисляване на всички клетки, които могат да се движат от текущата позиция се препоръчва използването на помощен масив с размер 2 * 8. Тук първия ред от колоната К се увеличава с OY ос съответно втора стойност низ се увеличава с ОХ ос. Един пример на такава матрица е даден по-долу (**):

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

Всеки рекурсивни дълбочина повикване S опитва да поставите коня във всички възможни клетки, които могат да бъдат пряко достъпни от ток (I, J) клетки за този пъзел на тока координират (I, J) компенсира коефициенти са добавени от своя страна (**). Разбира се, че всеки един от получените координати трябва да се проверява по темата за това дали ние сме преминали отвъд шахматната дъска. Така че, ще има нов координира (I1, J1) обръщаме внимание на това дали можем да направим, за да се движат, че дали клетката е празна (т.е. нула). Ако такъв ход е възможно, ние го правим чрез поставяне в клетката на нашата стойност масив A [I1, J1] = S. Чрез този ход, ние се опрости първоначалния проблем, сега трябва да се придвижва има N ^ 2 - S борда клетки. Ние трябва да споменем и наличието на така наречените "задънените улици" - това е тези държави, в които все още не са приключили всички клетки, но сегашното състояние няма място да отида. Това, което сме в период на застой означава, че някъде в по-ранните етапи на начина, по който ние направихме грешка и избра грешния път, следователно, ние трябва да се върнем и да се повтаря с момента на повредата вече изберете друга клетка. И сега внимание: по този начин и влиза всеки рекурсивен алгоритъм за търсене: на определен етап на гнездене рекурсия (етап спускане), когато се вземе решение за това кои от многото възможни начини да се избират, запазени в купчина функция местната памет, всички променливи и параметри, всеки копия от следните функции ще работят със своите копия на променливи. Ето защо, когато ние сме на етапа на възстановяване на подвижния обратно към предишно състояние се запазва благодарение на стойностите на променливите, които вече се знае точно кой път минахме и която остава. Това произведение е рекурсивно търсене е подобно на начина, по който туристите търсят търсят в гората на път за вкъщи. Или нещо като машина да играе шах с един човек в даден мач изброява (търсения, използва евристични методи), за да се реши как да ходи.

Пример код на алгоритъма е дадена по-долу:

Подмяна на рекурсия стека

В случаите, когато трябва да се приложи за търсене, но е необходимо да се намали натоварването при рекурсия, можете да го замените с комин. Следното е пример за код, който решава задачата за намиране на най-големите петна по кожата леопард. Необходимо е правоъгълна матрица с размер N * M изпълнен с нули и единици да се намери най-голямата площ на непрекъснати единици. Следното е разтвор с използване на рекурсия, и през комин. Замяна е възможно благодарение на факта, че е технически, рекурсията се осъществява чрез съхраняване на възможните варианти за стратегии за развитие, за да се насочи и да се върнете към тях по LIFO дисциплина. Особено внимание е, че замяната на рекурсия използване на комина трябва да се направи след това, когато рекурсия е много значително ниво, в тази ситуация ние не можем достатъчно житен куп паметта на компютъра, а защото стека можем да поставим в купчината, а след това на границата размерът му е по-малко чувствителни.

За нерекурсивни решения трябва да се свържете купчина клас от STL библиотека. Следното е пример за не-рекурсивни функционални решения. За да проверите неговата работа трябва да бъде заменен в горния списък извикване на функция "recursive_calc" на "stack_calc".

Задача: всички задачи, които са изброени по-долу и са рекурсивни, ще трябва също така да се прилагат с помощта на стека. Можете да опитате да изчислите времето, прекарано в двата подхода.

Задачи: По-долу е даден списък от задачи, свързани с решението за използване на рекурсия и връщане назад методи за търсене на решения.

1) пъзела на осем царици: на борда трябва да бъдат поставени осем царици така че никой от тях не е под атака и двете.

2) Когато пътувате с влак, момичето във влака заменя името на всяка буква на негово място в българската азбука и получен запис от тези и двама "211221-21221". Определете как и къде влакът върви?

3) Данните N домино камъни в съответствие с правилата, изложени в права верига, като се започне с семена, подбрани на случаен принцип, в двата края възможно най-дълго. Construct алгоритъм за определяне на опция за въвеждане на някои дал семена, в който по времето, когато веригата не може да продължи ", на ръцете си" ще бъде максималният брой точки.

4) писмено експресията ((((1? 2)? 3)? 4)? 5)? 6, вместо на всеки символ. вмъкване на една от четирите аритметични операции +, -, *, /, така че резултатът на изчисление е равна на 35 (чрез разделяне на фракционна част се изхвърля в частност). Вижте всички решения.

5) въвеждане на поредица от не повече от 6 цифри и някои число R. осеяли аритметични оператори ( "+", "-", "*", "/", не е унарна минус, т.е., да не представляват негативизъм номер, разделяне е цяло число разделяне, т.е. 11/3 = 3) и отваряне и затваряне на скоби, така че да доведат до изчисляване на резултат експресия брой R. грешка ненужното скоби не са.
6) Създаване на програма, която отпечатва всички различни представяне на номер N под формата на всички възможни продукти (суми) K числа (М, К-влезе 1