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

Смотреть слайды в полном размере
Презентация Перебор подмножеств и перестановок


Вашему вниманию предлагается презентация на тему «Перебор подмножеств и перестановок», с которой можно предварительно ознакомиться, просмотреть текст и слайды к ней, а так же, в случае, если она вам подходит - скачать файл для редактирования или печати.

Презентация содержит 12 слайдов и доступна для скачивания в формате ppt. Размер скачиваемого файла: 65.47 KB

Просмотреть и скачать

Pic.1
Перебор подмножеств и перестановок Хадиев Р. М.
Перебор подмножеств и перестановок Хадиев Р. М.
Pic.2
Перебор подмножеств Для n=4 – {X1,X2,X3,x4} // (0000) -> { } // (0001) -> { X4 } // (0010) -&g
Перебор подмножеств Для 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
Pic.3
#include <iostream> #include <iostream> using namespace std; Main() { Int p[100]={0}, i
#include <iostream> #include <iostream> using namespace std; Main() { Int p[100]={0}, i ,n, k; cin >> n; do { // печать множества cout << '('; for (i=0; i<n; i++) cout << p[i] << ' '; cout << ' ) -> { '; for (i=1; i<=n; i++) if (p[i-1]) cout <<‘X’ << i << ' '; cout << '}\n';
Pic.4
Задача о ранце Задано множество товаров с весами – v1, v2, v3 … Максимальная возможная загрузка ранц
Задача о ранце Задано множество товаров с весами – v1, v2, v3 … Максимальная возможная загрузка ранца Т. Описание переменных var x, {массив индексов для перебора подмножеств} max,{массив для максимума} v:array[0. . 10] of integer;{массив весов} max_v, {максимальный вес найденной загрузки} n,j,i,t:integer;{t – предел ранца}
Pic.5
Процедура печати задачи о ранце procedure print; var s,i:integer; begin write('( '); for i
Процедура печати задачи о ранце 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;
Pic.6
Основной модуль задачи о ранце begin read(n,t); for i:=1 to n do begin read(v[i]); // вес i-го товар
Основной модуль задачи о ранце 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.
Pic.7
2^N  время работы в сутках 2^5=32  1. 7e-13 2^10=1024  2. 4e-10 2^15=32768  1e-8 2^20=1048576 
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
Pic.8
Перебор перестановок Для n=4 – (1,2,3,4)  (X1,X2,X3,X4) // (1,2,3,4)  (X1,X2,X3,X4) // (1,2,4,3) 
Перебор перестановок Для 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)
Pic.9
Сортировка перебором перестановок Const n=10; Var a, p:array[1. . n] of integer; i, j, k, r:integer;
Сортировка перебором перестановок 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;
Pic.10
Begin Begin // ввод данных и инициализация перестановки for i:=1 to n do begin a[i]:=random(100); p[
Begin Begin // ввод данных и инициализация перестановки for i:=1 to n do begin a[i]:=random(100); p[i]:=i end;
Pic.11
repeat // проверка упорядоченности и вывод результата repeat // проверка упорядоченности и вывод рез
repeat // проверка упорядоченности и вывод результата repeat // проверка упорядоченности и вывод результата if sort then begin print; halt end; j:=n; // 1) (1,3,5,7,6,4,2) – поиск элементов перестановки while (j>0) and (p[j]<p[j-1]) do j-=1; if j>0 then begin k:=n; while a[p[k]]<a[p[j]] do k-=1; // 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.
Pic.12
N!  время работы в сутках 5!=120  3e-10 6!=720  2e-9 7!=5 040  2e-8 8!=40 320  1. 6e-7 9!=362 8
N!  время работы в сутках 5!=120  3e-10 6!=720  2e-9 7!=5 040  2e-8 8!=40 320  1. 6e-7 9!=362 880  1. 6e-6 10!=3 628 800  1. 8e-5 – секунда! 11!=39 916 800  2e-4 12!=479 001 600  0. 002 13!=6 227 020 800  0. 04 14!=87 178 291 200  0. 59 – пол дня! 15!=1307 674 468 000  9. 4 16!=2e12  160. 6 17!=36e14  2895


Скачать презентацию

Если вам понравился сайт и размещенные на нем материалы, пожалуйста, не забывайте поделиться этой страничкой в социальных сетях и с друзьями! Спасибо!