Алгоритмизации и программирования Текст Лекций на языках Pascal, VBA, C ++


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

 тексты лекций

В текстах лекций рассмотрены основы алгоритмизации процедур обработки экономической информации и вопросы программирования таких процедур на языках Pascal, VBA, C ++. Курс имеет целью сформировать научно обоснованные взгляды на современные технологии в информатике, выработать практические навыки по программированию экономических задач.

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

Курс «Алгоритмизация и программирование» по программе изучается студентами специальности «Экономическая кибернетика» на втором курсе. Количество лекционных занятий составляет 17 часов. Дисциплина «Алгоритмизация и программирование» опирается на знания, приобретенные в курсе «Информатика и компьютерная техника» и предшествует предметам «Технология программирование «,

«Объектно-ориентированное программирование».

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

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

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

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

В текстах лекций автор пытается убедить читателя в том, что различные языки программирования имеют между собой больше общего, чем различий. С этой позиции рассматриваются только основные конструкции языков Pascal, C ++ и VBA и оказывается общее между ними. С этой же точки зрения в данных лекциях не рассматриваются такие системы как Delphi, Borland C ++ Builder и др. Изучение этих систем является целью других дисциплин.

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

Материал лекций может быть полезен также студентам других экономических специальностей и студентам специальности «Прикладная математика».

 

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

 

1.1.Теоретические основы алгоритмизации

1.1.1. Принципиальные возможности алгоритмизации и компьютерной техники

 

Первая в мире электронно-вычислительная машина (ЭВМ) была создана в 1946 году в США группой ученых под руководством Дж. Фон Неймана. Ее работа основана на четырех основных принципах:

— принцип двийковости.Как информационная часть (числа, текст), так и управляющая (команды) представляются на машинном уровне в двоичной системе;

— принцип адресности.Все действия выполняются над содержанием определенных адресов.

Команды также размещены по адресам;

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

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

Эти принципы до сих пор называют принципами Неймана. Хотя основные идеи построения и функционирования ЭВМ были выдвинуты еще в 1890-х годах английским ученым Ч. Бэббиджем. В 1930-х годах были сформулированы (А.Тьюринг и др.) Принципы информатики, которые четко определяли возможности будущих ЭВМ. Итак, приступая в конце второй мировой войны к созданию первой ЭВМ, ученые четко осознавали возможности этого будущего для них техники.В частности, один из основных принципов информатики утверждает:

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

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

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

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

Теорема Райса (Rice). Не существует алгоритма (в принципе), который по тексту программы и по входных данных смог бы установить, состоится зацикливание.

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

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

Алгоритм, его свойства

Под алгоритмом понимают конечную систему правил для решения определенного класса задач, которая удовлетворяет следующим свойствам:

— массовость.Алгоритм — это не нахождение решения одной конкретной задачи, а единственный способ для решения класса задач. Как правило, множество входных данных алгоритма является бесконечной;

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

— детерминированность.Кто бы ни выполнял алгоритм и если бы его не выполнял, он при одних и тех же входных данных всегда должен получать тот же результат.

Последнее свойство выражает основную суть алгоритма: исполнитель может не понимать смысла. Он должен лишь верно выполнять предложенную ему последовательность действий.

Рассматривают три основных способа задания алгоритмов:

— вербальный (словесный)

— с помощью блок-схем;

— с помощью программы на алгоритмическом языке.

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

Как утверждает принцип информатики, для записи любого алгоритма достаточно наличия арифметических команд, операции ветвления и операции пересылки. Все алгоритмические языки (BASIC, PASCAL, C ++ и т.д.) эти операции включают. Итак, с позиции универсальности все языки программирования равномощны. Однако с позиции реального написания и отладки программ очень существенной является и методика написания этих программ.

Основная трудность при разработке больших программ (как и любой интеллектуальной деятельности) заключается в том, что человек не может одновременно держать в голове больше, чем 7 ± 2 объекта.Итак, блок-схему программы по 10 и более блоками уже невозможно понять. Мастерство программиста (как и писателя, ученого) состоит в умении разбить одну большую задачу на ряд простых, которые можно решать независимо во времени (или одновременно разными людьми). В частности, желательно так строить блок-схему (или текст программы), чтобы в каждый момент времени концентрировать свое внимание на небольшом фрагменте блок схемы (не более 7 блоков) или программы.

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

Теоретической основой применения структурного программирования является Теорема Бома-Джакопини.

Для того чтобы составить блок-схему произвольного алгоритма, достаточно трех конструкций: составного оператора типа BEGIN_END, оператора ветвления типа IF_THEN_ELSE и оператора цикла типа WHILE_DO:

 

 

 

∙ ∙ ∙ ∙ ∙ ∙ ∙

 

begin оператор … if условие then оператор while условие

…; оператор end else оператор do оператор

Для удобства на практике используют еще три следующие конструкции:

 

 

If условие Case выражение Of FOR переменная = начальное
Then оператор 1: оператор; значение
  . . . . . . . To конечное значение
  n: оператор Do оператор
  end  

Структурное программирование рекомендует:

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

2. Не использовать никаких других управляющих конструкций (в частности, оператора безусловного перехода GOTO).

Ряд систем программирования (PASCAL, C ++, школьная алгоритмический язык) имеют операторы, отвечающие всем шести конструкциям. Итак, в этих системах естественно использовать структурное программирование. Структурные программы намного понятнее и нагляднее, чем неструктурные. Большие программные разработки можно выполнить только с помощью технологии структурного программирования.

Некоторые системы, например, FOXPRO вообще не имеют оператора GOTO. На них, следовательно, можно писать только структурные программы.

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

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

 

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

Таким образом программы одного и того же алгоритма будут похожими на себя независимо от языка программирования.

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

 

Пример.Заданная матрица A = (a ij) i = 1, …, 3; j = 1, …, 4.На языке PASCAL составить программу, которая находит наибольший элемент во второй строке этой матрицы.

Program P; Uses Crt;

Const m = 3; n = 4; Var

A: array [1..n, 1..m] of real; max: real; i, j: integer;

Begin

Clrscr;

{Ввод входных данных} For i: = 1 to n do

For j = 1 to m do Begin

GoToXY (2 + i, j * 20-18) Write ( ‘a (‘, i: 1, ‘,’, j: 1, ‘) =’); Read (a [I, j])

End; max = a [2,1]; For j = 2 to n do

If A [2, j]> max then max = A [2, j]; Writeln;

Writeln ( ‘наибольший элемент второй строки равна’, max: 6: 2) Repeat Until KeyPressed

End.

В программе P реализовано вывода результата на экран и ввода исходных данных с клавиатуры с помощью модуля Crt.Конструкция GoToXY (i, j) устанавливает курсор на i-ю позицию j-ой строки. Тело цикла Repeat Until KeyPressed состоит только из пустого оператора. Таким образом этот цикл выполняет остановку работы программы до тех пор, пока не будет нажата произвольная клавиша.

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

Блок-схема алгоритма (независимо от того, этот алгоритм был реализован средствами языка PASCAL, C ++ или VBA) такова:

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

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

Грамматический анализ PASCAL-программы P таков:

 

For i: = 1 to n do оператор If условие Then оператор

 

max = A [2, j]

 

For j = 1 to m do оператор

Begin GoToXY Write Read End

И, наконец, выполним прокрутку этой программы для таких входных данных:

 

A [1,1] = 4 A [1,2] = 2 A [1,3] = 2 A [1,4] = 1
A [2,1] = 1 A [2,2] = 3 A [2,3] = 4 A [2,4] = 3
A [3,1] = 2 A [3,2] = 2 A [3,3] = 5 A [3,4] = 1

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

Имеем (согласно блок-схемы) следующие действия

max = 1 j = 2

A 22> max?(3> 1?) так

max = 3 j <4? Так j = 3

A 23> max?(4> 3?) так

max = 4 j <4? Так j = 4

A 24> max?(3> 4?) ни

j <4? ни

Вывод результата max = 4

 

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

Программист также не выполняет на бумаге грамматический анализ и прокрутку.Он выполняет все эти действия «в уме», часто на уровне подсознания.

Каждый человек в своей деятельности допускает описания. Так, машинистка высокой квалификации имеет право допустить две описки на страницу. Квалифицированный программист делает в среднем одну описку на 25 — 50 операторов. Конечный программный продукт, однако, не имеет права содержать этих описок.

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

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

1.2.Основные конструкции языка PASCAL

1.2.1. Типы данных в языке PASCAL

 

Общая структура PASCAL-программы такова: Заголовок (Program имя программы)

Раздел модулей (Uses) раздел меток (Label) раздел констант (Const) раздел типов (Type)

Раздел описаний переменных (Var)

Раздел процедур и функций (Procedure, Function)

Раздел операторов (Begin операторы, которые разделяются символом «,» End.) Некоторые из этих разделов можно переставлять местами.

С каждой переменной программы связан определенный тип. Тип переменной задает

— размер памяти, занимает эта переменная;

— способ машинного представления этой переменной

— множество допустимых значений этой переменной

— набор допустимых операций над переменной.

В языке Pascal все переменные должны быть описаны в разделе Var. Основными арифметическими типами данных в языке Pascal являются:

 

Тип переменной ключевое слово диапазон значений Объем памяти, байт
Длинное целое число longint -2147483648 ..

2147483647

