Понятия алгоритма и программы. Свойства алгоритмов. Составление алгоритмов различной структуры.

Понятия алгоритма и программы. Свойства алгоритмов. Составление алгоритмов различной структуры.

Алгори́тм — набор инструкций, описывающих порядок действий исполнителя для достижения результата решения задачи за конечное время

Компью́терная програ́мма — последовательность инструкций, предназначенная для исполнения устройством управления вычислительной машины.

Алгоритм обладает следующими свойствами:

1. Дискретность. Это свойство состоит в том, что алгоритм должен представлять процесс решения задачи как последовательное выполнение простых шагов. При этом для выполнения каждого шага алгоритма требуется конечный отрезок времени, т.е. преобразование исходных данных в результат осуществляется во времени дискретно.

2. Определенность. Каждое правило алгоритма должно быть четким, однозначным.

3. Результативность. Алгоритм должен приводить к решению за конечное число шагов.

4. Массовость. Алгоритм решения задачи разрабатывается в общем виде, т.е. он должен быть применим для некоторого класса задач, различающихся лишь исходными данными.

5. Правильность. Алгоритм правильный, если его выполнение дает правильные результаты решения поставленной задачи.

На практике получили известность два способа изображения алгоритмов:

в виде пошагового словесного описания;

в виде блок-схем.

Блок-схема – это последовательность блоков, предписывающих выполнение определенных операций, и связей между этими блоками. Внутри блоков указывается информация об операциях, подлежащих выполнению.

Линейный алгоритм – алгоритм, в котором команды выполняются в порядке их записи, то есть последовательно друг за другом

Алгоритм с ветвлением или разветвляющийся алгоритм - форма организации действий, при которой в зависимости от выполнения некоторого условия совершается одна или другая последовательность шагов

Алгоритм с повторением или цикл - форма организации действий, при которой выполнение одной и той же последовательности команд повторяется, пока выполняется некоторое заранее установленное условие.

 

Описание и типы алгоритмов поиска. Примеры.

В алгоритмах поиска существует два возможных окончания работы: поиск может оказаться удачным – заданный элемент найден в массиве и определено его место расположение, либо поиск может оказаться неудачным – необходимого элемента в данном объеме информации нет. Несмотря на то что целью поиска является значение элемента, алгоритм поиска в случае удачного окончания выдает местоположение искомого элемента, например его номер в массиве, так как по номеру элемента можно восстановить и его значение.

Алгоритм последовательного поиска в неупорядоченном массиве

 Имеется массив a[1 … n], требуется найти элемент массива, равный P:

Установить i = 1.

Если ai = P, алгоритм завершил работу успешно.

Увеличить i на 1.

Если i ≤ n, то перейти к шагу 2. В противном случае алгоритм завершил работу безуспешно.

Алгоритм поиска максимального элемента в неупорядоченном массиве:

Установить счетчик равным 1 (i = 1).

Положим значение текущего максимума равным первому исследуемому элементу (max = a1).

Если исследованы еще не все элементы (i < n), то перейти к шагу 5, иначе алгоритм окончен (максимальный элемент равен max).

Перейти к следующему элементу (увеличить i на единицу).

Если рассматриваемый элемент больше, чем текущий максимум (ai > max), то значение ai присвоить max.

Перейти к шагу 4.

Алгоритм одновременного поиска максимального и минимального элементов в неупорядоченном массиве:

Установить счетчик равным 1 (i = 1).

Положим значения текущего минимума и текущего максимума равными первому исследуемому элементу (min = a1, max = a1).

Если исследованы еще не все элементы i < n), то перейти к шагу 4, иначе алгоритм окончен (минимальный и максимальный элементы равны min и max соответственно).

Перейти к следующему элементу (увеличить i на единицу).

Если текущий элемент меньше чем минимум (ai < min), то присвоить min значение ai, иначе если текущий элемент больше, чем максимум (ai > max), то присвоить max значение ai

Перейти к шагу 3.

 

Пример поиска заданного значения в массиве. Код C#:

int[] array1 = new int[] { 1, 3, 5, 7, 9 };

       int p = 1;         

       for (int i = 0; i < 5; i++)

           if (array1[i] == p)

           { Console.WriteLine(i); }

 

       Console.ReadLine();

 

 

Описание и виды алгоритмов сортировки. Примеры.

Обычно сортировку подразделяют на два класса: внутреннюю и внешнюю. При внутренней сортировке все элементы хранятся в оперативной памяти, таким образом, как правило, это сортировка массивов. При внешней сортировке — элементы хранятся на внешнем запоминающем устройстве, это сортировка файлов.

Сортировка обменом (пузырьковая). Массив просматривается N-1 раз. При каждом просмотре сравниваются каждые два соседних элемента. Если элемент с меньшим индексом оказывается больше, производится их обмен.

var i, j: byte; vsp: integer;

begin

for i:= 1 to n - 1 do

  for j:= 1 to n - i do

    if a[j]>a[j+1] then

                         begin

                                          vsp:=a[j];

                                          a[j]:=a[j+1];

                                          a[j+1]:=vsp;

                                          end

end;

Сортировка вставками. Пусть часть массива отсортирована. Выбираем в неотсортированной части очередной элемент и вставляем его в отсортированную так, чтобы упорядоченность элементов сохранилась. При поиске места вставки осуществляем сдвиг элементов в сторону возрастания номеров.

var i, j: byte; vsp: integer;

begin

for i:= 2 to n do

begin vsp:=a[i];

      j:= i-1;

      while (a[j]>vsp) and (j>1) do

      begin

                   a[j+1]:=a[j];

                   j:=j-1

       end;

      if (a[j]>vsp) and (j=1)

      then begin

                              a[2]:=a[1];

                              a[1]:= vsp

                   end

       else a[j+1]:=vsp;

