1.6.3 Построение алгоритмов и практические вычисления

База знаний ЕГЭ Информатика Добавлено: 25-07-2017, 08:05
Видеоурок 1: Разбор заданий ЕГЭ на алгоритмы



Видеоурок 2: Разбор задания ЕГЭ на циклы



Лекция: Построение алгоритмов и практические вычисления

Циклы

Составим блок-схему алгоритма вычисления суммы знакопеременного ряда:



с заданной точностью ε.

Необходимо представить алгоритм в виде псевдокода.

Для решения данной задачи используем обозначения:
S - частичная сумма ряда (стартовое значение равно 0);
ε - точность вычисления;
i - номер очередного слагаемого;
m - значение очередного слагаемого;
p - числитель очередного слагаемого.

Требуемая точность вычисления будет достигнута в случае, когда очередное слагаемое станет по абсолютной величине меньше ε. Составим блок-схему алгоритма:































На псевдокоде запись алгоритма будет выглядеть следующим образом:
алг Сумма (арг вещ х, ε рез вещ S)
        дано  l  0<х<1
        надо  l  S=x-x2/2+x3/3+x4/4+...
        нач цел i, вещ m, p
вводх, ε
        S := 0;   i :=1
        m :=1;   p := -1
нц покаabc(m)>ε
            Р := -p*x
            m := p/i
            S := S+m  
            i := i+1
        кц
        вывод S
кон

Массивы

Массивы – это множество элементов, значение которых относится к одному типу. 
Все значения массива являются упорядоченными и имеют свой индекс.

Индекс позволяет присвоить элементу массива свое место.
 Именно поэтому найти некий элемент в массиве можно с помощью его имени и индекса.

Максимальное количество элементов данного массива – это его размерность.

Если массив состоит из некоторого ряда элементов, то он называется векторным или одномерным, если же он состоит из нескольких рядов, то он называется матричным или многомерным массивом.

Пример 1. В массиве а каждый элемент равен 0 или 1. Заменить все нули единицами и наоборот.
Решение. Достаточно одного оператора присваивания в теле цикла:
a[i] := 1 - a[i]

Пример 2. В массиве каждый элемент равен 0,1 или 2. Переставить элементы массива так, чтобы сначала располагались все 0, затем все 1 и, наконец, все 2. Дополнительный массив не использовать.
Решение. Можно не переставлять элементы массива, а подсчитать количество 0,1,2 и заново заполнить массив требуемым образом.
алг Сумма (арг цел n, рез арг вещ таб А[1:n] )
        дано  l  массив А содержит нули, единицы и двойки
        надо  l  упорядочить массив по возрастанию
        нач цел i, k1, k2
                   k1 := 0;  k2 :=0
нц дляот 1 до n
                         если А[i] =0
                             
то  k1 := k1+1; всё
                          если А[i] =1
                              
то  
k2 := k2+1всё
                   кц
нц дляот 1 до k1
                         А[i] =0
                   
кц   
                   нц для от k1+1 до k2+2
                         
А[i] =1
                   
кц  
                   нц для i от k1+k2 до n
                         
А[i] =2
                   
кц       
кон

Пример 3. Даны два n-элементных массива x и Y одного типа. Поменять местами все xi и Yi, (i=1...n) не используя промежуточные величины.
Решение. Обмен можно выполнить в цикле для всех от 1 до с помощью серии из трех операторов присваивания:
x[i] := x[i] + y[i]
y[i] := x[i] - y[i]
x[i] := x[i] - y[i]

Пример 4. Найти сумму элементов одномерного массива А(n).
Решение. Для суммирования положительных элементов массива вместо оператора S := S+А[i] необходимо записать:
   если А[i]>0
       то S := S+А[i]
       всё
На псевдокоде алгоритм расчета суммы выглядит следующим образом:
алг Сумма (арг цел n, арг вещ таб А[1:n], рез вещ S )
        дано  l  массив А  
        надо  l  найти сумму элементов массива
        нач
             цел i
             S := 0
             нц для от 1 до n
                    S := S+А[i]
             кц
кон

Действия над массивом

Данные в массиве можно искать или же сортировать. 

Основным действием, которое производится над массивом, называется поиск
Именно он лежит в основе множества других возможных манипуляций с массивами. В зависимости от того упорядочен массив или нет, поиск выполняется различным образом.

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

Сортировка – это действие, которое приводит к изменению положения элементов в заданном массиве, согласно поставленным условиям.
Сортировка производится перед поиском для более быстрого его завершения.

Существует большое разнообразие способов сортировки. Давайте рассмотрим некоторые из них:

1. Сортировка с помощью обмена

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

Пример сортировки массива с помощью псевдокода:
алг Обменная_сортировка (арг цел n, арг рез вещ таб А[1:n] )
        дано  l  А - массив размерности n
        надо  l  упорядочить массив по возрастанию
        нач
          цел i, j
вещ Tmp
нц дляiот2доn
нц дляjотnдо1
еслиА[j]<А[j-1]
тоTmp :=А[j];  А[j] :=А[j-1];
А[j-1] :=Tmp
всё
            кц
           кц
          кон

2. Метод сортировки прямым включением

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

Пример алгоритма методом сортировки прямым включением:
алг Сортировка_вставкой (арг цел n, арг рез вещ таб А[1:n] )
        дано  l  А - массив размерности n
        надо  l  упорядочить массив по возрастанию
        нач
          цел i, j
вещ Tmp
нц дляiот2доn
Tmp :=А[j];  j :=i-1;
нц покаj>= 1 и А[j]>Tmp
А[j+1] :=А[j]
j :=i-1
 кц
            А[j+1] :=Tmp
          кц
кон

3. Метод сортировки прямым выбором

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

Пример алгоритма сортировки методом прямого выбора:
алг Сортировка_выбором (арг цел n, арг рез вещ таб А[1:n] )
        дано  l  А - массив размерности n
        надо  l  упорядочить массив по возрастанию
        нач
          цел i, k
вещ Min
нц дляiот1доn-1
Min :=А[j];  k :=i
нц дляот i+1 до n
еслиMin > А[j]
тоMin :=А[j]; k :=j
       всё
          кц
          А[k] :=А[i]; А[i] :=Min
кц
кон

Процедуры и функции

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

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

Процедура – это некое действие, которое не позволяет вернуть исходное значение переменных.

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

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

Если же некая стандартная программа была написана вами, и вы сохраняете её в библиотеку, то она называется пользовательской.

Предыдущий урок
Следующий урок

  • 2.2 Характерные химические свойства и получение простых веществ - металлов: щелочных, щелочноземельных, алюминия; переходных элементов (меди, цинка, хрома, железа)
  • 1.2.4 Общая характеристика неметаллов IVA – VIIA групп в связи с их положением в Периодической системе химических элементов Д.И.Менделеева и особенностями строения их атомов
  • 1.2.3 Характеристика переходных элементов (меди, цинка, хрома, железа) по их положению в периодической системе химических элементов Д.И. Менделеева и особенностям строения их атомов
  • 4.1 Самостоятельные части речи. Имя числительное
  • 6.15 Правописание словарных слов
  • Оставить комментарий