Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате
Форум программистов > Delphi: Для новичков > Помогите разобраться с задачей (массивы)


Автор: floopless 24.11.2009, 11:54
Дано два массива. Найти наименьшее среди тех элементов первого массива, которые не входят во второй массив.

Я мыслю как - взять первый массив, отсортировать по возрастанию, дальше взять из него первый (наименьший элемент) и сравнивать со всеми элементами второго массива. Если элементы окажутся равны - брать следующий и снова сравнивать. В противном случае - вывести первый элемент.

Стопорюсь на сравнении - подскажите как правильно сделать..

Или есть такой вариант решения - тоже пришел в голову - 
сравнить оба массива на предмет одинаковых элементов, находя - удалять такой элемент из первого массива. Дальше отсортировать полученный массив по возрастанию и вывести первый (наименьший элемент).
Но тут проблемма - удаление элемента из массива..

Подскажите вообщем.. и вообще, какой способ лучше, оптимальнее..?

Автор: Уттара 24.11.2009, 13:34
Сравниваешь два массива если элемент из первого массива не найден во втором массиве то записать его в третий массив, потом третий массив сортируешь и самое первое число смотришь.

Автор: Демо 24.11.2009, 13:43
Простейший и железный алгоритм:

A,B - массивы
C - пустой массив

Пробегаем в цикле по A, каждый элемент ищем в B.
Если находим A[n], отсутствующий в B элемент, добавляем этот элемент A[n] в C.
Пробегаем один раз C и находим минимальный элемент.

Автор: Frees 24.11.2009, 13:50
A,B - массивы

перебегаем массив А для каждого элемента -  ищем в В если не наши сравниваем элимент с мин. если меньше то это новый мин

Добавлено через 1 минуту и 1 секунду
или 

перебегаем массив А для каждого элемента -  если он меньше мин то ищем его в В если не наши то это новый мин

Автор: floopless 24.11.2009, 15:10
А как быть с третьим массивом? Сколько выделить под него места? Естли ведь выделить больше, остальные элементы будут нули..и как тогда определить минимальный..

Автор: Демо 24.11.2009, 15:14
Цитата(floopless @  24.11.2009,  15:10 Найти цитируемый пост)
А как быть с третьим массивом? Сколько выделить под него места? Естли ведь выделить больше, остальные элементы будут нули..и как тогда определить минимальный..


А третий динамическим сделать.

Автор: Уттара 24.11.2009, 15:33
Цитата(Демо @  24.11.2009,  15:14 Найти цитируемый пост)
А третий динамическим сделать. 

Функцией SetLength в цикле изменяешь размеры
А класс TList тут не поможет?, хотя придется преобразовывать числа в указатели.

Автор: floopless 24.11.2009, 15:48
У меня массивы указателей.. напиши как использовать TList..

Автор: Frees 24.11.2009, 15:51
Код

with TList.Create do
begin
 Add(p);//добавление
 IndexOf(p);//вернет индекс если p уже есть
 items[i];//доступ к элементу
 count;//кол-во элементов
end;


Добавлено через 3 минуты и 26 секунд
и не забыть free когда список станет не нужен

Автор: floopless 25.11.2009, 00:22
Вообщем вот что получилось  -  (Дано два массива. Найти наименьшее среди тех элементов первого массива, которые не входят во второй массив)
Вроде все работает..но посмотрите на код плз..не нагородил ли я там глупых конструкций.. smile 
Код

unit Unit1;

interface

uses
  Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms,
  Dialogs, Grids, StdCtrls, Buttons, ExtCtrls;

type
  TForm1 = class(TForm)
    Panel1: TPanel;
    Edit1: TEdit;
    Button1: TButton;
    Label1: TLabel;
    Label2: TLabel;
    Label3: TLabel;
    StringGrid1: TStringGrid;
    StringGrid2: TStringGrid;
    procedure FormCreate(Sender: TObject);
    procedure Button1Click(Sender: TObject);
  private
    { Private declarations }
  public
    { Public declarations }
  end;
  const N = 9; // Максимальное кол-во элементов (в таблицах)
  type
  Arr1 = array of integer;
  Arr2 = array of integer;
  Arr3 = array of integer;

var
  Form1: TForm1;
  a: Arr1;
  b: Arr2;
  c: Arr3;
  i,j,k,temp,count: integer;

