C ++ двумерный массив битов

У меня есть задание, где мы решаем проблему коммивояжера.
Я не собираюсь лгать, часть, которую я делаю сейчас, я на самом деле не до конца понимаю, что они спрашивают, так что извините, если я сформулирую этот вопрос странно.
Я вроде понимаю, но не полностью.

Мы рассчитываем приблизительное расстояние для продавца. Нам нужно создать двумерный массив из наборов битов, я считаю? Хранение значений в двоичном виде в любом случае.
0 означает, что город не посещался, а 1 означает, что он был посещен.

Нам предоставлен алгоритм, который значительно помогает, и я смогу его закончить, если кто-нибудь здесь сможет помочь с первым шагом:

Create memoisation table [N][(1 << N)]

(где N = количество городов).
Я понял, что 1 << N означает преобразование количества городов (например, 5) в двоичное, а затем смещение набора влево на одно место.

Мои основные проблемы:

  1. Преобразование N в двоичный файл (я думаю, это то, что мне нужно сделать?)
  2. Перемещение набора влево на один
  3. Собственно создание 2-мерного массива этих размеров …

Я могу ошибаться, на самом деле это, вероятно, весьма вероятно … любая помощь приветствуется, спасибо!

0

Решение

Вот общее правило «<<«оператор означает сдвиг влево, а« >> »означает сдвиг вправо. Сдвиг вправо любого числа на 1 эквивалентен делению на 2, а сдвиг влево любого числа на 2 эквивалентен умножению на 2. Например, допустим, что число 7 (двоичное 111 ). Так 7 << 1 станет 1110, что составляет 7 * 2 = 14, а 7 >> 1 станет 11, что составляет 7/2 = 3.

Таким образом, алгоритм для преобразования числа N в массив битов в виде двоичного

  1. N mod 2 (возьмите остаток, если вы разделите N на 2)
  2. Сохраните остаток в коллекции (т. Е. List, Array, Stack)
  3. Разделите N на 2
  4. Если N / 2> 1, повторите с шага 1 с помощью N / 2
  5. В противном случае инвертируйте массив, и вы получите свой битсет.

Перемещение набора влево, если вы имели в виду левостороннее смещение, вы можете сделать это с помощью N<<1

Вот как вы создаете двумерный массив в C ++

[Тип переменной] TwoDimensionalArray [размер] [размер];

Хотя я полагаю, что для этой проблемы вы, возможно, захотите прочитать о битовом наборе C ++ и легко реализовать его с помощью битового набора. Для этого вам просто нужно определить размер набора битов, который вы хотите использовать. Например, если наибольшее значение N равно 15, то вам нужен размер набора битов 4. Поскольку с 4 битами максимальное число, которое вы можете представить, равно 15 (двоичное число 1111). Надеюсь это поможет.

0

Другие решения

Других решений пока нет …

По вопросам рекламы [email protected]