Помощь - Поиск - Пользователи - Календарь
Полная версия: Хитрое заполнение ячеек
Форум «Всё о Паскале» > Pascal, Object Pascal > Задачи
Unconnected
Привет всем.

Столкнулся с задачами, решение которых я если и в голове очень смутно, но представляю, то в коде ну вообще никак... Погуглил по слову Комбинаторика, кажется, это из этой области. Вот задача:

Цитата
Требуется в каждую клетку квадратной таблицы размером NxN поставить ноль или единицу так, чтобы в любом квадрате размера KxK было ровно S единиц.
Во входном файле записаны три числа – N, K, S (1 ≤ N ≤ 100, 1 ≤ K ≤ N, 0 ≤ S ≤ K2).


И вывести надо получившуюся матрицу. Может кто-нибудь объяснить алгоритм решения? Я додумался лишь до того, что сначала надо посчитать все возможные "квадраты", а уже потом, исходя из их расположения заполнять..
volvo
Если ты возьмешь и заполнишь квадрат K*K нужным количеством единиц, а потом этим квадратом заполнишь большой квадрат N*N - то твоя задача будет решена, в любом квадрате K*K внутри большого квадрата сумма единиц будет одинакова. Почему так - разберешься?

P.S. Заполнять квадрат N*N - "насколько хватит". Если N на K не делится нацело, и остался один свободный столбец - то заполнить этот столбец первым столбцом малого квадрата. То же самое - со строками.
Unconnected
Цитата
Если ты возьмешь и заполнишь квадрат K*K нужным количеством единиц, а потом этим квадратом заполнишь большой квадрат N*N - то твоя задача будет решена, в любом квадрате K*K внутри большого квадрата сумма единиц будет одинакова. Почему так - разберешься?

P.S. Заполнять квадрат N*N - "насколько хватит". Если N на K не делится нацело, и остался один свободный столбец - то заполнить этот столбец первым столбцом малого квадрата. То же самое - со строками.


Мысль понял, провел эксперимент - действительно условие выполняется... Буду воплощать в код, спасибо:)
Unconnected
Решил, ( blink.gif ), вот, если кому интересно:

uses sysutils;
var f:textfile;
n,k,i,j,x,y:byte;
s:integer;
big,small:array[1..100,1..100] of char;
begin
assignfile(f,'input.txt');
reset(f);
read(f,n,k,s);
closefile(f);
for i:=1 to n do
for j:=1 to n do big[i,j]:='0';
x:=0;
for i:=1 to k do
for j:=1 to k do
begin
if (x=s) then break;
inc(x);
small[i,j]:='1';
end;
for i:=1 to k do
for j:=1 to k do if small[i,j]<>'1' then small[i,j]:='0';
x:=0;
y:=0;
for i:=1 to n do
begin
if (y=k) then y:=1 else inc(y);
for j:=1 to n do
begin
if (x=k) then x:=1 else inc(x);
big[i,j]:=small[x,y];
end;
end;
assignfile(f,'output.txt');
rewrite(f);
for i:=1 to n do
begin
for j:=1 to n do write(f,big[i,j],' ');
writeln(f);
end;
closefile(f);
end.


Хотел правда массивы динамическими сделать, но я не знаю, как для многомерных память выделять.
volvo
Цитата
я не знаю, как для многомерных память выделять.
Вот так: Динамические массивы и матрицы
Unconnected
volvo, а как по-твоему, само решение верное? Будет ли отрабатывать на больших массивах?
volvo
Должно работать на любых матрицах. Хотя не совсем понятно:
1) зачем ты заполняешь элементы массива посимвольно, если есть FillChar:
//  for i:=1 to n do
// for j:=1 to n do big[i,j]:='0';
FillChar(big, sizeof(big), '0');

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

2) У тебя матрица big заполняется НЕ "образцом" из small. Распечатай small и убедись в этом. Потому что надо так:
  y:=0;
for i:=1 to n do
begin
if (y=k) then y:=1 else inc(y);
x := 0; // Вот тут обнуляем X
for j:=1 to n do
begin
if (x=k) then x:=1 else inc(x);
big[i,j]:=small[y, x]; // А тут - меняем индексы местами
end;
end;
Вот тогда будет точное заполнение. Здесь это не играет особой роли, но на будущее - внимательнее с такими вещами, где-нибудь может вылезти неправильное поведение. Можно попробовать похимичить с MOD и обойтись без доп. переменных X, Y.
Unconnected
Спасибо, учту..
Это текстовая версия — только основной контент. Для просмотра полной версии этой страницы, пожалуйста, нажмите сюда.