Logo GenDocs.ru

Поиск по сайту:  

Загрузка...

Лекция - Алгоритмизация - файл 1.doc


Лекция - Алгоритмизация
скачать (257.5 kb.)

Доступные файлы (1):

1.doc258kb.15.12.2011 16:02скачать

содержание

1.doc

Структура Данных (СД) в ЭВМ представляется в виде последовательных двоичных данных (множество связей между ними)

Простые СД – базовые, примитивные, не могут быть расчленены на составные части.

Интегрированные СД – частями к-ых являются другие СД.

СД – связные и несвязные (от наличия или отсутствия связей данных)

Изменчивость – изменение числа элементов (связей).

Простые (базовые): числовые, символьные, логические, перечисление, интервал, указатели.

Статистические: вектор, массивы, множество, записи, таблицы.

Полустатические: стек, очередь, деки, строки.

Динамические: линейные связные списки, разветвленные связные списки, графы, деревья.

Между элементами структуры не отражен факт изменения значения данных.

Вектор (одномерный массив) – СД с фиксированных числом элементов одного и того же типа.

Массив – последовательность элементов одного типа называется базовым.

Множество – набор неповторяющихся данных одного и того же типа.

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

Таблица – последовательные записи, к-ые имеют одну и ту же организацию.

Списки – упорядоченное множество, состоящее из переменного числа элементов, к к-ым применимы операции включение и выключение.

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

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

Связный список: 1. линейный (односвязные, двусвязные – (не)циклические).

2. нелинейный (двусвязные, многосвязные).

В зависимости от характера взаимного расположения СД: 1.с последовательным распределением элементов (векторы, строки, массивы, стеки, очереди), 2.с произвольным связным распределением элементов в памяти (связные и двусвязные списки).

СД в оперативной памяти: полуслово, слово, двойное слово, схема хранения (прямоугольные, связные)

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

Одно слово 8 бит – 1 байт.

Информация по каждому типу данных определяет:

  1. Структуру хранения данных указанного типа, т.е. выделения памяти и представления данных с одной стороны, а с другой – интерпретированного двоичного представления.

  2. Множество допустимых значений, к-ое может иметь тот или иной объект описанного типа.

  3. Множество допустимых операций, к-ые применимы к объектам описанного типа.

Типы данных: integer – целое короткое 4 байта, smallint – 2 байта, longint – целое нормальное, single – действительное нормальное 8 байт, boo-lean – логическое, char – символьное 1 байт, array – массив, record – запись.

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

Тип данных

Размер

Диапазон значений

Byte (байт)

1 байт

От 0 до 255.

Boolean (логический)

2 байт

True или False.

Integer (целое)

2 байт

От -32 768 до 32 767.

Long (длинное целое)

4 байт

От -2 147 483 648 до 2 147 483 647.

Single (с плавающей точкой обычной точности)

4 байт

От -3,402823E38 до -1,401298E-45 для отрицательных значений; от 1,401298E-45 до 3,402823E38 для положительных значений.

Double (с плавающей точкой двойной точности)

8 байт

От -1,79769313486232E308 до -4,94065645841247E-324 для отрицательных значений; от 4,94065645841247E-324 до 1,79769313486232E308 для положительных значений.

Currency (денежный)

8 байт

От -922 337 203 685 477,5808 до 922 337 203 685 477,5807.

Decimal (масштабируемое целое)

14 байт

+/-79 228 162 514 264 337 593 543 950 335 без дробной части; +/-7,9228162514264337593543950335 с 28 знаками справа от запятой; минимальное ненулевое значение имеет вид +/-0,0000000000000000000000000001.

Date (даты и время)

8 байт

От 1 января 100 г. до 31 декабря 9999 г.

Object (объект)

4 байт

Любой указатель объекта.

String (строка переменной длины)

10 байт + длина строки

От 0 до приблизительно 2 миллиардов.

String (строка постоянной длины)

Длина строки

От 1 до приблизительно 65 400.

Variant (числовые подтипы)

16 байт

Любое числовое значение вплоть до границ диапазона для типа Double.

Variant (строковые подтипы)

22 байт + длина строки

Как для строки (String) переменной длины.

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

Объем определяется элементами

Диапазон каждого элемента определяется его типом данных.

Поясним некоторые характерные для VBA типы данных.

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

^ Boolean - для хранения логических (булевых) значений. По умолчанию значением булевской переменной является False- ложь.

Currency - для хранения чисел с дробной частью до четырех цифр и целой частью до 15 цифр, то есть данных с фиксированной десятичной точкой, удобных для денежных вычислений. Числа с плавающей десятичной точкой (Single, Double) имеют больший диапазон значений, но могут приводить к ошибкам округления.

Decimal - в версии 5.0 поддерживается использование типа данных Decimal только в пределах типа Variant, т.е. невозможно описать переменную с типом Decimal. Пользователь, однако, имеет возможность создать переменную типа Variant с подтипом Decimal с помощью функции CDec.

Object - поскольку VBA является объектно-ориентированным языком, в нем можно манипулировать различными объектами, адреса расположения которых в памяти (указатели) имеют этот тип.

String - по умолчанию данные строкового типа имеют переменную длину и могут удлиняться или укорачиваться. Однако такие строки занимают на 10байт памяти больше, поэтому можно объявить строки фиксированной длины, чвно указав количество символов. Если количество символов будет меньше объявленного, то свободные места заполняются пробелами, при попытке занесения большего количества символов лишние отбрасываются.

Variant - может быть использован для хранения данных всех базовых типов без выполнения преобразования (приведения) типов. Применение данного типа позволяет выполнять операции, не обращая внимание на тип данных, которые они содержат. Удобен для объявления переменных, тип которых заранее неизвестен. Переменные этого типа могут содержать специальные значения: Empty, Null, Error.
Над всеми СД могут выполняться 4 операции: 1.создание (выделение памяти ), 2. уничтожение (противоположно созданию), 3. выбор/доступ ( используется программой внутри самой структуры), 3. обновление (позволяет изменить значение данных с СД).

Метод доступа – св-во СД имеет отношение к выбору конкретной СД.

Линейные СД – структуры, в к-ых связи между элементами не зависят от какого-либо условия (матрицы, множества, векторы).

Линейные СД: прямоугольные (партезианские), строчные (типа ряда), списковые.

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

Строчные: стек (последовательное включение и исключение элементов осуществляется с 1 стороны последовательности), очередь (последовательность, в к-ую включают с одной стороны, а исключают с другой), дек (последовательность, в к-ой включать и исключать элементы могут с 2х концов последовательности).

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

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

Нелинейные СД – СД, у к-ых связи между элементами зависят от определенных условий (деревья, древовидные, графы, многосвязные списки, сплетения/плексы).

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

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

Вершины, из к-ых не выходит ни 1 ребро называется листьями.

Дерево, из каждой вершины к-ого выходит только 2 ребра называется бинарным.

Графи – совокупность 2х множеств вершин и ребер.

Граф – сложная нелинейная многосвязная структура, к-ая отображает св-ва и связи сложного объекта.

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

Типичным графом является метро.

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

Сплетения = плексы – нелинейные СД, объединяющие такие понятия как деревья, графы, списковые структуры.

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

Сплетение – связь элементов, основанная на сплетении указателей.

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

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

Модель – упрощенное представление о реальном объекте, процессе или явлении.

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

Можно моделировать то, что уже есть или чего еще нет.

Типы моделирования:

Классификация по области использования:

  1. учебные (наглядные пособия, тренажеры, обучающие программы)

  2. научно-технические (создаются для исследования процессов или явлений)

  3. игровые (военные, эк., деловые игры)

  4. имитационные (отражают реальность и имитируют ее)

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

Классификация с учетом фактора времени:

  1. статические (одномоментный срез информации по объекту)

  2. динамические (позволяет увидеть изменение объекта во времени)

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

Информационные модели (знаковые, вербальные) – совокупность информации, к-ая характеризует св-во и состояние объекта, процесса, явления, а также взаимосвязь с внешним миром.

Вербальные модели – информация в мысленной и разговорной форме (идеи, рифма).

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

Классификация по способу представления:

  1. геометрические (геом. конструкции)

  2. словесные (устные писания)

  3. математические (взаимосвязь параметров объектов)

  4. структурные (схемы, графики, таблицы)

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

  6. специальные (химические формулы, ноты)
    Этапы моделирования:
    1. постановка задач (описание задач, осмысленные, направленные цели, анализ объекта моделирования)

2. разработка модели (св-ва, состояние, действия, другие св-ва объекта) Сложность модели обусловлена целью моделирования.

3. компьютерный эксперимент (тестирование, проверка правильности модели)

4. анализ результатов

5. принятие решений на основе предыдущих этапов.

если 3 и 4 не совпадают, то его моделируют заново.

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

