Слияние двух упорядоченных массивов

Задача

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

Решение

 

Например. Если
1-й массив: 4, 8, 12, 14, 23, 85,
а 2-й массив: 2, 4, 8, 9, 12, 16,
тогда 3-й массив будет таким: 2, 4, 4, 8, 8, 9, 12, 12, 14, 16, 23, 85.

Алгоритм и особенности решения задачи.

  1. Для начала надо определиться, как у нас будут формироваться первые два массива. Использование random нам не подходит, т.к. массивы должны быть упорядоченными. Будем вводить данные с клавиатуры.
  2. Длина третьего массива равна сумме двух первых.
  3. Элементы под текущими для каждого массива индексами сравниваются, и меньший по значению записывается в третий массив. При этом индекс массива, из которого элемент был скопирован в третий массив, должен увеличиться.
  4. Может возникнуть ситуация, когда один массив закончился, а второй еще нет. Поэтому в программе должен быть организован цикл записи возможного окончания как первого так и второго массива.

Программа на языке Паскаль: 

 

const
    N = 7;
var
    arr1,arr2: array[1..N] of integer;
    arr3: array[1..N+N] of integer;
    i,j,k,m: byte;
begin
    writeln('Заполните первый массив:');
    for i := 1 to N do
        read(arr1[i]);
 
    writeln('Заполните второй массив:');
    for i := 1 to N do
        read(arr2[i]);
 
    i := 1; j := 1; k := 1;
    while (i <= N) and (j <= N) do begin
        if arr1[i] < arr2[j] then begin
            arr3[k] := arr1[i];
            i := i + 1
        end
        else begin
            arr3[k] := arr2[j];
            j := j + 1
        end;
        k := k + 1;
    end;
 
    while i <= N do begin
        arr3[k] := arr1[i];
        i := i + 1;
        k := k + 1
    end;
 
    while j <= N do begin
        arr3[k] := arr1[j];
        j := i + 1;
        k := k + 1
    end;
 
    writeln;
    for i := 1 to N+N do
        write(arr3[i]:4);
 
end.	

 

Тема

Одномерные массивы

Уровень

Сложные задачи

Теги

Комментарии

uses crt;
var a,b,c:array[1..100] of integer; i,s,z,t:integer;
 
begin
clrscr;
randomize;
 
for i:=1 to 5 do begin a[i]:=random(8)+1; b[i]:=random(8)+1; end;
 
for z:=1 to i do c[z]:=a[z];
for s:=1 to z do begin
z:=z+1;
c[z]:=b[s]; end;
 
 
for s:=1 to z do {или размер первого + размер второго}
for i:=1 to z do 
if(c[i]<c[i+1]) then begin
 t:=c[i+1]; c[i+1]:=c[i]; c[i]:=t; end;
 
for i:=1 to z do write(c[i],' ');
end.

Добавить комментарий