Моя программа падает при переключении бит
У меня есть эта функция, и, очевидно, она вызывает сбой моей программы:
long long todos(long long x,long long i) {
x ^= (1 << i);
long long aux = i - 1;
if(aux >= 0) x ^= (1 << aux);
aux = i - 4;
if(aux >= 0) x ^= (1 << aux);
aux = i + 1;
if(aux < 16) x ^= (1 << aux);
aux = i + 4;
if(aux < 16) x ^= (1 << aux);
return x;
}
Я не понимаю, почему, когда я меняю все ^= ( за &= ~( он работает отлично (хотя вывод, который я получаю, отличается). Есть ли логическое объяснение этому поведению?
В случае, если вам нужен весь код: http://ideone.com/Z7qoof
Решение
Выглядит как твой dp() функция возвращается очень глубоко. Считайте, что призыв к dp(3) может оценить все 65536 возможных битбордов в последовательности с вашим ^в то время как с вашим &~ вызов dp(k) будет только численно оценивать битборды k, Обратите внимание, что вы заполняете mat в порядке в main(); если вы зависите только от чисел kВы не будете возвращаться очень глубоко.
РЕДАКТИРОВАТЬЧто касается решения этой проблемы, вы можете думать о динамическом программировании как о кратчайших путях в ориентированном ациклическом графе. Проблема в том, что у вас нет ациклического графика здесь. Вы делаете поиск в глубину, чтобы найти кратчайшие пути здесь, который не … работает. Попробуйте заменить его чем-то вроде поиска в ширину или алгоритма Дейкстры.
Другие решения
Я предполагаю, что эта строка падает:
соиЬ << мат [bs.to_ulong ()] << епсИ;
из-за того, что bs больше, чем зарезервированное пространство 1<<16
постскриптум зачем использовать длинный длинный тип данных для всего? long long это 64 бит. Большинство вещей, которые вы делаете, возможно, можно сделать с помощью короткого