求一个矩阵搜索算法

Question

已知一个矩阵A（M*M维，且至少有一行为全零元素）  其中元素皆为0或1现取出A的一行，比如第I行
若A[I,J]:=1，则记录J（J可能不唯一）；
再取出第J行，若A[J,K]:=1，则记录K（J也可能不唯一）；
取出地K行，若A[K,L]:=1，则记录L……依此类推，直到某一行不存在A[*,*]:=1为止（注意A还有个要求：若A[i,j]:=1，则A[j,i]<>1，且A中至少有一行为全零元素，那么这个搜索必能达到中止条件）。
依此来生成矩阵B（M*M维），使得B第I行的第J、K、L……列均为1。请问这个程序用delphi怎么实现？

Answer 1

是否应该还有一些条件,比如a[i,i]=0,不然如果a[1,1]是1,就一直会循环取第一行了吧.按你描述的情况来说.

Answer 2

楼上说的正是，对角元素A[i,i]<>1

Answer 3

type
  MyIntArray = array of Integer;
  MyTwoDArray = array of array of Integer;var
  Z, Y, X, V: MyTwoDArray;//*****************************************************//获取数组中值为1的元素在数组中的下标
function FindIndex(A: MyIntArray): MyIntArray;
var
  I, J, K: Integer;
  arraytemp: MyIntArray;
begin
  //  setlength(A,lenA);
  J := 0;
  for I := low(A) to High(A) do
    if A[I] = 1 then
      J := J + 1;  K := 0;
  setlength(arraytemp, J);
  for I := low(A) to High(A) do begin
    if A[I] = 1 then begin
      arraytemp[K] := I;
      K := K + 1;
    end;
  end;
  result := arraytemp;
end;//获取二维矩阵A的第I行
function FindRow(A: MyTwoDArray; I: Integer): MyIntArray;
var
  J: Integer;
  arraytemp: MyIntArray;
begin
  setlength(arraytemp, length(A[0]));
  for J := low(A[0]) to High(A[0]) do
    arraytemp[J] := A[I, J];
  result := arraytemp;
end;//获取二维矩阵A的第J列
function FindCol(A: MyTwoDArray; J: Integer): MyIntArray;
var
  I: Integer;
  arraytemp: MyIntArray;
begin
  setlength(arraytemp, length(A));
  for I := low(A) to High(A) do
    arraytemp[I] := A[I, J];
  result := arraytemp;
end;//判断数组中是否全为0元素
function isallzero(A: MyIntArray): Boolean;
var
  I: Integer;
begin
  for I := low(A) to High(A) do begin
    if A[I] = 1 then begin
      result := False;
      exit;
    end;
  end;  result := true;
end;//找出行标I所对应的所有下标
procedure FindAllIndex(I: Integer; ATwo: MyTwoDArray);
var
  J, K: Integer;
  ArrayTempC, ArrayTempD: MyIntArray;
begin  StrList.Add(inttostr(I));  ArrayTempC := FindRow(ATwo, I);
  if not isallzero(ArrayTempC) then begin
    ArrayTempD := FindIndex(ArrayTempC);
    for J := low(ArrayTempD) to High(ArrayTempD) do begin
      K := ArrayTempD[J];
      FindAllIndex(K, ATwo);
    end;
  end;end;procedure TForm1.Button1Click(Sender: TObject);
var
  arraytemp1: MyIntArray;
  arraytemp2, arraytemp3, arraytemp4, arraytemp5: MyIntArray;
  SLTemp: Tstringlist;
  I,J,K,L:integer;
begin//由Z生成Y，Z为初始矩阵
  for I := low(Z) to High(Z) do begin
    arraytemp1 := FindRow(Z, I);
    if not isallzero(arraytemp1) then begin
      SLTemp := Tstringlist.Create;
      StrList := Tstringlist.Create;      FindAllIndex(I, Z);
      for K := 1 to StrList.Count - 1 do begin
        Y[I, strtoint(StrList.Strings[K])] := 1;
      end;
      SLTemp.Free;
      StrList.Free;
    end;
  end;end;这是截取出来的一部分，拿出来希望大家多提意见
主要是那个递归程序FindAllIndex