Конспект лекций по программированию для начинающих. Гладков В.П. - 165 стр.

UptoLike

ВУЗ: 

ПНИПУ | Пермь

Составители: 

Рубрика: 

167
приводить по мере вычисления промежуточных одночленов. Таким образом,
коэффициенты результата будут получаться по формуле
c = ab
i+j i j
j=0
m
i=o
n
⋅
∑∑
.
Соответствующий алгоритм приведен ниже:
for i:=0 to n do
for j:=0 to m do c[i+j]:=c[i+j]+a[i]*b[j].
Упражнение. Напишите алгоритм подстановки в многочлен на место
переменной другого многочлена и раскрытия всех скобок.
Пример 11.29. Заданы два упорядоченных по возрастанию элементов
одномерных массива: a размерности n и b размерности m. Требуется получить
третий массив с размерности n+m, который содержал бы все элементы исходных
массивов, упорядоченные по возрастанию.
Решение. Алгоритм решения этой задачи известен как «сортировка фон
Неймана». Идея алгоритма состоит в следующем. Сначала анализируются первые
элементы обоих массивов. Меньший элемент переписывается в новый массив.
Оставшийся элемент последовательно сравнивается с элементами из другого
массива. В новый массив после каждого сравнения попадает меньший элемент.
Процесс продолжается до исчерпания элементов одного
из массивов. Затем остаток
другого массива дописывается в новый массив. Полученный новый массив
упорядочен.
Для массива a будем использовать в качестве индекса переменную i, для
массива b - j, для массива c - k. Описанный алгоритм может быть реализован на
Паскале так:
k:=0; {в новом массиве пока нет элементов}
i:=1; j:=1; {сравнение начинаем с первых элементов}
while (i<=n) and (j<=m) do {пока один из массивов
не закончился}
if a[i]<b[j] {меньший элемент записываем в массив с}
then begin k:=k+1; c[k]:=a[i]; i:=i+1 end
else begin k:=k+1; c[k]:=b[j]; j:=j+1 end;
{если массив а не пуст, то дописываем оставшиеся элементы в массив с}
while i<=n do
begin k:=k+1;
c[k]:=a[i];
i:=i+1
end;
{если массив b не пуст, то дописываем оставшиеся элементы в массив с}
while j<=m do
begin k:=k+1;
c[k]:=b[j];
j:=j+1
end.
Часто в программировании встречается ситуация, когда требуется для
выбранных элементов массива просмотреть часть этого же массива.
Особенно
часто эта ситуация встречается в задачах сортировки массивов. Просматриваемая 
                                     167

приводить по мере вычисления промежуточных одночленов. Таким образом,
                                                               n   m
коэффициенты результата будут получаться по формуле c i+ j =   ∑∑a
                                                               i=o j=0
                                                                         i   ⋅bj .

   Соответствующий алгоритм приведен ниже:
   for i:=0 to n do
      for j:=0 to m do c[i+j]:=c[i+j]+a[i]*b[j].
   Упражнение. Напишите алгоритм подстановки в многочлен на место
переменной другого многочлена и раскрытия всех скобок.
   Пример 11.29. Заданы два упорядоченных по возрастанию элементов
одномерных массива: a размерности n и b размерности m. Требуется получить
третий массив с размерности n+m, который содержал бы все элементы исходных
массивов, упорядоченные по возрастанию.
   Решение. Алгоритм решения этой задачи известен как «сортировка фон
Неймана». Идея алгоритма состоит в следующем. Сначала анализируются первые
элементы обоих массивов. Меньший элемент переписывается в новый массив.
Оставшийся элемент последовательно сравнивается с элементами из другого
массива. В новый массив после каждого сравнения попадает меньший элемент.
Процесс продолжается до исчерпания элементов одного из массивов. Затем остаток
другого массива дописывается в новый массив. Полученный новый массив
упорядочен.
   Для массива a будем использовать в качестве индекса переменную i, для
массива b - j, для массива c - k. Описанный алгоритм может быть реализован на
Паскале так:
   k:=0; {в новом массиве пока нет элементов}
   i:=1; j:=1; {сравнение начинаем с первых элементов}
   while (i<=n) and (j<=m) do {пока один из массивов не закончился}
      if a[i]

Страницы