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