4
целое число integer -32768 .. 32767 2
Короткое целое число shortint -128 .. 127 1
действительное число real -2,9 * 10 -39 ..

1,7 * 10 38

6
Сокращенное действительное число single 1,5 * 10 -45 ..

3,4 * 10308

4

Над целыми и действительными числами выполняют арифметические операции и операции сравнения <,>, <=,> =, <> =. Функция round выполняет закругления действительного числа до ближайшего целого. Функция trunс осуществляет отбрасывания дробной части числа.

Описание переменных логического типа имеет вид Var

переменная, переменная: Boolean;

Логические переменные (высказывания) могут принимать одно из двух значений: True (истинное) или False (ложно). Над логическими переменными в языке Pascal выполняются три операции:

— And (конъюнкция, логическое умножение, логическое «И»)

— Or (дизъюнкция, логическое сложение, логическое «Или»)

— Not (отрицание).

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

Описание строчной (стрингов, текстового) типа задаются так:

Var

переменная: String [длина строки];

 

Значение символьных и строковых переменных берутся в одинарные кавычки: «a», «+», «информатика».Над строковыми переменными можно выполнять операции присваивания, ввода и вывода (R1 = R2; read (R1) write (R2)).Доступ к отдельному символу строки R осуществляется с помощью квадратных скобок: R [i].

Над переменным строчной типа можно выполнять операцию приписывания (R = ‘Эки’ + ’21’).

Пример. Const

N = 10;

Pi = 3,141592; {Комментарий: тип константы определяется ее видом}

Var

a, b, c: Real; x1, x1: Real; k: integer; S, S1, S2: string;

С: char;

b1, b2: Boolean; Begin

. . . . . . . . . . . . . . . . . . . c = a + k; S = S1 + ‘_’ + S2; C = S [3];

b1 = (a <b) and (b <c) End.

1.2.2. Основные управляющие операторы в языке PASCAL

 

Оператор присваивания в языке PASCAL имеет вид: имя переменной = выражение

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

Схемы операторов ввода с клавиатуры и вывода на экран следующие:

 

write (переменная,…, переменная)

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

Пример. Вычисления площади треугольника по формуле Герона. Program P1;

Var

a, b, c, p, s: real;

{Вычисление площади треугольника по трем сторонам} Begin

Writeln;

Writeln ( ‘введите длины сторон треугольника:’); read (a, b, c)

p = (a + b + c) / 2; s = Sqrt (p * (pa) * (pb) * (pc)) write ( ‘площадь треугольника со сторонами’); writeln (a: 5, 2, b: 5: 2, c 5: 2, ‘равно’, s: 6: 2) End.

Общий вид оператора вывода Write имеет вид: Write (x: n) или Write (x: n: m)

Этот оператор очень просто реализует отформатировано вывода. Параметр n указывает на количество позиций на экране, которые будут отведены под переменную x, а параметр m — на количество дробных цифр в настоящем числе.При необходимости текст (строчная переменная) дополняется пробелами справа, а число — пробелами слева.

Оператор Writeln осуществляет переход на новую строку, а оператор Writeln (сменные) сначала осуществляет вывод указанных переменных и затем выполняет переход на новую строку.

Основными управляющими операторами являются:

— составной оператор (begin_end)

— операторы ветвления (if_then и if_then_else )

— оператор варианта (множественного выбора, case_of)

— операторы цикла (For, While и Repeat )

Группа операторов внутри операторных скобок begin_end рассматривается языке PASCAL как один оператор — составной оператор.

Операторы ветвления (условные операторы) имеют следующий вид: If условие Then оператор

If условие Then оператор_1 Else оператор_2

Пример.При 0 <a <5 вычислить x = 1 и y = 2, иначе вычислить z = 3 и t = 4. if a> 0 and a <5 then

begin

x = 1; y = 2

 

else

end

 

begin z = 3; t = 4 end

 

Синтаксис оператора варианта таков:

Case выражение of

вариант_1: оператор_1; вариант_2: оператор_2;

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

вариант_n: оператор_n else оператор_n + 1

end

 

Пример.Case k of

1,2: write ( ‘не аттестован’);

3,4,5: write ( ‘аттестован’) else

write ( ‘неверная оценка’)

end

 

Конструкция else в операторе Case является необязательной.

Различают операторы цикла трех типов: For, While и Repeat. Схема оператора While такова:

While условие (логическое выражение) Do оператор

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

Пример.Вычислить с заданной точностью ε значение y = sin (x) по формуле

Y x   x

3!

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

read (x, eps)

x … ( 1) n 5!

x 2 n 1

 

(2 n 1)!

y = x; u = x; r = — x * x; i = 2; while abs (u)> eps do begin

u = (u * r) / (i * (i + 1)); y = y + u;

i = i + 2 end;

Для лучшего понимания рекомендуется выполнить прокрутку этой программы.

Синтаксис оператора цикла Repeat таков:

Repeat оператор …; оператор Until условие (логическое выражение)

Группа операторов в теле цикла выполняется до тех пор, пока условие еще не стала истиной.

Пример.Вычислить по формуле в предыдущем примере значение y = sin (x). Использовать оператор Repeat.

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

read (x, eps)

y = x; u = x; r = — x * x; i = 2;

Repeat

u = (u * r) / (i * (i + 1)); y = y + u;

i = i + 2

Until abs (u) <eps;

Определение оператора For (цикла с параметром, цикла с заранее известным количеством повторений) таков:

For переменная = начальное значение To конечное значение Do оператор

n 1

Пример.вычислить Y               i 2 .

i 1

…; y = 0; For i: = 1 to n-1 do y = y + i * i; …

Произвольный алгоритм всегда можно реализовать при помощи только рассмотренных выше управляющих конструкций. При этом рекомендуется использовать структурное программирование [7]. По этой причине оператор GOTO <метка> и раздел Label в данных указаниях не рассматриваются.

Общая схема описания переменных регулярного типа (массивов, переменных типа array) в языке PASCAL такова:

Type имя типа = Array [тип индексов] of тип компонент

Например, вектор (одномерный массив) A = (a 1, …, a n) можно описать одним из двух способов:

Type

T1 = array [1..n] of real; Var A: T1;

или

Var A: array [1..n] of real;

 

Здесь типу индексов является множество целых чисел в диапазоне от 1 до n.

Отдельные элементы массива A именуются так: A [1], …, A [i-2], …, A [n]. Действия возможны лишь с отдельными элементами массива.

Пример.Найти количество и сумму положительных элементов вектора A = (a 1, …, a 100).

Var

A: array [1..10] of real; s: real; k, i: integer; Begin

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

k = 0; s: = 0;

For i: = 1 to 100 do

If a [i]> 0 then

begin k: = k + 1; s = s + a [i] end

End.

1.2.3. Процедуры и функции в языке PASCAL

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

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

В языке PASCAL описание процедуры выглядит следующим образом: Procedure имья_процедуры (описания формальных параметров)

Var описания локальных переменных

Begin

операторы (тело процедуры) End;

Оператор процедуры таков:

имья_процедуры (перечень фактических параметров)

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

Еще более мощным средством, чем механизм замены формальных параметров на фактические механизм реализации локальных переменных.

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

Пример.Разработать процедуру m2 нахождения большего числа среди двух заданных. Написать программу m3 нахождения наибольшего числа среди трех заданных чисел, используя процедуру m2.

Введем обозначения для переменных. Аргументами программы m3 будут три числа, для которых выбираем символические имена x, y и z.Результатом программы m3 будет переменная m.Программа будет использовать вспомогательную переменную r.

Аргументы процедуры m2 обозначим через a и b, а результат через c.Процедура также будет использовать локальную (внутреннюю) переменную x (коллизии с переменной x в программе m3 НЕ возникнет).

Program m3;

Var

x, y, z: real; m: real; {Аргументы и результат} r: real; {Вспомогательная переменная}

Procedure m2 (a, b: real; var c: real)

var x: real; {локальная для процедуры переменная} begin

if a> b then x = a

else x = b;

c = x end;

Begin

Writeln ( ‘Введите три числа’); Read (x, y, z)

m2 (x, y, r)

m2 (r, z, m)

writeln ( ‘наибольшее число =’, m: 8: 2) End.

Описания формальных параметров a, b: real; var c: real выполнены иначе для параметров a и b и иначе для параметра c.Это связано с тем, что переменные a и b — это параметры- значения (замена этих формальных параметров на фактические происходит посредством присвоения значений).В то же время c — параметр- переменная (замена этого параметра на соответствующий фактический происходит заменой имени переменной).

Во время выполнения (во время разговора) первого из операторов процедуры m2 (x, y, r) состоятся следующие действия:

a = x; b = y (происходит присвоение значений) появляется локальная для процедуры переменная x выполняются операторы

if a> b then x = a

else x = b;

r = x (происходит замена имени c на r ) Локальная переменная x прекращает существование

В том случае, когда результатом работы процедуры является только одна переменная, то вместо конструкции Procedure часто используют конструкцию Function. Описание функции имеет вид:

Function имя_функции (описания формальных параметров): тип результата; Var описания локальных переменных

Begin

операторы (тело функции) End;

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

имя_функции (перечень фактических параметров)

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

Пример.Разработать функцию f2 нахождения большего числа среди двух заданных. Написать программу mm3 нахождения наибольшего числа среди трех заданных чисел, используя функцию f2.

