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

Форум работает в режиме архива, только для чтения и поиска.
Архив 2004 Архив 2007 Архив 2013

 
 
Опции темы Поиск в этой теме Опции просмотра
  #1  
Старый 04.01.2011, 15:46
Новичок

Отправить личное сообщение для getch Посмотреть профиль Найти все сообщения от getch
 
Регистрация: 04.01.2011
Сообщений: 2

Оптимальный перебор всех значений битового массива
Есть массив длины 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

Короткая формулировка задачи:
Оптимально перебрать все варианты битового массива, имея один дополнительный бит - флаг инвертирования.
  #2  
Старый 04.01.2011, 16:21
гocть

 
Сообщений: n/a

условие совершенно непонятно

надо вывести все возможные битовых массива длины N, но массивы, получающиеся инвертированием считать одинаковыми и вывести только один раз?

и рядом вывести число операций инвертирования одного бита для получения этого массива, которое равно min(число удиничных бит, N - число нулевых ьит)?
  #3  
Старый 04.01.2011, 16:21
Новичок

Отправить личное сообщение для getch Посмотреть профиль Найти все сообщения от getch
 
Регистрация: 04.01.2011
Сообщений: 2

После наводки на код Грея задачу можно считать решенной.
 


Опции темы Поиск в этой теме
Поиск в этой теме:

Расширенный поиск
Опции просмотра


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
Перебор всех возможных вариантов в масиве гость Реализация, исходники, языки 4 12.11.2009 23:54
Перебор всех возможных вариантов RuZk Реализация, исходники, языки 1 06.05.2009 18:41
Перебор всех значений матрицы гость Реализация, исходники, языки 1 23.11.2008 01:21
Перебор всех возможных комбинаций нулей и единиц в массиве гость Реализация, исходники, языки 5 02.11.2008 16:39
Метод моментов для прогнозирования значений определенной величины onit Математические алгоритмы (другое) 0 19.06.2008 13:23