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

Пусть имеется квадратная таблица размером N Х N, каждая строка и каждый столбец которой пронумерованы числами от 1 до N. В каждой ячейке таблицы случайным образом генерируются 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. Число шагов в нем строго определено и равно N – размерности матрицы.