Методы программрования: переборные алгоритмы

Во многих прикладных задачах требуется найти оптимальное решение среди очень большого (но конечного!) числа вариантов. Иногда удается построить это решение сразу, но в большинстве случаев единственный способ его отыскать состоит в переборе ВСЕХ возможных вариантов и сравнении их между собой. Поэтому так важно для нас научиться строить алгоритмы ПЕРЕБОРА различных комбинаторных объектов — последовательностей, перестановок, подмножеств и т.д.

Схема перебора всегда будет одинакова:

    — во-первых, надо установить ПОРЯДОК на элементах, подлежащих перечислению (в частности, определить, какой из них будет первым, а какой последним);

    — во-вторых, научиться переходить от произвольного элемента к HЕПОСРЕДСТВЕHHО СЛЕДУЮЩЕМУ за ним (т.е. для заданного элемента x1 строить такой элемент x2, что x1<x2 и между x1 и x2 нет других элементов).

Hаиболее естественным способом упорядочения составных объектов является ЛЕКСИКОГРАФИЧЕСКИЙ порядок, принятый в любом словаре (сначала сравниваются первые буквы слов, потом вторые и т.д.) — именно его мы и будем чаще всего использовать. А вот процедуру получения следующего элемента придется каждый раз изобретать за- ново. Пока запишем схему перебора в таком виде:

X:=First; while X<>Last do Next(X); где First — первый элемент; Last — последний элемент; Next — процедура получения следующего элемента.

Hапечатать все последовательности длины N из чисел 1,2,…,M.

First = (1,1,…,1) Last = (M,M,…,M)

Всего таких последовательностей будет M^N (докажите!). Чтобы понять. как должна действовать процедура Next, начнем с примеров. Пусть N=4,M=3. Тогда:

Next(1,1,1,1) -> (1,1,1,2) Next(1,1,1,3) -> (1,1,2,1) Next(3,1,3,3) -> (3,2,1,1)

Теперь можно написать общую процедуру Next:

procedure Next; begin {найти i: X[i]<M,X[i+1]=M,…,X1372=M}; X[i]:=X[i]+1; X[i+1]:=…:=X1372:=1 end;

Если такого i найти не удается, то следующей последовательности нет — мы добрались до последней (M,M,…,M). Заметим также, что если бы членами последовательности были числа не от 1 до M, а от 0 до M-1, то переход к следующей означал бы прибавление 1 в M-ичной системе счисления. Полная программа на Паскале выглядит так:

program Sequences; type Sequence=array [byte] of byte; var M,N,i:byte; X:Sequence; Yes:boolean; procedure Next(var X:Sequence;var Yes:boolean); var i:byte; begin i:=N; {поиск i} while (i>0)and(X[i]=M) do begin X[i]:=1;dec(i) end; if i>0 then begin inc(X[i]);Yes:=true end else Yes:=false end; begin write(‘M,N=’);readln(M,N); for i:=1 to N do X[i]:=1; repeat for i:=1 to N do write(X[i]);writeln; Next(X,Yes) until not Yes end.

Hапечатать все перестановки чисел 1..N (то есть последовательности длины N, в которые каждое из чисел 1..N входит ровно по одному разу).

First = (1,2,…,N) Last = (N,N-1,…,1)

Всего таких перестановок будет N!=N*(N-1)*…*2*1 (докажите!). Для составления алгоритма Next зададимся вопросом: в каком случае i-ый член перестановки можно увеличить, не меняя предыдущих? Ответ: если он меньше какого-либо из следующих членов (членов с номерами больше i).

Мы должны найти наибольшее i, при котором это так, т.е. такое i, что X[i]<X[i+1]>…>X1372 (если такого i нет, то перестановка последняя). После этого X[i] нужно увеличить минимально возможным способом, т.е. найти среди X[i+1],…,X1372 наименьшее число, большее его. Поменяв X[i] с ним, остается расположить числа с номерами i+1,…,N так, чтобы перестановка была наименьшей, то есть в возрастающем порядке. Это облегчается тем, что они уже расположены в убывающем порядке:

procedure Next; begin {найти i: X[i]<X[i+1]>X[i+2]>…>X1372}; {найти j: X[j]>X[i]>X[j+1]>…>X1372}; {обменять X[i] и X[j]}; {X[i+1]>X[i+2]>…>X1372}; {перевернуть X[i+1],X[i+2],…,X1372}; end;