Св-ва алгоритмов:
1. конечность = финитость (алгоритм должен приводить к результату задачи за конечное время)

  1. определенность = детерменированность ( неоднозначность записи алгоритма недопустима, только однозначность)

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

  2. результативность (доступность результата решения пользователю – возможность просматривать результат)

  3. массовость (алгоритм может быть применен для других исходных данных)

  4. эффективность/качество (должен сделаться за приемлемое для разработчика время)

Виды алгоритмов. В зависимости от цели, начальных условий, пунктов их решений, определенных действий разработчика: 1. Механические=детерменированные=жесткие – задает определенные действия, объединяет их в единую последовательность, к-ая ведет к результату. 2. Стахостические=вероятностные=гибкие – нарушение последовательности действий, результат решения задач достигается несколькими способами (эвристический), конечный результат и последовательность действий не определена, большую роль играет интуиция разработчика.

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

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

Признаком разветвляющегося алгоритма является блок проверки условия. Различают два вида условий: простые и составные. Простым условием (отношением) называется выражение составленное из двух арифметических или текстовых величин, связанных одним из знаков: <, >, <=, >=, <>. Например: x+y<7; “ma”<>”pa”. Блок проверки условия изображается ромбом, внутри которого указывается проверяемое условие, имеет один вход и два выхода: ДА, НЕТ. Если условие истинно (выполняется), то то выходим из блока по вывходу ДА, если ложно (не выполняется), то по выходу НЕТ.

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

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

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

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

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

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

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

Блок-схемы: графическое изображение алгоритма, в к-ой каждый этап процесса обработка данных представлен в виде геометрических фигур. При изображении алгоритмов, геометрические фигуры должны соответствовать гост 19.701-90 (ИСО 5807-85).

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

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

Транслятор (переводчик) – программа-переводчик, к-ая преобразует программу написанную на одном из языков высокого уровня в программу, состоящую из машинных кодов.

Транслятор представляется в виде компиляторов и интерпретаторов.

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

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

Откомпилированные программы работают быстрее, но интерпретированные проще изменить и исправить.

Каждый конкретный язык ориентирован на компилятор или интерпретатор.

Существуют программы, к-ые сначала интерпретируются, а потом откомпилируются.

Служебные слова алгоритма: алг (алгоритм), арг (аргумент), нач (начало), кон, цел, вещ, сим, лит, таб, нц, кц, длин, дано, надо, если, то, от, до, иначе, знач, все, и, пока, или, для, не, да, при, выбор, ввод, вывод, утв.

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

Характеризуются: средой, элементами действия, системой команд, отказами.

Среда – место обитания исполнителя.

Системы команд (СКИ) – строго определяют действия.

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

Отказы – если команда вызывается при недопустимой для нее цели, среды.

Команды алгоритмического языка:

  1. Команда присваивания служит для вычисления выражения и присвоения их значений переменным, где := - заменить прежнее значений переменной, стоящей в левой части на вычисление значения выражения, стоящего в правой части.

  2. Команды «если» и «выбор» применяют для организации ветвлений, команды «для», «пока» - для организации цикла.

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

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

Характерной особенностью базовых структур является наличие в них одного входа и одного выхода.

^ Базовая структура следование. Образуется из последовательности действий, следующих одно за другим:



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

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

если-то;

если-то-иначе;

выбор;

выбор-иначе.





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

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

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

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

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

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

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

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

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

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

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

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

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

^ Вложенные циклы.

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

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

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

В зависимости от степени детализации предписаний определяется уровень яз. программирования.

Чем меньше детализация, тем выше уровень языка.

машинные;

машинно-оpиентиpованные (ассемблеpы);

машинно-независимые (языки высокого уровня).

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

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

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

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

Алгоритмический язык (как и любой другой язык) образуют три его составляющие: алфавит, синтаксис и семантика.

Алфавит - это фиксированный для данного языка набор основных символов, т.е. "букв алфавита", из которых должен состоять любой текст на этом языке - никакие другие символы в тексте не допускаются. Из символов алфавита формируются лексемы языка:

константы;

идентификаторы;

знаки операций;

ключевые (служебные, иначе зарезервированные) слова;

разделители (знаки пунктуации).

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

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

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

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

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

^ Данные - величины, обрабатываемые программой. Имеется три основных вида данных: константы, переменные и массивы.

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

Числовые константы, Логические (да (истина, TRUE), нет (ложь, FALSE)), Символьные и строковые константы, литерные.

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

должны начинаться с буквы; не могут содержать точки и символов объявления типа;

