uzluga.ru
добавить свой файл
1

Алгоритмизация и программирование

Этапы решения задач на ЭВМ.


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

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

Лучше всего рассмотреть процесс решения задачи на компьютере на конкретном примере. Пусть мы изучаем полет пушечного снаряда. Сначала мы строим содержательную модель, в которой рассматриваем движение снаряда в поле тяготения Земли. В этой модели мы рассматриваем только те параметры, которые характеризуют движение снаряда (скорость и координаты), и отвлекаемся от других параметров (температура снаряда, его цвет и т. д.). Затем строим математическую модель.

Математическая модель всегда основана на некоторых упрощениях, и поэтому этап построения математической модели весьма ответственный, неправильно выбранная модель с неизбежностью приводит к неверным результатам. Реально существующую физическую систему опишем с помощью идеализированной математической модели. Снаряд считаем материальной точкой, сопротивлением воздуха и размерами пушки пренебрегаем, ускорение свободного падения считаем постоянным g = 9,8 м/с2. Снаряд вылетает из пушки со скоростью V под углом α к горизонту.

Математическая модель описывается с помощью уравнений.

Пользуясь формулами из курса физики 9-го класса и учитывая, что по оси Х движение равномерное, а по оси Y — равноускоренное, можно получить формулы зависимости координат снаряда от времени:

х = (V cos α)t,

y=(V sin α)t - gt2/2.

Следующим этапом является построение информационной модели и алгоритма. Каждый из нас постоянно встречается с множеством задач от самых простых и хорошо известных до очень сложных. Для многих задач существуют определённые правила (инструкции, предписания), объясняющие исполнителю, как решать данную задачу. Эти правила человек может изучить заранее или сформировать сам в процессе решения задачи. Такие правила принято называть алгоритмами.

^

Линейный алгоритм решение задач.



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

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


Рассмотрим пример алгоритма для нахождения середины отрезка при помощи циркуля и линейки.

Алгоритм деления отрезка АВ попалам:

  1. поставить ножку циркуля в точку А;

  2. установить раствор циркуля равным длине отрезка АВ;

  3. провести окружность;

  4. поставить ножку циркуля в точку В;

  5. провести окружность;

  6. через точку пересечения окружностей провести прямую;

  7. отметить точку пересечения этой прямой с отрезком АВ.

  • Каждое указание алгоритма предписывает исполнителю выполнить одно конкретное законченное действие.

  • Исполнитель не может перейти к выполнению следующей операции, не закончив полностью выполнения предыдущей.

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

  • Выполнение всех предписаний гарантирует правильное решение задачи.

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

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

Всякий алгоритм составляется в расчете на конкретного исполнителя с учётом его возможностей. Для того, чтобы алгоритм был выполним, нельзя включать в него команды, которые исполнитель не в состоянии выполнить. Так повару нельзя поручать работу токаря, какая бы подробная информация ему не давалась. У каждого исполнителя имеется свой перечень команд, которые он может исполнить. Такой перечень называется системой команд исполнителя алгоритмов (СКИ).

^ Свойства алгоритма

  1. Дискретность – выполнение алгоритма производится строго по этапам (шагам, командам);

  2. Результативность (конечность) – выполнение алгоритма должно приводить к результатам за конечное число шагов;

  3. Правильность – алгоритм должен правильно решать задачу;

  4. Понятность – все команды алгоритма должны быть понятны исполнителю, т. е. Алгоритм составляется из команд, входящих в СКИ исполнителя;

  5. Точность (однозначность) – каждая команда алгоритма должна иметь строго одно значение;

  6. Массовость – один алгоритм должен решать блок однотипных задач (это не обязательное свойство алгоритма).

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

  • Для приготовления блюда по кулинарному рецепту нужны соответствующие продукты (данные);

  • Для решения математической задачи (решения квадратного уравнения) нужны исходные числовые данные (коэффициенты уравнения)

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

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

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

^ Способы записи алгоритмов:

  1. Запись алгоритмов на естественном языке;

  2. Графическое представление алгоритма (с помощью блоксхем);

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


Блок-схема.

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

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

Приведем наиболее часто употребляемые символы.

Название символа

Обозначение и пример заполнения

Пояснение

Процесс




Вычислительное действие или последовательность действий

Решение

http://www.mini-soft.ru/soft/vba/kart/image015.gif

Проверка условий

Модификация

http://www.mini-soft.ru/soft/vba/kart/image016.gif

Начало цикла

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

http://www.mini-soft.ru/soft/vba/kart/image017.gif

Вычисления по подпрограмме, стандартной подпрограмме

Ввод-вывод

http://www.mini-soft.ru/soft/vba/kart/image018.gif

Ввод-вывод в общем виде

Пуск-останов

http://www.mini-soft.ru/soft/vba/kart/image019.gif

