Постановка задачи Описание алгоритма 1 Описание алгоритма 2 Математическая постановка задачи Сравнение алгоритмов Выбор оптимального алгоритма на примере Канторовского диагонального метода

Пусть имеется квадратная таблица размера N Х N, каждая строка и каждый столбец которой занумерованы числами от 1 до N. Известно, что в каждой строке таблицы находится 0 или 1, причем расстановка 0 и 1 в таблице совершенно произвольна. Требуется написать строку из N символов (каждый из этих символов должен быть 0 или 1) так, чтобы она не совпадала целиком ни с одной строкой нашей таблицы.

Генерировать строки из N элементов случайным образом и сравнивать с заданными. Такая строка заведомо найдется, т.к. строк N, а количество вариантов генерации различных строк 2 N. Количество искомых строк - 2 N –N.

Рассмотрим строку из диагональных элементов. Преобразуем строку, заменив в ней 0 на 1 и наоборот. Рассмотри частный случай (N=8) Таблица 1

Рассмотрим частный случай при n=8. Случайным образом заполняются элементы матрицы значений. В результате на диагонали получается строка из 0 и 1. Преобразуем ее элементы в соответствии с алгоритмом 2, тогда получим следующую строку: (Таблица 1)

Воспользуемся более строгим математическим языком: пусть A – исходная таблица (двумерный массив) и А[i,j] обозначает ее элемент, находящийся в строке i и столбце j. Тогда диагональ образована элементами А[1,1], А[2,2], А[3,3], …, А[8,8]. Заменим диагональные элементы А[i,i] элементами одномерного массива B[i] по правилу: B[i]=ABS(A[i,i]-1)

Алгоритм 2 носит название Канторовского диагонального процесса. Если, то диагональный процесс обеспечивает метод пошагового построения бесконечной диагональной строки, причем для выполнения каждого шага нужно знать только "конечный" кусок бесконечной диагонали. С помощью Канторовского диагонального метода существует доступное для школьников доказательство несчетности множества вещественных чисел R

1. Алгоритм 2 эффективнее. 2. Алгоритм 2 более производительный. 3. Алгоритм 2 строго детерминирован. 4. Число шагов в нем строго определено и равно N – размерности матрицы. 5. Алгоритм 2 более прост и изящен.