Вопрос № 39579: Здравствуйте, уважаемые эксперты!!! Меня зовут Harut .
У меня такой вопрос ...
Дана квадратная матрица (nxn),у каторого елементи толко 0 и 1 .
надо умножить ету матрицу собой,потом проверять есть ли такая матрица,если нет, надо еще умножи...
Вопрос № 39.579
Здравствуйте, уважаемые эксперты!!! Меня зовут Harut .
У меня такой вопрос ...
Дана квадратная матрица (nxn),у каторого елементи толко 0 и 1 .
надо умножить ету матрицу собой,потом проверять есть ли такая матрица,если нет, надо еще умножить получашая матрица с даной матрицой,потом еше проврять есть ли такая матрица,если нет еще раз умнажать с даной матицой,потом птоверять ... и т. д.
если есть такая матрица из етиx которые у нас получились,надо ети все матрици соединит с друг-другом ,и получашая матрица показать как ответ на екране.
X(+)=XuX(2)uX(3)u...uX(i) , X(i)=X(i-1)*X
X-ето даная матрица
Я знаю алгоритм етоы задачи,но не магу ее написать на PASCAL-е.
если можете помагите,заране огромное спасибо :)
и если я что-то написал не вердно ,извените я не очень xорошо владею русским.и если что-то не понятно в задаче скажите я постараюсь исправить ...
Еще раз ЗАРАНЕ ОГРОМНОЕ СПАСИБО ...
Отвечает: Полховский Александр Владимирович
Здравствуйте, Grigoryan Harut /Harutik!
Начнём.
Для начала определим то, что нам понадобится для рассчётов:
Массив из матриц (то есть из массивов), которые мы будем "складывать" при умножении (исходная матрица тоже будет в этом массиве под первым номером).
Массив матриц реализован динамически. Определяется размерностью матрицы. Есть ограничение: программа не сможет работать, если после 199 посчитанных матриц не будет совпадений.
Первым делом запрашиваем размерность (строка 54).
Затем резервируем память для наших массивов (строка 57).
Выводим первую матрицу (то есть исходную) (строка 58).
Далее выполняем перемножение каждой следующей матрицы на исходную, проверяя при этом наличие такой же матрицы среди уже полученных (и выводим каждую полученную матрицу). Перемножение, добавление и проверка реализованы в функции MultiPly. Если матрица уже есть, она возвращает значение true, если нет - false;
В конце выводим порядковый номер матрицы, с которой совпала последняя посчитанная.
Затем выводим результат сложения (соединения).
Освобождаем память.
Выходим после нажатия на Enter.
Код:
program matrix1;
uses
crt;
type
ElementType = array[1..200, 1..200] of byte;
const
MaxArraySize = (65520 div SizeOf(ElementType));
type
MyArrayType = array[1..MaxArraySize] of ElementType;
var
P: ^MyArrayType;
N, k1, k2, k3, CurPos, FoundAt: byte;
res: integer;
procedure AllocateArray;
begin
GetMem(P, N * SizeOf(ElementType));
end;
procedure DeallocateArray;
begin
FreeMem(P, N * SizeOf(ElementType));
end;
function MultiPly: boolean;
var
k1, k2, k3, temp: byte;
bool1: boolean;
begin
for k1:=1 to N do
for k2:=1 to N do
begin
temp:=0;
for k3:=1 to N do
temp:=temp+P^[CurPos, k1, k3]*P^[1, k3, k2];
temp:=ord(temp>=1);
P^[CurPos+1, k1, k2]:=temp;
end;
k3:=0;
repeat
inc(k3);
bool1:=true;
for k1:=1 to N do
for k2:=1 to N do
if P^[k3, k1, k2]<>P^[CurPos+1, k1, k2]
then bool1:=false;
until (k3=CurPos)or(bool1);
FoundAt:=k3;
Multiply:=bool1;
end;
begin
ClrScr;
write('Enter matrix size: ');
readln(N);
writeln;
AllocateArray;
for k2:=1 to N do
begin
write('Enter elements of ', k2, ' line: ');
for k1:=1 to N do
read(P^[1, k1, k2]);
writeln;
end;
writeln('=================');
writeln;
CurPos:=0;
repeat
inc(CurPos);
writeln('Matrix number ', CurPos, ':');
for k2:=1 to N do
begin
for k1:=1 to N do
write(P^[CurPos, k1, k2], ' ');
writeln;
end;
writeln('=================');
until Multiply;
writeln('Matrix number ', CurPos+1, ':');
for k2:=1 to N do
begin
for k1:=1 to N do
write(P^[CurPos+1, k1, k2], ' ');
writeln;
end;
readln;
writeln('=================');
writeln;
writeln('Found on step ', CurPos+1);
writeln('The matrix ', CurPos+1, ' was similar to the matrix ', FoundAt);
writeln;
writeln('Result:');
for k2:=1 to N do
begin
for k1:=1 to N do
begin
res:=0;
for k3:=1 to N do
res:=res+P^[k3, k1, k2];
write(res, ' ');
end;
writeln;
end;
DeallocateArray;
readln;
end. --------- Спасём нашу хрупкую планету !
Ответ отправил: Полховский Александр Владимирович (статус: Практикант)
Ответ отправлен: 08.04.2006, 23:57 Оценка за ответ: 5 Комментарий оценки: Огромное спасибо уважаемый Полховский Александр Владимирович !!!