implementation

{$R *.dfm}

procedure TForm1.FormCreate(Sender: TObject);
begin
// Заполняем таблицы случайными значениями
Randomize;
for i:=0 to N do
begin
StringGrid1.Cells[i,0]:=IntToStr(Random(100));
StringGrid2.Cells[i,0]:=IntToStr(Random(100));
end;

end;


procedure TForm1.Button1Click(Sender: TObject);
begin
// Устанавливаем длину массивов a и b
SetLength (a,10);
SetLength (b,10);
// Считываем в массивы значения с обеих таблиц
for i:=0 to N do
begin
a[i]:=StrToInt(StringGrid1.Cells[i,0]);
b[i]:=StrToInt(StringGrid2.Cells[i,0]);
end;
// Проверяем каждый элемент массива a на 'присутствие' в массиве b
//Если элемент из массива a отсутствует во втором массиве - копируем его в третьий массив
k:=0;
count:=0;
for i := 0 to N do
  for j := 0 to N do
  begin
    if a[i]=b[j] then Break;

    if (a[i]<>b[j]) and (j=9) then
    begin
    SetLength (c,k+1);
    c[k]:= a[i];
    inc(k);
    inc(count);
    end;
    end;
    a:=nil;
    b:=nil;


// Сортируем по возрастанию третий массив и выводим первый (наименьший) элемент
    for i:= 1 to count do
      for j:= count  downto i do
      if c[j-1]>c[j] then
      begin
       temp:=c[j];
       c[j]:=c[j-1];
       c[j-1]:=temp;
      end;
      Edit1.Text:=IntToStr(c[0]);
      c:=nil;
end;

end.

Автор: Демо 25.11.2009, 00:59
Я бы, честно говоря, вынес отдельные участки кода в доп. функции.

Автор: Демо 25.11.2009, 01:28
Раз уж ты всё сделал, вот посмотри на короткий вариант:

Код

type
  TArray=array of Integer;

var
  A: TArray;
  B: TArray;
...

function isElementInArray(El: Integer; B: TArray): BOolean;
var
   i: integer;
begin
   Result := True;
   for i := Low(B) to High(B) do
   begin
     if El=B[i] then Exit;
   end;
   Result := False;
end;

var
   i: Integer;
   MinEl: Integer;
   A,B: TArray;
begin
   MinEl := MaxInt-1;
   for i := Low(A) to High(A) do
   begin
     if not isElementInArray(A[i],B) then
     begin
       if A[i]<MinEl then MinEl := A[i];
     end;
   end;
  ShowMessage('Min element='+IntToStr(MinEl));


Автор: Frees 25.11.2009, 07:29
Демо

Код

     if  A[i]<MinEl then
     begin
       if not isElementInArray(A[i],B) then MinEl := A[i];
     end;


так ведь оптимальнее

Автор: Демо 25.11.2009, 08:03
Цитата(Frees @  25.11.2009,  07:29 Найти цитируемый пост)
так ведь оптимальнее


Может быть;)

Автор: amsoft 25.11.2009, 10:20
Код

if  ((A[i]<MinEl) and (not isElementInArray(A[i],B)))  then MinEl := A[i];

Автор: Frees 25.11.2009, 10:24
Цитата(amsoft @  25.11.2009,  13:20 Найти цитируемый пост)
надо же выбрать минимум, а ты не глядя переписываешь MinEl  smile 

почему не глядя я просто условия местами поменял..
если элемент больше минимума то можно и не смотреть есть ли он во втором массиве

Автор: amsoft 25.11.2009, 14:11
Frees
это я затупил - первую строку не увидел (потом сообщение отредактировал  smile )

Автор: Dom 25.11.2009, 17:01
А мне вот нравится первоначальная идея автора топика. Сортировать оба массива. Потом брать пошагово элементы первого массива, начиная с наименьшего, и бинарным поиском искать во втором массиве. Если элемент найден, то берем следующий элемент первого массива и ищем его во втором. Не силен в оценке сложности алгоритмов, но мне кажется, что такой алгоритм будет быстрее. Или я не прав?

Powered by Invision Power Board (http://www.invisionboard.com)
© Invision Power Services (http://www.invisionpower.com)