Перебор всевозможных состояний массива

@alex_31 · Регистрация: 13.11.2015

Author24 — интернет-сервис помощи студентам

Доброго времени суток.
Задача:
Дан двумерный массив(скажем, 4х4) заполненный рандомным образом числами, причем числа могут быть только +1 и -1(условно говоря, два варианта заполнения ячейки массива). Нужно перебрать и зафиксировать всевозможные состояния(конфигурации) данного массива(а таких состояний 2¹⁶).

Пробовал решать через рекурсию и трехмерный массив. Ни к чему дельному так и не пришел.

Подскажите пожалуйста, как наиболее корректным способом перебрать и зафиксировать конфигурации массива?

@zss · 13.11.2015, 22:32

Будем значение -1 записывать цифрой 0, тогда все комбинации 16 бит дадут последовательные числа от 0x0000 до oxffff=2¹⁶-1

@alex_31 · 15.11.2015, 22:56 **[ТС]**

Суть уловил, но как это реализовать? С помощью кодов Грея? Или рекурсивного перебора?

Не могли бы вы в общих чертах набросать программу?
Был бы очень благодарен.

@alex_31 · 16.11.2015, 23:28 **[ТС]**

Суть уловил, но как это реализовать? С помощью кодов Грея? Или рекурсивного перебора?

Не могли бы вы в общих чертах набросать программу?
Был бы очень благодарен.

Байт · 16.11.2015, 23:58

Сообщение от alex_31

но как это реализовать?

Прибавлением к числу 0 единички 2¹⁶-1 раз

Сообщение от alex_31

заполненный рандомным образом

А это здесь при чем?

Добавлено через 5 минут
Реализация:

C++

for(i=0, p=1; i<16; i++, p*=2) ; // p=2 в 16-той, чтобы вручную не считать
for(i=0; i<p; i++) {
  for(j=0; j<16; j++) {
    k = ((i<<j) &1) ? 1 : -1;
    a[J/4][j%4] = k;
  }
  // Вывод  (фиксация) массива a
}

@alex_31 · 19.11.2015, 00:05 **[ТС]**

Спасибо! В итоге реализовал таким способом, но ваша программа изрядно помогла разобраться в побитовых операторах.

C++

        for(i = 0; i < 65536; i++)
        {
            for(j = 0; j < 4; j++)
                for(k = 0; k < 4; k++)
                {
                    if(i&(1<<((j<<2)+k)))
                    {
                        LatticeOfSpins[j][k]=1;
                    }else
                    {
                        LatticeOfSpins[j][k]=-1;
                    }
                }
        }

Байт · 19.11.2015, 00:24

Сообщение от alex_31

но ваша программа изрядно помогла разобраться в побитовых операторах.

Приятно слышать, но у меня там опечатка в строке 5. следует читать

C++

1	a[j/4][j%4] = k;

@alex_31 0 / 0 / 0 Регистрация: 13.11.2015 Сообщений: 5
		1
	Перебор всевозможных состояний массива 13.11.2015, 22:00. Показов 2015. Ответов 6 Метки нет (Все метки) Доброго времени суток. Задача: Дан двумерный массив(скажем, 4х4) заполненный рандомным образом числами, причем числа могут быть только +1 и -1(условно говоря, два варианта заполнения ячейки массива). Нужно перебрать и зафиксировать всевозможные состояния(конфигурации) данного массива(а таких состояний 2¹⁶). Пробовал решать через рекурсию и трехмерный массив. Ни к чему дельному так и не пришел. Подскажите пожалуйста, как наиболее корректным способом перебрать и зафиксировать конфигурации массива? 0

@zss Модератор 13721 / 10918 / 6478 Регистрация: 18.12.2011 Сообщений: 29,147
	13.11.2015, 22:32	2
	Будем значение -1 записывать цифрой 0, тогда все комбинации 16 бит дадут последовательные числа от 0x0000 до oxffff=2¹⁶-1 1

@alex_31 0 / 0 / 0 Регистрация: 13.11.2015 Сообщений: 5
	15.11.2015, 22:56 [ТС]	3
	Суть уловил, но как это реализовать? С помощью кодов Грея? Или рекурсивного перебора? Не могли бы вы в общих чертах набросать программу? Был бы очень благодарен. 0

@alex_31 0 / 0 / 0 Регистрация: 13.11.2015 Сообщений: 5
	16.11.2015, 23:28 [ТС]	4
	Суть уловил, но как это реализовать? С помощью кодов Грея? Или рекурсивного перебора? Не могли бы вы в общих чертах набросать программу? Был бы очень благодарен. 0

	19.11.2015, 00:24

Перебор всевозможных состояний массива

Решение