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

Июль 25, 2022

Главная
Информатика
Перебор подмножеств и перестановок

Содержание

2. Перебор подмножеств Для n=4 – {X1,X2,X3,x4} // (0000) -> { } // (0001) -> { X4
3. #include using namespace std; Main() { Int p[100]={0}, i ,n, k; cin >> n; do {
4. Задача о ранце Задано множество товаров с весами – v1, v2, v3 … Максимальная возможная загрузка
5. Процедура печати задачи о ранце procedure print; var s,i:integer; begin write('( '); for i:=1 to n
6. Основной модуль задачи о ранце begin read(n,t); for i:=1 to n do begin read(v[i]); // вес
7. 2^N ⬄ время работы в сутках 2^5=32 ⬄ 1.7e-13 2^10=1024 ⬄ 2.4e-10 2^15=32768 ⬄ 1e-8 2^20=1048576
8. Перебор перестановок Для n=4 – (1,2,3,4) ⬄ (X1,X2,X3,X4) // (1,2,3,4) ⬄ (X1,X2,X3,X4) // (1,2,4,3) ⬄ (X1,X2,X4,X3)
9. Сортировка перебором перестановок Const n=10; Var a, p:array[1..n] of integer; i, j, k, r:integer; Function sort:boolean;
10. Begin // ввод данных и инициализация перестановки for i:=1 to n do begin a[i]:=random(100); p[i]:=i end;
11. repeat // проверка упорядоченности и вывод результата if sort then begin print; halt end; j:=n; //
13. Скачать презентацию

Слайд 2

Перебор подмножеств
Для n=4 – {X1,X2,X3,x4}
// (0000) -> { }
// (0001) -> {

X4 }
// (0010) -> { X3 }
// (0011) -> { X3 X4}
// (0100) -> { X2 }
// (0101) -> { X2 X4 }
// (0110) -> { X2 X3 }
// (0111) -> { X2 X3 X4
// (1000) -> { X1 }
// (1001) -> { X1 X4 }
// (1010) -> { X1 X3 }
// (1011) -> { X1 X3 X4}
// (1100) -> { X1 X2 }
// (1101) -> { X1 X2 X4 }
// (1110) -> { X1 X2 X3 }
// (1111) -> { X1 X2 X3 X4

Слайд 3

