Воспользуемся приемами модульного программирования для создания программного кода.
Модульность в языках программирования — принцип, согласно которому программное средство (ПС, программа, библиотека, веб-приложение и др.) разделяется на отдельные именованные сущности, называемые модулями. Модульность часто является средством упрощения задачи проектирования ПС и распределения процесса разработки ПС между группами разработчиков. При разбиении ПС на модули для каждого модуля указывается реализуемая им функциональность, а также связи с другими модулями.
Программный код часто разбивается на несколько файлов, каждый из которых компилируется отдельно от остальных. Такая модульность программного кода позволяет значительно уменьшить время перекомпиляции при изменениях, вносимых лишь в небольшое количество исходных файлов, и упрощает групповую разработку. Также это возможность замены отдельных компонентов (таких как jar-файлы, so или dll библиотеки) конечного программного продукта, без необходимости пересборки всего проекта (например, разработка плагинов к уже готовой программе).
Работа с программой «Алгоритм 2» (Урок № 1 вступление)
Одним из методов написания модульных программ является объектно-ориентированное программирование. ООП обеспечивает высокую степень модульности благодаря таким свойствам, как инкапсуляция, полиморфизм и позднее связывание.
Для контроля структуры программы можно использовать три метода:
1. Статический контроль,
2. Смежный контроль,
3. Сквозной контроль.
Статический контроль состоит в оценке структуры программы сточки зрения хорошо ли программа разбита на модули с учетом значений рассмотренных выше основных характеристик модуля.
Смежный контроль сверху — это контроль со стороны разработчиков архитектуры и внешнего описания ПС. Смежный контроль снизу — это контроль спецификации модулей со стороны разработчиков этих модулей.
Сквозной контроль — это мысленное прокручивание (проверка) структуры программы при выполнении заранее разработанных тестов. Является видом динамического контроля так же, как и ручная имитация функциональной спецификации или архитектуры ПС.
Следует заметить, что характер осуществления этих методов контроля зависит от выбранного метода разработки структуры программы: при классическом подходе они применяются до начала программирования модулей, а при конструктивном и архитектурном подходах — в процессе программирования модулей (в подходящие моменты времени).
Для контроля процесса разработки в составе каждого модуля будем применять архитектурный подход.
Архитектурный подход к разработке программы представляет собой модификацию восходящей разработки, при которой модульная структура программы формируется в процессе программирования модуля.
Обычно сначала выделяются и реализуются отдельными модулями более простые функции, а затем постепенно появляются модули, использующие ранее выделенные функции.
Это позволяет существенно сократить трудозатраты на разработку конкретной программы путем подключения к ней заранее заготовленных и проверенных на практике модульных структур нижнего уровня. Так как такие структуры могут многократно использоваться в разных конкретных программах, то архитектурный подход может рассматриваться как путь борьбы с дублированием в программировании. В связи с этим программные модули, создаваемые в рамках архитектурного подхода, обычно параметризуются для того, чтобы усилить применимость таких модулей путем настройки их на параметры.
Как программировать на русском языке | Алгоритмы
Источник: studentopedia.ru
Как перевести алгоритм в программу
При программировании на Delphi или Паскале иногда попадаются задачи, которые трудно «втиснуть» в стандартные конструкции языка. А решение лежит совсем рядом — в теории конечных автоматов. Мы не будем залезать в дебри, а просто покажем как это делается.
- Перед началом
- Лирическое отступление
- Зачем это надо
- Немного теории
- И как же это делается ?
- Осознание: некоторые следствия и последствия
- «Отмазка»
Рассуждения об алгоритмах — как раз такой особый случай.
Лирическое отступление
Однажды, еще в школе, на уроке алгебры, я в первый раз услышал о существовании формальных преобразований. Помнится это были (a+b) 2 .
Это было нечто! Меня поразила сама возможность выполнять ряд простых шагов и гарантированно получать правильный результат.
Ну а уж потом были примеры из тригонометрии: четырехэтажные дроби с ужасным количеством синусов, косинусов и бесконечно длинными аргументами, которые путем небольшой игры ума сворачивались в робкое 1+sin(x), а то и просто в неприметную 1.
С тех самых пор я весьма неравнодушен к формальным преобразованиям и стараюсь найти им применение в программировании. И, вы знаете, иногда получается! 🙂
Давным-давно, когда люди еще не придумали объектно-ориентированное программирование, модным направлением было программирование структурное . Шутки шутками, но в результате именно структурного подхода мы сейчас имеем Pascal и Delphi .
Почему я говорю то Паскаль, то Дельфи? Просто потому, что лингвистическая основа Delphi — это Object Pascal, сильно выросший из детских штанишек, но все же узнаваемый. И новые объектно-ориентированные возможности и замечательные библиотеки классов в совокупности с CASE-средствами так и не скрыли полностью длинные уши структурного языка (и это замечательно!). Они вылезают то здесь, то там, в отдельных процедурах, в обработчиках событий. 🙂
Так вот, в те давние времена возникла следующая ситуация:
-
«Сочинение» алгоритмов решения различных задач — процесс творческий, а творчество очень не любит каких-либо ограничений. Cтало быть алгоритм может быть любым, сколь угодно запутанным, образующим петли и прочие нелинейности.
(Особенно этим грешат процедуры, занимающиеся разного рода синтаксическим разбором.)
В нашем запутанном алгоритме наверняка не все так ужасно, как кажется. Скорее всего, там можно найти несколько фрагментов, подходящих под определение чисто структурных конструкций. Вопрос лишь в том, как эти конструкции соединить между собой.
А вот в этом как раз может помочь наша рабочая лошадка — непотопляемая конструкция REPEAT-CASE. При умелом применении эта нехитрая пара команд может «переварить» алгоритм любой сложности и запутанности. Главное, чтобы ВЫ четко представляли что делаете. Однако хватит нам ходить вокруг да около, не пора ли заняться делом?
Да нет, конечно! Если приглядеться, он легко разбивается на 3 вложенные стандартные структуры:
repeat while C1 do B1; if C2 then B2 else B3; until C3;
И все! Очень красиво и компактно, спасибо большое дедушке Вирту.
Как было бы хорошо, если бы в жизни нам попадались только такие алгоритмы. Однако в таком случае, вам незачем было бы читать эту статью! 🙂
| А что вы скажете на это: | Выглядит вроде просто, это мы мигом! |
Гмм.. да.. пробуем и так и эдак — в стандартный Паскаль это явно не укладывается. Можно, конечно, попытаться «расшить» процедурные блоки B1 и B3 или применить GOTO или EXIT из цикла. Но все это, согласитесь, выглядит как-то жалко и самодеятельно. Опять же надо каждый раз думать где разомкнуть цикл.
И вот тут-то появляемся мы, (на белом коне !-) с нашей универсальной отмычкой по имени REPEAT-CASE.
-
Выделяем в нашем алгоритме фрагменты, которые хорошо укладываются в структурную модель (если такие есть). В нашем случае такой фрагмент только один: B2 + C2, т.е. последовательность из блока и условия.
( Если вы считаете, что фрагмент можно взять несколько шире и включить в него C1+B2+C2, я с вами соглашусь, но см.ниже)
- на входе в модуль (обозначим ее 1 )
- на выходе модуля (обозначим 0 )
- на входах и выходах всех фрагментов, что мы нашли
- во всех местах, где есть пересечение линий на блок-схеме
var State:integer; begin State:=1; repeat case State of . end; until State=0; end;
case State of 1: begin B1; if C1 then State:=2 else State:=3 end; 2: begin B2; if C2 then State:=0 else State:=3 end; 3: begin B3; State:=1 end; end;
Осознание
А теперь, после того, как мы добились столь блестящего результата, давайте осознаем: что же мы сделали и что у нас получилось.
- Мы изобразили наш алгоритм как блок-схему или, другими словами, направленный граф
- Затем провели инвариантное преобразование этого графа с выделением нескольких стационарных состояний программы — конечного автомата
- В результате получили новый граф, который легко укладывается в структурные конструкции Паскаля (Delphi)
Проводя указанные действия несколько раз для разных алгоритмов, можно заметить, что на самом деле наши произвольно расставленные точки-состояния не такие уж случайные и произвольные. Как правило, при более глубоком рассмотрении вашего конкретного алгоритма можно найти каждому из этих состояний свое название. Это название может быть гораздо более выразительным, чем просто 1-2-3, поскольку это действительно состояния вашей программы.
О чем я говорю? Пусть ваш алгоритм занимается, скажем, синтаксическим разбором HTML-файла. Тогда одно из состояний может звучать как «Обнаружен тэг BODY» или «Найден конец документа».
Паскаль предлагает нам замечательное средство для работы с такими обозначениями в символическом виде и об этом средстве сейчас часто забывают. Программа из нашего примера может выглядеть так:
var State:(START, EOF_found, Line_Added, DONE); begin State:=START; repeat case State of START: begin B1; if C1 then State:=EOF_Found else State:=Line_Added end; EOF_Found: begin B2; if C2 then State:=DONE else State:=Line_Added end; Line_Added: begin B3; State:=START end; end; until State=DONE; end;
Замечательно, что Delphi все еще поддерживает эту спецификацию и даже показывает при отладке символьное представление состояния! Это очень удобно на практике. Спасибо, Borland!
Возможно вы, как и я, проделав подряд несколько таких преобразований и войдя во вкус, заметите, что стали мыслить при программировании чуть-чуть иначе. Иногда, особенно когда задача несколько запутана, хочется сразу выделить несколько важных состояний и строить обработчик уже вокруг них. Это правильное желание, ему стоит потакать. 🙂
Кстати, сейчас тема конечных автоматов вновь стала актуальной и то и дело мелькает на страницах компьютерных журналов.
Небольшое исследование: крайние случаи
Как сказал один мудрый человек, «Идея, доведенная до абсурда, часто превращается в свою противоположность» . Давайте попробуем довести наш метод до крайней степени.
В нашем случае это означает добавление еще двух состояний — 4 и 5. Тогда программа примет вид:
case State of 1: begin B1; State:=4 end; 2: begin B2; State:=5 end; 3: begin B3; State:=1 end; 4: if C1 then State:=2 else State:=3; 5: if C2 then State:=0 else State:=3; end;
Хорошо это или плохо?
Хорошо, в том смысле, что даже при таком издевательстве программа не перестает работать правильно. С другой стороны, посмотрите на исходный код: где прозрачность, где легкость и ясность? Суть алгоритма растворена в сплошных переходах состояний и из-за этого теряется.
Нет, пожалуй этот вариант нам не подходит.
А что, если пойти в другую сторону и уменьшить число выделенных состояний? В нашем примере реально только исключить состояние 2 .
(Да, я знаю, на блок-схеме двойка есть, но давайте пока ее не замечать, OK? 🙂
После «приведения подобных» программа будет иметь следующий вид:
case State of 1: begin B1; State:=3; if C1 then begin B2; if C2 then State:=0 end end; 3: begin B3; State:=1 end; end;
(Если непонятно, то здесь формально получаются две ветки ELSE, ведущие обе к третьему состоянию. Если состояние вынести вверх, до условия, то программа получается короче. Впрочем, это — дело вкуса 🙂
Как вам этот вариант? Мне кажется он тоже имеет право на жизнь, хотя лично мне вариант с четырьмя состояниями нравится больше. Как-то он нагляднее показывает что куда переходит и при каких условиях. А вам? Предвижу возражения такого толка, что при подобном подходе программы будут иметь повышенную склонность к зацикливанию.
И да и нет. Циклы вообще склонны к зацикливанию 🙂 особенно если написать что-нибудь вроде repeat until false; . Так на то и голова дана, чтобы карась не дремал!
А если серьезно, то устойчивость работы преобразованных таким образом программ прямо и недвусмысленно показывает, насколько удачно вы проработали исходную блок-схему и насколько аккуратно ее преобразовали. Поскольку на то оно и инвариантное преобразование, чтобы ничего не менять в смысле и логике программы , а затрагивать лишь ее внешнее представление .
Возможно кто-нибудь захочет поручить и само это преобразование программе, это мог бы быть компонент Delphi или отдельная утилита, этакий Diagram Automation Wizard. Если такое случится, мне бы очень хотелось посмотреть на результат.
И, наконец, мне нужно расставить точки над i.
Я ни в коей мере не претендую на авторство в данном формальном подходе, более того, все проблемы и решения, изложенные в этой статье, известны уже довольно давно. Моя цель была просто напомнить вам об одном красивом, но, боюсь, забытом подходе к программированию на Паскале и Delphi.
Пишите, если надумаете чем поделиться,
George Columbow
Источник: citforum.ru
7. Этапы решения задач на компьютере. Понятия структуры данных, алгоритма, программы. Перевод программы в машинные коды.
Для перевода программы с языка программирования в машинные коды, понятные компьютеру, существуют специальные программы – трансляторы. Трансляторы бывают двух видов: интерпретаторы и компиляторы.
Интерпретаторы переводят в машинный код (или некое промежуточное представление) и сразу выполняют каждый оператор программы
Компиляторы переводят весь текст программы в машинный код, затем его можно использовать отдельно от исходного текста. Компиляторы полностью просматривают весь текст программы (исходный код) в поисках синтаксических ошибок, выполняют определенный смысловой анализ и затем автоматически переводят на машинный язык — генерируют машинный код.
Структуры данных — это совокупность элементов данных и отношений между ними. Программа на python – это последовательность команд, выполняемых с верху в низ Алгоритм – четко определенная последовательность действий (элементарных операций, инструкций), приводящая, при их реализации исполнителем , к решению некоторой задачи.
8. Современные языки программирования. Поколения языков программирования. Распространённые классификации языков программирования.
Языки программирования – формальная знаковая система, предназначенная описанию структур данных и алгоритмов приводной для дальнейшей компиляции (интерпретации) и выполнения на компьютере.
Современные языки программирования:
JavaScript, Java, PHP, Python, C++, C#, CSS, Ruby, Swift и тд
Поколения языков программирования:
Машинный код (команды x86, ARM, MIPS, GPU)
Языки ассемблера (fasm, gas, PTX)
- Языки третьего поколения (3GL)
ЯВУ (COBOL, Java, C/C++, BASIC, ADA, C#, Python, Perl, PHP, Algol)
- Языки четвертого поколения (4GL)
ПОЯ, DSL (SQL, 1C, ABAP, XUL, CLIPPER, Oracle Reports, а также LISP, Forth)
Логическое программирование, естественный язык, визуальное программирование (Prolog, РЕФАЛ, OPS5, Mercury, Yahoo! Pipes)
Классификации языков программирования:
— Декларативные: Логические, Функциональные.
9. Алгоритм. Свойства алгоритмов. Основы алгоритмизации, типы алгоритмов. Способы описания алгоритмов
Алгоритм — набор инструкций, описывающих порядок действий исполнителя для достижения некоторого результата.
Дискретность — алгоритм должен представлять процесс решения задачи как последовательное выполнение некоторых простых шагов. При этом для выполнения каждого шага алгоритма требуется конечный отрезок времени, то есть преобразование исходных данных в результат осуществляется во времени дискретно.
— дискретность – разбиение процесса решения задачи на элементарные шаги
-определенность – в кажд момент вр след шаг работы алгоритма однозначно определяется состоянием системы
— понятность – кажд команда очевидна для исполнителя
— результативность – алгоритм долже заканчивать раб и приводитть к рез-ту
— универсальность – применение к различ исходным данным
— корректность – правильные р-таты для любых допустимых занчений исход данных
-текстуальные формы ( словесное, формульно-словесное)
— псевдокод (исп формальные язки прогр)
— схематич (диаграммы, графич)
- Алгоритмизация это раздел информатики, изучающий методы и приемы построений алгоритма, а также их свойства.
- Алгоритм может быть записан различными способами:
Словесное описание (на естественном языке) алгоритма представляет собой описание структуры алгоритма на естественном языке. Формальное описание — на формализованном языке, например, на языке программирования. Графическое описание алгоритма в виде блок-схемы – это описание структуры алгоритма с помощью геометрических фигур с линиями связи
Блок схема алгоритма – это графическое представление метода решения задачи, в которым используются специальные символы для отображения операций.
Источник: studfile.net