Скачать презентацию
Идет загрузка презентации. Пожалуйста, подождите
1
Постановка задачи Описание алгоритма 1 Описание алгоритма 2 Математическая постановка задачи Сравнение алгоритмов Выбор оптимального алгоритма на примере Канторовского диагонального метода
2
Пусть имеется квадратная таблица размера N Х N, каждая строка и каждый столбец которой занумерованы числами от 1 до N. Известно, что в каждой строке таблицы находится 0 или 1, причем расстановка 0 и 1 в таблице совершенно произвольна. Требуется написать строку из N символов (каждый из этих символов должен быть 0 или 1) так, чтобы она не совпадала целиком ни с одной строкой нашей таблицы.
3
Генерировать строки из N элементов случайным образом и сравнивать с заданными. Такая строка заведомо найдется, т.к. строк N, а количество вариантов генерации различных строк 2 N. Количество искомых строк - 2 N –N.
4
Рассмотрим строку из диагональных элементов. Преобразуем строку, заменив в ней 0 на 1 и наоборот. Рассмотри частный случай (N=8) Таблица 1
5
Рассмотрим частный случай при n=8. Случайным образом заполняются элементы матрицы значений. В результате на диагонали получается строка из 0 и 1. Преобразуем ее элементы в соответствии с алгоритмом 2, тогда получим следующую строку: (Таблица 1)
6
Воспользуемся более строгим математическим языком: пусть A – исходная таблица (двумерный массив) и А[i,j] обозначает ее элемент, находящийся в строке i и столбце j. Тогда диагональ образована элементами А[1,1], А[2,2], А[3,3], …, А[8,8]. Заменим диагональные элементы А[i,i] элементами одномерного массива B[i] по правилу: B[i]=ABS(A[i,i]-1)
![Воспользуемся более строгим математическим языком: пусть A – исходная таблица (двумерный массив) и А[i,j] обозначает ее элемент, находящийся в строке i и столбце j. Тогда диагональ образована элементами А[1,1], А[2,2], А[3,3], …, А[8,8]. Заменим диаг](http://images.myshared.ru/6/672333/slide_6.jpg "Воспользуемся более строгим математическим языком: пусть A – исходная таблица (двумерный массив) и А[i,j] обозначает ее элемент, находящийся в строке i и столбце j. Тогда диагональ образована элементами А[1,1], А[2,2], А[3,3], …, А[8,8]. Заменим диаг")
7
Алгоритм 2 носит название Канторовского диагонального процесса. Если, то диагональный процесс обеспечивает метод пошагового построения бесконечной диагональной строки, причем для выполнения каждого шага нужно знать только "конечный" кусок бесконечной диагонали. С помощью Канторовского диагонального метода существует доступное для школьников доказательство несчетности множества вещественных чисел R
8
1. Алгоритм 2 эффективнее. 2. Алгоритм 2 более производительный. 3. Алгоритм 2 строго детерминирован. 4. Число шагов в нем строго определено и равно N – размерности матрицы. 5. Алгоритм 2 более прост и изящен.
Еще похожие презентации в нашем архиве:
