Билет 15

Действия с нетипизированными понятиями с помощью директивы absolute.

Если в случает явного привидения типа в ПП описывается соответствующий локальный тип, то в этом случае внутри ПП следует описать локальную переменную и совместить ее в памяти с формальными параметрами без типа. Последнее реализуется следующей конструкцией var {локальная переменная ПП} <имя>:<тип><директива absolute> С помощью одной ПП вычислить сумму элементов массивов разного размера.

program Sovmes_Adres; const x:array[1..5] of real = (1,2,3,4,5); y:array[1..3] of real = (6,7,8); function Sum(var z; n:byte):real; var {задаем локальный массив большого размера} w:array[1..Maxit div size of(real)] of real absolute z; i:byte; {номер компонентов вектора} s:real; {текущая сумма} begin s:=0 for i:=1 to n do s:s+w[i] sum:=s end; {sum} begin writeln(‘Сумма элементов вектора х= ’ sum(x,5):2:0); writeln(‘Сумма элементов вектора y= ’ sum(y,3):2:0); end.

Цикл со счётчиком

Цикл со счётчиком — цикл, в котором некоторая переменная изменяет своё значение от заданного начального значения до конечного значения с некоторым шагом, и для каждого значения этой переменной тело цикла выполняется один раз. В большинстве процедурных языков программирования реализуется оператором for, в котором указывается счётчик (так называемая «переменная цикла»), требуемое количество проходов (или граничное значение счётчика) и, возможно, шаг, с которым изменяется счётчик

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

i := 100;

for i := 0 to 9 do

begin

... тело цикла

end;

k := i;

возникает вопрос: какое значение будет в итоге присвоено переменной k: 9, 10, 100, может быть, какое-то другое? А если цикл завершится досрочно? Ответы зависят от того, увеличивается ли значение счётчика после последней итерации и не изменяет ли транслятор это значение дополнительно. Ещё один вопрос: что будет, если внутри цикла счётчику будет явно присвоено новое значение? Различные языки программирования решают данные вопросы по-разному. В некоторых поведение счётчика чётко регламентировано. В других, например, в том же Паскале, стандарт языка не определяет ни конечного значения счётчика, ни последствий его явного изменения в цикле, но не рекомендует изменять счётчик явно и использовать его по завершении цикла без повторной инициализации. Программа на Паскале, игнорирующая эту рекомендацию, может давать разные результаты при выполнении на разных системах и использовании разных трансляторов.

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

Билет №16

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

Все формальные параметры можно разбить на четыре категории:

• параметры-значения;

• параметры-переменные;

• параметры-константы (используются только в версии 7.0);

• параметры-процедуры и параметры-функции.

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

function Max( A: array[ 1..100 ] of real ): real;

Чтобы правильно записать этот заголовок, следует в основной программе ввести тип-массив, а затем использовать его в заголовке:

type tArr =array [ 1..100 ] of real; function Max ( A: tArr ) : real;

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

Концепция типов ТР

В языке ПАСКАЛЬ существует правило: тип явно задается в описании переменной или функции, которое предшествует их использованию. Концепция типа языка ПАСКАЛЬ имеет следующие основные свойства:

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

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

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

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

Тип определяет:

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

• - внутреннюю форму представления данных в ЭВМ;

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

Обязательное описание типа приводит к избыточности в тексте программ, но такая избыточность является важным вспомогательным средством разработки программ и рассматривается как необходимое свойство современных алгоритмических языков высокого уровня. В языке ПАСКАЛЬ существуют скалярные и структурированные типы данных. К cкалярным типам относятся стандартные типы и типы, определяемые пользователем.

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

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

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

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

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

• - к любому порядковому типу могут быть применены стандартные функции Low и High, которые возвращают наименьшее и наибольшее значения величин данного типа.

В языке ПАСКАЛЬ введены понятия эквивалентности и совместимости типов. Два типа Т1 и Т2 являются эквивалентными (идентичными), если выполняется одно из двух условий:

• - Т1 и Т2 представляют собой одно и то же имя типа;

• - тип Т2 описан с использованием типа Т1 с помощью равенства или последовательности равенств.

Например:

type

T1 = Integer;

T2 = T1;

T3 = T2;

