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

Нажмите для полного просмотра!

Перебор подмножеств и перестановок, слайд №1

Перебор подмножеств и перестановок, слайд №2

Перебор подмножеств и перестановок, слайд №3

Перебор подмножеств и перестановок, слайд №4

Перебор подмножеств и перестановок, слайд №5

Перебор подмножеств и перестановок, слайд №6

Перебор подмножеств и перестановок, слайд №7

Перебор подмножеств и перестановок, слайд №8

Перебор подмножеств и перестановок, слайд №9

Перебор подмножеств и перестановок, слайд №10

Перебор подмножеств и перестановок, слайд №11

Перебор подмножеств и перестановок, слайд №12

Содержание ▲

Вы можете ознакомиться и скачать презентацию на тему Перебор подмножеств и перестановок. Доклад-сообщение содержит 12 слайдов. Презентации для любого класса можно скачать бесплатно. Если материал и наш сайт презентаций Mypresentation Вам понравились – поделитесь им с друзьями с помощью социальных кнопок и добавьте в закладки в своем браузере.

Слайды и текст этой презентации

Слайд 1

Описание слайда:

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

Слайд 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 #include using namespace std; Main() { Int p[100]={0}, i ,n, k; cin >> n; do { // печать множества cout

Слайд 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 smax_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)

Слайд 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 Begin // ввод данных и инициализация перестановки for i:=1 to n do begin a[i]:=random(100); p[i]:=i end;

Слайд 11

Описание слайда:

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]0 then begin k:=n; while a[p[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.

Слайд 12

Описание слайда:

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