не могут быть длиннее 255 символов. Длина имен объектов не должна превышать 40 символов, не могут быть ключевыми словами (именами операций, операторов, встроенных функций).

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

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

Операции. 1. арифметические операции, используемые для выполнения математических вычислений: ^, *, /, \, Mod, +, -. Здесь \ - Возвращает результат целого деления двух чисел, Mod - Возвращает остаток при целом делении двух чисел (значение по модулю).

2. операции сравнения, используемые для выполнения операций сравнения

< , > , <=, >= , = , <> ;

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

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

Выражения - предназначаются для выполнения необходимых вычислений, состоят из констант, переменных, объединенных знаками операций.

Выражения записываются в виде линейных последовательностей символов (без подстрочных и надстрочных символов.

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

2. Логические выражения описывают некоторые условия, которые могут удовлетворяться или не удовлетворяться. Таким образом, логическое выражение может принимать только два значения - "истина" или "ложь" (да или нет).

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

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

ключевые слова;

данные;

выражения и т.д.

Операторы подразделяются на исполняемые и неисполняемые. Неисполняемые операторы предназначены для описания данных и структуры программы, а исполняемые - для выполнения различных действий (например, оператор присваивания, операторы ввода и вывода, условный оператор, операторы цикла, оператор процедуры и дp.).
^

Таблица стандартных функций школьного алгоритмического языка


Название и математическое обозначение функции

Указатель функции

Абсолютная величина (модуль) 

| х | 

abs(x) 

Корень квадратный



sqrt(x)

Натуральный логарифм 

ln x

ln(x)

Десятичный логарифм 

lg x

lg(x)

Экспонента (степень числа е " 2.72)

ex

exp(x)

Знак числа x (-1,если х<0; 0,если x=0; 1,если x>0) 

sign x

sign(x)

Целая часть х (т.е. максимальное целое число,не превосходящее х)

 

int(x)

Минимум из чисел х и y

 

min(x,y)

Максимум из чисел х и y

 

max(x,y)

Частное от деления целого х на целое y

 

div(x,y)

Остаток от деления целого х на целое y

 

mod(x,y)

Случайное число в диапазоне от 0 до х-1

 

rnd(x)

Синус (угол в радианах) 

sin x

sin(x)

Косинус (угол в радианах)

cos x

cos(x)

Тангенс (угол в радианах)

tg x

tg(x)

Котангенс (угол в радианах)

ctg x

ctg(x)

Арксинус (главное значение в радианах)

arcsin x 

arcsin(x)

Арккосинус (главное значение в радианах)

arccos x

arccos(x)

Арктангенс (главное значение в радианах)

arctg x

arctg(x)

Арккотангенс (главное значение в радианах) 

arcctg x

arcctg(x)




















sin(3.05)
min(a, 5)

 sin(x)
 min(a, b)

sin(2*y+t/2)
min(a+b, a*b)

sin((exp(x)+1)**2)
min(min(a,b),min(c,d))
В качестве аргументов функций можно использовать константы, переменные и выражения. Например:
 

Каждый язык программирования имеет свой набор стандартных функций.

Арифметические выражения записываются по следующим правилам:

  • Нельзя опускать знак умножения между сомножителями и ставить рядом два знака операций.

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

  • Для обозначения переменных используются буквы латинского алфавита.

  • Операции выполняются в порядке старшинства: сначала вычисление функций, затем возведение в степень, потом умножение и деление и в последнюю очередь — сложение и вычитание.

  • ^ Операции одного старшинства выполняются слева направо. Например, a/b*c соответствует a/b*c. Однако, в школьном АЯ есть одно исключение из этого правила: операции возведения в степень выполняются справа налево. Так, выражение 2**(3**2) в школьном АЯ вычисляется как 2**(3**2) = 512. В языке QBasic аналогичное выражение 2^3^2 вычислясляется как (2^3)^2 = 64. А в языке Pascal вообще не предусмотрена операция возведения в степень, в Pascal x^y записывается как exp(y*ln(x)), а x^y^z как exp(exp(z*ln(y))*ln(x)).
^

Примеры записи арифметических выражений


Математическая запись

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



x*y/z



x/(y*z) или x/y/z



(a**3+b**3)/(b*c)



(a[i+1]+b[i-1])/(2*x*y)



(-b+sqrt(b*b-4*a*c))/(2*a)

(x<0)

sign(x)*abs(x)**(1/5)



0.49*exp(a*a-b*b)+ln(cos(a*a))**3



x/(1+x*x/(3+(2*x)**3))

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

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


Условие

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

Дробная часть вещественого числа a равна нулю

int(a) = 0

Целое число a — четное

mod(a,2) = 0

Целое число a — нечетное

mod(a,2) = 1

Целое число k кратно семи

mod(a,7) = 0

Каждое из чисел a,b положительно

(a>0) и (b>0)

Только одно из чисел a,b положительно

((a>0) и (b<=0)) или
((a<=0) и (b>0))

Хотя бы одно из чисел a,b,c является отрицательным

(a<0) или (b<0) или (c<0)

Число x удовлетворяет условию a<x<b 

(x>a) и (x<b)

Число x имеет значение в промежутке [1, 3]

(x>=1) и (x<=3)

Целые числа a и b имеют одинаковую четность

((mod(a,2)=0) и (mod(b,2)=0) или
((mod(a,2)=1) и (mod(b,2)=1))

Точка с координатами (x,y) лежит в круге радиуса r с центром в точке (a,b)

(x-a)**2+(y-b)**2<r*r

Уравнение ax^2+bx+c=0 не имеет действительных корней

b*b-4*a*c<0

Точка (x,y) принадлежит первому или третьему квадранту

((x>0) и (y>0)) или
((x<0) и (y>0))

Точка (x,y) принндлежит внешности единичного круга с центром в начале координат или его второй четверти

(x*x+y*y>1) или
((x*x+y*y<=1) и
(x<0) и (y>0))

Целые числа a и b являются взаимнопротивоположными

a = -b

Целые числа a и b являются взаимнообратными

a*b = 1

Число a больше среднего арифметического чисел b,c,d

a>(b+c+d)/3

Число a не меньше среднего геометрического чисел b,c,d

a>=(b+c+d)**(1/3)

Хотя бы одна из логических переменных F1 и F2 имеет значение да

F1 или F2

Обе логические переменые F1 и F2 имеют значение да

F1 и F2

Обе логические переменые F1 и F2 имеют значение нет

не F1 и не F2

Логическая переменная F1 имеет значение да, а логическая переменная F2 имеет значение нет

F1 и не F2

Только одна из логических переменных F1 и F2 имеет значение да

(F1 и не F2) или
(F2 и не F1)

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

  1. Постановка задачи:

    • сбоp инфоpмации о задаче;

    • фоpмулиpовка условия задачи;

    • опpеделение конечных целей pешения задачи;

    • определение формы выдачи результатов;

    • описание данных (их типов, диапазонов величин, структуры и т.п. ).

  2. Анализ и исследование задачи, модели:

    • анализ существующих аналогов;

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

    • pазpаботка математической модели;

    • разработка структур данных.

  3. Разработка алгоритма:

    • выбор метода проектирования алгоритма;

    • выбор формы записи алгоритма (блок-схемы, псевдокод и др.);

    • выбоp тестов и метода тестиpования;

    • проектирование алгоритма.

  4. Пpогpаммиpование:

    • выбор языка программирования;

    • уточнение способов организации данных;

    • запись алгоpитма на выбpанном языке пpогpаммиpования.

  5. Тестиpование и отладка:

    • синтаксическая отладка;

    • отладка семантики и логической стpуктуpы;

    • тестовые pасчеты и анализ pезультатов тестиpования;

    • совершенствование пpогpаммы.

  6. Анализ результатов решения задачи и уточнение в случае необходимости математической модели с повторным выполнением этапов 2 - 5.

  7. Сопровождение программы:

    • доработка программы для решения конкретных задач;

    • составление документации к pешенной задаче, к математической модели, к алгоpитму, к пpогpамме, к набору тестов, к использованию.

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

создавая математическую модель для решения задачи, нужно:

  1. выделить предположения, на которых будет основываться математическая модель;

  2. определить, что считать исходными данными и результатами;

  3. записать математические соотношения, связывающие результаты с исходными данными.

Разработка программы = изготовление + доказательство правильности.

Текст программы можно проконтролировать за столом с помощью просмотра, проверки и прокрутки.

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

  • Проверка. При проверке программы программист по тексту программы мысленно старается восстановить тот вычислительный процесс, который определяет программа, после чего сверяет его с требуемым процессом. На время проверки нужно "забыть", что должна делать программа , и "узнавать" об этом по ходу её проверки. Только после окончания проверки программы можно "вспомнить" о том, что она должна делать и сравнить реальные действия программы с требуемыми.

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

Отладка программы — это процесс поиска и устранения ошибок в программе, производимый по результатам её прогона на компьютере.

Тестирование — это испытание, проверка правильности работы программы в целом, либо её составных частей.

  • при отладке происходит локализация и устранение синтаксических ошибок и явных ошибок кодирования;

  • в процессе же тестирования проверяется работоспособность программы, не содержащей явных ошибок.

Программа-отладчик обычно обеспечивает следующие возможности:

  • пошаговое исполнение программы с остановкой после каждой команды (оператора);

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

  • установку в программе "контрольных точек", т.е. точек, в которых программа временно прекращает свое выполнение, так что можно оценить промежуточные результаты, и др.

При отладке программ важно помнить следующее:

  • в начале процесса отладки надо использовать простые тестовые данные;

  • возникающие затруднения следует четко разделять и устранять строго поочередно;

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

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

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

тестирование может показать лишь наличие ошибок, но не их отсутствие.

Для реализации метода тестов должны быть изготовлены или заранее известны эталонные результаты.

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

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

  • должна быть испытана каждая ветвь алгоритма;

  • очередной тестовый прогон должен контролировать нечто такое, что еще не было проверено на предыдущих прогонах;

  • первый тест должен быть максимально прост, чтобы проверить, работает ли программа вообще;

  • арифметические операции в тестах должны предельно упрощаться для уменьшения объема вычислений;

  • количества элементов последовательностей, точность для итерационных вычислений, количество проходов цикла в тестовых примерах должны задаваться из соображений сокращения объема вычислений;

  • минимизация вычислений не должна снижать надежности контроля;

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

  • усложнение тестовых данных должно происходить постепенно.

Процесс тестирования можно разделить на три этапа.

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

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

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

^ Вид ошибки

Пример

Неправильная постановка задачи

Правильное решение неверно сформулированной задачи

Неверный алгоритм

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

Ошибка анализа

Неполный учет ситуаций, которые могут возникнуть; логические ошибки

Семантические ошибки

Непонимание порядка выполнения оператора

Синтаксические ошибки

Нарушение правил, определяемых языком программирования

Ошибки при выполнении операций

Слишком большое число, деление на ноль, извлечение квадратного корня из отрицательного числа и т. п.

Ошибки в данных

Неудачное определение возможного диапазона изменения данных

Опечатки

Перепутаны близкие по написанию символы, например, цифра 1 и буквы I, l

Ошибки ввода-вывода

Неверное считывание входных данных, неверное задание форматов данных

Примеры синтаксических ошибок:

  • пропуск знака пунктуации;

  • несогласованность скобок;

  • неправильное формирование оператора;

  • неверное образование имен переменных;

  • неверное написание служебных слов;

  • отсутствие условий окончания цикла;

  • отсутствие описания массива и т.п.

Существует множество ошибок, которые транслятор выявить не в состоянии, если используемые в программе операторы сформированы верно.

Примеры таких ошибок.

Логические ошибки:

  • неверное указание ветви алгоритма после проверки некоторого условия;

  • неполный учет возможных условий;

  • пропуск в программе одного или более блоков алгоритма.

Ошибки в циклах:

  • неправильное указание начала цикла;

  • неправильное указание условий окончания цикла;

  • неправильное указание числа повторений цикла;

  • бесконечный цикл.

Ошибки ввода-вывода; ошибки при работе с данными:

  • неправильное задание тип данных;

  • организация считывания меньшего или большего объёма данных, чем требуется;

  • неправильное редактирование данных.

Ошибки в использовании переменных:

  • использование переменных без указания их начальных значений;

  • ошибочное указание одной переменной вместо другой.

Ошибки при работе с массивами:

  • массивы предварительно не обнулены;

  • массивы неправильно описаны;

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

Ошибки арифметических операций:

  • неверное указание типа переменной (например, целочисленного вместо вещественного);

  • неверное определение порядка действий;

  • деление на нуль;

  • извлечение квадратного корня из отрицательного числа;

  • потеря значащих разрядов числа.

Эти ошибки обнаруживаются с помощью тестирования.

Сопровождение программ — это работы, связанные с обслуживанием программ в процессе их эксплуатации.

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

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

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

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

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

Оператор с предусловием можно заменить на оператор с постусловием. Сложнее заменить оператор с параметром на оператор с постусловием.


Скачать файл (257.5 kb.)

Поиск по сайту:  

© gendocs.ru
При копировании укажите ссылку.
обратиться к администрации