Теперь можно написать программу:

program Perestanovki; type Pere=array [byte] of byte; var N,i,j:byte; X:Pere; Yes:boolean; procedure Next(var X:Pere;var Yes:boolean); var i:byte; procedure Swap(var a,b:byte); {обмен переменных} var c:byte; begin c:=a;a:=b;b:=c end; begin i:=N-1; {поиск i} while (i>0)and(X[i]>X[i+1]) do dec(i); if i>0 then begin j:=i+1; {поиск j} while (j<N)and(X[j+1]>X[i]) do inc(j); Swap(X[i],X[j]); for j:=i+1 to (N+i) div 2 do Swap(X[j],X[N-j+i+1]); Yes:=true end else Yes:=false end; begin write(‘N=’);readln(N); for i:=1 to N do X[i]:=i; repeat for i:=1 to N do write(X[i]);writeln; Next(X,Yes) until not Yes end.

Эта программа демонстрирует два алгоритма перебора перестановок: перебор в лексикографическом порядке и перебор методом рекурсии. С помощью кнопки «Шаг» программа совершает очередной шаг построения следующей перестановки, с помощью кнопки «Перестановка» программа сразу переходит к следующей перестановке. Кнопкой «Авто» программа переключается в автоматический режим. Кнопки «Быстрее» и «Медленнее» позволяют варьировать скорость работы программы в автоматическом режиме. С помощью кнопки «Сброс» алгоритм инициализируется для работы. До того, как совершен хотя бы один шаг можно изменить количество элементов

Перебор перестановок в лексикографическом порядке

Каждая следующая перестановка строится следующим образом:

  1. На первом шаге программы, двигаясь с конца массива, сравниваем соседние элементы, если предыдущий (по расположению в массиве) элемент больше следующего, двигаемся дальше, если меньше, останавливаемся и запоминаем его номер (), этот элемент будет изменен (на этом шаге он отмечается красным треугольником снизу, а потом просто красным цветом).
  2. Элементы, стоящие слева от -го, не изменяем (они станут окрашенными в серый цвет). Среди элементов, стоящих справа, нужно выбрать элемент (), который должен встать на место -го. Это минимальный элемент среди тех, которые больше -го (отмечается синим треугольником, потом просто синим цветом).
  3. Меняем -ый и -ый элементы.
  4. Осталось упорядочить по возрастанию элементы, стоящие справа от нового -го элемента, но т.к. они упорядочены по убыванию, достаточно их обернуть (оборачиваемая часть обозначена стрелками).

Запустить визуализатор

Перебор перестановок методом рекурсии

Основная идея метода состоит в следующем: для того, чтобы построить все перестановки для элементов, построим все перестановки для -1 элементов и добавим к каждой из них -ый элемент всеми возможными способами. Например к перестановке 2431 элемент 5 добавим следующими способами: 24315, 24351, 24531, 25431, 52431.

Методы программирования: переборные алгоритмы

Можно заметить, что 5 как бы двигается по массиву. Для построения следующей перестановки подвинется 4, после чего снова будет двигаться 5. На протяжении всего процесса хранится информация о том, в каком направлении двигается каждый элемент (показано стрелками над квадратиками с элементами).

При построении следующей перестановки на первом шаге рассматривается наибольший элемент (отмечен красным треугольником). Если в направлении его движения еще есть, куда двигаться, передвигаем на одну позицию, это и будет следующей перестановкой. Если двигаться больше некуда (элемент стоит на краю массива и направление его движения — к краю), то меняем его направление движения, после чего «забываем» про этот элемент и строим следующую перестановку для оставшейся части массива, для этого находим в ней наибольший элемент и т.д. (повторяем все снова).

Запустить визуализатор

Автор визуализатора: Михалев Евгений


Митя / 2008-02-21 01:04:09

Изучаю защиту данных, создавал перебор ключей, алгоритм "Перебор перестановок в лексикографическом порядке" подошел супер! Особенно для ситуаций с одинаковыми буквами (нет копий). Большое спасибо за наглядную иллюстрацию, без нее не справился бы так быстро!

Marbo / 2008-06-14 13:56:14

Большое спасибо, отличные описание и визуализация.

Alex / 2008-06-23 18:14:09

