Методичка С++ (FIRST)

Посмотреть архив целиком

35



Аннотация

Настоящее учебное пособие предназначено для студентов 1 курса кафедр ИУ6 и АК5, обучающихся по программе бакалавра техники и технологии направления «Информатика и вычислительная техника». В пособии рассмотрены основные приемы составления алгоритмов программ разветвленной и циклической структуры. Кратко пояснены математические методы решения некоторых задач вычислительной математики, а также пояснены приемы обработки массивов и матриц.

Оглавление

Введение 3

1 Разветвляющиеся процессы 5

2 Циклические процессы. Алгоритмы решения задач вычислительной математики 9

2.1 Типы циклических процессов 9

2.2 Табулирование функции 10

2.3 Нахождение суммы ряда 11

2.4 Приближенное вычисление определенных интегралов 13

2.4.1 Метод прямоугольников 13

2.4.2 Метод трапеций 15

2.5 Определение корней уравнения 15

2.5.1 Метод половинного деления 15

2.5.2 Метод хорд 16

2.6 Нахождение длины кривой 16

3 Массивы 18

3.1 Приемы обработки одномерных массивов 18

3.1.1 Последовательная обработка элементов массива 18

3.1.2 Выборочная обработка элементов массива 21

3.1.3 Изменение порядка следования элементов без изменения размеров исходного массива. Сортировка массива 23

3.1.4 Переформирование массива с изменением его размеров 27

3.1.5 Одновременная обработка нескольких массивов или подмассивов 30

3.1.6 Поиск в массиве единственного элемента, отвечающего некоторому условию (поисковые задачи) 31

3.2 Приемы обработки матриц 32

3.2.1 Последовательная обработка элементов матрицы 33

3.2.2 Изменение порядка следования элементов без изменения размеров исходной матрицы. 34

Литература 35



Введение

Умение хорошо писать программы для компьютера предполагает не только хорошее владение средствами разработки программ, но и хорошо развитое алгоритмическое мышление. Вся практика программирования говорит о том, что именно отсутствие алгоритмического мышления – причина неудач студентов при изучении программирования.

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

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

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

Для представления алгоритмов в пособии использованы графические обозначения основных алгоритмических блоков по ГОСТ 19.701–90 (см. таблицу 1).

Таблица 1

Название блока

Обозначение

Назначение блока

1. Терминатор

Начало, завершение программы или подпрограммы

2. Процесс

Обработка данных (вычисления, пересылки и т.п.)

3. Данные

Операции ввода-вывода


4. Решение

Ветвления, выбор, итерационные и поисковые циклы

5. Подготовка

Счетные циклы

6. Граница цикла

Любые циклы




7. Предопределенный процесс

Вызов процедур



8. Соединитель

Маркировка разрывов линий

9. Комментарий

Пояснения к операциям


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

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

  1. Разветвляющиеся процессы

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

В качестве примера разветвляющегося вычислительного процесса рассмотрим алгоритм вычисления корней квадратного уравнения

Пример 1.1. Определение действительных корней квадратного уравнения:

ax2+bx+c=0.

В зависимости от значения дискриминанта D = b2 ­- 4ac, уравнение имеет либо два действительных корня, либо один, либо вообще не имеет действительных корней. Поэтому, для того, чтобы найти корни квадратного уравнения, необходимо предварительно вычислить дискриминант D и проверить выполнение условий D<0 и D=0. Схема алгоритма вычисления корней квадратного уравнения приведена на рисунке 1.1.

Рисунок 1.1 – Схема алгоритма вычисления действительных корней квадратного уравнения

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

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

  • букву Y, если для соответствующего варианта условие должно выполняться,

  • букву N, если условие обязательно должно не выполняться,

  • прочерк, если исход сравнения не важен.

Например, для алгоритма вычисления корней квадратного уравнения можно составить следующую таблицу:

Схему алгоритма строят по таблице. Сначала проверяют выполнение первого условия. Из таблицы следует, что первое условие должно выполняться только для первого варианта решения, поэтому после его проверки ветвь «да» соответствует случаю «нет корней». В ветви «нет» необходимо проверить условие D=0 и, в зависимости от выполнения этого условия, указать оставшиеся два случая.

Иногда, составленная таблица решений имеет сложный вид. Рассмотрим, например, таблицу:

где P1, P2, P3, P4 – варианты решений.

Если сразу приступить к построению алгоритма, то будет получена схема алгоритма, приведенная на рисунке 1.2.

Рисунок 1.2 – Неоптимальная схема фрагмента алгоритма

Этот алгоритм не кажется простым, и его построение вызывает определенные трудности, но его можно существенно упростить, если в таблице поменять местами проверяемые условия. Кроме того, для удобства построения алгоритма, целесообразно поменять местами столбцы таблицы:

Алгоритм, построенный по такой таблице, окажется значительно проще, к тому же его построение требует меньших усилий (см. рисунок 1.3).

Рисунок 1.3 Оптимизированный фрагмент схемы алгоритма

Рассмотрим еще один пример использования таблиц решений.

Пример 1.2. Решить систему уравнений:

При составлении алгоритма решения задачи необходимо рассмотреть 5 случаев:

  1. a=0, b=0, тогда x=1-cy, y - любое число;

  2. a=0, b0, тогда решений нет;

  3. a0, c=0, a=b, тогда x=1, y любое число;

  4. a0, c=0, ab, тогда решений нет:

  5. a0, c0, тогда x=b/a, y=(a-b)/(ac).

Составим таблицу решений, указывая в первом столбце условие, которое необходимо проверить:

Теперь преобразуем таблицу для более удобной реализации. На первое место целесообразно поставить условие a=0, т.к. соответствующая строка не содержит прочерков, и, следовательно, действия однозначно разделятся на две ветви. Вторым лучше проверять условие b=0, т.к. на оставшиеся два условия оно не оказывает никакого влияния. Третьим условием удобно взять b=0. В результате получили таблицу в следующем виде:

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

Рисунок 1.4 Фрагмент схемы алгоритма решения системы уравнений

  1. Циклические процессы. Алгоритмы решения задач вычислительной математики

    1. Типы циклических процессов

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

В любом процедурном языке программирования существуют средства реализации трех типов алгоритмов циклической структуры: цикла-пока, цикла-до и счетного цикла (см. рисунки 2.1, а-в).

Рисунок 2.1 – Три структурные конструкции циклов:

а – цикл-пока; б – цикл-до; в – счетный цикл

Каждый из трех алгоритмов циклических процессов состоит из нескольких основных этапов:

  • подготовка цикла – задание начальных значений переменным, изменяющимся в цикле;

  • тело цикла – действия, выполняемые непосредственно в цикле;

  • подготовка итерации – изменение значений переменных для нового выполнения тела цикла;

  • условие – проверка условия продолжения или окончания цикла;

  • организация счетчика – задание начального и конечного значения, а также шага переменной цикла.

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

Различают циклы с заданным числом повторений и циклы с заранее не известным числом повторений (итерационные циклы). Итерационные циклы характеризуются последовательным приближением к исходному значению с заданной точностью.

В конкретных типах циклических процессов указанные этапы цикла могут присутствовать в различных сочетаниях, однако порядок их проектирования не меняется:

  1. определяются действия, составляющие тело цикла;

  2. заполняется блок подготовки итерации;

  3. определяется условие выхода из цикла (счетчик или логическое выражение);

  4. заполняется блок подготовки цикла.

Пример 2.1. Задано натуральное число a. Получить все члены последовательности a, a2, a3, …, не превышающие числа b.

Схема алгоритма решения этой задачи представлена на рисунке 2.2.

Рисунок 2.2 Схема алгоритма получения последовательности

При подготовке цикла присваивается начальное значение вспомогательной переменной с. Тело цикла включает последовательное вычисление переменной c, которая равна a, a2, a3, … Изменение значения с происходит до тех пор, пока оно не станет больше или равно значению b. Если a b, то не будет выведено не одного элемента последовательности.

    1. Табулирование функции

Типичным примером циклического процесса с заданным числом повторений является задача табулирования функции (получение таблицы значений функции).

Задача сводится к вычислению значений функции y = f(x) при изменении x от начального значения a до конечного значения b с постоянным шагом h. Такая программа реализуется посредством цикла с заданным числом повторений, причем число повторений определяется по формуле:

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

Рисунок 2.3 – Схема алгоритма вычисления значений функции

Здесь при подготовке цикла вычисляется количество его повторений и присваивается начальное значение переменной x. В теле цикла рассчитывается значение функции в точке x и, затем, выводится значение x и y. При подготовке итерации изменяется значение x.

    1. Нахождение суммы ряда

Многие задачи вычислительной математики сводятся к вычислению суммы рядов вида . Определение суммы предполагает последовательное вычисление члена ряда и прибавление его к частичной сумме S до тех пор, пока не будет выполнено условие выхода из цикла. Общий вид схемы алгоритма решения такой задачи приведен на рисунке 2.4.

Условие окончания цикла зависит от поставленной задачи, как правило, оно связано с достижением требуемой точности.

