Лекции по "Языкам и методам программирования" (PascalABC)

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

Методологический принцип  решения задач на компьютере можно  сформулировать как триаду «модель – алгоритм – программа». Любая практическая задача, как правило, формулируется вначале на естественном языке. Затем человек, пытающийся решить эту задачу, ищет закономерности, позволяющие получить результат, имея заданный набор исходных данных. Как правило, эти закономерности записываются в виде математических соотношений. Совокупность математических соотношений, описывающих данную задачу, называют ее математической моделью.

Поясним сказанное выше примером. Пусть необходимо решить такую задачу. В классе 32 мальчика и 24 девочки, а всего учащихся в  классе 100. В какой системе счисления ведется счет и сколько мальчиков и девочек в классе в системе счисления с основанием 10?

1 этап – построение  математической модели задачи. Обозначим  через х основание неизвестной системы счисления. Тогда 3х+2 – число мальчиков в классе, 2х+4 – число девочек в классе, 1х²+0х+0 – число учеников в классе. В итоге получаем 3х+2+2х+4=х² или х²-5х-6=0. Итак, моделью нашей задачи является квадратное уравнение х² – 5х – 6=0.

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

Выполнив эту программу  для исходных данных р=-5, q=-6, получим результат х1=6, х2=-1. Поскольку в нашем случае основание системы счисления не может быть отрицательным числом, то получили, что основанием системы счисления должно быть число 6. Значит в классе 3*6+2=20 девочек и 2*6+4=16 мальчиков, а всего в классе 6²=36 учеников, что верно так как 20+16=36.

 

 

 

Разработка алгоритма по его математической модели.

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

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

Вернемся к примеру  предыдущего пункта и выполним 3 этап – представление алгоритма  в виде программы. Запишем алгоритм  в виде программы на языке ИнтАл.

 

Программа ur

Описание

p,q: Целый 

d,x1,x2: Вещественный 

Конец_Описания

Ввод(p, 'Ввести значение коэффициента при х')

Ввод(q,'Ввести значение свободного члена')

d:=(p/2)*(p/2)-q

Если d<0

  То Вывод('Уравнение  не имеет корней')

  Иначе x1:=-p/2+Корень(d)

        x2:=-p/2-Корень(d)

        Вывод('x1=',x1,'  x2=',x2)

Конец_Если

Конец_Программы

 

 Алгоритмически неразрешимые задачи.

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

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

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

 

Основные положения  структурного программирования

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

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

Такой подход хорош тем, что:

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

2.Небольшие подпрограммы  легче отладить, что повышает  надежность программы.

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

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

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

1.Ввести массив баллов.

2.Удалить самый высокий  балл.

3.Удалить самый низкий  балл.

4.Вычислить среднее  арифметическое оставшихся баллов.

5.Вывести результат.

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

 

Что такое

объектно-ориентированное программирование

(ООП)

Объектно-ориентированное программирование (ООП) – более прогрессивный метод проектирования программ.

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

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

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

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

ИНКАПСУЛЯЦИЯ

Описание объекта, как и всех других типов должна содержаться  в разделе описаний. Данные, которые  содержит объект, называются полями объекта. Описание простейшего объектного типа очень похоже на описание записи, только вместо зарезервированного слова Record  используется слово OBJECT.

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

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

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