Спасибо за визуализацию, с ней все гораздо понятнее

Дамир / 2008-09-27 03:57:42

Первая программа бажная. Случай когда элементов 4. Идут перестановки 1234 1243 1342 а дальше программа глючит и превращает эту перестановку в 1324.

WC / 2009-04-13 13:45:52

Спасибо, но есть два вопроса:

1. Будет ли добавлена опция переборов с вырожденными перестановками, когда несколько элементов одинаковы?

Нет. Визуализатор разработан только для множеств, а не для мультимножеств.

2. Какой из представленных алгоритмов переборов работает быстрее?

См. соответствующие статьи на нашем сайте.

Игорь / 2009-09-10 21:26:47

Супер сайт!!!

SL / 2010-01-16 23:50:52

Большое спасибо, все просто и понятно. Даже я сразу разобрался.

Андрей / 2012-11-21 10:59:11

Среди элементов, стоящих справа, нужно выбрать элемент (k), который должен встать на место m-го.

Это минимальный элемент среди тех, которые больше m-го (отмечается синим треугольником, потом просто синим цветом).

Если элемент(к) не определяется однозначно, то есть несколько равных элементов претендуют на его место, то какой из них следует выбрать? Пример: 123455, какую из 5рок надо поменять с 4кой?

См. выше — реплику на вопрос от 2009-04-13.<>

Андрей / 2012-11-22 10:00:17

См. выше — реплику на вопрос от 2009-04-13.

Тот ответ про визуализатор, мой вопрос про был алгоритм.

Алгоритм рассчитан на обработку МНОЖЕСТВА (см. описание над окном визуализатора), а не МУЛЬТИМНОЖЕСТВА. Во втором случае необходима некоторая модификация.

Серый / 2013-12-29 18:31:44

Спасибо! Кучу сайтов облазил и только тут разобрался.

Перестановка двух элементов массива

Предыдущая12131415161718192021222324252627Следующая

 

Для перестановки двух элементов массива x[] с индексами k и m, необходимо использование дополнительной переменной (tmp), для хранения копии одного из элементов (рисунок 6.3 а), но можно обойтись и без использования дополнительной переменной tmp.

Полный перебор перестановок

В этом случае алгоритм перестановки имеет следующий вид (рисунок 6.3 б).

В большинстве случаев предпочтительнее использовать первый способ, поскольку он не содержит дополнительных вычислений, что особенно важно при перестановке вещественных чисел.

 

tmp=x[k]; x[k]=x[m]; x[m]=tmp; x[k]=x[k]+x[m]; x[m]=x[k]-x[m]; x[k]=x[k]-x[m];
(а) (б)

Рис. 6.3 Алгоритм и фрагмент программы перестановки двух элементов массива c использованием дополнительной переменной (а) и без нее (б)

 

Пример 6.1. Переставить первый и последний элементы массива x[] местами. Количество элементов массива n.

Решение:

В С нумерация элементов массива начинается с нуля, поэтому номер последнего элемента массива (n–1) .

1 способ: tmp=x[0];

x[0]=x[n-1];

x[n-1]=tmp;

2 способ: x[0]=x[0]+x[n-1];

x[n-1]=x[0]-x[n-1];

x[0]=x[0]-x[n-1];

 

Пример 6.2.Поменять местами заданный элемент массива x[k] с последующим.

Решение:

При решении этой задачи необходимо учитывать, что если заданный элемент массива x[k] является последним, то обмен выполнить не возможно, поскольку последующий элемент отсутствует.

 

if(k == n-1) puts("Обмен не возможен."); else { tmp=x[k]; x[k]=x[k+1]; x[k+1]=tmp; }

Рис. 6.4 Алгоритм и фрагмент программы перестановки заданного элемент массива x[k] с последующим

 

При перестановке с предыдущим элементом обмен не возможен, если заданный элемент является первым (k=0).

 

Предыдущая12131415161718192021222324252627Следующая

Алгоритм. Основные принципы составления алгоритмов. Примеры.

⇐ Предыдущая20212223242526272829Следующая ⇒

Алгоритм-система точных и понятных предписаний, опр-ая последовательность элементарных операций над исходными данными, выполнение кот-ых обеспечивает решение задач данного типа.

Свойства алгоритма:

дискретность-последовательность решения (процесс) задач должен быть разбит на последовательность отдельных шагов.

