| Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате |
| Форум программистов > Алгоритмы > Оптимальный перебор всех значений битового массива |
| Автор: getch2 4.1.2011, 14:53 |
| Есть массив длины N, в котором элементы могут принимать значения либо 0, либо 1. Над ним можно проводить только два вида операций: 1. Менять ячейку массива на противоположную (0 -> 1, 1 -> 0). 2. "Инвертировать" массив - все значения в ячейках заменяются противоположными. Требуется найти оптимальный алгоритм (наименьшее количество операций) перебора всех возможных вариантов массива для произвольной его длины (N). Первым вариантом массива считается массив со всеми нулевыми значениями в ячейках. Замечание: Массив и его "инвертированный" вариант считаются одинаковыми. Например, 01000 == 10111. Решение задачи для N = 1: 1. 0 Решение задачи для N = 2: 1. 00 2. 01 Решение задачи для N = 3: 1. 000 - 0 2. 010 - 2 3. 110 == 001 - 1 4. 100 == 011 - 3 Решение задачи для N = 4: 1. 0000 - 0 2. 0010 - 2 3. 0110 - 6 4. 1110 == 0001 - 1 5. 1010 == 0101 - 5 6. 1011 == 0100 - 4 7. 0011 - 3 8. 0111 - 7 Короткая формулировка задачи: Оптимально перебрать все варианты битового массива, имея один дополнительный бит - флаг инвертирования. |
| Автор: getch2 4.1.2011, 15:29 |
| После http://forum.sources.ru/index.php?showtopic=322651&view=findpost&p=2794708 на код Грея задачу можно считать решенной. |
| Автор: maxim1000 4.1.2011, 20:05 |
| всё проще гораздо то, что можно менять независимо любые ячейки, означает, что можно построить любую комбинацию т.к. инвертированные комбинации считаются одинаковыми, нужно из них оставить только одну например, ту, у которой первый бит 0 так что устанавливаем первый бит в 0, а для остальным перебираем все возможные комбинации (2^(n-1)) |
| Автор: getch2 4.1.2011, 20:17 |
| Спасибо, но проще кода Грея решения быть не может. |
| Автор: maxim1000 4.1.2011, 22:20 |
| упс... извиняюсь не заметил "наименьшее количество операций" |