Вопрос – см. 13 вопрос ТИМОИ (экзамен)

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

Циклы с предусловием (условие проверяется до выполнения цикла) – вычисляется значение логического выражения Если оно истинно, то выполняется оператор, после чего снова вычисляется значение логического выражения, в противном случае действие заканчивается. While <логическое выражение> do <оператор>.

Цикл с постусловием, для этого цикла условие выхода – истинное условие, пока условие ложно цикл выполняется. Выполняется последовательность операторов, далее вычисляется значение логического выражения. Если оно истинно, то действие заканчивается, иначе снова выполняется последовательность операторов. Repeat <последовательность операторов > until <логическое выражение>.

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

for <параметр>:= <выражение 1> to <выражение 2> do <оператор>

S:=0;

for i:=1 to n do S:=S+1;

Пример цикла с постусловием

Repeat

readln (x,k); S:= S+x*k; Until S>p;Write (‘S=’, S)

 

 

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

 

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

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

- выработать требования (свойства, качества и возможности), необходимые для решения проблемы или достижения цели (экспертный характер этой деятельности);

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

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

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

• как определить решение; • каких данных не хватает и все ли они нужны; • какие сделаны допущения и т. п.

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

• имя/цель - дается имя модулю и предложение о функции модуля с формальны­ми параметрами;

• неформальное описание - обзор действий модуля;

• ссылки - какие модули ссылаются на него и на какие модули ссылается данный модуль;

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

• примечания - полезные комментарии общего характера по модулю.

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

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

Методы проектирования архитектуры делятся на две группы:

1) ориентированные на обработку и 2) ориентированные на данные.

3. Построение модели в большинстве случаев является непростой задачей. Чтобы приобрести опыт в моделировании, необходимо изучить как можно больше извест­ных и удачных моделей.

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

При дедуктивном подходе (рис.3.3) рассматривается частный случай общеизве­стной фундаментальной модели. Здесь при заданных предположениях известная модель приспосабливается к условиям моделируемого объекта. Например, можно построить модель свободно падающего тела на основе известного закона Ньютона та = mg - Fconp и в качестве допустимого приближения принять модель равноуско­ренного движения для малого промежутка времени.

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

4. Разработка алгоритма - самый сложный и трудоемкий процесс, но и самый ин­тересный в творческом отношении. Выбор метода разработки зависит от постанов­ки задачи, ее модели. (О некоторых приемах и методах разработки алгоритмов говорилось ранее в гл. 1 и будет сказано в следующих разделах данной главы.) На этом этапе необходимо провести анализ правильности алгоритма, что очень непросто и трудоемко. Наиболее распространенная процедура доказательства правильности алгоритма - это прогон его на множестве различных тестов. Однако, это не гарантирует того, что не может существовать случая, в котором программа <<не сработает». В общей методике доказательства правильности алгоритма предпо­лагают, что алгоритм описан в виде последовательности шагов. Для каждого шага предлагается некое обоснование его правильности для всех подходящих входных (условиях до данного шага) и выходных данных (условиях после этого шага). Затем предлагается доказательство конечности алгоритма с окончательными исходными входными и выходными данными.

5. На этапе реализации алгоритма происходит конструирование и реализация алгоритма, включая:

• кодирование; • интеграцию; • тестирование (сертификацию).

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

подпрограмм, модулей и объектов.

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

Перед началом эксплуатации программы необходим этап ее отладки и тести­рования.

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

7. Существуют различные способы тестирования программ.

Тестирование программы как «черного ящика» (стратегия «черного ящика» оп­ределяет тестирование с анализом входных данных и результатов работы программы). Критерием исчерпывающего входного тестирования является использование всех возможных наборов входных данных.

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

Разумная и реальная стратегия тестирования - сочетание моделей «черного» и «белого ящиков».

Принципы тестирования:

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

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

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

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

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

• тестирование - процесс творческий.

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

Инспекция и сквозной просмотр - это набор процедур и приемов обнаружения ошибок при чтении текста.

Основные типы ошибок, встречающихся при программировании:

• обращения к переменным, значения которым не присвоены или не инициали­зированы;

• выход индексов за границы массивов;

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

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

• ошибочные передачи управления и • логические ошибки.

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

8. Есть золотое правило программистов – оформляй свои программы в том виде, в котором ты хотел бы видеть программы, написанные другими. К каждому конечному программному продукту необходимо документированное сопровождение в виде помощи (help), файлового текста (readme.txt).

Билет 4

Задание 1.

Описать систему команд исполнителя «Геометр», который мог бы выполнять геометрические построения с помощью циркуля и линейки.

Вопросы:

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

- организовать деятельность учащихся и управлять ею в процессе решения задачи;

- подбирать средства для решения учебной задачи;

- формулировать организационные и управляющие вопросы по решению задачи;

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

 

 

Задание 2.

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

Вопросы:

1. Какую роль в компьютерных программах играют процедуры и функции? В чем их различия?

2. В чем суть и особенности использования рекурсивных алгоритмов в компьютерных программах? Приведите примеры.

 

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

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

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

Описание и вызов. В Паскале подпрограммы называются процедурами и функ­циями и описываются в разделе с тем же названием.

Процедура имеет такую же структуру, как и программа, но с двумя отличиями:

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

• описание процедуры заканчивается точкой с запятой (а не точкой).

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

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

procedure <имя> (<список описаний формальных параметров>) Описание формальных параметров может иметь вид

<список имен>: <тип> или var <список имен>: <тип>

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

Оператор вызова процедуры имеет вид

<имя процедуры> (<список выражений>);

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

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

Пример: составим программу, которая с помощью строки символов разделит экран на части, где напечатает таблицу квадратных корней для чисел 1, 2,..., 10 и таблицу натуральных логарифмов для чисел 1, 2,..., 5.

Функция - это подпрограмма, определяющая единственное скалярное, вещественное или строковое значение. Отличия подпрограммы-функции от процедуры:

• заголовок функции начинается со служебного слова function и заканчивается указанием типа значения функции:

function <имя> (список описаний формальных параметров): <тип>;

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

• обращение к функции - не оператор, а выражение вида

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

т.е. могут быть рекурсивными.

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

сравнит их по величине.

В программе определим рекурсивную функцию nod(x,y) по формулам

Применяя эти формулы к числам 21 и 15, последовательно находим nod(21,15) = nod(6,15) = nod(15,6) = nod(3,6) = nod(6,3) = nod(0,3) = nod(3,0) = 3.

Программа 19

program four;

var a,b,c,d,m,n:integer;

function nod(x,у: integer) '.integer;

var h:integer;

begin

if y=0 then h:=x

else if x<y then h:=nod(y,x) else h:=nod(x mod у, у); nod:=h end; begin

writeln('введите 4 натуральных числа¹)»

read(a,b,c,d); writeln;

m:=nod(a,b); n:=nod(c,d);

writeln ('нодС, a, ', ',b, ') = ',m);

writeln('нод(',c,',',d,')=',n);

if m>n then writeln('первый > второго')

else if m<n then writeln(' первый < второго')

else writeln('нод пар равны') end.

2.Рекурсия - это такой способ организации вычислительного процесса, при котором подпрограмма в ходе выполнения составляющих ее операторов обращается сама к себе. Рассмотрим классический пример - вычисление факториала (пример 18). Программа вводит с клавиатуры целое число N и выводит на экран значение N!, которое вычисляется с помощью рекурсивной функции РАС. Для выхода из программы необходимо либо ввести достаточно большое целое число, чтобы вызвать переполнение при умножении

чисел с плавающей запятой, либо нажать Ctrl-Z и Enter. При выполнении правильно организованной рекурсивной подпрограммы осуществляется многократный переход от некоторого текущего уровня организации алгоритма к нижнему уровню последовательно до тех пор, пока, наконец, не будет получено тривиальное решение поставленной задачи. В примере 8.5 решение при N = 0 тривиально и используется для остановки рекурсии. Пример 8.5

Program Factorial;

{$S+} {Включаем контроль переполнения стека}

var

n: Integer;

Function Facfn: Integer): Real;

{Рекурсивная функция, вычисляющая n! }

begin {Fac}

if n < 0 then

WriteLn ('Ошибка в задании N')

else

if n = 0 then

Fac:= 1

else Fac:= n * Fac(n-l)

end {Fac};

{---------------}

begin {main} repeat

ReadLn (n);

WriteLn ('n!= ',Fac(n))

until EOF

end {main}.

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

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

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

procedure RETR; begin

инициализация начального хода repeat выбор очередного хода

if подходит then его запись; if решение не полное then RETR;

if неудача then стирание хода и возврат на предыдущий until удача or нет хода end.

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