понятность-алгоритм обязательно должен быть понятен исполнителю. В связи с этим алгоритм нужно разрабатывать с ориентацией на опр-ого исполнителя, т.е.

Перебор перестановок

в алгоритм можно включать команды из систем команд данного исполнителя.

детерминированность — будучи понятным, алгоритм не должен содержать команды, смысл кот-ых может восприниматься неоднозначно. Нарушение составителями алгоритмов этих требований приводит к тому, что одна и та же программа после выполнения разными исполнителями дает не одинаковые результаты.

результативность –состоит в том, что при точном исполнении всех команд алгоритма, процесс решения задач должен прекратиться за конечное число шагов и при этом должен быть получен опред-ый при постановке задач результат.

массовость— пригодность алгоритма для решения задач некоторого класса.

Способы записи алгоритма:

словесный – способ на естественном языке.

графический-описания алгоритма с помощью схем.

Процесс выполнения операций или групп операций

ввод исходных данных, вывод результата

Решение-выбор направления выполнения

Модификация-выполнение операций , меняющих команды или группы команд, изменяющих программ.

Соединители линий на одной странице.

Межстраничные соединители.

язык программирования –удобен для ввода в комп-р.

псевдокод-это язык, к-ый использует структуру и синтексис достаточно формализованного языка и одновременно допускает конструкции естеств. Языка.

 

 

Виды алгоритмов и основные принципы составления алгоритмов.

Линейный – алгоритм, в кот-ом команды выполняются последовательно друг за другом в порядке их естественного следования независимо от каких-либо условий. S1, s2 , S3…Sn

-ветвящийся ( разветвящийся) — это процесс, в кот-ом его реализация происходит по одному из нескольких заранее предусмотренных направлений, в зависимости от исходных данных или промежуточных результатов.

· Полная условная конструкция (полное ветвление)

 

· Неполное условная конструкция

 

· Выбор из нескольких

 

циклический – алгоритм, в кот-ом последовательность может выполняться более 1 раза.

· Цикл с параметром

 

· Цикл с предусловием. Может не выполниться ни разу. В теле цикла обязательно нах-ся оператор, к-ый изменяет значение переменной, входящей в блок Q.

 

· Цикл с постусловием. Выполняется хоть один раз.

 

Основные принципы алгоритмизации:

1. Выявить исходные данные, результаты и назначить им имена.

2. Метод решения задач.

3. Разбить метод решения задач на этапы.

4. При граф-ом представлении алгоритма каждый этап в виде соответствующего блока –схемы алгоритма и указать линиями связи порядок их выполнения.

5. В полученной схеме при любом варианте вычислений.

— предусмотреть выдачу результатов или сообщений об их отсутствии.

-обеспечить возможности после выполнение любой операции так или иначе перейти к блоку конец.

40.Основные алгоритмические структуры

Мы уже рассмотрели основные понятия программирования и переходим немного ближе к делу (но только ближе, программировать будем позже).

Рассмотрим основные структуры алгоритмов, а их шесть:

· Следование. Это последовательность блоков (или групп блоков) алгоритма. В программе следование представлено в виде последовательного выполнения операций

 

 

· Разветвление. Данная алгоритмическая структура применяется в том случае, когда в зависимости от условия необходимо выполнить одно или другое действие

· Обход. Эта структура является частным случаем разветвения, когда в одной из ветвей нет никаких действий.

 

· Множественный выбор. Эта структура является обобщением раветвления, когда необходимо выполнить одно из нескольких действий в зависимости от значения переменной A.

 

· Цикл До. Эта алгоритмическая структура применяется в том случае, когда нужно какие-либо операции исполнить несколько раз до того, как будет истинным определенное условие. Бло к выполняемый многократно называется телом цикла. Особенностью данного цикла является его обязательное исполнение хотя бы один раз.

 

 

· Цикл Пока. Это цикл отличается от цикла До тем, что проверка условия осуществляется перед самым первым исполнением операторов тела цикла.

 

 


⇐ Предыдущая20212223242526272829Следующая ⇒


Дата добавления: 2017-02-25; просмотров: 1846 | Нарушение авторских прав


Похожая информация:


Поиск на сайте:


Добавить комментарий

Ваш e-mail не будет опубликован. Обязательные поля помечены *