Начало, конец алгоритма, вход и выход в подпрограмму

Документ

http://www.mini-soft.ru/soft/vba/kart/image020.gif

Вывод результатов на печать

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

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

Блок "модификация" используется для организации циклических конструкций. (Слово модификация означает видоизменение, преобразование). Внутри блока записывается параметр цикла, для которого указываются его начальное значение, граничное условие и шаг изменения значения параметра для каждого повторения.

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


^ Базовые алгоритмические конструкции.

Различают алгоритмы линейной, разветвляющейся, и циклической структуры, а также алгоритмы со структурой вложенных циклов.

^ Алгоритм линейной структуры. Алгоритм, в котором блоки выполняются последовательно друг за другом, в порядке, заданном схемой. Такой порядок назывется естественным.

Пример Найти по 2 точкам на плоскости расстояние между ними.


Ввести х1, у1, х2, у2. Посчитать катеты. Найти гипотенузу. Вывести ее на экран.


Задание для самостоятельного выполнения. Найти расстояние от окружности до точки на плоскости. (Вводятся х1, у1, r, х2, у2.)


Пример. Составить блок-схему алгоритма определения высот ha, hb, hc треугольника со сторонами a, b, c, если

http://www.mini-soft.ru/soft/vba/kart/image022.gif
http://www.mini-soft.ru/soft/vba/kart/image025.gif
http://www.mini-soft.ru/soft/vba/kart/image026.gif
где p = (a + b + c) / 2.
Решение. Введем обозначение http://www.mini-soft.ru/soft/vba/kart/image028.gifтогда ha = t/a, hb = t/b, hc = t/c. Блок-схема должна содержать начало, ввод a, b, c, вычисление p, t, ha, hb, hc, вывод результатов и останов.

http://www.mini-soft.ru/soft/vba/kart/image027.gif
^

Основные типы данных. Переменные. Ввод-вывод данных.


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

1. Переменные.

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

^ Тип переменной. Значениями переменных могут быть данные различных типов Тип переменной определяется типом данных, которые могут быть значениями переменной. Значениями переменных числовых типов (Integer(целое), Single(десятичное)) являются числа, логических (Boolean) — True или False, строковых (String) — последовательности символов и так далее.

Над различными типами данных (различными типами переменных) допустимы различные операции. Над числовыми переменными возможны арифметические операции, над логическими переменными — логические операции, над строковыми — операции преобразования символьных строк и так далее.

^ Имя переменной. Имя переменной определяет области памяти, в которой хранится значение переменной. Имя переменной может состоять из различных символов (латинские буквы, цифры и так далее). Оно должно обязательно начинаться с буквы и не должно включать знак «.» (точка), нельзя использовать зарезервированные слова, например «else».

^ Объявление типа переменной.

Для объявления типа переменной используется оператор определения переменной. Синтаксис этого оператора следующий:

Dim ИмяПеременной [As ТипПеременной]

Например: Dim a As Integer

С помощью одного оператора можно объявить сразу несколько переменных, например:

Dim A, B As Integer, str1 As String

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

Const T As String = «Иванов И.И.»

^ Присваивание переменным значений.

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

ИмяПеременной = Выражение

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


2. Операторы

В Visual Basic операторы бывают следующих типов:


  1. Арифметические:

    • ^ оператор возведения в степень.

    • оператор умножения.

    • / оператор деления

    • \ оператор целочисленного деления

    • Mod оператор вычисления остатка от деления

    • + оператор сложения

    • – оператор вычитания

  2. Сравнения:

    • < меньше

    • > больше

    • <= меньше или равно

    • >= больше или равно

    • = равно

    • <> не равно

  3. Конкатенации:

    • + оператор конкатенации

    • & оператор конкатенации

  4. Логические:

    • And оператор логического умножения

    • Or оператор логического сложения

    • Not оператор логического отрицания


3. Стандартные функций.

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

Общий вид записи функции - ИмяФункции(СписокАргументов )

Примеры:

VAL(«строка») – превращает строку символов в число.

STR(х) – превращает число ч в строку символов

SIN(x), COS(x), ATN(x) – синус, косинус, арктангенс, аргумент задается в радианах.

SQR(X) – корень из Х,

EXP(X) – ex.

ABS(x) – абсолютное значение x. Пример ABS(-3.2)=3,2

INT(x) – целая часть от х. Берется целое число, не превышающее х. Например 5,78 будет браться 5.

RND(x) – случайное число от 0 до 1.

LOG(number) - вычисляет натуральный логарифм числа number Для того, чтобы получить логарифм по основанию n нужно произвести следующее вычисление: Logn(x) = Log(x) / Log(n)
^

Занятие 21. Оператор присваивания. Арифметические действия с числами.


Арифметические выражения.

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

Пример:

Выражение



на языке программирования записывается, как:

((1+х)/(1-х)+(2+х)/(2-х))*(а+в)


