Пятница. Большая пачка сложных задачек...

← →
Sandman25 © (2004-07-27 10:03) [160]

[158] Sha © (27.07.04 10:02)

Теперь я понимаю, зачем ты приплел де Моргана :)
Но все-таки он оказывается лишним.

← →
Sha © (2004-07-27 10:05) [161]

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

← →
Sandman25 © (2004-07-27 10:06) [162]

[161] Sha © (27.07.04 10:05)

Молодец! Очень полезный прием приведения сложной задачи к простой.

← →
Sha © (2004-07-27 10:07) [163]

Sandman25 © (27.07.04 10:06) [162]

Рад стараться!

← →
SergP © (2004-07-27 12:29) [164]

Я тоже немного подумал, получается примерно так: (вариант похожий на default"овский, но немножко усовершенствованный...
Правда может где и ошибся... Я не проверял...

// Подготавливаем один вектор на месте первой строки A[1..M,1] x:=a[1,1]; for i:=2 to M do begin x:=x or a[i,1]; // в конце цикла в х будет true, если в строке есть хотя бы один true for j:=2 to N do // формируем вектор begin a[i,1]:=a[i,1] or a[i,j]; if a[i,1] then break; // если уже true то далее незачем проверять end; end; // Заполнение массива for j=2 to N do begin // для начала узнаем есть ли в данной строке A[1..M,j] true z:=A[1,j] for i:=2 to M do begin z:=z or A[i,j]; if z then break; end; // если есть то сразу же и заполняем строку... // как видно второй вектор нам не требуется if z then for i:=1 to M do a[i,j]:=z and a[1,j]; end; // Если в первой строке не было true, то ставим там везде false if not x then for i:=1 to M do a[i,1]:=false;

← →
SergP © (2004-07-27 12:31) [165]

> SergP © (27.07.04 12:29) [164]

Я исходил из того что в массиве числа boolean, а не 0 или 1

← →
Sandman25 © (2004-07-27 12:32) [166]

[165] SergP © (27.07.04 12:31)

Это одно и то же :)

← →
SergP © (2004-07-27 12:41) [167]

Есть еще простой вариант но с большой сложностью:
for i:=1 to M do for j:=1 to N do if a[i,j] then for x:=1 to M do for y:=1 to N do if a[x,y] then a[i,y]:=true;

← →
SergP © (2004-07-27 12:43) [168]

> Sandman25 © (27.07.04 12:32) [166]
> [165] SergP © (27.07.04 12:31)
>
> Это одно и то же :)

Это понятно. Просто писать проще if a[i,j] чем if a[i,j]=1
:)))

> SergP © (27.07.04 12:41) [167]
> Есть еще простой вариант но с большой сложностью:
>
> for i:=1 to M do for j:=1 to N do
> if a[i,j] then for x:=1 to M do for y:=1 to N do
> if a[x,y] then a[i,y]:=true;

Или чуть побыстрее, типа так:

for i:=1 to M do for j:=1 to N do
if a[i,j] then for y:=1 to N do for x:=1 to M do
if a[x,y] then a[i,y]:=true else break else break;

Ой, блин, ошибся...

for i:=1 to M do
for j:=1 to N do
if a[i,j] then
begin
for y:=1 to N do
for x:=1 to M do
if a[x,y] then
begin
a[i,y]:=true;
break;
end;
break;
end;

Пятница. Большая пачка сложных задачек... Найти похожие ветки