даны 2 возрастающих массива. Найти их пересечение. Опции

[Insomnia]

даны 2 массива, причем x[1]<=x[2]<=..<=x[k] и y[1]<=y[2]<=..=y[l] . НАйти их пересечение, т.е. масиив z[1]<=z[2]<=...<=z[m] , содержайщий их общие элементы, причем кратность каждого элемента в массиве z равняется минимум из его кратностей в массивах x и y . Число действий порядка k+1.

Не совсем понятно условие с кратностями. Подскажите пожалуйста на простом примере что имелось ввиду.

[Lapp]

даны 2 массива, причем x[1]<=x[2]<=..<=x[k] и y[1]<=y[2]<=..=y[l] . НАйти их пересечение, т.е. масиив z[1]<=z[2]<=...<=z[m] , содержайщий их общие элементы, причем кратность каждого элемента в массиве z равняется минимум из его кратностей в массивах x и y . Число действий порядка k+1.

Не совсем понятно условие с кратностями. Подскажите пожалуйста на простом примере что имелось ввиду.

Под кратностью, полагаю, понимается число вхождений одинаковых элементов. То есть, если в x 10 двоек, а в y их 20, то в z должно быть 10 двоек.

С решением не надо подсказок? Можно как-то так:

  m:= 0;
  i:= 1;
  j:= 1;
  while (i<=k) and (j<=l) do
    if x[i]<y[j] then Inc(i)
    else if x[i]>y[j] then Inc(j)
    else begin
      Inc(m);
      z[m]:= x[i];
      Inc(i);
      Inc(j)
    end;

P.S.
добавил инициализацию m

[Insomnia]

в условии, когда мы увеличиваем i . Что будет если x[i] будет всегда меньше чем 1 элемент y[j] . Например x=(1,2,2,3..k ) , y=(6,1,3,3..L ) ?

[Lapp]

в условии, когда мы увеличиваем i . Что будет если x[i] будет всегда меньше чем 1 элемент y[j] . Например x=(1,2,2,3..k ) , y=(6,1,3,3..L ) ?

Такого не может быть. У тебя массив y неупорядочен (и я вообще слабо себе представляю, что ты имел в виду, дописывая k и L после многоточий).

[Insomnia]

ой,верно. я невнимателен. но если будет вот так x=(1,2,3,4,5) а y=(10,11,12,13,14) ?

[Lapp]

ой,верно. я невнимателен. но если будет вот так x=(1,2,3,4,5) а y=(10,11,12,13,14) ?

А у тебя компилятора под рукой нет, чтоб проверить?..

Хорошо.
сравниваем 1 и 10 - первое меньше, увеличиваем i
сравниваем 2 и 10 - первое меньше, увеличиваем i
сравниваем 3 и 10 - первое меньше, увеличиваем i
сравниваем 4 и 10 - первое меньше, увеличиваем i
сравниваем 5 и 10 - первое меньше, увеличиваем i
i вышло за пределы массива x, процесс закончен
результат - массив z пуст, количество элементов в нем (m) равно 0

[Insomnia]

черт. это же очевидно. спасибо.

[Insomnia]

выводит что пересечением является z=(4,2,3,5,7,9,6) не зависимо какими элем-ми я заполняю x и y . В чем лажа?

program peres_mass;

{$APPTYPE CONSOLE}

uses
  SysUtils,windows;

const
  k=3;
  l=3;
  m=6;
type
  TElem=integer;
  Arr=array [1..k] of TElem;
  Brr=array [1..l] of TElem;
  Crr=array [1..m] of TElem;
var
  x: Arr;
  y: Brr;
  z: Crr;
  i,j,p:TElem;

procedure creatZ ( var Z: Crr);
var
  x: Arr;
  y: Brr;
  i,j,p:TElem;
begin
  p:=0;
  i:=1;
  j:=1;
  while (i<=k) and (j<=l) do
  if x[i]<y[j] then inc(i)
			   else
	if x[i]>y[j] then inc(j)
				 else
   begin
	 inc(p);
	 z[p]:=x[i];
	 inc(i);
	 inc(j);
   end;
 writeln('пересечение массивов=', z[p]);
end;

begin
SetConsoleCP(1251);
SetConsoleOutputCP(1251);
writeln ('введите массив Arr');
for i:=1 to k do
readln(x[i]);
writeln ('введите массив Brr');
for j:=1 to l do
readln(y[j]);
creatZ (Z);
readln;
end.

Сообщение отредактировано: Insomnia - 4.06.2011 7:45

[Lapp]

выводит что пересечением является z=(4,2,3,5,7,9,6) не зависимо какими элем-ми я заполняю x и y . В чем лажа?

Однако, такое у них пересечение.

Ты заполняешь одни x и y, а обрабатываешь совсем другие.

И вывод массива z тоже сделай в цикле, а то ты выводишь только последний элемент.

[Insomnia]

 program peres_mass;

{$APPTYPE CONSOLE}

uses
  SysUtils,
  windows;

const
  k=2;
  l=3;
  m=5;
type
  TElem=integer;
  Arr=array [1..k] of TElem;
  Brr=array [1..l] of TElem;
  Crr=array [1..m] of TElem;
var
  x: Arr;
  y: Brr;
  z: Crr;
  i,j,p:TElem;

procedure creatZ ( var z: Crr; x: Arr; y: Brr);
var
  i,j,p:TElem;
begin
  p:=0;
  i:=1;
  j:=1;
  while (i<=k) and (j<=l) do
  if x[i]<y[j] then inc(i)
               else
    if x[i]>y[j] then inc(j)
                 else
   begin
     inc(p);
     z[p]:=x[i];
     inc(i);
     inc(j);
   end;
 writeln('пересечение 2_х массивов');
 for p:=1 to m do
 write(z[p]:2);
 writeln;
end;

begin
SetConsoleCP(1251);
SetConsoleOutputCP(1251);
writeln ('введите массив x');
for i:=1 to k do
readln(x[i]);
writeln ('введите массив y');
for j:=1 to l do
readln(y[j]);
creatZ (z,x,y);
readln;
end.

Работает теперь. Но в массиве z пустые ячейки заполняет нулями и выводит их вместе с найденным пересечением. Как мне их не выводить?

Сообщение отредактировано: Insomnia - 4.06.2011 19:33

[Lapp]

в массиве z пустые ячейки заполняет нулями и выводит их вместе с найденным пересечением. Как мне их не выводить?

Выводи не весь массив z, а только от 1 до p.