Основы программирования (947332), страница 31

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 31)

Для таких задачдалеко не всегда удается найти алгоритм, который позволил бы получить ре­шение без анализа всех или большого количества комбинаций исходных дан­ных, т.е. без осуществления перебора. Осуществление полного перебора тре­бует много времени. Вычислительная сложность решения задач с использо­ванием перебора обычно оценивается как 0(п!) или даже 0(п").179Часть I. Основы алгоритмизации и процедурное программированиеДля решения задач данного типа применяют две стратегии:• формируют сразу всю комбинацию исходных данных и выполняют ееанализ в целом;• генерацию и анализ комбинации осуш.ествляют по частям.Если имеется возможность, анализируя часть комбинации исходныхданных, оценить ее перспективность с точки зрения получения решения, товторая стратегия позволит получить результат за меньшее время за счет ис­ключения из рассмотрения всех комбинаций, в которые входит данная часть.Исключение бесперспективных комбинаций (отсечение вариантов) позволя­ет осуществить не полный, а ограниченный перебор.Если по части комбинации исходных данных нельзя сделать заключе­ние о ее перспективности, то предпочтительнее первая стратегия, так какобычно она требует меньше времени на анализ варианта.Общий алгоритм решения задачи с использованием полного переборапо первой стратегии может быть представлен следующим образом.Цикл-пока еще есть вариантыГенерировать комбинацию исходных данныхесли вариант удовлетворяет условию,то Обработать вариантвсе-еслиВсе-циклДля генерации всех комбинаций исходных данных можно использоватьвложенные циклы или программно реализуемый счетчик (по типу, например,электросчетчика).

Второй способ позволяет получить более общее решение.Пример 5.17. Разработать программу генерации следующих комбина­ций: 1111, 1112, 1113, 1121, 1122, 1123, 1131, 1132, 1133, 1211,..., 3333.В а р и а н т 1. Для генерации комбинаций используем вложенные цик­лы. Количество разрядов - 4. Следовательно, для генерации всех комбинацийпонадобится 4 цикла, вложенных один в другой (рис. 5.18, а). Если ввестипараметр m - максимальное значение в каждом разряде, то эта же програм­ма будет генерировать комбинации от 1111 до mmmm.Если количество разрядов генерируемой комбинации изменить, то при­дется переписывать программу, увеличивая или уменьшая количество вло­женных циклов.Ва р и а н т 2. С точки зрения увеличения универсальности программыдля генерации всех комбинаций лучше использовать программно реализуе­мый счетчик в общем случае на п разрядов, который в каждом разряде счи­тает от 1 до т .

Каждое состояние такого счетчика соответствует комбинации.Для генерации следующего варианта в младший разряд счетчика добавляют1 и осуществляют межразрядные переносы в соответствии с характеристика­ми каждого разряда (рис. 5.18, б). Ниже представлена программа, реализую­щая данный алгоритм для п < 10.1805.

Модульное программирование(Начало jВводmГНачало/ВводjТa=(I,l,l,1,1,1,1,1,1,1)i=l,m,la[l] = iКJ=b"^»i/Выводa(n)//a[21=jk=l,m,la[3] = kn=I,m,Ia[4] = nВыводa(4)/{//Конец JРис. 5.18. Два варианта алгоритма генерации комбинаций:а-сиспользованием вложенных циклов;б-программно-реализуемый счет^шкProgram ex;Consta:array[L, 10] ofbyte^dFbr Im^n:integer;7,7,7,7,7,7,7,7,7;;181Часть I. Основы алгоритмизации и процедурное программированиеBeginReadLn(ri,m);while aflj<m+l do {условие «сброса» счетчика}beginfor i:=] to n do Write(a[i]); (вывод комбинации}WriteC У;a[n]:=afnj+l; {добавление 1 в последний разряд}for i:=n downto 2 йЬ{анализ и осуществление переносов}ifa[i]>m thenbeginafij:=l;a[i'l]:^a[i'l]+l:end;endEndАссоциируя комбинации счетчика с вариантами данных и проверяя по­лученные комбинации по критериям конкретной задачи, можно осуществитьполный перебор вариантов.Как уже упоминалось выше, для реализации ограниченного перебораиспользуется вторая стратегия, при которой генерацию и анализ комбинацийисходных данных выполняют поэтапно.

С этой целью удобно использоватьрекурсию, при которой процесс генерации комбинации продолжается, покаполученная часть комбинации перспективна, или не исчерпаны все вариан­ты.Пример 5.18. Задача о расстановке ферзей. Разработать программу, ко­торая формирует все возможные варианты расстановки m (m>3) ферзей нашахматной доске mxm клеток, при которых ферзи не «бьют» друг друга.Начнем с выбора способа представления данных задачи. С первоговзгляда кажется, что доска должна представляться матрицей, а местоположе­ние ферзей - размещением символов «*» в матрице.

Однако заметим, что го­раздо удобнее вариант, при котором доска представлена вектором. Индексвектора в таком представлении соответствует номеру столбца доски, а значе­ние - номеру строки, в которой располо­12 3 4жен ферзь (рис. 5.19).*Определим, что для векторногопредставления означает «бьет». Ферзь j*(=:0> 1 3 I 1 4 | 2 | «бьет» ферзь i, если они расположены на*12 3 4одной диагонали, вертикали или гори­*зонтали. При векторном представлениишахматной доски расположение на од­ной вертикали невозможно, следователь­Рис.

5.19. Представление дан­но,необходимо проверять два условия:ных для задачи о ферзях1825. Модульное программированиеpole[j] = poIe[i] - одна горизонталь;I Pol^LJ] " pole[i] I =1 j - i I - одна диагональ.Для определения всех вариантов расстановок ферзей, удовлетворяющихусловию задачи, необходимо проверить все возможные варианты расстано­вок.Полный перебор. Полный перебор будем реализовывать в соответствиис алгоритмом, описанным в начале данного раздела. Ниже приведена про­грамма, реализующая стратегию полного перебора для данной задачи.

Онавключает две функции: функцию генерации вариантов расстановки и функ­цию проверки комбинации.Функция генерации вариантов возвращает в точку вызова булевское зна­чение: true - если еще есть варианты, false - если просмотрены все вариан­ты. Следующий вариант расстановки возвращается через параметр-перемен­ную pole.Функция проверки комбинаций для каждых двух ферзей на доске прове­ряет условие «бьет».

Если хотя бы один раз это условие выполняется, то дан­ный вариант не является решением.Program ex;Type p=arrayfl.. 100] of integer;Var pole.'p;i,m: integer;{функция проверки комбинации}Function newj-(m:integer;pole:p).boolean;Var iJ: integer;Beginnew_r:=false;for i:=I to m-J doforj:=i+l to m doif(pole[i]='polelj]) or(abs(polelj]'pole[i])==j'i) then exit;new_r:-true;End;{функция генерации вариантов}Function Variantfm:integer; Var pole:p):boolean;Var i: integer;BeginpolefmJ:=pole[mJ+I;{добавление единицы в младший разрядсчетчика}for i:=m downto 2 do{обработка переносов}if pole [i] > m thenbegin pole[i]:=l;polefi'l]: =^polefi'IJ+1;end;183Часть I.

Основы алгоритмизации и процедурное программированиеifpoIefJJ <=т then {если есть еще варианты}Variant: =trueelse Variant:'='false;End;{основная программа}BeginWritelnCВведите размер доски');ReadLn(m);for i:=l to m dopole[i]:=l;{исходная комбинация}repeatif Newr(m,pole) then{проверяем расстановку}beginfor i:=l to m do Write(pole[i]:2);Writein;end;until not Variant(m,pole); {если есть варианты, то генериру­ем новый вариант}EndНедостаток полного перебора, как уже говорилось выше, заключается втом, что вычислительная сложность данного решения составляет 0(т"^).Ограниченный перебор, реализованный с использованием рекурсии.

Длягенерации комбинаций будем использовать древовидную рекурсию, на каж­дом уровне которой ставится один ферзь m различными способами. Приэтом появляется возможность проверки перспективности уже имеющейсякомбинации. Поясним сказанное на примере доски 4x4.На первом шаге первого ферзя можно поставить на одно из четырех по­лей первого вертикального ряда, что соответствует комбинациям]..., 2...,3...,4....На втором шаге второго ферзя можно поставить на одно из четырех по­лей второго вертикального ряда.

