Алгоритмы в программировании c. Роль алгоритмов в программировании
Алгоритм Кнута-Морриса-Пратта
Алгоритм Кнута-Морриса-Пратта (КМП) получает на вход слово X=xx... x[n] и просматривает его слева направо буква за буквой, заполняя при этом массив натуральных чисел l... l[n], где l[i]=длина слова l(x...х[i]) (функция l определена в предыдущем пункте). Словами: l[i] есть длина наибольшего начала слова x...x[i], одновременно являющегося его концом.
Какое отношение все это имеет к поиску подслова?
Другими словами, как использовать алгоритм КМП для определения того, является ли слово A подсловом слова B?
Решение. Применим алгоритм КМП к слову A#B, где # - специальная буква, не встречающаяся ни в A, ни в B. Слово A является подсловом слова B тогда и только тогда, когда среди чисел в массиве l будет число, равное длине слова A.
Описать алгоритм заполнения таблицы l...l[n].
Решение. Предположим, что первые i значений l...l[i] уже найдены. Мы читаем очередную букву слова (т.е. x) и должны вычислить l.
Другими словами, нас интересуют начала Z слова x...x . Слово Z" является началом и концом слова x...x[i]. Однако не любое слово, являющееся началом и концом слова x...x[i], годится - надо, чтобы за ним следовала буква x.
Получаем такой рецепт отыскания слова Z. Рассмотрим все начала слова x...x[i], являющиеся одновременно его концами. Из них выберем подходящие - те, за которыми идет буква x. Из подходящих выберем самое длинное. Приписав в его конец х, получим искомое слово Z. Теперь пора воспользоваться сделанными нами приготовлениями и вспомнить, что все слова, являющиеся одновременно началами и концами данного слова, можно получить повторными применениями к нему функции l из предыдущего раздела.
Вот что получается:
{таблица l..l[i] заполнена правильно}
while i <> n do begin
{len - длина начала слова x..x[i], которое является
его концом; все более длинные начала оказались
неподходящими}
while (x<>х) and (len>0) do begin
if x=x do begin
{х..x - самое длинное подходящее начало}
{подходящих нет}
Доказать, что число действий в приведенном только что алгоритме не превосходит Cn для некоторой константы C.
Решение. Это не вполне очевидно: обработка каждой очередной буквы может потребовать многих итераций во внутреннем цикле. Однако каждая такая итерация уменьшает len по крайней мере на 1, и в этом случае l окажется заметно меньше l[i]. С другой стороны, при увеличении i на единицу величина l[i] может возрасти не более чем на 1, так что часто и сильно убывать она не может - иначе убывание не будет скомпенсировано возрастанием.
Более точно, можно записать неравенство
l (число итераций на i-м шаге)<= l[i]-l+1 Остается сложить эти неравенства по всем i и получить оценку сверху для общего числа итераций. Будем использовать этот алгоритм, чтобы выяснить, является ли слово X длины n подсловом слова Y длины m. (Как это делать с помощью специального разделителя #, описано выше.) При этом число действий будет не более C(n+m}, и используемая память тоже. Придумать, как обойтись памятью не более Cn (что может быть существенно меньше, если искомый образец короткий, а слово, в котором его ищут - длинное). Решение. Применяем алгоритм КМП к слову А#В. При этом: вычисление значений l,...,l [n] проводим для слова X длины n и запоминаем эти значения. Дальше мы помним только значение l[i] для текущего i - кроме него и кроме таблицы l...l[n], нам для вычислений ничего не нужно. На практике слова X и Y могут не находиться подряд, поэтому просмотр слова X и затем слова Y удобно оформить в виде разных циклов. Это избавляет также от хлопот с разделителем. Написать соответствующий алгоритм (проверяющий, является ли слово X=x...x[n] подсловом слова Y=y...y[m] Решение. Сначала вычисляем таблицу l...l[n]как раньше. Затем пишем такую программу: {len - длина максимального качала слова X, одновременно являющегося концом слова y..j[j]} while (len<>n) and (j<>m) do begin while (x<>у) and (len>0) do begin {начало не подходит, применяем к нему функцию l} {нашли подходящее или убедились в отсутствии} if x=y do begin {x..x - самое длинное подходящее начало} {подходящих нет} {если len=n, слово X встретилось; иначе мы дошли до конца слова Y, так и не встретив X} Алгоритм Бойера - Мура
Этот алгоритм делает то, что на первый взгляд кажется невозможным: в типичной ситуации он читает лишь небольшую часть всех букв слова, в котором ищется заданный образец. Как так может быть? Идея проста. Пусть, например, мы ищем образец abcd. Посмотрим на четвертую букву слова: если, к примеру, это буква e, то нет никакой необходимости читать первые три буквы. (В самом деле, в образце буквы e нет, поэтому он может начаться не раньше пятой буквы.) Мы приведем самый простой вариант этого алгоритма, который не гарантирует быстрой работы во всех случаях. Пусть x...х[n] - образец, который надо искать. Для каждого символа s найдем самое правое его вхождение в слово X, то есть наибольшее k, при котором х[k]=s. Эти сведения будем хранить в массиве pos[s]; если символ s вовсе не встречается, то нам будет удобно положить pos[s]=0 (мы увидим дальше, почему). Как заполнить массив pos? положить все pos[s] равными 0 for i:=1 to n do begin В процессе поиска мы будем хранить в переменной last номер буквы в слове, против которой стоит последняя буква образца. Вначале last=n (длина образца), затем last постепенно увеличивается. {все предыдущие положения образца уже проверены} while last<= m do begin {слово не кончилось} if x[m]<>y then begin {последние буквы разные} last:=last+(n-pos]); {n - pos] - это минимальный сдвиг образца, при котором напротив y встанет такая же буква в образце. Если такой буквы нет вообще, то сдвигаем на всю длину образца} если нынешнее положение подходит, т.е. если x[i]..х[n]=y..y, то сообщить о совпадении; Знатоки рекомендуют проверку совпадения проводить справа налево, т.е. начиная с последней буквы образца (в которой совпадение заведомо есть). Можно также немного сэкономить, произведя вычитание заранее и храня не pos[s], а n-pos[s], т.е. число букв в образце справа от последнего вхождения буквы Возможны разные модификации этого алгоритма. Например, можно строку заменить на last:=last+(n-u), где u - координата второго справа вхождения буквы x[n] в образец. Как проще всего учесть это в программе Решение. При построении таблицы pos написать написать last:=last+n-pos]; Приведенный упрощенный вариант алгоритма Бойера-Мура в некоторых случаях требует существенно больше n действий (число действий порядка mn), проигрывая алгоритму Кнута-Морриса-Пратта. Пример ситуации, в которой образец не входит в слово, но алгоритму требуется порядка mn действий, чтобы это установить. Решение. Пусть образец имеет вид baaa... aa, а само слово состоит только из букв а. Тогда на каждом шаге несоответствие выясняется лишь в последний момент. Настоящий (не упрощенный) алгоритм Бойера-Мура гарантирует, что число действий не превосходит C(m+n) в худшем случае. Он использует идеи, близкие к идеям алгоритма Кнута-Морриса-Пратта. Представим себе, что мы сравнивали образец со входным словом, идя справа налево. При этом некоторый кусок Z (являющийся концом образца) совпал, а затем обнаружилось различие: перед Z в образце стоит не то, что во входном слове. Что можно сказать в этот момент о входном слове? В нем обнаружен фрагмент, равный Z, а перед ним стоит не та буква, что в образце. Эта информация может позволить сдвинуть образец на несколько позиций вправо без риска пропустить его вхождение. Эти сдвиги следует вычислить заранее для каждого конца Z нашего образца. Как говорят знатоки, все это (вычисление таблицы сдвигов и ее использование) можно уложить в C(m+ n) действий. Алгоритм Рабина
Этот алгоритм основан на простой идее. Представим себе, что в слове длины m мы ищем образец длины n. Вырежем окошечко размера n и будем двигать его по входному слову. Нас интересует, не совпадает ли слово в окошечке с заданным образцом. Сравнивать по буквам долго. Вместо этого фиксируем некоторую функцию, определенную на словах длины n. Если значения этой функции на слове в окошечке и на образце различны, то совпадения нет. Только если значения одинаковы, нужно проверять совпадение по буквам. В чем выигрыш при таком подходе. Казалось бы, ничего - ведь чтобы вычислить значение функции на слове в окошечке, все равно нужно прочесть все буквы этого слова. Так уж лучше их сразу сравнить с образцом. Тем не менее выигрыш возможен, и вот за счет чего. При сдвиге окошечка слово не меняется полностью, а лишь добавляется буква в конце и убирается в начале. Хорошо бы, чтобы по этим данным можно было рассчитать, как меняется функция. Привести пример удобной для вычисления функции. Решение. Заменим все буквы в слове и образце их номерами, представляющими собой целые числа. Тогда удобной функцией является сумма цифр. (При сдвиге окошечка нужно добавить новое число и вычесть пропавшее.) Для каждой функции существуют слова, к которым она применима плохо. Зато другая функция в этом случае может работать хорошо. Возникает идея: надо запасти много функций и в начале работы алгоритма выбирать из них случайную. (Тогда враг, желающий подгадить нашему алгоритму, не будет знать, с какой именно функцией ему бороться.) Привести пример семейства удобных функций. Решение. Выберем некоторое число p (желательно простое, смотри далее) и некоторый вычет x по модулю p. Каждое слово длины n будем рассматривать как последовательность целых чисел (заменив буквы кодами). Эти числа будем рассматривать как коэффициенты многочлена степени n-1 и вычислим значение этого многочлена по модулю p в точке x. Это и будет одна из функций семейства (для каждой пары p и x получается, таким образом, своя функция). Сдвиг окошка на 1 соответствует вычитанию старшего члена (хn-1 следует вычислить заранее), умножению на x и добавлению свободного члена. Следующее соображение говорит в пользу того, что совпадения не слишком вероятны. Пусть число p фиксировано и к тому же простое, а X и Y - два различных слова длины n. Тогда им соответствуют различные многочлены (мы предполагаем, что коды всех букв различны - это возможно, если p больше числа букв алфавита). Совпадение значений функции означает, что в точке x эти два различных многочлена совпадают, то есть их разность обращается в 0. Разность есть многочлен степени n-1 и имеет не более n-1 корней. Таким образом, если и много меньше p, то случайному x мало шансов попасть в неудачную точку. Теоретические сведения. Основные понятия. Строка, её длина, подстрока. Понятие о сложности алгоритма. Алгоритмы основанные на методе последовательного поиска. Алгоритмы Рабина, Кнута - Морриса - Пратта, Бойера – Мура. курсовая работа , добавлен 13.06.2007 Организация возможности просмотра текстовых файлов и осуществления поиска нужных слов в тексте. Редактирование текста (шрифт, размер). Алгоритм поиска подстроки в строке (метод Кнута-Морриса-Пратта). Загрузка текста из файла (с расширением.txt). курсовая работа , добавлен 29.05.2013 Поиск в массивах и списках, ключ и произвольные данные. Линейный (последовательный) поиск. Бинарный поиск в упорядоченном массиве. Алгоритм Рабина-Карпа, простая и улучшенная хэш-функция. Алгоритм Бойера-Мура со сдвигом по стоп-символам и по суффиксам. презентация , добавлен 19.10.2014 Исследование понятия алгоритма, особенностей линейных и разветвляющихся алгоритмов. Свойства алгоритма: понятность, точность, дискретность, массовость и результативность. Составление программы для вычисления значения функции и построение её графика. контрольная работа , добавлен 25.03.2013 Изучение определения, описания и вызова функций, указателей и ссылок на них. Написание функции умножения произвольного столбца двумерного массива на const. Умножение 2 столбцов массива на константы. Составление блок-схемы алгоритма и текста программы. лабораторная работа , добавлен 09.01.2012 Основные свойства алгоритма. Формальный и неформальный исполнитель алгоритма, система его команд. Способы записи алгоритма. Словесное описание, построчная запись, опорный конспект. Характеристики алгоритмического языка. Выполнение алгоритма компьютером. презентация , добавлен 04.04.2014 Теоретические и практические аспекты решения прикладных задач с применением функций и процедур структурного (модульного) программирования. Особенности разработки схемы алгоритма и программы для вычисления массива z на языке Turbo Pascal 7.0, их описание. курсовая работа , добавлен 11.12.2009 Характеристика особливостей реалізації пошуку по масиву методами лінійним, бінарним, по "дереву Фібоначе" та екстраполярним на мові програмування Turbo Pascal. Використання алгоритма Рабіна-Карпа та Кнута-Морріса-Пратта для знаходження підрядка в рядку. курсовая работа , добавлен 16.09.2010 Описание принципа работы генетического алгоритма, проверка его работы на функции согласно варианту на основе готовой программы. Основные параметры генетического алгоритма, его структура и содержание. Способы реализации алгоритма и его компонентов. лабораторная работа , добавлен 03.12.2014 Разработка на языке ассемблера алгоритма контроля, на циклический CRC-код, массива данных хранящегося в некоторой области памяти. Сохранение кода для последующей периодической проверки массива данных. Сообщение об искажении данных. Описание алгоритма. Чтобы писать приложения разного уровня сложности, сначала необходимо получить знания по том, как это делается. И начинать желательно с самой основы алгоритмизации и программирования. Вот о них мы и поговорим в рамках статьи. Так называется комплексная техническая наука, задача которой - систематизация приёмов создания, обработки, передачи, сохранения и воспроизведения данных с использованием Также к ней относят принципы функционирования и методы управления, которые помогают достичь цели. Сам термин «информатика» имеет французское происхождения и является гибридом слова «информация» и «автоматика». Возник он благодаря разработке и распространению новых технологий сбора, обработки и передачи данных, которые были связаны с их фиксацией на машинных носителях. Вот какое происхождение имеет информатика. Основы алгоритмизации и программирования являются одним из самых важных направлений данной науки. Перед информатикой стоят такие задачи: Для обозначения технической части часто применяется термин «интерфейс». Вот перед нами произвольная программа. Основы алгоритмизации и программирования всегда используются при создании продуктов массового распространения, которые «должны» завоевать широкую аудиторию. Ведь для популярности разрабатываемое приложение должно оптимально работать и выглядеть. Они могут быть записаны значительным количеством способов. Наиболее популярными являются следующие: Псевдокод. Набросок костяка программы. Как начать создавать свой прообраз программы, функции или процедуры? Для этого достаточно пользоваться такими общими рекомендациями: Представлений алгоритма может быть целых пять. Но вот способов записи всего лишь два: Можно выделить три основных вида: Циклический. Чтобы облегчить себе работу со многими задачами, некоторые участки программного кода имеет смысл многократно повторять. Чтобы не прописывать сколько раз и что нужно сделать, используют циклическую структуру. Она предусматривает наличие последовательности команд, которая будет повторяться до выполнения заданного условия. Использование циклов позволяет многократно снизить трудоемкость написания программы. Важным является на котором будут создаваться программы. Следует учесть, что многие из них «заточены» под конкретные условия работы (например, в браузере). В целом языки программирования делят на две группы: Не процедурные; Процедурные. Можете предположить, какие из них чаще всего применяются? Операторно-процедурные - вот ответ. Они могут быть ориентированы на машины или независимыми. К первым относят ассемблеры, автокоды, символическое кодирование. Независимые делят, основываясь на их ориентации: Каждый из них имеет свою сферу применения. Но для написания программ (полезных приложений или игр) чаще всего используются объектно-ориентрованные языки. Конечно, можно воспользоваться и другими, но дело в том, что они являются наиболее проработанными для создания конечных продуктов потребления для широких масс. Да, и если пока у вас нет точного видения, с чего начать, предлагаю обратить внимание на основы алгоритмизации и объектно-ориентированного программирования. Сейчас это очень популярное направление, по которому можно найти уйму учебного материала. Вообще основы алгоритмизации и языки программирования сейчас нужны ввиду того, что существует недостаток квалифицированных разработчиков, и их важность в будущем будет только расти. При работе с алгоритмами (а в последующем и с программами) следует стремиться продумать все детали до самой мелкой. В последующем выявление каждого непроработанного участка кода приведёт только к дополнительным работам, увеличению затрат на разработку и сроков выполнения задачи. Тщательное планирование и проработка всех нюансов позволит значительно сэкономить время, усилия и деньги. Что ж, сейчас могут сказать, что после прочтения данной статьи у вас есть понятие про основы алгоритмизации и программирования. Осталось только применить эти знания. Если есть желание изучить тему более детально, могу посоветовать книгу «Основы алгоритмизации и программирования» (Семакин, Шестаков) 2012 года. Хорошо, если он обучается на платном отделении, а если за счет государства? Это значит, что кто-то, мечтавший стать архитектором, менеджером, финансистом, военным, не попал на это место. Ему пришлось искать другое место под солнцем, возможно, он пошел учиться на программиста. Приведу несколько жизненных примеров:
«Найди себе дело по душе и ни единой минуты в жизни ты не будешь работать» - Конфуций. Важно не потратить на поиск этого дела всю жизнь, иначе придется всю жизнь «вкалывать». В одной компании, моей знакомой и всему отделу по работе с клиентами показали, как верстать страницы, рассказали, что такое теги. Они даже сверстали простые странички. Но не стоит считать себя после этого знающим все о программировании. Это только начало. А вот дальше надо изучать множество сложных, и попроще материалов и технологий, несколько томов алгоритмов и несчетное число хороших практик и методик. Все же, думаю, большинство «новых программистов» стремятся больше зарабатывать: сидишь себе - деньги получаешь. Правда, потом такие люди сильно подводят свою команду, работают не в полную силу. А если еще и начальство закроет на это глаза (да, да, такое бывает!), то с ними каши не сваришь, google не разработаешь. Как показывают исследования . IT в России - не самая высокооплачиваемая отрасль. Она занимает лишь третье место. На втором месте сырьевые отрасли, а на первом - высший менеджмент . Из-за специфики IT, программист никогда не достигнет ступеньки высшего менеджмента. Максимум, на что стоит рассчитывать, это должность руководителя отдела, ведущего направления, директора собственной компании. Поэтому делайте выводы. Смена рода деятельности серьезный шаг, он должен быть обдуман. Минимум, надо будет изучить современный курс программирования, и это займет не один год. P.S. В комментариях спрашивают про цели заметки: серьезнее относиться в выбору профессии, заниматься только любимым делом, учиться тому что нравится, профессионально расти, а не пробовать все понемногу без определенной цели. Удивляют люди, которые в 30-40 лет так и не смогли найти себе занятие по душе. Введение в экономическую информатику Решение задач на компьютере основано на понятии алгоритма. Алгоритм – это точное предписание, определяющее вычислительный процесс, ведущий от варьируемых начальных данных к исходному результату. Алгоритм означает точное описание некоторого процесса, инструкцию по его выполнению. Разработка алгоритма является сложным и трудоемким процессом. Алгоритмизация – это техника разработки (составления) алгоритма для решения задач на ЭВМ. Для записи алгоритма решения задачи применяются следующие изобразительные способы их представления: Для записи алгоритма существует общая методика: Общий вид алгоритма: Формульно-словесный способ записи алгоритма характеризуется тем, что описание осуществляется с помощью слов и формул. Содержание последовательности этапов выполнения алгоритмов записывается на естественном профессиональном языке предметной области в произвольной форме. Графический способ описания алгоритма (блок - схема) получил самое широкое распространение. Для графического описания алгоритмов используются схемы алгоритмов или блочные символы (блоки), которые соединяются между собой линиями связи. Каждый этап вычислительного процесса представляется геометрическими фигурами (блоками). Они делятся на арифметические или вычислительные (прямоугольник), логические (ромб) и блоки ввода-вывода данных (параллелограмм). Порядок выполнения этапов указывается стрелками, соединяющими блоки. Геометрические фигуры размещаются сверху вниз и слева на право. Нумерация блоков производится в порядке их размещения в схеме. Алгоритмические языки - это специальное средство, предназначенное для записи алгоритмов в аналитическом виде. Алгоритмические языки близки к математическим выражениям и к естественным языкам. Каждый алгоритмический язык имеет свой словарь. Алгоритм, записанный на алгоритмическом языке, выполняется по строгим правилам этого конкретного языка. Операторные схемы алгоритмов. Суть этого способа описания алгоритма заключается в том, что каждый оператор обозначается буквой (например, А – арифметический оператор, Р – логический оператор и т.д.). Операторы записываются слева направо в последовательности их выполнения, причем, каждый оператор имеет индекс, указывающий порядковый номер оператора. Алгоритм записывается в одну строку в виде последовательности операторов. Псевдокод – система команд абстрактной машины. Этот способ записи алгоритма с помощью операторов близких к алгоритмическим языкам. Типы алгоритмических процессов По структуре выполнения алгоритмы и программы делятся на три вида: Линейные вычислительные процессы Линейный алгоритм (линейная структура) – это такой алгоритм, в котором все действия выполняются последовательно друг за другом и только один раз. Схема представляет собой последовательность блоков, которые располагаются сверху вниз в порядке их выполнения. Первичные и промежуточные данные не оказывают влияния на направление процесса вычисления. Алгоритмы разветвляющейся структуры На практике часто встречаются задачи, в которых в зависимости от первоначальных условий или промежуточных результатов необходимо выполнить вычисления по одним или другим формулам. Такие задачи можно описать с помощью алгоритмов разветвляющейся структуры. В таких алгоритмах выбор направления продолжения вычисления осуществляется по итогам проверки заданного условия. Ветвящиеся процессы описываются оператором IF (условие). Циклические вычислительные процессы Для решения многих задач характерно многократное повторение отдельных участков вычислений. Для решения таких задач применяются алгоритмы циклической структуры (циклические алгоритмы). Цикл – последовательность команд, которая повторяется до тех пор, пока не будет выполнено заданное условие. Циклическое описание многократно повторяемых процессов значительно снижает трудоемкость написания программ. Существуют две схемы циклических вычислительных процессов. Особенностью первой схемы является то, что проверка условия выхода из цикла проводится до выполнения тела цикла. В том случае, если условие выхода из цикла выполняется, то тело цикла не выполняется ни разу. Особенностью второй схемы является то, что цикл выполняется хоты бы один раз, так как первая проверка условия выхода из цикла осуществляется после того, как тело цикла выполнено. Существуют циклы с известным числом повторений и итерационные циклы. При итерационном цикле выход из тела цикла, как правило, происходит при достижении заданной точности вычисления. Языки программирования – это искусственные языки записи алгоритмов для исполнения их на ЭВМ. Программирование (кодирование) - составление программы по заданному алгоритму. Классификация языков программирования. В общем, языки программирования делятся на две группы: операторные и функциональные. К функциональным относятся ЛИСП, ПРОЛОГ и т.д. Операторные языки делятся на процедурные и непроцедурные (Smalltalk, QBE). Процедурные делятся на машино - ориентированные и машино – независимые. К машино – ориентированным языкам относятся: машинные языки, автокоды, языки символического кодирования, ассемблеры. К машино – независимым языкам относятся: Бураков П.В., Косовцева Т.Р. Информатика. Алгоритмы и программирование. Учебное пособие.-СПб НИУ ИТМО, 2013. – 83с. Учебное пособие предназначено для студентов экономических специальностей специальности 080100 «Экономика» гуманитарного факультета, изучающих дисциплину «Информатика». Пособие представляет собой вводный курс по построению алгоритмов и по программированию на языке Турбо Паскаль. Пособие содержит много примеров. Подробно излагаются теоретические аспекты построения алгоритмов и основ программирования. Во второй части учебного пособия приводтся лабораторный практикум. В 2009 году Университет стал победителем многоэтапного конкурса, в результате которого определены 12 ведущих университетов России, которым присвоена категория «Национальный исследовательский университет». Министерством образования и науки Российской Федерации была утверждена Программа развития государственного образовательного учреждения высшего профессионального образования «Санкт-Петербургский государственный университет информационных технологий, механики и оптики» на 2009– 2018 годы. © Санкт-Петербургский национальный исследовательский университет информационных технологий, механики и оптики, 2013 ©П.В. Бураков, Т.Р.Косовцева Постановка задачи......................................................................................................................... Разработка математической модели............................................................................................ Выбор метода численного решения............................................................................................. Разработка алгоритма и структуры данных................................................................................ Реализация алгоритма в виде программы................................................................................... Отладка и тестирование программы............................................................................................ Решение задачи на компьютере................................................................................................... ПОСТРОЕНИЕ АЛГОРИТМА РЕШЕНИЯ ЗАДАЧИ............................................................................. Описание алгоритма...................................................................................................................... Схема алгоритма.......................................................................................................................... Структурированные схемы алгоритмов.................................................................................... СРЕДСТВА РЕАЛИЗАЦИИ АЛГОРИТМА.......................................................................................... Критерии выбора языка программирования............................................................................. СТРУКТУРА ПРОГРАММЫ И ЕЕ ЭЛЕМЕНТЫ................................................................................. Основные элементы программирования................................................................................... Алфавит и словарь языка TurboPascal (TPascal)....................................................................... Структура программы................................................................................................................. ТИПЫ ДАННЫХ...................................................................................................................................... Скалярные типы данных............................................................................................................. Структурированные типы данных............................................................................................. ВВОД-ВЫВОД ДАННЫХ....................................................................................................................... Процедуры ввода-вывода........................................................................................................... ОПЕРАТОРЫ............................................................................................................................................ Общие сведения........................................................................................................................... Простые операторы..................................................................................................................... Структурные операторы............................................................................................................. Условные операторы................................................................................................................... Операторы цикла......................................................................................................................... МАССИВЫ................................................................................................................................................ Действия над массивами............................................................................................................. Действия над элементами массива............................................................................................ Операции с матрицами................................................................................................................ ПРОЦЕДУРЫ И ФУНКЦИИ................................................................................................................... Необходимость структуризации в программировании............................................................ Подпрограммы в языке ТPascal.................................................................................................. Процедуры.................................................................................................................................... Функции....................................................................................................................................... Механизм передачи параметров................................................................................................ ФАЙЛЫ..................................................................................................................................................... Общие сведения........................................................................................................................... Описания файлового типа.......................................................................................................... Средства обработки файлов....................................................................................................... Текстовые файлы......................................................................................................................... ЛАБОРАТОРНЫЙ ПРАКТИКУМ.......................................................................................................... Лабораторная работа 1. Программирование линейных и разветвляющихся вычислительных процессов............................................................................................................. Лабораторная работа № 2. Циклические вычислительные процессы................................... Лабораторная работа № 3. Операции с массивами................................................................. Лабораторная работа № 4. Операции с файлами..................................................................... Лабораторная работа 5. Процедуры и функции...................................................................... БИБЛИОГРАФИЧЕСКИЙ СПИСОК..................................................................................................... ЭЛЕМЕНТЫ ТЕХНОЛОГИИ РЕШЕНИЯ ПРАКТИЧЕСКИХ ЗАДАЧ НА КОМПЬЮТЕРЕ Решение задач с применением персонального компьютера включает следующие основные этапы. 1.
Постановка задачи.
2.
Разработка математической модели.
3.
Выбор метода численного решения для расчетных задач.
4.
Разработка алгоритма решения и структуры данных.
5.
Реализация алгоритма в виде программы.
6.
Отладка и тестирование программы.
7.
Решение задачи на компьютере, численные эксперименты и анализ результатов.
Постановка задачи В работе специалиста, проектирующего новое изделие, технологический процесс или решающего определенную практическую задачу для нужд пользователя, сочетаются наука и искусство. Конечным итогом является нахождение подходящего решения и представление его в виде удобном для практического применения. Эффективность решения во многом определяется четким осознанием потребности и точной словесной формулировкой этой потребности в виде цели (или нескольких целей). После этого в исследуемой предметной области собирается информация о тех факторах, которые влияют на достижение конечной цели, о взаимосвязи этих факторов, об ограничениях, связанных с различными сторонами рассматриваемой задачи. Таким образом, создается возможно более полное словесное описание задачи и условий ее решения. Требуется определить длину пути, который проходит тело, движущееся с переменной скоростью. Начальная скорость тела равна 0. С определенной степенью степенью достоверности движение можно считать равноускоренным. Использование пакетов стандартных программ не предполагается. В настоящее время эффективное решение сложных задач базируется на использовании математических моделей. Кроме возможности получения решения целого класса задач применение математических моделей обеспечивает проведение многовариантных расчетов, быструю адаптацию к изменению условий и поиск наилучших решений. Разработка математической модели На основе словесной формулировки задачи выбираются переменные, участвующие в процессе решения, определяется их область изменения, математически описываются связи между этими переменными и ограничения. Выделяются и формально описываются те факторы, которые входят в эти взаимосвязи как параметры. В результате инженерная задача приобретает вид формализованной математической модели. Математической моделью задачи, сформулированной в примере 1 является формула: S
= 0,5 a t
2
,
где в качестве основной переменной выступает время t
, параметром движения является ускорение а
. Формула показывает зависимость между длиной пути и временем в соответствии с законом механики. Следует отметить, что для математического описания зависимостей можно использовать различную степень детализации и различные формы математического описания. Так, в общем случае при движении с переменной скоростью длина пути определяется интегралом S =
∫
V (t)
dt ,
при этом закон изменения скорости V(t) в зависимости от времени может быть достаточно сложным и определить значение интеграла аналитически не удается. Поэтому в большинстве случаев практически целесообразно использовать приближенные методы решения. Особое внимание следует уделять адекватности математической модели по отношению к исходному описанию задачи и условиям ее решения с одной стороны. Неоправданная сложность приводит к ненужным затратам сил, средств и времени. С другой стороны, недостаточная точность математического описания (грубость модели) приводит к большим погрешностям в решении, а иногда и к ошибочным выводам. Выбор метода численного решения Для расчетной задачи необходимо выбрать метод ее численного решения, сводящий решение задачи к последовательности арифметических и логических операций. Разработкой и изучением таких методов занимается раздел математики, называемый численным анализом. В качестве примера численного метода для вычисления определенных интегралов можно привести метод прямоугольников. В этом методе интеграл заменяется конечной суммой ∫
f
(x
)
dx
≈ ∆
x
∑
f
(x
i
)
, где ∆х - шаг интегрирования (const), ∆х=(b-a)/n, x i+1
=xi
+∆
х, x1
=a , xn+1
=b Вычисление приближенного значения определенного интеграла по этому методу сводится к последовательному расчету значений подынтегральной функции, их суммированию и умножению на величину шага интегрирования. При выборе метода надо учитывать требования, предъявляемые постановкой задачи, и возможности его реализации на компьютере: точность решения, быстроту получения результата, требуемые затраты оперативной памяти для хранения исходных и промежуточных данных и результатов (для задач большого объема), сложность программной реализации, трудоемкость подготовки программы и решения задачи. Разработка алгоритма и структуры данных Если выбранный для решения задачи численный метод реализован в виде стандартной библиотечной подпрограммы, то алгоритм обычно сводится к описанию и вводу исходных данных, вызову стандартной подпрограммы и выводу результатов на экран или на печать. Более характерен случай, когда стандартные подпрограммы решают лишь какую-то часть задачи. Четкая структуризация задачи, разбиение ее на последовательность подзадач, реализация подзадач отдельными модулями, постепенная детализация логики алгоритма, использование типовых логических конструкций являются хорошими средствами, позволяющими в разумные сроки создавать работоспособные программы для решения сложных задач. Важной составной частью разработки алгоритма является выбор состава и способов организации (структур) данных: исходных, промежуточных и конечных результатов. Языки программирования, позволяют работать с числовыми и символьными константами, переменными, массивами данных (векторами и матрицами). Так в языке Turbo Pascal допускаются и более сложные структуры данных, удобные для задач обработки нечисловых данных, например текстов, для решения комбинаторных задач и имитационного моделирования. Поэтому выбор состава, типов и структур данных обычно производится с учетом особенностей реализации алгоритма на том или ином входном языке. Если разработчик программы владеет программированием на разных алгоритмических языках, то у него появляется возможность выбрать язык, наиболее соответствующий структуре данных задачи. Разработка алгоритма завершается либо его представлением в виде графической схемы, либо записью с помощью символов специального языка проектирования программ, называемого псевдокодом. Используются также другие средства представления логики алгоритма: диаграммы, таблицы решений, схемы. Реализация алгоритма в виде программы При составлении программы на выбранном языке следует познакомиться с описанием особенностей реализации этого языка. Сначала рекомендуется использовать основные конструкции и типы данных языка, расширяя диапазон применяемых средств по мере приобретения опыта программирования и практического решения задач на компьютере. При разработке и реализации алгоритмов не следует стремиться к получению программ, наилучших по быстродействию, объему требуемой памяти, удобству работы с данными. Дополнительное время, затраченное на разработку, программирование и отладку слишком сложного алгоритма, может обесценить результаты от его применения, так как они будут получены слишком поздно. Важно получить работоспособную программу как можно раньше, жертвуя при этом на первых порах изяществом, компактностью, а порой и вычислительной эффективностью алгоритма. Совершенствование программы можно отложить до более позднего времени, когда проведенные эксперименты позволят уточнить постановку задачи, выяснить сферу применимости программы, требования удобства ввода исходных данных и обработки результатов. С этой точки зрения также полезно использовать принцип модульности при разработке алгоритма, так как программу, составленную из модулей, легче модернизировать. Выделение в программе модулей ввода данных, расчета характеристик, вывода результатов позволит локализовать будущие изменения в программе в пределах каждого модуля, а также использовать некоторые из них в качестве готовых «строительных» блоков для новых задач. Отладка и тестирование программы При программировании и вводе данных с клавиатуры могут быть допущены ошибки. Их обнаружение, локализацию и устранение выполняют на этапе отладки и испытания (тестирования) программы. Одним из критериев профессионального мастерства программистов является их способность обнаруживать и исправлять собственные ошибки: начинающие программисты не умеют этого делать, у опытных программистов особых затруднений это не вызывает. Тем не менее ошибки в программах делают все. По данным разных авторов, этап отладки и тестирования программы занимает от 50 до 70 % времени, затрачиваемого на все этапы создания программы и получения решения. В связи с важностью и трудоемкостью этапа отладки все современные системы программирования имеют специальные средства, помогающие в обнаружении и устранении ошибок. Уже на этапе разработки алгоритма полезно предусмотреть простейшие средства контроля, встраиваемые в разрабатываемую программу: печать введенных данных непосредственно после их считывания в память машины (эхо-печать), печать промежуточных результатов в узловых точках. Но главное - надо максимально упрощать структуру программы за счет расчленения ее на модули, реализуемые в виде подпрограмм или процедур, и использования конструкций языка, наиболее простых и освоенных программистом. Решение задачи на компьютере На этом этапе компьютер выполняет все предусмотренные программой вычисления и выдает результаты на экран или на печать. Чтобы облегчить последующую обработку результатов счета, надо при проектировании программы предусмотреть вывод результатов с пояснениями. Выводимым числам и таблицам результатов должны предшествовать заголовки, одни группы данных следует отделять от других пропусками строк. При табулировании функции полезно указывать и значения аргументов, а если функции зависят от параметров, то перед выдачей значений функции следует указать и значения параметров. При недостаточном опыте программирования не следует увлекаться формой представления результатов, однако какое-то время все же следует уделять этим вопросам, так как в конечном итоге это сокращает трудоемкость последующей обработки данных. Целесообразно отрабатывать форму представления выводимых данных на пробных прогонах программы, анализируя результаты на экране. Контрольные вопросы 1.
Какие факторы влияют на эффективность решения задач на компьютере?
2.
Перечислите этапы решения задач на компьютере.
3.
Каковы основные требования к математической модели задачи?
4.
Назовите главные характеристики алгоритмов.
5.
Какие особенности следует учитывать при разработке программ на компьютере?
6.
Чем завершается разработка алгоритма?
ПОСТРОЕНИЕ АЛГОРИТМА РЕШЕНИЯ ЗАДАЧИ Описание алгоритма Под алгоритмом
понимается конечная последовательность точно сформулированных правил решения некоторого касса задач. Алгоритм обладает следующими свойствами: Определенность.
Все действия, которые необходимо произвести должны быть строго определены. Понятность.
Все действия, которые необходимо произвести, должны быть однозначно поняты и выполнены каждым исполнителем алгоритма. Это свойство может быть интерпретировано как однозначность
алгоритма, под которой понимается единственность толкования исполнителем правил выполнения действий и порядка их выполнения. Конечность
. Обязательность завершения каждого из действий, составляющих алгоритм и завершимость выполнения алгоритма в целом. Результативность
. Если алгоритм применим к данной задаче, то после конечного числа шагов должен быть получен результат. Массовость.
Возможность применения данного алгоритма для решения класса задач, отвечающих общей постановке задачи. Правильность
. Способность алгоритма давать правильные результаты решения поставленных задач. Каждое правило алгоритма записывается в виде повелительного предложения, понимаемого исполнителем алгоритма как команда на выполнение. Рассмотрим алгоритмы решения нескольких задач. Задача 1
.
Составить алгоритм вычисления x по формуле x
=
a
(r
−
q
)
2
,
где p ≠ -12. p +
12
1. Начало; 2. Вычислить b:= p + 12; 3. Вычислить c:= r – q; 4. Вычислить d:= c c; 5. Вычислить e:= a d; 6. Вычислить x:= e / b; 7. Записать результат: x; В записи алгоритма решения задачи 1
введены буквенные обозначения – переменные. Так, через b
обозначено p + 12
, через c
– разность r – q.
Запись b:= p+12
означает, что вначале должна быть найдена сумма p + 12
при определенных значениях p, а затем это значение присваивается переменной b. Придавая a, p, q, r
разные значения, будем получать различные задания на вычисление x
. Поэтому алгоритм обычно позволяет решать не одну, а целый класс задач. Такую особенность алгоритма называют массовостью алгоритма. Возможны алгоритмы, решающие только единственную задачу. Величины a, p, q, r, 12
составляют исходные данные для алгоритма, 12 – постоянную составляющую, a, p, q, r – переменную составляющую информации. Величины b, c, d, e
являются вспомогательными переменными, x
– результат исполнения алгоритма. Алгоритм называется линейным
, если при его исполнении все команды выполняются строго последовательно, без нарушения порядка их следования. Предложенный алгоритм решения задачи 1
является линейным. Следует отметить, что сама формула не является алгоритмом, так как не указан однозначный порядок исполнения операций. Задача 2
. По формуле x
=
−
b
±
b
2
−
4
ac
составить алгоритм решения квадратного уравнения ax2
+ bx + c = 0 (a ≠ 0). 1.
Начало;
2.
p:= 2a;
3.
D:= b
2
– 4ac; 4.
Если D ≥ 0, то перейти к п. 5, иначе к п. 10;
5.
d:=
D
; 6.
x
1
:
=
−
b
−
d
;
p
7.
x
2
:
=
−
b
+
d
;
p
8.
Записать результат: x
1
, x2
; 9.
Перейти к п. 11;
10.
Записать результат: уравнение действительных корней не имеет;
11.
Конец.
При исполнении алгоритма выполняются не все его команды, следовательно, алгоритм решения задачи 2
не является линейным. Кроме арифметических действий и операций извлечения квадратного корня, вычислительный процесс содержит в правиле 4 операцию проверки условия: в зависимости от выполнения условия (да) или невыполнения условия (нет) выбирается одно из двух возможных продолжений. Такой алгоритм называют разветвляющимся. Операцию, которая может изменить последовательность выполнения правил алгоритма, назовем оператором управления. Команды, определяющие порядок исполнения операций, подразделяются на два типа: команды условного перехода
и команды безусловного перехода
. К командам условного перехода относится, например, правило 4 алгоритма решения задачи 2
. Правило 9 содержит безусловный переход. В командах условного перехода обязательно присутствует логическое условие типа: если α
◊
β
, то …(где ◊
- один из операторов >
,
≥
,
<
,
≤
,
=
,
≠
). Схема алгоритма Схема алгоритма представляет собой графическое изображение алгоритма с помощью определенным образом связанных между собой блоков. Каждый блок изображается определенной фигурой. Блоки в схеме соединяются дугами. Дуги указывают порядок следования блоков при исполнении алгоритма. Типы блоков представлены на рисунке 1. Рис.1
. Типы блоков Прямоугольник вместе с заключенным в нем этапом вычисления S
называют функциональным блоком
, или процессом
(рис.1, а). Ромб с заключенным в нем условием P
называют блоком проверки условия
, или решением
(рис.1, б). Он используется для управления порядком исполнения блоков в схеме алгоритма. Из функционального блока выходит одна стрелка, а из блока проверки условия – две. Последнее объясняется тем, что в результате исполнения команды проверки условия получаем либо выполнение (да), либо невыполнение (нет) заданного условия P. Информационный блок
(рис.1, в) используется для ввода и вывода А. Блоки (рис.1, г) и (рис.1, д) называют соответственно начальным
и конечным
. Блок-схема решения задачи начинается в начальном блоке и заканчивается в конечном. Исполнение алгоритма решения задачи осуществляется по схеме в направлении, заданном дугами от начального блока к конечному. В информационных блоках указываются значения параметров, которые задаются исполнителю, и значения переменных, которые вводятся. В функциональных и логических блоках записаны операторы от переменных. Исполнение функциональных блоков осуществляется согласно записанным в них действиям. В логических блоках в результате анализа происходит выбор одной из двух возможных дуг «да» или «нет» и передача управления блоку, на который указывает выбранная дуга. Поэтому при исполнении алгоритма существует всего один путь от начального блока к конечному. При составлении схемы алгоритмов решения задач подразумевается, что значения переменных в операциях, записанных в блоках, уже заданы. Однако для исполнения алгоритмов необходимы специальные указания на то, откуда брать значения этих переменных. На рисунках 2 и 3 изображены схемы алгоритмов решения задачи
нахождения суммы n
- чисел: a1
, a2
, a3
, a4
,.., an
.Подобные документы
Чем она занимается?
Представление алгоритмов
Запись алгоритма
Способы записи
Разрабатываем программную структуру
Программирование
Заключение
Мотивирующее изображение:Проблема
Обычно в разработчики переходят новоиспеченные специалисты до 30-ти лет. И сразу же возникает несколько серьезных проблем:Время
Спрашивается, зачем человек изучал несколько лет не нужные ему науки? Зачем подвергал себя таким умственным нагрузкам? Чтобы потом все бросить и начать все с начала? Даже 5 лет это много. За это время можно стать миллиардером или же получить Нобелевскую премию, так нет, человек изучает то что ему не интересно, спит на парах и говорит, что философия - это полнейший бред!Там же все просто!
Сколько таких новоявленных «программистов», прочитавших о JAVA у Брюса Эккеля. Все они считают себя гениями программирования, а ООП, MVC, Agile, двоичная система исчисления, теория сложности вычислений… не для них.
Могу сказать только одно: если бы программирование было таким простым, то ему бы не учили в университетах по пять лет. Достаточно было бы и трехмесячных курсов .Таланты
Конечно, нельзя не упомянуть про таланты. Есть талантливые люди, которые занимаются разными работами, они везде преуспевают. Но таких крайне мало. Лучше быть компетентным специалистом в одной области, чем в нескольких понемногу. Запах пороха
Очень хорошая идея показать, что представляет собой разработка. Понюхать пороха, так сказать! Вот уже и мэры начали изучать JS .Заключение
Программирование - это ремесло, разработка - сродни искусству. Для обычных людей - это магия, для программистов тяжелый труд, трансляция непостоянства окружающего мира в мир конечных состояний, нулей и единиц, ограничений оперативной памяти, канала и тактовой частоты процессора.Тема 1.3: Системное программное обеспечение
Тема 1.4: Сервисное программное обеспечение и основы алгоритмизации
1.4. Сервисное программное обеспечение ПК и основы алгоритмизации
1.4.2. Основы алгоритмизации и языки программирования
Алгоритм и его свойства
Изобразительные средства для описания (представление) алгоритма
Рис. 1.Принципы разработки алгоритмов и программ
Рис. 2.
Рис. 3.Языки программирования
