Создание единичной матрицы M*N

Нужно создать единичную матрицу размером M*N. При условии,что каждая строка имеет i единиц,а каждый столбец j единиц. Поэтому нужно организовать алгоритм ,который будет производить заполнение. Идей и мыслей что-то совсем не густо. Подскажите с чего начать.

0

Сообщение от AlexVRud std::gcd

Не подскажите ,что данная строчка делает?Немного почитав,я понял ,что это НОД. Просто VS ругается и поэтому немного непонятно

Добавлено через 20 минут
Кстати,совсем забыл. Матрица должна генерироваться по разному(рандомно).

0

Сообщение от valek_neznashka Не подскажите ,что данная строчка делает?Немного почитав,я понял ,что это НОД. Просто VS ругается и поэтому немного непонятно

Всё верно. Если студия ругается, то либо берёшь более свежую, либо реализуй НОД самостоятельно.

0

Сообщение от COKPOWEHEU if( (x+y)%l < n )m[x][y]=1;else m[x][y]=0;

Подскажите пожалуйста,по какому принципу работает проверка? или на какую формулу опирается

0

Прошу прощения что поздно ответил. Никак не мог внятно сформулировать как же эта штука работает. То есть понимать-то понимаю, но наукообразно объяснить не могу. Надеюсь, сейчас получилось.
.
Разделим матрицу на одинаковые квадраты размером lxl. По горизонтали их количество составит m=M/l, а по вертикали n=N/l. Такой квадрат можно заполнить таким образом, чтобы количество единиц в каждой строке равнялось количеству в каждом столбце. При этом само количество единиц (u) может быть любым от 0 до l.
На примере l=4:
u=0 и u=4 слишком тривиально
u=1
u=2
u=3
Поскольку по горизонтали таких квадратов m штук, количество единиц в строке равно i=u*m. Аналогично количество единиц в столбце равно j=u*n.
Поскольку размер квадрата d должен быть кратен как размеру строки, так и столбца, он должен являться их делителем. Лучше всего - наибольшим общим делителем, НОД. То есть l = НОД(M, N).
Проверим по формуле Байта:
Все сходится
Теперь вычислим u (в коде оно неудачно обозначено буквой n):

Итак, если у нас есть квадрат размера l, в каждой строке и в каждом столбце которого u единиц, мы можем размножить его m раз по горизонтали и n раз по вертикали и получим желаемую матрицу.
Теперь о заполнении собственно квадрата.
Заполнять будем по строкам. Длина каждой строки l, в ней ровно u единиц. Пусть сначала идут единицы, потом оставшиеся нули. Например, если l=5, u=2, строка будет выглядеть как 11000. В коде это запишется как
Теперь заполним остальные. Проще всего циклически сдвигать каждую следующую строчку. Например, если 1 строчка равна 12345, то вторая может быть
23451 (<--) или 51234 (-->)
третья
34512 (<--) или 45123 (-->)
и т.д.
Я выбрал сдвиг влево, потому что он проще в коде. Достаточно к горизонтальной координате прибавить вертикальную:
Возникает проблема если эта сумма выйдет за пределы стороны квадрата. Кроме того, заполнять матрицу по отдельным квадратам неудобно. Придется делать 4 вложенных цикла. Вместо этого воспользуемся остатком от деления, чтобы шаблон автоматически повторялся на любом расстоянии от начала:
Добавлено через 9 минут
Теперь можно проанализировать диапазоны значений.
Здесь мы видим, что числа m и n взаимно простые и однозначно вычисляющиеся из размеров матрицы. Отсюда можно найти диапазоны значений i, j:
Таким образом, чтобы получить какую-нибудь красивую картинку (для тестов и прочего) сначала выбираем любое число в качестве НОД. Чем оно больше, тем больше вариантов заполнения. Скажем, для l=1 вариантов всего два: 0 и 1. Потом выбираем не слишком большие взаимно простые числа m и n, умножаем их на НОД и передаем программе как M, N. Теперь выбираем какое-нибудь число в диапазоне от 0 до НОД, оно будет коэффициентом заполнения. Умножаем его на m и n и тоже передаем программе как i, j.
Наслаждаемся красотой двоичных рисунков!

0

del

0