При этом мы получим 4 комбинации длякаждого варианта установки первого ферзя:11..,21..,31..,41..,12.., 13.., 14..22.., 23.., 24..32.., 33.., 34..42.., 43.., 44..На этом этапе уже можно исключить все варианты, для которых первыедва ферзя «бьют» друг друга: 11.., 12.., 21.., 22.., 23.., 32.., 33.., 34.., 43.., 44..Генерацию остальных комбинаций необходимо продолжить, установив тре­тьего ферзя одним из четырех способов и исключив неперспективные реше­ния. На последнем этапе необходимо установить четвертого ферзя и опять1845, Модульное программирование1421 1422 1423 14242411 2412 2413 2414Рис. 5.20.

Дерево вариантов с отсечением неперспективныхветвейисключить варианты, в которых ферзи бьют друг друга. Оставшиеся вариан­ты являются решениями задачи.На рис. 5.20 показан фрагмент дерева генерации вариантов для m = 4 сотсечением неперспективных ветвей. Первое найденное решение - комбина­ция 2413.На рис. 5.21 показаны алгоритм основной программы, ре1о^рсивной под­программы добавления ферзя ferz и функции проверки перспективности по­лученной комбинации new_r, а ниже приведена соответствующая програм­ма.Program ex;Type p=arrayfl..

Характеристики

Список файлов книги