возникла необходимость создавать с помощью c++ матрицы 10 на 10 из нулей и единиц (всегда 25 единиц и 75 нулей в случайных позициях). При этом генерировать их нужно не рандомно, подскажите каким образом это можно делать (примерный алгоритм или готовый код). Алгоритм должен (в теории) за конечное время перебрать все возможные варианты этих матриц.
2 ответа
Ладно, только раз, только у нас, только для вас.
Перенумеруем все решетки - число от 0 до 1125899906842623. Получить решетку по ее номеру можно вот так:
array<array<int,10>,10> Cardano(unsigned long long n)
{
array<array<int,10>,10> m;
for(int i = 0; i < 10; ++i)
for(int j = 0; j < 10; ++j)
m[i][j] = 0;
for(int i = 0; i < 25; ++i)
{
int q = n&0x3;
n >>= 2;
int rr = i/5, cc = i%5, r, c;
switch(q)
{
case 0: r = rr; c = cc; break;
case 1: r = cc; c = 9 - rr; break;
case 2: r = 9 - rr; c = 9 - cc; break;
case 3: r = 9 - cc; c = rr; break;
}
m[r][c] = 1;
}
return m;
}
Вот вам и способ перебора :) - цикл от нуля до 1125899906842623 включительно, и выводите себе...
Вот пример работы программы: https://ideone.com/D1QvjC
Делим матрицу на 4 квадрата, и нумеруем их: 0 - левый верхний, 1 - правый верхний, 2 - правый нижний, 3 - левый нижний
Нумеруем цифры внутри 0-го из квадратов от 0 до 24 слева на право, сверху вниз.
Внутри остальных трех квадратов нумеруем элементы от 0 до 24 так, чтобы они соответствовали номерам их 0-го при повороте на 90, 180 и 270 градусов соответственно.
Вот пример такой нумерации из Википедии, но матрица 8*8 и нумерация с 1, а не с нуля, но это не меняет сути
Теперь как собственно сгенерировать.
Берем 50-битное N
от 0
до 1 125 899 906 842 623
- номер решетки, которую мы хотим сгенерировать.
Разбиваем его на 25 двухбитных чисел (от 0 до 3 каждое).
Номер двухбитной пары - это номер ячейки внутри квадрата, значение - номер квадрата, в котором ставим 1
. В остальных трех квадратах в ячейке с этим номером ставим 0
.
-
Мда, как у Белла с кем там? пока я писал исходник, вы изложили идею :) С разницей 8 минут. Эх, не надо было мне код тестировать :), все равно правильным оказался...– Harry3 ноя 2020 в 13:29
-
Сударь, благодарю за навыки ясновидения, вы смогли сформулировать ответ точно на тот вопрос, который мне сформулировать не удалось.– sanok103 ноя 2020 в 14:54
1 125 899 906 842 624
. Это, конечно, меньше, чем 1125899906842624, но все же не мало. Вы все еще уверены, что Вам нужно перебрать все?