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

[Milanista]

Пример матрицы,

111100000000
000011110000
000000001111
101001000100
010000110001
000110001010
100100100100
010001010010
001010001001

Длина строки - 12
Длина столбца - 9
Вес строки - 4
Вес столбца - 3
В программе я должен задавать эти параметры, и должен получить матрицу в примере этого, с этими параметрами, заранее спасибо,
Модератор без обид, честно не знал как сформулировать вопрос, это всего лишь часть чего то)

[Serge_Bliznykov]

теперь всё понятно.

задачка, на мой взгляд, весьма непростая.
как решать, с наскоку не скажу...
просится, конечно, перебор (можно рекурсивно, с возвратом), но, думаю, что можно (нужно) подумать над более эффективным алгоритмом.

но у меня есть подозрение, что далеко не для всех сочетаний весов строки/столбца решение вообще существует!

ну, например, ваш пример
(Длина строки - 12
Длина столбца - 9
Вес строки - 4)
только Вес столбца берём побольше (ну, скажем, 6)
решение есть?


p.s. а если не секрет - откуда подобная задача возникла?

[Аватар]

без повторения циклов

Тоже уточнить не помешает на примере каком-то что имеется ввиду.

[evg_m]

с определенным весом строки, столбца, с длиной строки, столбца, и без повторения циклов,

так с весами разобрались.

- вес строки это количество единиц в строке ( или то же самое - сумма элемнтов строки)

а как насчет циклов?

Строки могут быть одинаковыми ? А столбцы? У вас в примере - три первых столба одинаковые и три последних.

это повторение строк(столбцов)? или что-то другое?

[newerow1989]

Всего 36 единиц надо расставить!

[Serge_Bliznykov]

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

Всего 36 единиц надо расставить!

точно. как же я очевидного не заметил!!!

Задача имеет решение только в том случае,
если
Длина строки * Вес столбца = Длина столбца * Вес строки


что же касается циклов - то, возможно, ожидается рекурсивное решение, ведь рекурсия вполне себе заменяет циклы...

[evg_m]

просто мысль вслух.
берем "простую" матрицу с правильными весами

1111 0000 0000
1111 0000 0000
1111 0000 0000
0000 1111 0000
0000 1111 0000
0000 1111 0000
0000 0000 1111
0000 0000 1111
0000 0000 1111

для исключения повторов строк/столбцов перемешиваем "одновременно" строки и столбцы

for i =1 to N
  k:=random(N);
  строка[i]<->строка[k];// обмен местами строк
  repeat m:=random(N); until k<>m;//номер строки должен отличаться от номера столбца 
  столбец[i]<->столбец[m];// обмен местами столбцов
end;

[newerow1989]

Все-таки без циклов не обойтись!!!

var p:array of array of byte;
    x,y,i,j,j0,a,b,rand:integer;

procedure pere;
var c,d,z:integer;
begin
   rand:=rand-1;
   If rand<=0 then
      Exit;
   c:=Random(y);
   Repeat
      d:=Random(y);
   Until c<>d;
   For j:=0 to x-1 do
   begin
      z:=p[c,j];
      p[c,j]:=p[d,j];
      p[d,j]:=z;
   end;
   c:=Random(x);
   Repeat
      d:=Random(x);
   Until c<>d;
   For i:=0 to y-1 do
   begin
      z:=p[i,c];
      p[i,c]:=p[i,d];
      p[i,d]:=z;
   end;
   pere;
end;

begin
   Randomize;
   Write('dlina stroki = ');
   Readln(x);
   Write('dlina stolbca = ');
   Readln(y);
   Write('ves stroki = ');
   Readln(a);
   Write('ves stolbca = ');
   Readln(b);
   SetLength(p,x,y);
   j:=0;
   For i:=0 to y-1 do
   begin
      For j0:=j to j+a-1 do
         p[i,j0]:=1;
      If i mod b=b-1 then
         j:=j+a;
   end;
   rand:=Random(x*y);
   pere;
   For i:=0 to y-1 do
   begin
      For j:=0 to x-1 do
         Write(p[i,j],'  ');
      Writeln;
   end;
   Readln;
end.

Сойдет?

[steps]

теперь всё понятно.

задачка, на мой взгляд, весьма непростая.
как решать, с наскоку не скажу...
просится, конечно, перебор (можно рекурсивно, с возвратом), но, думаю, что можно (нужно) подумать над более эффективным алгоритмом.

но у меня есть подозрение, что далеко не для всех сочетаний весов строки/столбца решение вообще существует!

ну, например, ваш пример
(Длина строки - 12
Длина столбца - 9
Вес строки - 4)
только Вес столбца берём побольше (ну, скажем, 6)
решение есть?


p.s. а если не секрет - откуда подобная задача возникла?

Нужно уменьшить один в другой префикс как-то что-то предсказав вес стороки.
алгортм paq, который предсказывает 0 или 1 и уменьшает каждый раз на один вес строки.

[type_Oleg]

И еще ограничение.
Допустим, длина строки = n, вес строки = m . Тогда количество различных вариантов строк равно:
= n!/(m!*(n-m)!) ( в комбинаторике это - число сочетаний)
То есть число строк ( а это = длина столбца ) не может быть больше этого числа.
И наоборот.

Например, длина строки = 4, вес строки = 2, тогда максимальное число строк =
= 4!/(2!*(4-2)!) = 6
0011
0101
0110
1001
1010
1100
То есть, столбы здесь не могут быть длиннее 6. Иначе строки будут повторяться.

Кстати, и короче 6 - тоже не всегда можно. Например, если убрать нижнюю строку ( сделать столбы длиной 5), то вес столбов будет разный ( 2 или 3).
0011
0101
0110
1001
1010