Программа 39

program tur;

var i, j, ii, jj, n, nn: integer; q: boolean;

dx, dy:array[1..8] of integer; h: array[1..8,1..8] of integer; (*рекурсивная процедура - попытка сделать ход*) procedure try(i,x,у:integer; var q:boolean);

var k, u, v: integer; ql: boolean; begin

k:=0; repeat k:=k+l; ql:=false; u:=x+dx[k]; v:=y+dy[k];

if { (K=u)and(u<=n)and(K=v)and(v<=n)) and(h[u, v]=0)

then begin h[u,v]:=i;

(*для отладки и наблюдения процесса поиска с возвратом*) for ii:=l to n do begin for jj:= 1 to n do

write(h[ii,jj]:5); writeln; end; readln;

if i<nn then begin try(i+l,u,v,ql); if not(ql) then h[u,v]:=0 else ql:=true; end

else ql:=true end;

until (ql) or (k=8); q:=ql;

end; (*конец процедуры*) begin

dx[l]:=2; dx[2]:=l; dx[3]:=-l; dx[4]:=-2; dx[5]:=-2;

dx[6]:=-l; dx[7]:=l; dx[8]:=2; dy[l]:=1; dy[2]:=2;

dy[3]:=2; dy[4]:=1; dy[5]:—1; dy[6]:=-2;

dy[7]:=-2; dy[8]:—1;

write('введи n: '); readln(n);

for i:=l to n do for j:=l to n do h[i,j]:=O;

write('введи i,j: '); readln(i,j); nn:=n*n;

h[i, j]:=1; try (2, i, j,q);

if q then begin

for i:=l to n do begin

for j:= 1 to n do write(h[i,j]:5); writeln; end; end

