Консультации Портала - Консультация #180301

Задать вопрос Консультации Пользователи Форум

Задать вопрос экспертам

Консультация № 180301

13.10.2010, 04:37

0.00 руб.

13.10.2010, 10:05

0 5 1

Компьютеры Программирование

Дорогие эксперты!

У меня есть к вам непростая задачка...
Мой преподаватель по Дискретной математике на вот эту процедуру:

Код:

const n=10;
type t_matr=array[1..n,1..n] of 0..1;

procedure kompozichia(var a, b, c:t_matr);
var x,y,z:integer;
begin
     for x:=1 to n do
         for y:=1 to n do
             begin
                  c[x,y]:= 0;
                  for z:=1 to n do
                      c[x,y]:=c[x,y] or a[x,z] and b[z,y];
             end;
end;

дал задание чтобы я заменил вот этот цикл:
for z:=1 to n do
c[x,y]:=c[x,y] or a[x,z] and b[z,y];

так, чтобы он работал быстрее... и дал подсказку чтобы я работал и итерационными циклами а не с фиксированным числом шагов. Я не могу понять как тут модернизировать это все!
Помогите прошу идейками...

P/s:замена цикла и то же самое действие не произвело должного впечатления на преподавателя!
По моему надо как то вот эту побитовую проверку переделать...
Для справки: это процедура одной из операций над отношениями - композиция!

(Композицией (суперпозицией или умножением) А и В (АoВ) называется отношение, состоящее из всех тех и только тех упорядоченных пар (x,y), для которых найдётся хотя бы один элемент z такой, что (x,z)эA и (z,y)эB, т.е.
А?В = {(x,y) | существует z такой, что (x,z)эA и (z,y)эB }.)

Обсуждение

Неизвестный

13.10.2010, 07:21

общий

Насколько я понимаю вашего преподавателя, он хочет что бы ваш цикл прерывался по нахождении подходящего z, а не как у вас сделано - прогоняется весь диапазон, вне зависимости было ли найдено z ранее или нет. Тогда вместо вашего:

Код:

c[x,y]:= 0;
for z:=1 to n do
c[x,y]:=c[x,y] or a[x,z] and b[z,y];

Можно сделать примерно так:

Код:

z:=1;
while ((a[x,z]=0) or (b[z,y]=0)) and (z<n) do inc(z);
c[x,y]:=a[x,z] and b[z,y];

Если то что надо - напишите - оформлю ответ.

Неизвестный

13.10.2010, 17:24

общий

а это значит если нашли то прерываемся и скачем уже для другой ячейки? думаю у вас то что надо а есть еще варианты?

Неизвестный

13.10.2010, 21:24

общий

Да, цикл выполняется до момента, когда будет найдено подходящее значение z, ну или до конца - если подходящего z не найдется, а затем переходим к следующей ячейке. Вариантов реализации можно еще придумать, но мне показалось что вам важна идея, а не конкретная реализация. Больше в этом цикле вряд-ли что-то удастся ускорить.

Неизвестный

13.10.2010, 22:54

общий

спасибо) оформляйте как ответ +5

Неизвестный

14.10.2010, 07:12

общий

14.10.2010, 15:33

это ответ

Здравствуйте, Юдин Евгений Сергеевич!

Насколько я понимаю вашего преподавателя, он хочет что бы ваш цикл прерывался по нахождении подходящего z, а не как у вас сделано - прогоняется весь диапазон, вне зависимости было ли найдено z ранее или нет. Тогда вместо вашего:

Код:

c[x,y]:= 0;
for z:=1 to n do
c[x,y]:=c[x,y] or a[x,z] and b[z,y];

Можно сделать например так:

Код:

z:=1;
while ((a[x,z]=0) or (b[z,y]=0)) and (z<n) do inc(z);
c[x,y]:=a[x,z] and b[z,y];

или так:

Код:

z:=0;
repeat
  inc(z);
until (z=n)or((a[x,z]=1)and(b[z,y]=1));
c[x,y]:=a[x,z] and b[z,y];

ps:второй вариант создает более быстрый и компактный код.
С уважением, Дмитрий

Спасибо! Оперативно!

Форма ответа

Отправка постов/ответов доступна только зарегистрированным и подтвержденным пользователям.

Если Вы уже зарегистрированы на Портале - войдите в систему, если Вы еще не регистрировались - пройдите простую процедуру регистрации.