Сгенерируйте матрицу Адамара заданного порядка

Матрица Адамара — это квадратная матрица с уникальным свойством, состоящим в том, что любые две ее строки ортогональны. В геометрических терминах это означает, что две строки обозначают два перпендикулярных вектора, а в комбинаторных терминах это означает, что две строки имеют совпадающие элементы ровно на половине мест, а другие половины элементов не совпадают.

Некоторые важные свойства матрицы Адамара:

• Матрица Адамара первого порядка равна {{1}} .
• Матрица Адамара содержит только +1 и -1 в качестве своих элементов.
• Любая матрица Адамара порядка 2 ^m может быть построена с использованием матриц Адамара порядка 2 ^m-1 следующим образом. Это облегчает создание матрицы, если мы знаем матрицы более низкого порядка.

H_2m
{ {H_2m-1 ,  H_2m-1}
  {H_2m-1, -H_2m-1}}

Учитывая неотрицательное целое число M , задача состоит в том, чтобы сгенерировать матрицу Адамара порядка 2 ^M .

Примеры:

Input: M = 2
Output:
1 1 1 1
1 -1 1 -1
1 1 -1 -1
1 -1 -1 1

Input: M = 3
Output:

Hadamard matrix of order 8

Подход: это простая проблема, основанная на реализации. Идея состоит в том, чтобы использовать приведенное выше соотношение и выполнять итерации от порядка 1 до 2 ^M для создания матрицы Адамара порядка 2 ^M .

Следуйте шагам, указанным ниже, чтобы реализовать идею.

• Вычислите 2 ^M (скажем, N ) и сохраните его.
• Объявите матрицу порядка N .
• Теперь инициализируем 0 ^-й столбец 0 ^-го элемента строки матрицы как 1 .
• Затем запустите цикл, который копирует верхнюю левую четверть в другие четверти с правильным знаком, соответствующим свойству матрицы Адамара, как показано ранее в этой статье. Размер матрицы растет на каждой итерации и в итоге достигает порядка N .
• Наконец, отобразите матрицу на консоли.

Ниже приведена реализация описанного выше подхода.

Временная сложность: O( ^2M )
Вспомогательное пространство: O(2 ^м )