^ 5. Правила записи чисел.

Числа с десятичной точкой записываются со знаком «точка».

Вещественные константы могут записываться в основной и экспоненциальной форме.


Например: 1,534*10-8 = 1.534E-8 1,008*105 =1.008E5

^

Графические возможности среды программирования..



Язык программирования Basic позволяет программно рисовать различные графические примитивы с использованием графических методов:

Точка с координатами 0,0 по умолчанию находится в левом верхнем углу.

Графические примитивы:

^ Pset – установка точки с заданными координатами и цветом:

Pset (X,Y) [,color]

Line – рисование линии, прямоугольника или закрашенного прямоугольника заданного цвета:

^ Line (X1,Y1) - (X2,Y2) [,color][,B][F]

Circle – рисование окружности, овала или дуги с заданными координатами центра, радиусом, цветом, начальным и конечным углом дуги и коэффициентом сжатия:

Circle (X,Y),radius [,color, start, end, aspect]

Дуга. Этот же оператор позволяет нарисовать дугу. CIRCLE (х,у),R,C, U1, U2, A

U1,U2 – начальные и конечные углы в радианах. Параметр A означает эллипс. >1 сплюснутый по горизонтали. <1 по вертикали.

^

Алгоритмическая структура «ветвление», «выбор». Решение задач на ветвление..


Алгоритмическая структура «ветвление». Примеры.

. Базовая структура ветвление. Обеспечивает в зависимости от результата проверки условия (да или нет) выбор одного из альтернативных путей работы алгоритма. Каждый из путей ведет к общему выходу, так что работа алгоритма будет продолжаться независимо от того, какой путь будет выбран.

Структура ветвление существует в четырех основных вариантах:

http://www.mini-soft.ru/kart/krug.gifесли-то;

http://www.mini-soft.ru/kart/krug.gifесли-то-иначе;

http://www.mini-soft.ru/kart/krug.gifвыбор;

http://www.mini-soft.ru/kart/krug.gifвыбор-иначе.

1) если-то

если условие

то действия

конец если

http://www.mini-soft.ru/soft/vba/kart/image030.gif

2) если-то-иначе

если условие

то действия 1

иначе действия 2

конец если

http://www.mini-soft.ru/soft/vba/kart/image031.gif

3) выбор

выбор

при условие 1: действия 1

при условие 2: действия 2

. . . . . . . . . . . .

при условие N: действия N

конец выбора

http://www.mini-soft.ru/soft/vba/kart/image032.gif

4) выбор-иначе

выбор

при условие 1: действия 1

при условие 2: действия 2

. . . . . . . . . . . .

при условие N: действия N

иначе действия N+1

конец выбора

http://www.mini-soft.ru/soft/vba/kart/image033.gif

Пример. Составить блок-схему алгоритма вычисления функции

http://www.mini-soft.ru/soft/vba/kart/image035.gifhttp://www.mini-soft.ru/soft/vba/kart/image036.gif


^

Алгоритмическая структура «Цикл»


Алгоритмы циклической структуры.

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

Для организации цикла необходимо:

  1. Задать перед циклом начальное значение переменной, изменяющейся в цикле.

  2. Изменять переменную перед каждым новым повторением цикла.

  3. Проверять условие окончания или повторения цикла;

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

Последние 3 функции выполняются многократно.

Переменная, изменяющаяся в цикле, называется параметром цикла. В одном цикле может быть несколько параметров.


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

Структура цикл существует в трех основных вариантах:

Цикл типа для.

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

Цикл типа пока.

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

Цикл типа делать - пока.

Предписывает выполнять тело цикла до тех пор, пока выполняется условие, записанное после слова пока. Условие проверяется после выполнения тела цикла.

Заметим, что циклы для и пока называют также циклами с предпроверкой условия а циклы делать - пока - циклами с постпроверкой условия. Иными словами, тела циклов для и пока могут не выполниться ни разу, если условие окончания цикла изначально не верно. Тело цикла делать - пока выполнится как минимум один раз, даже если условие окончания цикла изначально не верно.

цикл для i от i1 до i2 шаг i3

тело цикла (последовательность действий)

конец цикла

http://www.mini-soft.ru/soft/vba/kart/image037.gif

цикл пока условие

тело цикла (последовательность действий)

конец цикла

http://www.mini-soft.ru/soft/vba/kart/image038.gif

цикл делать

тело цикла (последовательность действий)

пока условие

конец цикла

http://www.mini-soft.ru/soft/vba/kart/image039.gif

Пример. Составить блок-схему алгоритма вычисления функции

yk = sin (kx) + cos (k/x), k = 1, 2, ..., 50

Пример. Составить блок-схему вычисления функции

y = a3 / (a2 + x2)

при x, изменяющимся от x = 0 до x = 3 с шагом Dx = 0,1