#include
using namespace std;
Main() {
Int p[100]={0}, i ,n, k;
cin

>> n;
do {
// печать множества
cout << '(';
for (i=0; i cout << p[i] << ' ';
cout << ' ) -> { ';
for (i=1; i<=n; i++)
if (p[i-1]) cout <<‘X’ << i << ' ';
cout << '}\n';

// переход к след. подмнож-ву
j=n-1;
while (p[j] && j>0) {
p[j]=0;
j--;
}
if (j) \\ новый элемент
p[j]=1;
}
while (j>0);
}

Слайд 4

Задача о ранце
Задано множество товаров с весами –
v1, v2, v3

…
Максимальная возможная загрузка ранца Т.
Описание переменных
var
x, {массив индексов для перебора подмножеств}
max,{массив для максимума}
v:array[0..10] of integer;{массив весов}
max_v, {максимальный вес найденной загрузки}
n,j,i,t:integer;{t – предел ранца}

Слайд 5

Процедура печати задачи о ранце
procedure print;
var s,i:integer;
begin
write('( ');
for i:=1

to n do write(x[i],' ');
s:=0;
write(') <-> { ');
for i:=1 to n do begin
if x[i]=1 then write('X[',i,'](',v[i],') ');
s+=v[i]*x[i];
end;
if s<=t then begin
writeln('}=',s,' +');
if s>max_v then begin // фиксация максимального подмножества
max_v:=s;
max:=x
end
end
else writeln('} – недопустимая загрузка')
end;

Слайд 6

Основной модуль задачи о ранце
begin
read(n,t);
for i:=1 to n do begin
read(v[i]);

// вес i-го товара
x[i]:=0 // первое множество пустое
end;
max:=x; max_v:=0; // параметры пустого множества
repeat
print;
j:=n;
while (x[j]=1) and (j>0) do begin
x[j]:=0;
j-=1
end;
if j>0 then begin x[j]:=1
until j=0;
// печать варианта максимальной загрузки
writeln('MAX');
x:=max;
print
end.

Слайд 7

2^N ⬄ время работы в сутках
2^5=32 ⬄ 1.7e-13
2^10=1024 ⬄ 2.4e-10
2^15=32768 ⬄

1e-8
2^20=1048576 ⬄ 4.9e-7
2^25=33554432 ⬄ 2e-5
2^30=1e9 ⬄ 7.5e-4 – секунда!
2^35=34e9 ⬄ 0.028
2^40=101e10 ⬄ 1.02 – день!
2^45=35e12 ⬄ 36.8
2^50=1.1e15 ⬄ 1309

Слайд 8

Перебор перестановок Для n=4 – (1,2,3,4) ⬄ (X1,X2,X3,X4)
// (1,2,3,4) ⬄ (X1,X2,X3,X4)
// (1,2,4,3) ⬄

(X1,X2,X4,X3)
// (1,3,2,4) ⬄ (X1,X3,X2,X4)
// (1,3,4,2) ⬄ (X1,X3,X4,X2)
// (1,4,2,3) ⬄ (X1,X4,X2,X3)
// (1,4,3,2) ⬄ (X1,X4,X3,X2)
// (2,1,3,4) ⬄ (X2,X1,X3,X4)
// (2,1,4,3) ⬄ (X1,X2,X3,X4)
// (2,3,1,4) ⬄ (X2,X3,X1,X4)
// (2,3,4,1) ⬄ (X2,X3,X4,X1)
// (2,4,1,3) ⬄ (X2,X4,X1,X3)
// (2,4,3,1) ⬄ (X2,X4,X3,X1)
// (3,1,2,4) ⬄ (X3,X1,X2,X4)
// (3,1,4,2) ⬄ (X3,X1,X4,X2)
// (3,2,1,4) ⬄ (X3,X2,X1,X4)

// (3,2,4,1) ⬄ (X3,X2,X4,X1)
// (3,4,1,2) ⬄ (X3,X4,X1,X2)
// (3,4,2,1) ⬄ (X3,X4,X2,X1)
// (4,1,2,3) ⬄ (X4,X1,X2,X3)
// (4,1,3,2) ⬄ (X4,X1,X3,X2)
// (4,2,1,3) ⬄ (X4,X2,X1,X3)
// (4,2,3,1) ⬄ (X4,X2,X3,X1)
// (4,3,1,2) ⬄ (X4,X3,X1,X2)
// (4,3,2,1) ⬄ (X4,X3,X2,X1)

1) // (1, 3, 5, 7, 6, 4, 2) – поиск элементов перестановки
2) // (1, 3, 6, 7, 5, 4, 2) – перестановка элементов
3) // (1, 3, 6, 2, 4, 5, 7) – транспонирование

Слайд 9

Сортировка перебором перестановок
Const n=10;
Var a, p:array[1..n] of integer;
i, j, k,

r:integer;
Function sort:boolean; // проверка упорядоченности перестановки
Var ch:boolean;
Begin
ch:=true;
for i:=1 to n do
if a[p[i]]>a[p[i+1]] then ch:=false ;
sort:=ch
End;
Procedure print; // печать упорядоченной последовательности
Begin
for i:=1 to n do
write(a[pi]],’ ‘)
End;

Слайд 10

Begin
// ввод данных и инициализация перестановки
for i:=1 to n

do begin
a[i]:=random(100);
p[i]:=i
end;

Слайд 11

repeat // проверка упорядоченности и вывод результата
if sort

then begin print; halt end;
j:=n; // 1) (1,3,5,7,6,4,2) – поиск элементов перестановки
while (j>0) and (p[j] if j>0 then begin
k:=n;
while a[p[k]] // 2) (1,3,6,7,5,4,2) – перестановка элементов
r:=a[p[k]]; a[p[k]]:=a[p[j]]; a[p[j]]:=r;
k:=(n-j) div 2; // 3) (1,3,6,2,4,5,7) – транспонирование
while k>0 do begin
r:=a[p[k+j]]; a[p[k+j]]:=a[p[n-k+1]]; a[p[n-k+1]]:=r
end
end
until j=0 // условие завершения
End.