Помощь - Поиск - Пользователи - Календарь
Полная версия: Рекурсия
Форум «Всё о Паскале» > Pascal, Object Pascal > Задачи
setare
22.02.2005 23:26
Здравствуйте!
Нам дали задачу на определение детерминанта матрицы с помощью рекурсии и сказали что часть этой задачи можно посмотреть в учебнике. Эта часть состояла в вычеркивании столбца и строки. И как раз эта часть доставила нам очень много хлопот для понимания. Короче мы ничего не поняли. Не могли бы вы мне объяснить как они написали эту часть проги. Большое спасибо!

Код
procedure GetMatr(a:matr; var b:matr; m,i,j:integer);
{ Вычеркивание из матрицы строки и столбца }
var ki,kj,di,dj:integer;
 begin
 di:=0;
 for ki:=1 to m-1 do
   begin
   if (ki=i) then di:=1;
   dj:=0;
   for kj:=1 to m-1 do
     begin
     if (kj=j) then dj:=1;
     b[ki,kj]:=a[ki+di,kj+dj];
     end;
   end;
 end;


Что могут означать di dj и тд.?
Код должен быть в тегах
volvo
22.02.2005 23:31
setare, вообще-то дискриминант рекурсивно находится так, как здесь:

Реализация алгоритма перенесена сюда: FAQ: Матрицы
setare
22.02.2005 23:38
Спасибо за предоставленный код, но к самому большому сожалению, мы половину того что вы там написали не проходили, следовательно этот код является для нас ещё большим темным гремучим лесом.

Вся программа вообще выглядит так:

Код

const n=4; { размерность матрицы }
type matr=array[1..n,1..n] of longint;
var a,b:matr;
   i,j,dt:longint;
procedure PrintMatr(m:matr;n:integer);
{ процедура вывода матрицы на экран }
var i,j:integer;
 begin
 for i:=1 to n do
   begin
   for j:=1 to n do
     write(m[i,j]:3);
   writeln;
   end;
 end;
procedure GetMatr(a:matr; var b:matr; m,i,j:integer);
{ Вычеркивание из матрицы строки и столбца }
var ki,kj,di,dj:integer;
 begin
 di:=0;
 for ki:=1 to m-1 do
   begin
   if (ki=i) then di:=1;
   dj:=0;
   for kj:=1 to m-1 do
     begin
     if (kj=j) then dj:=1;
     b[ki,kj]:=a[ki+di,kj+dj];
     end;
   end;
 end;
Function Determinant(a:matr;n:integer):longint;
{ Вычисление определителя матрицы }
var i,j,d,k:longint;
   b:matr;
 begin
 d:=0; k:=1;
 if (n<1) then
   begin
   writeln('Determinant: Cann''t run. N=',n); halt;
   end;
 if (n=1)
   then d:=a[1,1]
 else if (n=2)
   then d:=a[1,1]*a[2,2]-a[2,1]*a[1,2]
 else { n>2 }
   for i:=1 to n do
     begin
     GetMatr(a,b,n,i,1);
     {writeln('i=',i,' a[',i,',1]=',a[i,1]);
     PrintMatr(b,n-1);}
     d:=d+k*a[i,1]*Determinant(b,n-1);
     k:=-k;
     end;
 Determinant:=d;
 end;
begin
{ Заполнение матрицы случайными числами }
randomize;
for i:=1 to n do
for j:=1 to n do
 a[i,j]:=random(5);
{ Печать исходной матрицы }
PrintMatr(a,n);
{ Вычисление и вывод определителя }
dt:=Determinant(a,n);
writeln('=========');
writeln('Determinant=',dt);
end.
Altair
22.02.2005 23:47
и чего не понятно там?
А что, самомстоятельное изучение материала в институтах уже запрещенно?
То что не проходили, скажешь прошла на умном форуме smile.gif
setare
22.02.2005 23:57
Как раз в том то и проблема, что наш чудак препод сказал, чтобы ничего того, что я не говорил не использовали! А этого он конечно не говорил! Так я давно бы все сама выучила!!!! smile.gif
В программе непонятно та часть, где вычеркиваются столбцы и строки! Непонятны обозначения! И как вообще это делается. В учебнике тоже не объясняется, а преподу уже сдать надо! И спрашивать нельзя! sad.gif
volvo
23.02.2005 0:21
Ну а если я перепишу эту процедуру вот так:
Код

procedure GetMatr(a:matr; var b:matr; m,i,j:integer);
 var ki,kj:integer; curr_i, curr_j: integer;
 begin
   curr_i := 1;
   for ki := 1 to m do begin
     if ki <> i then begin
       curr_j := 1;
       for kj := 1 to m do begin
         if kj <> j then begin
           b[curr_i, curr_j] := a[ki, kj];
           curr_j := curr_j + 1;
         end;
       end;
       curr_i := curr_i + 1;
     end;
   end;
 end;

Алгоритм по-моему стал понятнее...
setare
23.02.2005 0:38
Спасибо! Так стало нагляднее! Но извините, конечно за неумный вопрос, но что все таки означает curr_j & i? И почему мы берем 2 матрицы а и б? Вы написали если ki(что это означает) не равно строке тогда тд. И что может значить равенство двух матриц? Это случайно не матрицы, которые были получены перечеркиванием? А где тогда основная матрица?
volvo
23.02.2005 1:01
тут работа производится с матрицей A (основная) и матрицей B (результат, уже с вычеркнутыми строкой и столбцом).

Алгоритм такой: curr_i - это номер строки, с которым мы работаем в данный момент, curr_j , соответственно - номер столбца. Что делаем? В цикле перебираем ВСЕ строки (для этого нам и нужно ki) и только если очередной ki (то есть номер очередной выбранной строки) не равен номеру строки, которую надо вычеркнуть (у нас это: i) продолжаем работу с элементами этой строки (работа с элементами строки построена на таком же принципе: проверяем, не нужно ли вычеркнуть очередной столбец, и если нет, записываем элемент из исходной матрицы в результат).

Почему элементы строки i и столбца j не попадают в результирующую матрицу? Дело в том, что curr_j и curr_j увеличиваются только тогда, когда строка или столбец не является вычеркиваемым. А ki и kj (при переборе) увеличиваются всегда, таким образом мы добиваемся игнорирования ненужных строки и столбца...

А вот "равенство матриц" - совсем не то, что Вы подумали...
Код
b[curr_i, curr_j] := a[ki, kj];
значит взять элемент a[ki, kj] и поместить его значение в b[curr_i, curr_j] ...

Попробуйте на листе бумаги нарисовать две матрицы 3х3 и произвести те действия, которые должна производить эта процедура (записывая промежуточные значения переменных)...
setare
23.02.2005 1:10
Спасибо вам большое за объяснение! Уже начинаются просветления! Если бы нам все так объясняли, мы уже давно стали бы гениями! ;) :D Попробую сделать все что вы сказали!!!
Это текстовая версия — только основной контент. Для просмотра полной версии этой страницы, пожалуйста, нажмите сюда.