Program mm3;

Var

x, y, z: real; m: real; {аргументы и результат} Function f2 (a, b: real): real;

var x: real; {локальная переменная} begin

if a> b then x = a else x = b; f2 = x

end;

Begin

Writeln ( ‘Введите три числа’) Read (x, y, z) m = f2 (f2 (x, y), z)

writeln ( ‘наибольшее число =’, m: 8: 2) End.

Наборы процедур и функций в языке Pascal объединяются в модули. Например, подключив в разделе Uses модуль Crt, программист получает возможность использовать такие стандартные процедуры, как ClrScr — очистка экрана и GoToXY (x, y) — установление курсора на позицию x в строке y.

Рассмотрим еще один тип данных — комбинированный тип, (запись, тип record). Описание переменной типа record таков:

имя: Record переменная: тип, …; переменная: тип End Пример.

x1, x2: record

Name: string; Price: real;

Qty: integer end

Доступ к отдельным элементам записи осуществляется через символ «.»: X1.name:=’телевізор ‘; x2.Qty = x1.Qty + 12;

 

1.2.4. Файлы в языке PASCAL

Наборы записей одинаковой структуры образуют последовательные файлы (файлы типа record):

Type

Zap = record Name: string; Price: real; Qty: integer end;

Var

 

 

Var

F: file of Zap; или

 

F: file of record Name: string; Price: real; Qty: integer end;

 

Над файлами типа record выполняются такие операции (процедуры):

Assign (F, ‘путь к набору данных «) — связывает символьное имя F в программе по конкретным набором данных на внешнем носителе;

Reset (F) и Rewrite (F) — подготавливают файл к чтению (до записи) с его начала; указатель устанавливается на начало файла;

Read (F, x) — считывает в оперативную память x та запись файла F, на который установлен указатель; указатель при этом передвигается на одну запись далее;

Write (F, x) — записывает одну запись из памяти по адресу x в конец файла F;

Функция EOF (F) распознает, указатель достиг конца файла. Процедура Seek (F, k) устанавливает указатель на k-й запись файла F.

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

Program Pr3;

Type Z = record Name: string; Price: real; Qty: integer end; Var F: file of z; x: z; .S; real;

Begin

Assign (f, ‘C: \ f.dat’); reset (F) S: = 0;

while not eof (F) do begin

read (F, x)

S = S + x.Price * x.Qty end;

Writeln ( ‘Стоимость =’, s: 8: 2) End.

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

В языке PASCAL существуют файлы, которые не делятся записи: текстовые файлы (описание: file of text или text). Все переменные (даже числа) текстового файла представлены в символьном виде. Поэтому операторы считывания и записи в такой файл перечисляют все необходимые переменные. Преимущество текстового файла заключается в том, что его можно просматривать простейшими редакторами.

Program Pr4;

Var F: file of text; Name: string; Price: real; Qty: integer; S: real; Begin

Assign (f, ‘C: \ f.dat’); reset (F) S: = 0;

while not eof (F) do begin

read (F, Name, Price, Qty)

S = S + Price * Qty end;

Writeln ( ‘Стоимость =’, s: 8: 2) End.

1.3.Основные конструкции языка VBA

 

1.3.1. Типы данных в языке VBA

Язык Visual Basic for Application (VBA) широко применяется в среде Microsoft Office.

Арифметические типы данных языка VBA представим таблицей:

 

Тип переменной ключевое слово диапазон значений Объем памяти, байт
Длинное целое число long -2147483648 ..

2147483647

4
целое число integer -32768 .. 32767 2
действительное число single -1,4 * 10 -45 ..

3,4 * 10 38

4
Действительное число двойной точности double -4,9 * 10 -324 ..

1,7 * 10308

8

Текстовые (символьные) строки задаются, как и в языке PASCAL, конструкцией string.

Описание типа данных в VBA таков: DIM имя переменной As тип переменной

Если некоторое значение не должно в процессе выполнения программы меняться, то его объявляют как константу оператором Const:

Пример.

Const n = 10

Const pi = 3.141592 DIM a1, a2 as single DIM i, j as integer,

z, x, y as double DIM S, S1, S2 as string

Над целыми и действительными типами речь VBA позволяет выполнять арифметические действия. Над переменным типа string можно выполнять операцию & (сцепление, конкатенации, приписывание). Пусть S1 = «бан» и S2 = «ка» Тогда результатом операции S1 & S2 будет строка (последовательность символов) «банка», а результатом операции S2 & S1 — «кабан».

В языке VBA существует два способа задания массивов:

DIM имя переменной (Nmax) As тип элементов и

DIM имя переменной (Nmin to Nmax) As тип элементов

 

Пример.

Dim a (5) as single

Dim m (1 to 3, 1 to 4) as single

В первом случае задан вектор (одномерный массив) с элементами a (o), a (1), a (2), a (3), a (4).

Во втором случае описано двумерный массив (матрицу) с элементами m (1,1), …, m (3,4).

Язык VBA позволяет использовать также динамические массивы. Количество элементов такого массива заранее неизвестна (например, количество отличников на факультете):

DIM A () as string

После того, как программным путем это количество отличников найдена (например, в переменной n), то дальше с помощью оператора ReDim можно задать конкретные размеры этого массива:

ReDim A (n)

 

1.3.2. Основные управляющие операторы в языке VBA

Вместо символа «=» в языке PASCAL оператор присваивания в языке VBA использует символ «=».

Простейшие операторы ввода и вывода (в текстовом режиме) имеют следующий вид:

Cls — очистка экрана;

Locate i, j — установить курсор на j-ю позицию i-го строки;

Input переменная — введение конкретного значения переменной с клавиатуры; Print переменная; переменная ; переменная — вывод значений переменных на экран.

Как и во всех других языках, речь VBA имеет два типа оператора ветвления (условного оператора):

If условие Then

операторы End if

и

If условие Then

Оператори_1 Else

Оператори_2 End if

Пример. Если x> 3, то вычислить a = a + 1 и b = 2, иначе вычислить a = a + 3 и c = 4.

If x> 3 then a = a + 1 b = 2

Else

a = a + 3 c = 4

Endif

 

Оператор цикла типа For имеет такой синтаксис:

 

For счетчик = начальное_значение To кинцеве_значення [Step шаг] операторы

Next счетчик

 

Конструкция [Step шаг] при этом необязательно.

Пример.Найти сумму a (n + 3) + a (n + 5) + … + a (n + 13) Dim A (1 to n + 20) as single

Dim i as integer

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

S = 0

For i = n + 3 to n + 13 step 2 S = s + a (i)

Next i

Print «s =»; s

 

Пример.Найти количество элементов вектора A = (a 1, …, a 4), которые превышают значения 2,5.

REM «Это комментарий ‘Const n = 4

Dim A (1 to n) as single Dim i as integer, k as integer Cls

Locate 2,8

Print «Программа на VBA» For i = 1 to n

Locate 4, i * 15 Print «a («; i; «) =» Locate 4, i * 15 + 8 Input a (i)

Next ik = 0

For i = 1 to n step 1

if a (i)> 2,5 then k = k + 1

End if Locate 6,8

Print «количество элементов, которые являются большими, чем 2,5 равно»; k

Один из операторов цикла с условием имеет такой синтаксис:

While условие операторы

Wend

Пример.Решить предыдущую задачу с помощью оператора While:

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

k = 0 i = 1

While i <= n

if a (i)> 2,5 then k = k + 1

end if

i = i + 1

Wend

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

1.3.3. Использование VBA в сиcтемах EXCEL

 

Экономист в своей практике постоянно работает со стандартными приложениями системы Windows — Word, Excel, Access. Последние две системы имеют достаточно мощные средства для обработки экономической информации. Однако всегда возникают ситуации, когда одними встроенными функциями системы Excel или Access решить задачу невозможно. В таких случаях пользователь (самостоятельно или с помощью программиста) должен создать макрос (программу на языке VBA).

Пример.В системе Excel задана таблица

 

 

1

2

. . . 28

29

30

Записать в ячейку C30 средний балл по макроэкономике среди студентов, получивших «3» по математике.

Ответ на этот запрос можно получить, записав в C30 достаточно сложную формулу = Sumif (E2: E28,3, F2: F28) / countif (E2: E28,3) .

Однако есть также возможность построить макрос (Tools, Macro, Macros, имя макроса, Step Into и записать VBA-процедуру) с использованием операторов For и if материалы Cells (i, j) — ячейки на пересечении i-ого строки и j -ого столбца:

Sub mm1 ()

S = 0

k = 0

For i = 3 to 28

if Cells (i, 5) = 3 then S = S + Cells (i, 6)

End if Next i

Cells (30,3) = S / k End sub

Отметим, что сложные запросы (студенты, которые сдавали только макроэкономику; группы, где нет «двоек» по математике и т.д.) можно выполнить в Excel (а также в Access) только с помощью языка VBA.

1.4. Основные конструкции языка C ++

1.4.1. Понятие о языке С ++

В настоящее время речь С ++ является самым распространенным языком программирования. Большая часть системного и прикладного программного обеспечения разрабатывается на этом языке. Язык С ++ в противовес языке PASCAL позволяет писать очень эффективные программы по токи зрения использования машинных ресурсов. Однако данный язык значительно сложнее для изучения, чем такие языки, как Pascal и VBA. Кроме того, терминология языка С ++ часто является весьма специфической.

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

void main ()

{

// тело программы

} / * Конец программы * /

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

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

Комментарии или помещаются в скобки типа / * * /, или начинаются символами //.

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

Описания переменных и операторы записываются в произвольном порядке.

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

В частности, подключив (директивой #include) файл iostream.h, мы получаем возможность использовать функцию ввода с клавиатуры

cin >> переменная … >> переменная и функция вывода на экран

cout << выражение … << выражение

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

 

# Include <iostream.h> void main ()

{Int a; float b, c;

cout << endl << «введите два числа» cin >> a >> b;

c = a + b;

cout << endl << «Сумма чисел равна» << c int r; / * Для задержки * /

cin >> r; / * Экрана * /

}

Параметр endl в операторе cout выполняет переход на новую строку.

 

1.4.2. Типы данных в языке С ++

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

Рассмотрим описания некоторых типов арифметических переменных:

 

Тип данных ключевое слово диапазон значений Объем памяти, байт
Знаковый длинный целый Int -2147483648 ..

2147483647

4
Знаковый короткий целый Signed char int -32768 .. 32767 2
Действительный (с плавающей точкой) Float 3,4 * 10 -38 ..

3,4 * 10 38

4
С плавающей точкой двойной точности Double -1,7 * 10 -308 ..

1,7 * 10308

8

Общий вид объявления переменных таков:

<тип> <имя переменной> {, <имя переменной>};

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

Пример.

 

const int n = 10; float x, y;

int i;

 

Над арифметическими переменными выполняются операции +, -, *, /, а также операция инкрементация (увеличение на единицу) ++ (вместо пары операторов a = a + 1, b = a можно записать один оператор b = a ++).

Над числами выполняются такие операции сравнения: <>, <=, > =,

== (равно),!= (Не равно).

Рассмотрим объявления символьного и строчной (последовательность символов) типов:

char <переменная> {, <переменная>}; / * Описание символьного типа * /

 

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

char x, y, z; char a; char s1, s2;

Символьная константа берется в отдельные кавычки: «есть», «+», «z».

Последовательность символов представляет собой строку. Символьная строка берется в кавычки: «группа Экк-21», «a + b = c».

Строчный тип можно задать как массив символов: char a [6]. Теперь переменной a

можно, например, присвоить строку символов:

a = «Ekf-11»

Как и в языке Pascal, в языке С ++ наличествует конструкция регулярного типа данных (массива).

Формат объявления массива таков:

 

<тип> <имя массива> [размерность]

Пример.

 

float a [10] [10]; int b [5];

Первое объявление задает матрицу размером 10 * 10. Элементы этой матрицы имеют имена от a [0] [0] до a [9] [9]. Второе объявление задает вектор (одномерный массив) с элементами b [0], b [1], b [2], b [3], b [4].

 

1.4.3. Основные управляющие операторы в языке С ++

Как и в языке Qbasic, так и в языке С ++ оператор присваивания использует символ «=» вместо символа «=».

Составной оператор — это последовательность операторов, которая находится посередине фигурных скобок (в языке PASCAL — посередине слов begin и end).

Формат условного оператора (оператора ветвления) является одним из таких:

 

if (<выражение>) if (<выражение>)

<Оператор1>; <Оператор1>; else

<Оператор2>;

 

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

В условии (логическом выражении) используют такие логические операции:

! — отрицание, логическое «Нет»; && — конъюнкция, логическое «И»;

|| — дизъюнкция, логическое «Или».

 

Пример.Если a> b и b = c, то вычислить s1 = a + 3 и s2 = a + 4, иначе вычислить s3 = a + 5.

if (a> b && b == c)

{S1 = a + 3;

s2 = a + 4

}

else s3 = a + 5;

Как и в других алгоритмических языках, в языке С ++ существуют оператор цикла типа FOR и оператор цикла типа WHILE.

Синтаксис оператора типа FOR таков:

for (выражение1; выражение2; выражение3)

<Оператор (тело цикла)>;

Здесь первое выражение задает начальное значение параметра цикла, второе выражение — конечное значение, а третий — условие переадресации. Например, заголовок цикла, который должен выполняться для i = 1,2, …, n, должен иметь вид

for (i = 1; i <n + 1; i ++)

S   10 января

Пример.Найти сумму

i 1

с использованием оператора for.

float s, a; int i; s = 0;

for (i = 1; i <11; i ++)

{A = 1 / i; s = s + a

}

Синтаксис оператора while в языке С ++ таков: while (<выражение>)

<Оператор>;

S   10 января

Пример. Найти сумму

i 1

с использованием оператора while.

float s, a; int i; s = 0; i = 1;

while (i <11)

{

a = 1 / i; s = s + a; i = i + 1;

}

Раздел 2.Типичные алгоритмы обработки экономической информации

 

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

 

2.1.алгоритмы поиска

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

Рассмотрим несколько классических алгоритмов поиска данных (информации), которые размещены в одномерной таблицы.

2.1.1. линейный Поиск

 

Пример. Выяснить, находится ли элемент b в одномерном целочисленном массиве (одномерной таблицы) a = (a 1, …, a n).

Program P1; Const n = 100; Var

A: array [1..n] of integer; b: integer; i: byte; R: Boolean;

Begin

. . . . . . . . .

R = false;

For i: = 1 to n do

if b = a [i] then R; = true;

if b then write ( ‘искомый элемент находится в таблице’) else write ( ‘искомый элемент не находится в таблице’);

. . . . . . .

Этот алгоритм всегда выполняет n сравнений.Среднюю скорость алгоритма можно увеличить почти вдвое, завершая цикл сразу после нахождения элемента b:

. . . . . . .

R = false; i: = 1; While R and i <= n do

Begin if b = a [i] then r = true; i = i + 1 end;

if b then write ( ‘искомый элемент находится в таблице’) else write ( ‘искомый элемент не находится в таблице’);

. . . . . . .

Пример. Задано упорядоченный массив целых чисел a 1 ≤ a 2 ≤ … ≤ a n и некоторое целое число b.Нужно найти такое место i, чтобы

a i ≤ ba i + 1

Program P2; Var

A: array [1..n] of integer; b: integer;

. . . . . . . . . . . . i: = 1;

while (a [i] <b) and (i <n) do i = i + 1; {Найдено место вставки}

 

Пример. Вставить элемент b в упорядоченный массив (целых чисел, действительных чисел, символов) a 1 ≤ a 2 ≤ … ≤ a n-1 так, чтобы упорядочение массива не нарушилось.

Program P3; Var

A: array [1..n] of integer; b: integer;

. . . . . . . . . . . . i = n-1;

while (a [i] <b) and (i> = 1) do

begin a [i + 1] = a [i]; i = i-1 end; {Поиск и передвижения} a [i + 1] = b; {вставка элемента в массив}

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

 

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

Пример. Вставить элемент b в упорядоченный массив a 1 ≤ a 2 ≤ … ≤ a n-1

.Использовать метод половинного деления.

Program P4; Const n = 100;

Type vector = array [1..n] of integer; Var a: vector;

b; integer; I, p, q, s: byte;

Begin

. . . . . . . .

p: = 1; q = n; {Начальные границы поиска} while (p <> q) do

begin

s = (p + q) div 2; {Середина}

if a [s] <b then p = s + 1 else q = s

end; {элемент нужно вставить после a p = a q} for i = n-1 downto p do a [i + 1] = a [i];

a [p] = b {вставка}

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

Количество сравнений для поиска места вставки в методе половинного деления составляет [log 2 (n + 1)] вместо n или n / 2 в методе линейного поиска.Однако собственно вставка (а также исключения) элемента в таблицу все же требует n / 2 шагов.

2.1.3. Поиск в двоичном дереве

 

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

Пусть, например, задана такая последовательность: a 1, a 2, …, a n … = 215, 192, 250, 220, 100, 260, 231, …

Первое из чисел (a 1) помещается в корень дерева.Каждое последующее число a i сравнивается с тем, что находится в корне.Когда a i <a 1, то происходит движение (перемещение) по дереву влево, если же a i> a 1, то происходит движение вправо.Если после такого движения оказывается свободное место, то число a i записывается на это свободное место.Если же в результате одного перемещения свободного места не оказывается, то выполняются новые сравнения.

Для нашей последовательности получается такое бинарное дерево (рис. 1):

 

215

192250

100220260

231

 

Рис. 1.

 

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

 

 

 

 

 

  192

 

 

13 14 15 10 11 12 16 17 18

 

231

19 20 21

 

Рис. 2.

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

В случае больших массивов дуги задаются с помощью конструкции «указатель (pointer)». Эта конструкция будет рассмотрена нами в пункте 2.5. Сейчас с целью понимания алгоритма поиска в дереве применим конструкцию «array»:

DER: array [1..n] of integer

 

 

5 215 8 14 192 11 250 17 220 20 100 260 231

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22

 

Напишем программу, которая находит место (адрес) элемента k в последовательности a 1, a 2, …, a n, заданной массивом DER (в предположении, что элемент k в этой последовательности существует).

Program P5; Const n = 50;

Var DER: array [1..n] of integer; k: integer; i: integer;

Begin

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

write ( ‘введите элемент k’); readln (k) i = 2; {корень дерева}

while DER [i] <> k do

if k <DER [i] then i = DER [i-1]

else i = DER [i + 1]; writeln ( ‘элемент’, k: 5, «находится на», i: 3, «- ом месте ‘);

. . . . . . . . . . .

Доказано, что при ривновипадковому поступлении элементов a i в таблицу среднее время поиска в двоичном дереве составляет 1,44log 2 n шагов.Для двоичных деревьев специального вида (так называемых сбалансированных деревьев) среднее время еще меньше: 1,04log 2 n.

Работа алгоритмов вставки и исключения элементов из дерева заключаются в поиске места вставки (исключения) и в исполнении потом лишь нескольких действий по перестройке дерева. Таким образом быстродействие последних алгоритмов также порядок log 2 n.

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

 

2.2.алгоритмы сортировки

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

2.2.1. Сортировка вставками

 

Изначально считается, что упорядоченная часть таблицы состоит только из элемента a 1.Рассматривается поочередно каждый j-й элемент таблицы (j = 2,3, …, n) и вставляется в нужное место в уже упорядоченный массив a 1, a 2, …, a j-1.Для вставки a j в массив a 1, a 2, …, a j-1 используется алгоритм программы P3.

Program P6;

. . . . . . . . . . .

for j = 2 to n do begin

b = a [j]; i = j-1;

while (i> = 1) and (a [i]> b) do

begin a [i + 1] = a [i]; i = i-1 end; {Поиск места} a [i + 1] = b {вставка}

end;

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

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

Очевидно, что алгоритм сортировки вставками имеет оценку O (n 2), т.е.

выполняет C ∙ n 2 сравнений.Поэтому этот метод имеет смысл применять только для небольших массивов.

2.2.2. Сортировка выбором

 

Идея этого алгоритма такова: выбирают наибольший элемент и записывают его в последнее j = n место. Далее выбирают самый большой среди оставшихся и записывают на предпоследнее j = n-1 место. Такое действие выполняют n-1 раз.

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

Program P7;

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

for i = n downto 2 do {вставка на место j = n, n-1, …, 2} begin

b = a [1]; k: = 1;

for i: = 2 to j do {выбрано самый}

if a [i]> b then {элемент в последовательности a1, …, aj} begin b = a [i]; k = i end;

a [k] = a [j]; a [j]: = b {обмен местами} end;

. . . . . . . . .

Оценка скорости этого алгоритма также составляет O (n 2).При сортировке выбором выполняется несколько больше сравнений, чем при сортировке вставками, однако перемещений осуществляется меньше.

2.2.3. Сортировка обменами

 

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

Program P8;

. . . . . . . . . . .

for i: = 1 to n do

for j = 1 to n-1 do

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

begin R = a [j + 1]; a [j + 1] = a [j]; a [j]: = R end

Оценка скорости алгоритма также равна O (n 2).Недостатком алгоритма является достаточно большое количество перемещений. Однако для частично упорядоченных массивов этот метод является очень удобным. В этом случае желательно, чтобы внутренний цикл производил признак «происходили перемещения, или нет». Тогда количество повторений внешнего цикла существенно уменьшается.

2.2.4. адресное сортировка

 

Пусть известно, что все элементы целочисленного массива a 1, a 2, …, a n не превышают величины M. тогда возникает возможность выполнить сортировку этого массива по n + M шагов.Для этого строится дополнительный массив b = (b 1, b 2, …, b n),

где b j

1,

 

существует i,

что a i   j.

0,

иначе

Далее пересматривается массив b и то значение j, где b j = 1 образуют впорядований массив.

Program P9;

Const n = 10; M = 1000;

Var a: array [1..n] of 1 ..M;

b: array [1 ..M] of 0..1; i, j: integer;

Begin

. . . . . . . . . .

for j = 1 to M do b [j]: = 0; {построение} for i: = 1 to n do b [a [i]] = 1; {массива b} i = 0;

for j = 1 to M do

if b [j] = 1 then

begin i: = i + 1; a [i] = j end;

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

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

 

2.2.5. Сортировка с помощью перемешанных таблиц

 

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

Пример.В каждый момент времени массив данных может содержать не более, чем n = 10 элементов, каждый из которых является целым числом от 1 до M = 999. Нужно так разместить эти элементы, чтобы поиск каждого из них заключался в выполнении лишь нескольких шагов.

Предлагается следующий алгоритм сортировки (алгоритм перемешивания, алгоритм рассеяния):

1. Образуется пустой (например, заполненный нулями) массив с n = 10 ячеек;

2. Каждый элемент, который является числом, содержащий k сотен, записывается в ячейку k; если эта ячейка уже занята, то этот элемент записывается в следующую свободную ячейку.

Пусть массив строится из таких цифр: 215, 910, 305, 250, 826, 827.

После рассеивания первых трех цифр имеем:

 

номер ячейки ключ Данные, связанные с ключом
 
1  
2 215 данные, относящиеся к ключу 215
3 305 данные, относящиеся к ключу 305
4  
5  
6  
7  
8  
9 910 данные, относящиеся к ключу 910

Ячейка с номером 2 для ключа 250 уже есть занятой, поэтому записываем этот ключ и связанные с ним данные в первую следующую свободную ячейку — ячейку 4. Для последнего элемента (элемента 827) свободной ячейкой буду ячейка с номером 0 (как следующая за ячейкой 9).

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

827
1
2 215
3 305
4 250
5
6
7
8 826
9 910

 

Имеет место такая теорем а: если

1. Каждой ячейке таблицы соответствует одинаковое количество элементов множества возможных значений ключей;

2. ключи поступают в таблицу ривновипадково;

3. таблица заполнена не более чем на 75%,

то среднее время поиска конкретного ключа в таблице составляет 1,5 шагов.

Составим программу записи нового элемента b в таблицу T = t 0 … t 9. .Program P10;

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

k = trunс (b / 100); {целая часть от b / 100} while T [k}> 0 do

begin {поиск ячейки для b} if k = 9 then k = 0

else k = k + 1

end;

T [k] = b; {запись элемента b в таблицу}

 

Алгоритм исключения элемента из перемешанной таблицы заключается сначала в его поиске, а затем в записывании на его место специального символа, например, числа «-1».

Алгоритм поиска начинает поиск с ячейки trunс (b / 100) и заканчивает поиск или нахождением элемента b, или выйдя на нулевую ячейку.

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

2.3.Алгоритмы над файлами

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

2.3.1. нахождение частных итогов

 

Пусть задано файл такой структуры:

 

группа предмет Количество неудовлетворительных оценок
К11 Р1 2
К11 Р4 1
С21 Р1 4
К21 Р1 3
К21 Р3
К21 Р4 1
. . . . . . . . . . . . . . . . . .

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

Нужно найти частичные итоги неудовлетворительных оценок по каждой из групп в частности. То есть нужно получить файл следующего вида:

 

группа Количество неудовлетворительных оценок
К11 3
С21 4
К21 4
. . . . . . . . . . . .

Основная идея алгоритма такова: в память считывается первая запись файла F1. Далее в цикле считываются все последующие записи этого файла. Если следующая запись относится к этой же группе, что и предыдущий, то происходит суммирование. Если нет — то формируется одна запись файла F2.

Program P11; Type

T1 = record Gr: string [3]; Pr: string [2]; M2: integer end; T2 = record Gr: string [3]; M2: integer end;

Var

x1: T1; x2: T2;

F1: file of T1; F2: file of T2; G: string [3]; M: integer;

Begin

Reset (F1) Rewrite (F2); Read (F1, X1) {первый запись} G = x1.Gr; M = x1.m2;

While not EOF (F1) do Begin

Read (F1, x1)

if x1.Gr = G then M = M + x1.m2 {группа не изменилась} else {группа изменилась}

begin

x2.Gr = x1.Gr; x2.M2 = M;

write (F2, x2) G = x1.Gr; M = x1.M2

end

End;

x2.Gr = x1.Gr; x2.M2 = M; {Последняя группа} write (F2, x2)

Программа P11 очень просто превращается в программу проекции файла   F1 по первому столбцу, то есть в программу, которая находит перечень групп без повторений:

К11
С21
К21
. . . .

Для этого нужно лишь удалить операторы, которые подсчитывают величину M — количество неудовлетворительных оценок.

2.3.2. Нахождение пересечения и объединения файлов

 

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

«Неудовлетворительно» по математике, а файл F2 — номера зачетных и фамилии студентов, получивших оценку «неудовлетворительно» по праву. Файлы F1 и F2 не обязательно рассортированных.

Объединением файлов F1 и F2 (аналогично операции объединения множеств в математике) есть файл F3, записи которого соответствуют тем студентам (без повторений), которые получили хотя бы одну неудовлетворительную оценку. Сечением файлов F1 и F2 есть файл F4 — файл студентов, получивших неудовлетворительные оценки по обоим предметам.

Program P12; {сечение } Type

T = record N: string [8]; F: string [15] end;

Var

x1, x2, x4: T;

F1, F2, F4: file of T; Begin

. . . . ; Reset (F1) Rewrite (F4) while not eof (F1) do

begin

read (F1, x1) reset (F2);

while not eof (F2) do begin

read (f2, x2)

if x1.n = x2.n then

begin x4.n = x1.n; x4.F = x1.F; write (F4, x4) end

end

end;

. . . . . . .

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

Program P13; {объединения} Var R: boolean;

. . . . . . . . .

Begin

Reset (F1) Rewrite ((F3)

While not eof (F1) do begin

read (F1, x1) x3 = x1; write (F3, x3) end; {Весь файл F1 переписываем в F3}

Reset (F2);

While not eof (F2) do begin

read (F2, x2)

R = false; {в F1 Не найдено записи x2} Reset (F1)

While not eof (F1) do

begin read (F1, x1) if x2.n = x1.n then R = true end if R = false then

begin x3 = x2; write (F3, x2) end {дописываем запись x2 с F2}

end;

 

2.3.3. Построение сочетание двух файлов

 

Операция сочетание двух файлов ключом на практике встречается, пожалуй, чаще всех операций над таблицами (файлами).

Пусть задано два файла:

F1 F2

 

Предположим, что каждый код товара из файла F1 найдется в файле F2. Однако количество записей файла F2 может быть больше, чем в файле F1.Нужно построить файл F3, записи которого имеют такую структуру:

F3

 

код товара

C

количество товара

Q

Цена за единицу продукции

P

Рассмотрим случай, когда файл F1 не является упорядоченным по кодам товаров (поскольку файл F2, как правило, на практике является упорядоченным). Тогда алгоритм построения F3 заключается в последовательном просмотре файла F1 (цикл), где для каждой записи x1 с F1 пересматриваются все записи из F2 (цикл в цикле).

Program P14; Type

T1 = record C: string; Q: integer; end; T2 = record C: string; P: real; end;

T3 = record C: string; Q: integer; P: real end; Var

X1: T1; x2: T2; x3: T3;

F1: file of T1; F2: file of T2; F3: file of T3;

. . . . . . . . . .

reset (F1) rewrite (F3) repeat

Read (F1, x1)

Reset (F2); {Установке указателя на начало файла F2} Repeat

Read (F2, x2)

if x1.C = x2.c then {коды совпали} begin

x3.C = x1.C; x3.Q = x1.Q, x3.P = x2.P

end; {Формирования записи файла F3} Until eof (F2);

Write (F3, x3) until eof (F1)

close (F1) close (F2); close (F3)

 

В противном случае, когда в качестве F1, так и F2 одинаково упорядоченными, быстродействие алгоритма может стать значительно лучше. Для этого во внешнем цикле не нужно каждый раз устанавливать указатель файла F2 на начало (команду Reset (F2) следует перенести рядом с командой Reset (F1)).

Пусть файл F1 содержал n записей, а файл F2 — m записей.Тогда в случае неодинаково упорядоченных файлов сообщения по ключом требует n · m считываний, а в случае одинаково упорядоченных — лишь n + m.

2.3.4. Алгоритм слияния двух упорядоченных файлов

 

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

Пусть файлы F1 и F2 имеют одинаковую структуру:

F1, F2

 

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

Program P15; Type

Z = record key: string; D: string end;

Var

x1, x2, x3: z; F1, F2, F3: file of z;

. . . . . . . . .

reset (F1) reset (F2); rewrite (F3) While not eof (F1) do

Begin

Read (F1, x1)

While (not eof (F2)) and (x2.key <x1.key) do begin

read (F2, x2) x3 = x2; write (F3, x3)

end; {Переписать на F3 с F2 все записи, меньше x1} x3 = x1;

write (F3, x3) {переписать на F3 запись x1}

End;

While not eof (F2) do {этот цикл иногда не работает ни разу}

Begin

read (F2, x2) x3 = x2; write (F3, x3) {переписать «хвост» файла F2} End;

. . . . . . .

2.4. Алгоритмизация приближенных вычислений

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

2.4.1. вычисления числовых рядов

 

Пусть требуется в некоторой точке x вычислить значение функции y = e -x с точностью ε = 10 -6.

Из курса высшей математики известно, что функция разлагается в такой ряд Тейлора:

e x a

( 1) n x 1 x x x

 

n

n 0

n 0

n!1!              2!              3!

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

условие

x .

n!

Сделаем два замечания.

1. Несмотря на то, что мы должны вычислить ряд различных значений a 0, a 1, …, a n, …, программистский подход позволяет рассчитывать все эти значения в той же ячейке памяти a.

2. Для больших значений n как числитель x n, так и знаменатель n!выражения a n

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

 

a 0 1

a a

x

(N 1, 2, …).

n

n 1 n!

Program P16; var

x: real; y: extended; {Максимальный порядок числа = 4932} eps: real; n integer; a: extended;

. . . . . . . . . . . n = 1; a = 1; y = a;

Repeat

a = a * (- x / n) y = y + an = n + 1

Until abs (a) <eps;

Writeln ( ‘x =’, x: 10: 6, «y = ‘, y: 10: 6)

. . . . . . . . . .

Как видно из приведенного выше примера, программирование математических расчетов имеет некоторые специфические особенности по отношению к расчетам в классической математике.

2.4.2. Решение уравнений методом половинного диленные

 

Нахождение корней уравнения f (x) = 0 является сложной математической задачей уже в том случае, когда f (x) не является линейной или квадратичной функцией.

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

2. Уточнение корней.Если функция f (x) является непрерывной на отрезке [a; b] и имеет [a; b] ровно один корень, то знаки чисел f (a) и f (b) должны быть разными.Поделив отрезок [a; b] пополам (на отрезки [a; c] и [c; b]), обнаруживаем тот из них, где функция f (x) на его концах снова имеет различные знаки.Таким образом интервал, где находится искомый корень, уменьшается вдвое. Процесс разделения отрезка пополам продолжается, пока длина отрезка, где находится корень, не станет меньше заданного числа ε.

Program P17;

Var

a, b, c: real; eps: real;

function f (x: real): real; <Тело функции>;

Begin

While ba> eps do begin

 

 

end;

c = (a + b) / 2;

if f (a) * f (b)> 0 then a = c else b = c

writeln ((b + a) / 2: 10: 6)

. . . . . . . . .

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

b

определенным интегралом f ( x) dx

a

на отрезке [a; b] от непрерывной на

этом отрезке функции f (x) называется предел интегральных сумм

lim S

li m b a n

f (x ) li m b a n

f (a i b a)

n

n

n               n

i

i 1

n               n

i 1 n.

Понятно, что для достаточно больших значений n интегральная сумма S n становится близкой к точного значения интеграла:

f (x) dx b a f (a i b a ) .

 

a i 1

Итак, программа нахождения определенных интегралов состоит в нахождении интегральных сумм. А программа нахождения суммы — это обычный цикл типа FOR.

Program P18;

Var S, a, b: real; x: real; i: integer; function f (x: real): real; <Тело функции>;

. . . . . . . . . . S: = 0; x = a;

For i: = 1 to n do begin

x = a + i * ((ba) / n) S = S + f (x)

end; S = S * ((ba) / n) write ( ‘интеграл =’, S)

… . . . . . . . . . . .

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

2.5. списков программирования

2.5.1. Понятие о динамическом программирования

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

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

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

На рис. 3. представлены обычный однонаправленных список:

 

. . .

 

Рис. 3.

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

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

Пример.Пусть элементами списка являются целые числа. Нужно подсчитать количество элементов, превышающих число 4. Признаком конца списка считать число 0 (рис. 4.).

 

. . .

6 7 Первая 4 5

 

1

Рис. 4.

В случае конструкции array имеем такой вектор:

 

А: 8 5 10 2 7 4 2 2
  1 2 3 4 5 6 7 8 9 10 11

Алгоритм состоит в организации такого цикла, который начинается с элемента A [1] и далее согласно указателей осуществляет переходы от A [i] до A [i + 1], пока значение A [i + 1] не станет нулем.

Program P19;

Var A: array [1..n] of integer; i, k: integrer

. . . . . . . . . k = 0; i = 0;

While A [i + 1] <> 0 do begin

i = A [i + 1];

if A [i]> 4 then k = k + 1; end;

write ( ‘количество искомых элементов равна’, k);

. . . . . . .

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

1 2 3 4. . .

(Файл F)

Рис. 5.

Нужно переставить местами записи файла F, которые являются первым и вторым согласно порядку, заданного списком (т.е. переставить первый и второй элементы списка соответствует записям номер 1 и номер 4 в файле F).

Адресу первого элемента списка является A [1], второго элемента — A [A [1] 1], третьего элемента — A [A [A [1] 1] +1].

Итак, алгоритм состоит в замене трех указателей (новые указатели изображены пунктиром на рис. 5).

Program P20;

R1 = A [1]; R2 = A [A [1] 1]; R3 = A [A [A [1] 1] +1]; {куда стрелки} L1 = 1; L2 = A [1] 1; l3 = A [A [1] 1] 1; {откуда стрелки} A [L1] = R2; A [L2] = R3; A [L3] = R2;

Программа изменила последовательность просмотра записей файла F, а не переставляя физически эти записи.

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

F

Рис. 6.

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

Program P21; Var

A: array [1..100] of integer;

F: file of record … end; x: record … end;

. . . . . . . . .

read (k) {K — содержательный ключ} i = A [1];

while (A [i] <> k) do i = A [i + 2];

j = A [i + 1]; seek (F, j) {J — машинный ключ} read (F, x) {Считывание нужной записи}

В программе P21 использована конструкция seek (F, j) — установление указателя файла F на запись с номером j. Программа фактически реализовала индексный доступ к файлу (переход от содержательного с точки зрения человека ключа k к машинному ключа j).

2.5.2. переменные типа «Указатель»

 

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

С целью организации списков в современных языках программирования вводятся переменные типа указатель (pointer). Синтаксис описания указателя таков:

Type

<Тип указателя> = ^ <тип>, например,

Type

p = ^ integer;

Var

x, y: p; {Указатели на переменную типа integer} z ^ char; {Указатель на переменную типа char}

целое число

 

x

Далее в программе возможны такие операторы: x ^ = 10; y = x;

 

 

y

 

x ^ = x ^ + 1; x = nil;

 

 

 

y

Для того чтобы выделить в процессе работы программы место памяти, в языке Pascal используют оператор new; чтобы освободить место — оператор dispose.

Пример.Составить программу по вырастанием операторов new и dispose.Program P22;

Var i: integer; p, g: ^ integer;

Begin

{Первая строка} new (p) new (q) i = 5;

{Вторую строчку} p ^ = 7; q ^ = p ^ -i; i = i + 1;

{Третью строчку} p ^ = q ^ + i; q = p;

write (q ^)

End.

После описаний имеем:

p q i

После выполнения операторов первой строки:

p p ^

q q ^

5

i

 

После следующих трех операторов (вторая строка):

 

7

p p ^

2

q q ^

6

i

 

После оператора p ^ = q ^ + i (в третьей строке) имеем:

8

p p ^

После выполнения присвоения q = p получаем:

8

p p ^

2

q q ^

6

i

 

Оператор write (q ^) выводит число 8.

Отметим, что место памяти под число 2 уже нельзя уволить. Эту память можно было освободить, выполнив оператор dispose (q) перед выполнением q = p:

q

6

i

 

2.5.3. списке структуры

 

Рассмотрим определение (рекурсивное): Type d = ^ t;

t = record

. . . . .

end;

Переменными типа t есть записи. Одно из полей каждой записи есть или nil, или ссылки (указатель):

. . .

 

 

Пример. Построение списочного структуры. Type pointer {указатель} = ^ elem {элемент}

elem = record

inf: integer {информационная часть} next: pointer {указатель}

end;

var

p, q: integer;

Begin

. . . . . . . . . .

p = nil;

For i = 10 downto 1 do begin

new (q) q ^ .inf: = i; q ^ .next = p; p = q end;

После операторов p = nil и new (q) имеем:

q

После q ^ .inf: = i; q ^ .next; p = q:

q

Далее, после выполнения группы операторов new (q) q ^ .inf: = i; q ^ .next = p; p = q, получаем:

 

 

p

 

q

Следующие шаги выполнения цикла будут строить новые элементы списочного структуры (от последнего к первого).

Пример.Просмотр списка.

Пусть значением переменной p является указатель на первый элемент списка:

. . .

p

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

. . . . . .

q = p;

while q <> nil do begin

write (q ^ .inf)

q = q ^ .next {аналог оператора i = A [i + 1]}

end;

 

Пример.Задано список вида

 

. . .

p

Нужно вставить элемент

 

между вторым и третьим элементами списка.

Выполняем операторы: q = p; {Для просмотра}

new (r) r ^ .inf: = 17; r ^ .next = q ^ next;

 

. . .

p

 

q r

 

Выполняем операторы: q ^ .next = r; dispose (q) dispose (r):

 

. . .

 

 

 

 

 

 

Новый элемент вставлен в нужное место.

 

Пример.Перенести из списка p второй элемент в список r, а затем подсчитать количество таких элементов, где информационная часть является буквой «н».

Program P23;

Type pointer = ^ elem;

elem = record inf: char; next: pointer end;

Var

p, q, r: pointer; k: integer;

Begin r = p ^ next;

p ^ .next = p ^ .next ^ .next;

r ^ .next = nil; {Элемент перенесено из одного списка в другой} k: = 0;

while q <> nil do begin

if q ^ .inf = ‘н’ then k = k + 1 q = q ^ .next

end End.

Списков программирования является достаточно сложным для начинающих. Однако такое программирование является основным в работе профессионального программиста.

2.6. Алгоритмы на графах и деревьях

2.6.1. Деревья и алгоритмы над ними

 

Древовидной структурой (деревом) называют множество взаимосвязанных объектов (вершин, узлов), расположенных по уровням по следующему правилу:

— на первом уровне один узел (корень дерева)

— любой узел i-го уровня (i ≠ 1) связан только с одним узлом (i-1) -го уровня (рис. 7.).

 

ребро

корень

 

узел (элемент, вершина, node)

 

листок

 

 

Рис. 7.

Дерево по своей природе является рекурсивной структурой данных.Поэтому возможно и такое определение дерева:

Дерево — это либо пустое дерево,

или вершина, которой подчиняется окончена количество деревьев (поддеревьев).

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

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

15

 

20 августа

 

10 апреля 16 25

 

19

 

Рис. 8.

 

Пример.Элементами двоичного дерева есть целые числа. Подсчитать сумму этих чисел.

Type tree = ^ node;

node = record elem: integer; left, right: tree end; Function Sum (t: tree): integer;

begin

if tree = nil then sum: = 0; {Рекурсивное обращение к функции sum} else sum = sum (t ^ .left) + t ^ .elem + sum (t ^ .right)

end; {Описания функции}

 

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

Пример.Задано бинарное дерево. Найти сумму всех значений его вершин, используя механизм возврата назад. Для дерева, представленного на рис. 8. порядок прохождения вершин будет таким:

15 8 (запомнить 20), 4 (запомнить 10), 10, 20, 16 (запомнить 25), 19, 25 Для запоминания отложенных «на потом» вершин строится магазин

(стек, stack, структура типа LIFO) в виде одномерного массива (рис.9):

 

i

 

 

Рис. 9.

Stack: array [1..50] of integer; i {текущее количество элементов стека}: integer;

Основные действия над стеком выглядят так:

{Записать элемент в стек:} i = i + 1; stack [i]: = k;

{Считать один элемент из стека:} k = stack [i]; i = i-1;

Двоичное дерево представим в памяти с помощью списочного структуры:

q

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

Program P24;

Type rebro = ^ node

node = record

l, r: rebro; inf: integer end;

Var p, q: rebro; S: integer; i; integer; Stack: array [1..50] of integer;

. . . . . . . . . . . . . q = p; S: = 0;

while q <> nil or i> 0 {стек не пустой} do

begin {*}

S = S + q ^ .inf;

if q ^ .l <> nil then begin {**}

if q ^ .r <> nil then {записать правую вершину в стек} begin

i = i + 1; Stack [i]: = q ^ .r end;

q = q ^ .l {движение влево} end {**}

else {влево вершин форуме} begin q = Stack [i]; i = i-1 end

end {*}

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

Пример.В памяти компьютера находится файл F, каждая запись которого содержит ключ и информационную часть. Индекс для этого файла имеет вид двоичного дерева (рис. 10):

F

1 2 3 4

 

Рис. 10.

С клавиатуры вводится значение ключа k.Составить программу, которая организует индексный доступ к файлу F, то есть находит запись файла, связанный с этим ключом (в предположении, что такая запись существует). Индексом является списочная структура с использованием конструкции «указатель».

Program P25; Type

z = record k: integer; end; rebro = ^ node;

node = record l, r: rebro; k {ключ}, n {номер записи в F}: integer end;

Var

p, q: rebro;

F: file of z; x: z; k, n: integer;

. . . . . . . . .

Read (k) q = p;

while k <> q ^ .k do

if k <q ^ .k then q = q ^ .l

else q = q ^ .r

n = q ^ .n;

seek (F, n)

read (F, x)

. . . . . . . .

 

2.6.2. Графы и алгоритмы над ними

 Графом (сетевой структурой) называют множество взаимосвязанных объектов (вершин), которые соединены направленными или ненаправленными дугами (рис.11.).

ненаправленные дуги, направленные дуги,

неориентированный граф ориентирован граф Рис. 11.

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

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

 

Рис. 12.

 

Время работы 1 → 2 составляет 4 дня, работы 1 → 3 равна 6 дней, а работы 2 → 3 — 3 дня. Состояние № 2 достигается выполнением только одной работы 1 → 2, то есть за 4 дня. Состояние № 3 может быть достигнут только после того, как из состояния № 1 будет выполнена работа 1 → 3 (6 дней) и из состояния № 2 (4 дня) работа 2 → 3 (3 дня).Поэтому состояние № 3 достигается max {0 + 6, 4 + 3} = 7 (дней). Следовательно, при переходе из начального состояния № 1 в состояние № 3 критическим путем является путь <1, 2, 3>. Рассчитав время достижения каждого из состояний <R1 = 0 R2 = 4; R3 = 7; R4 = 9; R5 = 13>, обнаруживаем критический путь в заданном графе: <1, 2, 3, 5>.

Построим общий алгоритм нахождения критического пути.

Входные данные алгоритма — это граф с пятью вершинами {1, 2, 3, 4, 5} и

восьми дугами {<1,2>; <1,3>; <2,3>; <2,4>; <2,5>; <3,4>; <3,6.>; <4,5>}.

Каждой дуге <i; j> соответствует время t ij.

Каждой вершине j соответствует завершении всех предыдущих работ R j.Алгоритм состоит из двух частей:

А. Для всех вершин j, начиная с первой, находим величины R j по

формулами

R j max {R i t ij};

i: i, j

В. Для каждой вершины j, начиная с последней, находим предварительную

ей вершину i такую, что

R j

max {R i t ij}.

i, j

 

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

Возможны различные способы таких представлений, в частности:

А. Матрица.Каждая дуга <i, j> характеризуется одним из элементов матрицы (элементом на пересечении i-ого строки и j-ого столбца).Матричное представление удобно для программирования, однако требует значительных затрат памяти компьютера:

0 t 12 4

0 0

t 13 6

t 23 3

0 0

t 24 5 0

 

34

t 35

6

0 0 0

0 t 45 3

 

 

 

В. Набор дуг и вершин.

дуги Вершины

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

2.7. Эвристические и генетические алгоритмы

2.7.1. эвристические алгоритмы

 

Рассмотрим одну из классических экономических задач — задачу коммивояжера (salesman).

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

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

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

Пронумеруем города числами 1, 2, …, N. Обозначим через c ij = c ji стоимость переезда из i-ого города в j е.

Введем следующие переменные:

Var k, i, j, u, v: 1 ..N; {номера городов}

tour: array [0..n] of 1 ..N; {тур, последовательность номеров городов} min, cost: real; {стоимость тура}

visited: set of 1 ..N; {Множество уже посещенных городов} Запишем эвристический алгоритм коммивояжера на языке PASCAL: Begin

Readln (u) {задаем начальное город}

tour [0] = u; visited = u; {тур начинается в городе u} v = u; cost = 0; {v — текущее город}

For k = 1 to N-1 do Begin {*}

Min = 65535; {Число, превышает все возможные значения cij}

For i: = 1 to n do

if not (i in visited) then begin {**}

if c [v, i] <min then

begin min = c [v, i]; j = i end

end; {**} {наименьшая расстояние среди непосещенных городов} tour [k]; = j; cost = cost + c [v, u];

visited = visited + [j]; v = j {осуществляется переезд в другой город} End; {*}

tour [u] = u; {Последний переезд — переезд в исходное город} cost = cost + c [v, u];

. . . . . . . . . . .

 

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

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

Var

x: 1..3; {переменная x принимает одно из значений 1, 2, 3}

N, M: set of 1..3; {Переменные N и M являются множествами, состоящие ИЗ элементов 1, 2, 3}

Значениями переменных n и m могут быть такие множества [], [1], [2], [3], [1,2] = [2,1], [1,3], [2,3], [ 1,2,3].

Операторы над множествами в языке Pascal представим таблицей:

 

Операции над множествами Операторы в языке Pascal
x M x in M
N ∩ M N * M
N M N + M
N M N M

Примеры операторов над множествами: M = [2,3]; if (3 in M) then …; if N M then …

N = M + [1,2]; {Результатом работы оператора будет множество N = [1,2,3]}.

 

2.7.2. генетические алгоритмы

 

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

Таким образом кандидаты на решение постепенно улучшают свои характеристики — эволюционируют. Поэтому решение задач с помощью генетических алгоритмов еще называют эволюционным исчислением (evolutionary computing).

Общая схема генетического алгоритма такова:

Как видно из схемы, при разработке генетического алгоритма нужно принять конкретные решения по каждой из четырех проблем P1, P2, P3, P4.

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

городов).

Конкретизируем проблемы P1, P2, P3, P4 для нашей задачи.

 

проблема P3.Оценку приспособленности осуществляют с помощью

целевой функции — общей длины тура (или общей стоимости тура).

Проблема P4. Правила отбора состоит в том, чтобы на каждом цикле оставлять небольшое количество лучших туров. Более сложные правила отбора могут заключаться в том, что «слабые» решения имеют право на существование (жить) еще несколько поколений (циклов). Решение этой проблемы является непростой как с точки зрения программирования, так и с позиций разумного отбора данных.

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

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

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

А. родительский тур порожденный тур

(произошла перестановка)

 

В. родительские туры

 

 

порожденный тур

1 5 4 3 2 6 (состоялся обмен «генами «)

 

С родительские туры

. . . . . .

 

порожденный тур

. . . . . . (состоялся обмен «Генами»)

 

 

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

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

Итоговые вопросы курса

1. Уметь писать программы, аналогичные, приведенным в разделе 1.

2. Уметь строить блок-схемы; выполнять грамматический анализ и прокрутку таких программ.

3. Алгоритм, его свойства, способы задания.

4. Принципы фон Неймана функционирования компьютеров.

5. Алгоритмическая полнота (универсальность) ЭВМ (компьютеров) и алгоритмических языков.

6. Задачи, не решаются алгоритмически.

7. Теоретические основы структурного программирования.

8. Основные идеи структурного программирования.

9. Арифметические типы данных в языках программирования PASCAL, C ++ и VBA.

10. Символьные типы данных в языках программирования PASCAL, C ++, VBA.

11. Массивы (array, dim) в языках программирования PASCAL, C ++, VBA.

12. Операторы ветвления в языках программирования PASCAL, C ++ и VBA.

13. Операторы цикла (For и While) в языках программирования PASCAL, C ++ и VBA.

14. Описание процедуры и оператор процедуры в языке PASCAL.

15. Описание функции и указатель функции языке PASCAL.

16. Записи и файлы языке PASCAL.

17. Операции над последовательными файлами языке PASCAL.

18. Локализация переменных в языках программирования.

19. Алгоритм линейного поиска в упорядоченном и в невпорядкова- ном массиве.

20. Алгоритм поиска методом половинного деления, его характеристика.

21. Алгоритм поиска в двоичном дереве, его характеристика.

22. Алгоритм сортировки вставками, его характеристика.

23. Алгоритм сортировки выбором, его характеристика.

24. Алгоритм сортировки обменами, его характеристика.

25. алгоритм адресного сортировки.

26. Алгоритм сортировки с помощью перемешанных таблиц, его характеристика.

27. Алгоритм нахождения частных итогов, его характеристика.

28. Алгоритм нахождения пересечения двух таблиц (файлов).

29. Алгоритм нахождения объединения двух таблиц (файлов).30 Алгоритм нахождения сочетание двух таблиц (файлов).

31. Алгоритм слияния двух упорядоченных файлов, его характеристика.

32. Метод половинного деления решения уравнений f (x) = 0.

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

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

35. Программа просмотра однонаправленных списке заданного конструкцией array.

36. Организация индексного доступа к файлу (индекс задано конструкции array).

37. Переменные типа «указатель (ссылка)». действия над ними.

38. Определение (рекурсивное) списочного структуры в языке Pascal.

39. Программа просмотра списочного структуры (с использованием переменной типа «Указатель»).

40. Алгоритм возвращения назад (backtracing). Стек.

41. Организация индексного доступа к файлу (индекс задано списочной структурой с использованием переменной типа «Указатель»).

42. Алгоритм построения критического пути в графе.

43. эвристические алгоритмы.

44. Генетические алгоритмы. Основные проблемы их построения.

 

 

литература

 

1. Щедрина А.И. Алгоритмизация и программирование процедур обработки информации: Учеб. пособие — М .: Финансы, 2001. — 240 с.

2. Ежова Л.Ф. Алгоритмизация и программирование процедур обработки информации: Учеб. пособие для самост. изуч. дисц. — М .: Финансы, 2000. — 152 с.

3. Семотюк В. Программирование в среде Турбо Паскаль. Львов: Бак, 2000. — 248 с.

4. Костов А.В., Ярошко С.А. Методы разработки алгоритмов: Тексты лекций.

— Львов: ЛНУ, 2002. — 98 с.

5. Костов А. Структуры данных. — Львов, ЛНУ, 2000. — 56 с.

6. Лукьянова В.В. Компьютерный анализ данных. — М .: Академия, 2003. — 342 с.

7. Информатика. Компьютерная техника. Компьютерные технологии: Пидруч- ник / Под ред.А. И. Пушкаря. — М .: «Академия», 2002. — 704 с.

8. Помеха А.П. Методические указания к выполнению контрольных работ по курсу «Информатика и компьютерная техника». — Львов: ЛНУ, 2003. — 24 с.

9. Помеха А.П. Методические указания к выполнению контрольных работ по курсу «Алгоритмизация и программирование». — Львов: ЛНУ, 2004. — 68 с.

10. Кнут Д. Искусство программирования для ЭВМ. Т. 3. Сортировка и поиск. — М .: Мир, 1977 (перевод с английского на русский).

11. Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы : Построение и анализ. — М .: МЦНМО, 1999 (перевод с английского на русский).

12. Ахо А., Хопкрофт Дж., Ульман Дж. Построение и анализ вычисли- тельных алгоритмов. — М .: Мир, 1979 (перевод с английского на русский).

13. Дал В., Дейкстра Э., Хоор К. Структурное программирование. — М .: Мир, 1975 (перевод с английского на русский).

14. Евстигнеев В.А. Применение теории графов в программировании. — М .: Наука, 1985.

15. Кристофидес Н. Теория графов. Алгоритмического поход. — М .: Мир, 1978 (перевод с английского на русский).

16. Майника Э. Алгоритмы оптимизации на сетях и графах. М .: Мир, 1981 (перевод с английского на русский)

[Всего голосов: 4    Средний: 5/5]

Читать  Краткий курс программирования в среде Delphi