C ++ двумерный массив битов
У меня есть задание, где мы решаем проблему коммивояжера.
Я не собираюсь лгать, часть, которую я делаю сейчас, я на самом деле не до конца понимаю, что они спрашивают, так что извините, если я сформулирую этот вопрос странно.
Я вроде понимаю, но не полностью.
Мы рассчитываем приблизительное расстояние для продавца. Нам нужно создать двумерный массив из наборов битов, я считаю? Хранение значений в двоичном виде в любом случае.
0 означает, что город не посещался, а 1 означает, что он был посещен.
Нам предоставлен алгоритм, который значительно помогает, и я смогу его закончить, если кто-нибудь здесь сможет помочь с первым шагом:
Create memoisation table [N][(1 << N)]
(где N = количество городов).
Я понял, что 1 << N означает преобразование количества городов (например, 5) в двоичное, а затем смещение набора влево на одно место.
Мои основные проблемы:
- Преобразование N в двоичный файл (я думаю, это то, что мне нужно сделать?)
- Перемещение набора влево на один
- Собственно создание 2-мерного массива этих размеров …
Я могу ошибаться, на самом деле это, вероятно, весьма вероятно … любая помощь приветствуется, спасибо!
Решение
Вот общее правило «<<«оператор означает сдвиг влево, а« >> »означает сдвиг вправо. Сдвиг вправо любого числа на 1 эквивалентен делению на 2, а сдвиг влево любого числа на 2 эквивалентен умножению на 2. Например, допустим, что число 7 (двоичное 111 ). Так 7 << 1 станет 1110, что составляет 7 * 2 = 14, а 7 >> 1 станет 11, что составляет 7/2 = 3.
Таким образом, алгоритм для преобразования числа N в массив битов в виде двоичного
- N mod 2 (возьмите остаток, если вы разделите N на 2)
- Сохраните остаток в коллекции (т. Е. List, Array, Stack)
- Разделите N на 2
- Если N / 2> 1, повторите с шага 1 с помощью N / 2
- В противном случае инвертируйте массив, и вы получите свой битсет.
Перемещение набора влево, если вы имели в виду левостороннее смещение, вы можете сделать это с помощью N<<1
Вот как вы создаете двумерный массив в C ++
[Тип переменной] TwoDimensionalArray [размер] [размер];Хотя я полагаю, что для этой проблемы вы, возможно, захотите прочитать о битовом наборе C ++ и легко реализовать его с помощью битового набора. Для этого вам просто нужно определить размер набора битов, который вы хотите использовать. Например, если наибольшее значение N равно 15, то вам нужен размер набора битов 4. Поскольку с 4 битами максимальное число, которое вы можете представить, равно 15 (двоичное число 1111). Надеюсь это поможет.
Другие решения
Других решений пока нет …