Форум программистов
 

Восстановите пароль или Зарегистрируйтесь на форуме, о проблемах пишите сюда - alarforum@yandex.ru, проверяйте папку спам!

Вернуться   Форум программистов > IT форум > Помощь студентам
Регистрация

Восстановить пароль
Повторная активизация e-mail

Купить рекламу на форуме - 42 тыс руб за месяц, летом дешевле!

Ответ
 
Опции темы Поиск в этой теме
Старый 14.12.2012, 06:32   #1
Решетова Алена
Форумчанин
 
Регистрация: 13.12.2012
Сообщений: 116
По умолчанию free pascal. Где-то Ошибка. Бинарный поиск в двумерном динамическом целочисленном массиве.

Даны число N и двумерный динамический целочисленный массив A, содержимое строк которого отсортировано по возрастанию, а сами строки - отсортированы по возрастанию значений первого элемента строк. Используя универсальную функцию поиска SearchBinMultiDyn (см.лекции), найти все строки массива A, которые содержат не менее 2-х значений N. Вывести содержимое найденных строк на экран.

Функцию эту SearchBinMultiDyn нам не давали. надо было написать самим. зато есть такая:

Код:
Const N=15;
type TArray=array[0..N-1] of integer;

Function SearchBinMulti(Const A:TArray; X:integer; var LeftBound,RightBound:integer):boolean;
 var left,right,center:integer;
begin
 result:=false;
 left:=0; right:=N-1;
 while left<=right do begin
   center:=left+(right-left)div 2;
   if a[center]=X then begin
    result:=true;
    LeftBound:=center; 
    while (LeftBound>=0)and(a[LeftBound]=X) do dec(LeftBound);
    inc(LeftBound);
    RightBound:=center; 
    while (RightBound<N)and(a[RightBound]=X) do inc(RightBound);
    dec(RightBound);
    exit;
   end
   else if  a[center]<X then left:=center+1
   else right:=center-1;
  end;
 end;

var a:tarray=(1,1,1,2,3,4,4,4,5,6,7,9,9,9,9);
    L,R:integer;
begin
 if SearchBinMulti(a,1,L,R) then begin
  while L<=R do begin
   writeln ('индекс=',L,' значение=',a[L]);
   inc(L);
  end;
 end
 else writeln('не найдено');
end.

И преподаватель сказал, что в динамической только тип поменять и некоторые изменения ввести. я такую написала: 

type TDynArray=array of pointer;

Function SearchBinMultiDyn(Const A:TDynArray; X:integer; var LeftBound,RightBound:integer):boolean;
 var left,right,center:integer;
begin
 result:=false;
 left:=0; right:=length(A)-1;
 while left<=right do begin
   center:=left+(right-left)div 2;
   if integer(a[center]^)=X then begin
    result:=true;
    LeftBound:=center; 
    while (LeftBound>=0) and (integer(a[LeftBound]^)=X) do dec(LeftBound);
    inc(LeftBound);
    RightBound:=center; 
    while (RightBound<length(A)) and (integer(a[RightBound]^)=X) do inc(RightBound);
    dec(RightBound);
    exit;
   end
   else if integer(a[center]^)<X then left:=center+1
   else right:=center-1;
  end;
 end;


var a:TDynArray;
	i:integer;
	x:^integer;
    L,R:integer;
begin

 setLength(a,10);
 for i:=0 to 4 do begin
  new(x);
  x^:=i+1;
  a[i]:=x;
 end;
 for i:=5 to 6 do begin
  new(x);
  x^:=7;
  a[i]:=x;
 end;
 for i:=7 to 9 do begin
  new(x);
  x^:=9;
  a[i]:=x;
 end;

 if SearchBinMultiDyn(a,7,L,R) then begin
  while L<=R do begin
   writeln ('index=',L,' znachenie=',integer(a[L]^));
   inc(L);
  end;
 end
 else writeln('net');
end.
Не знаю правильно или нет. И в программе её менять нельзя. только саму программу дописать. Но у меня после запуска error 216 No heap dump by heaptrc unit. Я понимаю почему так. В функции виден только первый столбец. а не стоки. но как правильно сделать я не понимаю. если функцию менять нельзя. типы должны быть такими. Я сделала так:

Код:
{$mode objfpc}
uses heaptrc;

type TDynArray=array of pointer;

Function SearchBinMultiDyn(Const A:TDynArray; X:integer; var LeftBound,RightBound:integer):boolean;
 var left,right,center:integer;
