Лексичний перебір Печать
Добавил(а) Administrator   
02.11.11 09:24

Лексичний перебір

1.Повернемось до перебору:

а). Ми мали:   1,2,3

1,3,2

2,1,3

2,3,1

3,2,1

3,1,2

 

б). А якщо ми маємо

3,8,7

Як утворити всі можливі перестановки?

1. Утворити перестановки 1,2,3 і використати їх як індексний масив.

 

в) Маємо                                            1,1,2

1,2,1

2,1,1

2. Побудуємо лексичний перебір для довільних  елементів масиву

X=3 2 4 2 4 3 1

а) Рухаємось справа наліво. Крок вперед можна зробити, якщо  наступне число більше за попереднє. Ми зупинилися перед числом 2. Це число потрібно помітити.

X=3  2  4  2 4   3 1

 

б) Рухаємось справа наліво. Крок вперед можна зробити, якщо   число менше за знайдене число(2). Ми зупинилися перед числом 3. Це число потрібно помітити.

X= 3  2  4  23 1

 

в) Переставляємо знайдені числа.

 

X= 3  2  4  32 1

г) Запишемо числа, розміщені після першого знайденого в зворотному порядку.

X=3  2  4  3 1  2  4

функція наступна : логічна

поч.

і:=n

пошук:=хибно

1)

 

4)

і:=k+1; j:=n;

поки І>j пц

t:=x[j]; x[j]:=x[і]; x[і]:=t; іnc(і);

і:=і+1;

кц.

все

наступна:=пошук;

кін.

поч

x[1..n]; ввести х ; поки наступна                 пц вивести х кц кін.