Примеры постановок задач.

  1. Найти сумму первых n членов ряда . В этом случае условие выхода из цикла: i > n.

  2. Вычислять сумму ряда до тех пор, пока очередной член ряда ri не будет меньше заданного . Здесь условием выхода из цикла будет: | ri | < .

  3. Вычислить сумму ряда с точностью , если известно точное значение суммы, равное A. Здесь условие выхода из цикла: | S - A | < .


Рисунок 2.4 – Обобщенная схема алгоритма вычисление суммы ряда

Очередной член ряда вычисляют одним из следующих способов:

  • в простейших случаях – по общей формуле, например:

1) , ;

2) , ;

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

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

1) , ;

2) , ;

  • если член ряда удобно представить в виде произведения, один из сомножителей вычисляется по рекуррентному соотношению (т.е. по предыдущему члену), второй – непосредственно, например:

, .

    1. Приближенное вычисление определенных интегралов

Пусть требуется вычислить определенный интеграл , где f(x) – некоторая непрерывная функция, заданная на промежутке [a, b]. Как известно, значение определенного интеграла равно площади криволинейной трапеции, ограниченной подынтегральной функцией. Простейшими методами приближенного вычисления определенных интегралов являются метод прямоугольников и метод трапеций.

      1. Метод прямоугольников

Разобьем отрезок [a,b] точками a=x0 < x1 < x2 <... < xn-1 <xn=b, причем |xi, xi+1|=(b-a)/n. Заменим площадь каждой криволинейной трапеции с основанием [xi, xi+1] площадью прямоугольника со сторонами (b-a)/n и f(xi) (см. рисунок 2.5).

Рисунок 2.5 Метод прямоугольников

Тогда площадь каждого такого прямоугольника вычисляется по формуле: Si=f(xi)(b - a)/n. Сумма всех площадей полученных прямоугольников приближенно равна значению определенного интеграла:

.

Очевидно, что чем больше количество отрезков разбиения, тем выше точность вычислений.

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

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

Рисунок 2.6 – Схема алгоритма вычисления интеграла методом прямоугольников

Условие точности зависит от поставленной задачи. Будем пользоваться двумя способами оценки погрешности:

1. Если задано точное значение интеграла, равное I, то условием выхода из цикла будет условие | S - I | < .

2. Если не задано точное значение интеграла, то будем сравнивать сумму, полученную при последнем разбиении n, с суммой, полученной при предыдущем значении параметра n.

      1. Метод трапеций

Метод трапеций аналогичен методу прямоугольников, только здесь криволинейная трапеция заменяется не прямоугольниками, а трапециями (см. рисунок 2.7).

Рисунок 2.7 – Метод трапеций

Формула приближенного вычисления определенного интеграла методом трапеций примет вид:

или

    1. Определение корней уравнения

Рассмотрим уравнение f(x)=0, о котором известно, что оно имеет корень на отрезке [a, b], причем функция f(x) на этом интервале непрерывна и на концах отрезка [a, b] принимает различные знаки (т.е. f(a)f(b)<0). Излагаемые здесь методы состоят в приемах, при помощи которых находится новый интервал [a1, b1], такой что

a a1 < x0 < b1 b,

где x0 корень уравнения.

      1. Метод половинного деления

Этот метод является одним из самых простых. Приближение к корню уравнения здесь осуществляется с помощью деления отрезка [a, b] пополам. В результате мы получаем новую точку c (см. рисунок 2.8).

Рисунок 2.8 – Метод половинного деления

Далее проверяется, является ли точка c корнем уравнения f(x)=0. В случае положительного ответа задача решена, в случае отрицательного мы сравниваем знак функции в точке c и, в дальнейшем, будем рассматривать тот отрезок ([a, c] или [c, b]), где функция принимает разные знаки. Новый отрезок снова делится пополам, и все действия повторяются вновь. Таким образом, длина рабочего отрезка будет постоянно уменьшаться, а искомый корень уравнения будет оставаться внутри этого отрезка. Вычисления прекращаются тогда, когда будет достигнута заданная точность вычислений (т.е. |f(с)|< ).

      1. Метод хорд

Метод хорд аналогичен методу половинного деления, но дает более быстрое приближение к корню уравнения. Здесь новая точка выбирается по несколько другому закону. Точки с координатами (a, f(a)) и (b, f(b)) соединяются отрезком (хордой) и точка c выбирается как точка пересечения полученной хорды с осью OX(см. рисунок 2.9.)

Рисунок 2.9 – Метод хорд

Координату точки c находят по формуле: