IPB
ЛогинПароль:

> Прочтите прежде чем задавать вопрос!

1. Заголовок темы должен быть информативным. В противном случае тема удаляется ...
2. Все тексты программ должны помещаться в теги [code=pas] ... [/code], либо быть опубликованы на нашем PasteBin в режиме вечного хранения.
3. Прежде чем задавать вопрос, см. "FAQ", если там не нашли ответа, воспользуйтесь ПОИСКОМ, возможно такую задачу уже решали!
4. Не предлагайте свои решения на других языках, кроме Паскаля (исключение - только с согласия модератора).
5. НЕ используйте форум для личного общения, все что не относится к обсуждению темы - на PM!
6. Одна тема - один вопрос (задача)
7. Проверяйте программы перед тем, как разместить их на форуме!!!
8. Спрашивайте и отвечайте четко и по существу!!!

 
 Ответить  Открыть новую тему 
> Хитрое заполнение ячеек
сообщение
Сообщение #1


mea culpa
*****

Группа: Пользователи
Сообщений: 1 372
Пол: Мужской
Реальное имя: Николай

Репутация: -  24  +


Привет всем.

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

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


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


--------------------
"Знаешь, стыдно - когда не видно, что услышал всё, что слушал.."
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #2


Гость






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

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


mea culpa
*****

Группа: Пользователи
Сообщений: 1 372
Пол: Мужской
Реальное имя: Николай

Репутация: -  24  +


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

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


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


--------------------
"Знаешь, стыдно - когда не видно, что услышал всё, что слушал.."
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #4


mea culpa
*****

Группа: Пользователи
Сообщений: 1 372
Пол: Мужской
Реальное имя: Николай

Репутация: -  24  +


Решил, ( 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.


Хотел правда массивы динамическими сделать, но я не знаю, как для многомерных память выделять.

Сообщение отредактировано: Unconnected -


--------------------
"Знаешь, стыдно - когда не видно, что услышал всё, что слушал.."
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #5


Гость






Цитата
я не знаю, как для многомерных память выделять.
Вот так: Динамические массивы и матрицы
 К началу страницы 
+ Ответить 
сообщение
Сообщение #6


mea culpa
*****

Группа: Пользователи
Сообщений: 1 372
Пол: Мужской
Реальное имя: Николай

Репутация: -  24  +


volvo, а как по-твоему, само решение верное? Будет ли отрабатывать на больших массивах?


--------------------
"Знаешь, стыдно - когда не видно, что услышал всё, что слушал.."
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #7


Гость






Должно работать на любых матрицах. Хотя не совсем понятно:
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.
 К началу страницы 
+ Ответить 
сообщение
Сообщение #8


mea culpa
*****

Группа: Пользователи
Сообщений: 1 372
Пол: Мужской
Реальное имя: Николай

Репутация: -  24  +


Спасибо, учту..


--------------------
"Знаешь, стыдно - когда не видно, что услышал всё, что слушал.."
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 

 Ответить  Открыть новую тему 
1 чел. читают эту тему (гостей: 1, скрытых пользователей: 0)
Пользователей: 0

 





- Текстовая версия 29.03.2024 14:38
500Gb HDD, 6Gb RAM, 2 Cores, 7 EUR в месяц — такие хостинги правда бывают
Связь с администрацией: bu_gen в домене octagram.name