begin
 result:=false;
 left:=0; right:=length(A)-1;
 while left<=right do begin
   center:=left+(right-left)div 2;
   if integer(a[center]^)=X then begin
    result:=true;
    LeftBound:=center; 
    while (LeftBound>=0) and (integer(a[LeftBound]^)=X) do dec(LeftBound);
    inc(LeftBound);
    RightBound:=center; 
    while (RightBound<length(A)) and (integer(a[RightBound]^)=X) do inc(RightBound);
    dec(RightBound);
    exit;
   end
   else if integer(a[center]^)<X then left:=center+1
   else right:=center-1;
  end;
 end;

Const N=5;
var ps:array of array of integer;
	i,j:integer;
    L,R: integer;

procedure fill(); // заполнение матрицы
 var i,j:integer;
begin
randomize;
 setlength(ps,N);
 for i:=0 to N-1 do begin
  setlength(ps[i],N);
  if i=0 then ps[i][0]:=1+random(4)
  else ps[i][0]:=ps[i-1][0]+random(4);
  for j:=0 to N-2 do begin 
   ps[i][j+1]:=ps[i][j]+random(4);
  end;
 end;
end;

procedure out(); // вывод матрицы на экран
 var i,j:integer;
begin
 writeln;
 for i:=0 to N-1 do begin
  for j:=0 to N-1 do write(ps[i][j]:5);
  writeln;
 end;
end;

Begin
 fill();
 out();
 writeln;
 for i:=0 to (N-1) do begin
   If SearchBinMultiDyn(@ps[i],7,L,R) then begin writeln(L,' ',R);
     If R-L=0 then writeln('net')
     Else begin
          write('stroka ',i+1,' znachenya: ');
          for j:=0 to N-1 do begin write(ps[i][j],' '); end;
          end;
   end;
 end;
End.
Помогите, пожалуйста, разобраться. Уже 3-ий день думаю! Не могу больше(((



___________
Код нужно оформлять по правилам:
тегом [CODE]..[/СODE] (это кнопочка с решёточкой #)
Не забывайте об этом!
Модератор.

Последний раз редактировалось Serge_Bliznykov; 14.12.2012 в 11:32.
Решетова Алена вне форума Ответить с цитированием
Старый 14.12.2012, 09:15   #2
DiemonStar
Старожил
 
Регистрация: 08.02.2012
Сообщений: 2,173
По умолчанию

1. поскольку ваши строки отсортированы по возрастанию, то проверяете лишь те строки, где первый элемент <=N
2. В каждой строке подсчёт ведёте до первого элемента >N. После этого можете привязать строку к массиву результатов, если выполняется условие поиска.

з.ы. в вашем примере никак не двумерный массив, судя по описанию:

Цитата:
Код:
type TArray=array[0..N-1] of integer;
Правильно поставленная задача - три четверти решения.

Последний раз редактировалось DiemonStar; 14.12.2012 в 09:18.
DiemonStar вне форума Ответить с цитированием
Старый 15.12.2012, 06:22   #3
Решетова Алена
Форумчанин
 
Регистрация: 13.12.2012
Сообщений: 116
По умолчанию

нееет. двумерный. type TDynArray=array of pointer; var ps:array of array of integer;
А эта функция

Const N=15;
type TArray=array[0..N-1] of integer;
Function SearchBinMulti(Const A:TArray; X:integer; var LeftBound,RightBound:integer):boole an;

для примера. Она для одномерного статического массива. Нам её препод дал. И надо написать такую же только для одномерного динамического. А потом эту написанную для одномерного динамического использовать в задаче для двумерного динамического, передавая функции по строке массива.
У меня в мозгах зацикливание. Потому что заголовок функции и типы менять нельзя. и вообще всю функцию. Вот как она есть для одномерного динамического (которую я написала) так её и надо использовать в задаче, дописав только основной блок задачи. Но как если передавая по строке массива array of array of integer передается array of integer то есть pointer, а не array of pointer (TDynArray). И функция не понимает что ей передаются строки(адресом на первый элемент строки @ps[i]), она видит только первый столбец массива. поэтому и вылетает за пределы памяти.
Если в функции array of pointer, то надо передавать не адрес на строку, а на весь массив @ps. А уже в функции for i:=0 to length(a)-1 do ... и каждую строку проверять. НО тогда надо будет записывать результат (строки, подходящие под критерий) в массив TIndexArray = array of integer. И ставить его вместо boolean в result. НО менять заголовок нельзя! Вот я и понять не могу что делать...

Ладно сама потом разберусь. Препода замучаю. Скажет, что хочет. А то понять не могу...
Решетова Алена вне форума Ответить с цитированием