else writeln('нет маршрута¹); readln end.

Билет 5

Задание 1.

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

Вопросы:

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

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

3. Предложите форму организации учебного процесса для успешного решения задачи.

4. Какие умения учащихся можно проверить в процессе решения задачи?

 

Задание 2.

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

Вопросы:

1. В чем суть объектно-ориентированной парадигмы программирования?

2. Что такое объект, класс, инкапсуляция, наследование и полиморфизм?

 

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

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

Основные шаги разработки программы, предусмотренные данной методологией

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

Большинство современных языков и систем программирования развивается в направлении все большего использования объектной методологии в создании программ. Характерными примерами являются универсальные языки Паскаль, СИ и даже Бейсик, в современных версиях которых появились средства объектно-ориентированного программирования. Так, начиная с версии 5.5, Турбо-Паскаль охватывает метод проектирования программ на основе объектно-ориентирован­ного программирования.

 

2. Объект в Турбо-Паскале - это структура данных, содержащая поля данных раз­личных типов и заголовки методов и обобщающая структуру «Запись» (record). Методы – это процедуры и/или функции, объявленные или действующие внутри объекта. Синтаксис описания объекта:

<ИмяПотомка>=

оЬ j ес^<ИмяПредка> поле;

поле;

метод;

метод; end;

Инкапсуляция. Основой решения задачи является задание положения (позиции отдельной точки на экране, описываемого координатами X и Y. Для задани* координат подходит тип «запись»:

Pozition = record X, У: integer; end;

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

procedure Init(CoordX, CoordY: integer);

begin

X: = CoordX;

Y: = CoordY;

end;

Затем потребуется знание фактических значений координат. Для этого вводим две функции:

function GetX: integer;

begin

GetX: = X;

end;

function GetY: integer;

begin

GetY: - Y;

end;

Наследование. Рассмотрим точку с координатами X и Y. Ее можно сделать ви­димой или невидимой, ей можно задать цвет, ее можно переместить. Создадим объект с такими возможностями:

Point=object

X,Y: integer;

procedure Init(CoordX, CoordY: integer);

function GetX: integer;

function GetY: integer;

Visible: Boolean;

Color: Word;

procedure Init(CoordX, CoordY: integer; InitColor: Word);

function Is Visible: Boolean;

procedure Show;{показывает точку}

procedure Blind;{стирает точку}

procedure Jump(NextX, NextY: integer);{перемещает точку} end;

Заметим, однако, что поля X,Y и методы GetX, GetY практически совпадают с соответствующими полями и методами объекта Pozition.

Турбо-Паскаль предоставляет возможность учесть эту ситуацию. Следует счи­тать тип объекта Point порожденным типом Pozition, записав это следующим образом:

Point=object(Pozition)

Visible: Boolean;

Color: Word;

procedure Init(CoordX, CoordY: integer; InitColor: Word);

function Is Visible: Boolean;

procedure Show;

procedure Blind;

procedure Jump(NextX, NextY: integer); end;

Объект Point теперь наследует свойства объекта Pozition. Поля X,Y явно не за­даны в Point, но Point ими обладает благодаря наследованию, т.е. можно написать

Point.X:=17;

Смысл объектно-ориентированного программирования заключается в работе с полями объекта через его методы.

Полиморфизм. Предположим, надо создать объект «кружок». Очевидно, что новый объект должен иметь предком объект Point, обладая всеми его свойствами, кроме того, быть больше по размеру. Однако, ясно, что «высветить» точку и закрашенную окружность не удастся одними и теми же командами. Турбо-Паскаль разрешает сохранить потомку имя родительского метода, «перекрывая» его. Чтобы перекрыть родительский метод, надо просто задать его с тем же именем, но с другим телом (кодом) и, если необходимо, с другим набором параметров. Такой метод делается виртуальным и к его объявлению добавляется слово virtual. Приме­нение виртуальных методов налагает ограничения на процедуры инициализации, которые должны записываться с зарезервированным словом constructor и иметь общее имя Init.

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

Для очистки и удаления динамически распределенных объектов существует спе­циальная процедура destructorDone.

Деструктор комбинирует шаг освобождения памяти в «куче» с некоторыми дру­гими задачами. Метод деструктора может быть пустым, поскольку работу выпол­няет не только код тела, но и код, генерируемый Турбо-Паскалем в ответ на зарезервированное слово destructor.

Билет 6

Задание 1.

Что нарисует Черепашка по команде REPEAT 4 [TR RIGHT 90], где

TO TR

REPEAT 3 [ FORWARD 40 RIGHT 120]

END?

Вопросы:

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

2. Сформулируйте этапы решения этой задачи учащимися.

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

4. В чем заключается достоинство учебных исполнителей типа Черепашки.

 

Задание 2.

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

Вопросы:

1. В чем суть понятий алгоритма и исполнителя? Перечислите их основные свойства.

2. Каковы особенности различных подходов и парадигм в развитии программирования? Приведите классификацию языков программирования.

 

1. Алгоритм – это точное и понятное предписание исполнителю совершить некоторую последовательность действий на решение поставленной задачи.

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

1) Описываемый процесс должен быть разбит на последовательность отдельных шагов (дискретность);

2) Алгоритмы составляются с ориентацией на определенного исполнителя (нужно знать, какие команды этот исполнитель может понять и исполнять, а какие не может);

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

4) Результативность (за конечное число шагов должен получиться определенный результат);

5) Массовость (наиболее распространены алгоритмы, обеспечивающие решение не одной конкретной задачи, а некоторого класса задач данного типа)

Любой алгоритм для своего исполнения требует исполнителя.

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

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

Основная характеристика исполнителя: система команд исполнителя – это конечное множество команд, которое понимает исполнитель.

Понятие исполнителя выполняет в информатике несколько функций:

1. Дидактическое средство для придания процессу исполнителя

алгоритма наглядности (понятности).

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

информатики.

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

В практике алгоритмизации принято делить все алгоритмы на 2 класса:

1) Алгоритмы “в обстановке”;

2) Алгоритмы работы с величинами.

Под алгоритмами “в обстановке” понимаются те, которые не содержат

вершин, а также не содержат команд изменения значений каких-то величин.

Примерами таких исполнителей явл-ся: машинист, чертёжник, робот.

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

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

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

 

 

2. Парадигма – это некоторый набор идей и рекомендация, определяющих стиль написания программ.

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

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

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

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

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

Эта структура называется также «ЕСЛИ - ТО - ИНАЧЕ», или «развилка». Каж­дый из путей (ТО или ИНАЧЕ) ведет к общей точке слияния, так что выполнение программы продолжается независимо от того, какой путь был выбран.

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

Цикл (или повторение) предусматривает повторное выполнение некоторого на­бора команд программы. Если бы циклы не существовали, вряд ли занятие про­граммированием было бы оправданным: циклы позволяют записать длинные последовательности операций обработки данных с помощью небольшого числа повторяющихся команд. Разновидности цикла изображены на рис. 1.22 и рис. 1.23.