Презентация «Перебор подмножеств и перестановок»
Смотреть слайды в полном размере 
Вы можете ознакомиться с презентацией онлайн, просмотреть текст и слайды к ней, а также, в случае, если она вам подходит - скачать файл для редактирования или печати. Документ содержит 12 слайдов и доступен в формате ppt. Размер файла: 65.47 KB
Pic.1
Перебор подмножеств и перестановок Хадиев Р. М.
Pic.2
Перебор подмножеств Для n=4 – {X1,X2,X3,x4} // (0000) -> { } // (0001) -> { X4 } // (0010) -> { X3 } // (0011) -> { X3 X4} // (0100) -> { X2 } // (0101) -> { X2 X4 } // (0110) -> …
Pic.3
![#include <iostream> #include <iostream> using namespace std; Main() { Int p[100]={0}, i](/documents_6/39db092248ee0e1b6742af2e335a720f/img2.jpg)
#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++) …
Pic.4
Задача о ранце Задано множество товаров с весами – v1, v2, v3 … Максимальная возможная загрузка ранца Т. Описание переменных var x, {массив индексов для перебора подмножеств} max,{массив для …
Pic.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 …
Pic.6
![Основной модуль задачи о ранце begin read(n,t); for i:=1 to n do begin read(v[i]); // вес i-го товар](/documents_6/39db092248ee0e1b6742af2e335a720f/img5.jpg)
Основной модуль задачи о ранце 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 …
Pic.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 – …
Pic.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) …
Pic.9
![Сортировка перебором перестановок Const n=10; Var a, p:array[1. . n] of integer; i, j, k, r:integer;](/documents_6/39db092248ee0e1b6742af2e335a720f/img8.jpg)
Сортировка перебором перестановок 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; …
Pic.10
![Begin Begin // ввод данных и инициализация перестановки for i:=1 to n do begin a[i]:=random(100); p[](/documents_6/39db092248ee0e1b6742af2e335a720f/img9.jpg)
Begin Begin // ввод данных и инициализация перестановки for i:=1 to n do begin a[i]:=random(100); p[i]:=i end;
Pic.11
repeat // проверка упорядоченности и вывод результата repeat // проверка упорядоченности и вывод результата if sort then begin print; halt end; j:=n; // 1) (1,3,5,7,6,4,2) – поиск элементов …
Pic.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 …
Если вам понравился сайт и размещенные на нем материалы, пожалуйста, не забывайте поделиться этой страничкой в социальных сетях и с друзьями! Спасибо!