end

end;

 

 

Понятия алгоритма и программы. Свойства алгоритмов. Составление алгоритмов различной структуры.

Алгори́тм — набор инструкций, описывающих порядок действий исполнителя для достижения результата решения задачи за конечное время

Компью́терная програ́мма — последовательность инструкций, предназначенная для исполнения устройством управления вычислительной машины.

Алгоритм обладает следующими свойствами:

1. Дискретность. Это свойство состоит в том, что алгоритм должен представлять процесс решения задачи как последовательное выполнение простых шагов. При этом для выполнения каждого шага алгоритма требуется конечный отрезок времени, т.е. преобразование исходных данных в результат осуществляется во времени дискретно.

2. Определенность. Каждое правило алгоритма должно быть четким, однозначным.

3. Результативность. Алгоритм должен приводить к решению за конечное число шагов.

4. Массовость. Алгоритм решения задачи разрабатывается в общем виде, т.е. он должен быть применим для некоторого класса задач, различающихся лишь исходными данными.

5. Правильность. Алгоритм правильный, если его выполнение дает правильные результаты решения поставленной задачи.

На практике получили известность два способа изображения алгоритмов:

в виде пошагового словесного описания;

в виде блок-схем.

Блок-схема – это последовательность блоков, предписывающих выполнение определенных операций, и связей между этими блоками. Внутри блоков указывается информация об операциях, подлежащих выполнению.

Линейный алгоритм – алгоритм, в котором команды выполняются в порядке их записи, то есть последовательно друг за другом

Алгоритм с ветвлением или разветвляющийся алгоритм - форма организации действий, при которой в зависимости от выполнения некоторого условия совершается одна или другая последовательность шагов

Алгоритм с повторением или цикл - форма организации действий, при которой выполнение одной и той же последовательности команд повторяется, пока выполняется некоторое заранее установленное условие.

 

Описание и типы алгоритмов поиска. Примеры.

В алгоритмах поиска существует два возможных окончания работы: поиск может оказаться удачным – заданный элемент найден в массиве и определено его место расположение, либо поиск может оказаться неудачным – необходимого элемента в данном объеме информации нет. Несмотря на то что целью поиска является значение элемента, алгоритм поиска в случае удачного окончания выдает местоположение искомого элемента, например его номер в массиве, так как по номеру элемента можно восстановить и его значение.

Алгоритм последовательного поиска в неупорядоченном массиве

 Имеется массив a[1 … n], требуется найти элемент массива, равный P:

Установить i = 1.

Если ai = P, алгоритм завершил работу успешно.

Увеличить i на 1.

Если i ≤ n, то перейти к шагу 2. В противном случае алгоритм завершил работу безуспешно.

Алгоритм поиска максимального элемента в неупорядоченном массиве:

Установить счетчик равным 1 (i = 1).

Положим значение текущего максимума равным первому исследуемому элементу (max = a1).

Если исследованы еще не все элементы (i < n), то перейти к шагу 5, иначе алгоритм окончен (максимальный элемент равен max).

Перейти к следующему элементу (увеличить i на единицу).

Если рассматриваемый элемент больше, чем текущий максимум (ai > max), то значение ai присвоить max.

Перейти к шагу 4.

Алгоритм одновременного поиска максимального и минимального элементов в неупорядоченном массиве:

Установить счетчик равным 1 (i = 1).

Положим значения текущего минимума и текущего максимума равными первому исследуемому элементу (min = a1, max = a1).

Если исследованы еще не все элементы i < n), то перейти к шагу 4, иначе алгоритм окончен (минимальный и максимальный элементы равны min и max соответственно).

Перейти к следующему элементу (увеличить i на единицу).

Если текущий элемент меньше чем минимум (ai < min), то присвоить min значение ai, иначе если текущий элемент больше, чем максимум (ai > max), то присвоить max значение ai

Перейти к шагу 3.

 

Пример поиска заданного значения в массиве. Код C#:

int[] array1 = new int[] { 1, 3, 5, 7, 9 };

       int p = 1;         

       for (int i = 0; i < 5; i++)

           if (array1[i] == p)

           { Console.WriteLine(i); }

 

       Console.ReadLine();

 

 

Описание и виды алгоритмов сортировки. Примеры.

Обычно сортировку подразделяют на два класса: внутреннюю и внешнюю. При внутренней сортировке все элементы хранятся в оперативной памяти, таким образом, как правило, это сортировка массивов. При внешней сортировке — элементы хранятся на внешнем запоминающем устройстве, это сортировка файлов.

Сортировка обменом (пузырьковая). Массив просматривается N-1 раз. При каждом просмотре сравниваются каждые два соседних элемента. Если элемент с меньшим индексом оказывается больше, производится их обмен.

var i, j: byte; vsp: integer;

begin

for i:= 1 to n - 1 do

  for j:= 1 to n - i do

    if a[j]>a[j+1] then

                         begin

                                          vsp:=a[j];

                                          a[j]:=a[j+1];

                                          a[j+1]:=vsp;

                                          end

end;

Сортировка вставками. Пусть часть массива отсортирована. Выбираем в неотсортированной части очередной элемент и вставляем его в отсортированную так, чтобы упорядоченность элементов сохранилась. При поиске места вставки осуществляем сдвиг элементов в сторону возрастания номеров.

var i, j: byte; vsp: integer;

begin

for i:= 2 to n do

begin vsp:=a[i];

      j:= i-1;

      while (a[j]>vsp) and (j>1) do

      begin

                   a[j+1]:=a[j];

                   j:=j-1

       end;

      if (a[j]>vsp) and (j=1)

      then begin

                              a[2]:=a[1];

                              a[1]:= vsp

                   end

       else a[j+1]:=vsp;

end

end;