Менее строгие ограничения определены совместимостью типов. Например, типы являются совместимыми, если:

• - они эквивалентны;

• - являются оба либо целыми, либо действительными;

• - один тип - интервальный, другой - его базовый;

• - оба интервальные с общим базовым;

один тип - строковый, другой - символьный.

В ТУРБО ПАСКАЛЬ ограничения на совместимость типов можно обойти с помощью приведения типов. Приведение типов позволяет рассматривать одну и ту же величину в памяти ЭВМ как принадлежащую разным типам. Для этого используется конструкция

Имя_Типа(переменная или значение). Например,

Integer('Z')

представляет собой значение кода символа 'Z' в двухбайтном представлении целого числа, а Byte(534) даст значение 22, поскольку целое число 534 имеет тип Word и занимает два байта, а тип Byte занимает один байт, и в процессе приведения старший байт будет отброшен.

Билет №17

Этапы решения задачи на ПК

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

• постановка задачи;

• математическая формализация;

• построение алгоритма;

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

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

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

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

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

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

Моделирование.

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

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

Итак, создавая математическую модель для решения задачи, нужно: выделить предположения, на которых будет основываться математи­ческая модель; определить, что считать исходными данными и результатами; записать математические соотношения, связывающие результаты с исходными данными.

Построение алгоритма.

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

Программирование.

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

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

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

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

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

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

Анализ результатов. Уточнение модели.

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

Символьный тип (Char) - это тип данных, состоящих из одного символа (знака, буквы, кода). Значением типа Char может быть любой символ из набора ASCII. Если символ имеет графическое представление, то в программе он записывается заключенным в одиночные кавычки (апострофы), например:

'ж'     's'    '.'    '*'    ' '-(пробел)

Для представления самого апострофа его изображение удваивается: ''''.  Если же символ не имеет графического представления, например, символ табуляции или символ возрата каретки, то можно воспользоваться эквивалентной формой записи символьного значения, состоящего из префикса # и ASCII-кода символа:

#9     #32    #13

Допустимые операции:  - присваивание; - сравнение: <, >, >=, <=, <>, =. Большим считается тот символ, который имеет больший ASCII-номер.

Билет 18

ИСТ в ВК

Сортировка числовых данных

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

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

{ сортировка пузырьковым методом}

procedure Bubble (var item: DataArray; count: integer);,j: integer;: DataItem;i: = 2 to count doj: = count downto i doitem [j-1] >item [j] then: = item [j-1];[j-1]: = item [j];[j]: = x;;;

end; {конец сортировки пузырьковым методом}

В этом случае данное "item" является массивом элементов "DataItem", который сортируется, а данное "count" содержит число элементов в массиве.

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

Для иллюстрации работы сортировки пузырьковым методом ниже даны результаты каждого этапа сортировки массива "dcab":

исходное положение: d c a b;

первый проход: a d c b;

второй проход: a b d c;

третий проход: a b c d.

Билет 19

Бесконечное произведение

Бесконечное произведение представляет собой произведение бесконечного числа сомножителей:

.

Если такое произведение стремится при i  к некоторому пределу P, то P называют значением бесконечного произведения. Если P конечно и отлично от нуля, то произведение называют сходящимся, в противном случае - расходящимся. Если бесконечное произведение сходится, то . Именно это обстоятельство можно использовать для прекращения циклических вычислений частичных произведений, а именно когда очередной сомножитель станет отличаться от 1 на величину меньше заданной погрешности . Разберем правила решения данной задачи на конкретном примере.

Пример 2. С погрешностью 0,0001 вычислить значение числа  с использованием формулы Валлиса: .

Ввод ()

p:= 1; m:= 4/3; n:= 2

Пока m-1 > 

p:= p*m

m:= 4n*n/(4n*n-1); n := n + 1

Вывод (2*p)

В соответствии с приведенным выше алгоритмом имеем:

program Vallis;

const

e = 0.0001;

var

n: byte;

p, m: real;

begin

p:= 1; m:= 4/3; n:= 2;

while m-1 > e do begin

p:= p*m;

m:= 4*n*n/(4*n*n - 1);

end; {while}

writeln(‘Число ПИ = ‘, p*2);

writeln(‘Учтено ’,n-1, ‘сомножителей’)

end.

Эволюция языков программирования