Техника составления алгоритмов и программ для решения задач на компьютере называется
Эта глава, с которой начинается изучение курса, служит двум основным целям:
- подготовить необходимую теоретическую базу для последующего овладения различными методами обработки информации, навыками программирования в малом и построения правильных эффективных программ;
- дать минимально необходимые для практического программирования знания о языке Java и предоставить образцы небольших типовых программ.
В процессе знакомства с теоретическим материалом главы может возникнуть ощущение его оторванности от нужд практики — решения конкретных задач на языке Java. С другой стороны, именно решение задач на программирование должно привести к осознанному пониманию того факта, что написать правильную и эффективную программу совсем не так просто, как это кажется на первый взгляд.
Знание необходимых теоретических основ позволит во второй главе перейти к изучению методов построения программ и доказательства их правильности — теории, которая будет применяться для практического написания программ параллельно со знакомством с ней. Таким образом, два кажущиеся совершенно не связанными друг с другом потока изучения материала — теоретический и практический, сольются в один уже в следующей главе. Пока же читателю остается только поверить в то, что знание всего материала первой главы является необходимым условием для успешного перехода к изучению следующей.
И последнее замечание — чисто технологическое. На первой стадии изучения языка Java полезно отвлечься от того факта, что он является объектно-ориентированным, и сосредоточиться на содержательных проблемах корректной реализации алгоритма. Однако это не так просто сделать — написание даже самой простейшей программы на нем невозможно без понимания основных концепций ООП. Для частичного решения этой проблемы используется созданный специально для этих целей класс Xterm , ограждающий начинающего программиста от сложностей реального мира языка Java.
Предмет науки программирования
С давних пор человеку приходится создавать описания последовательностей действий, требуемых для достижения некоторой поставленной цели. Такие описания могут быть рассчитаны на их выполнение людьми или автоматическими устройствами. Тексты, написанные для людей, как правило, обладают известной степенью неопределенности и неформальности. Примером может служить фраза из кулинарного рецепта о щепотке соли. Только весьма опытный человек в состоянии правильно посолить блюдо в соответствии с подобной рекомендацией.
Этот пример вполне объясняет, почему описания последовательности действий, предназначенные для автоматического устройства, должны быть совершенно однозначны и заданы с помощью некоторой формальной системы обозначений. Очень часто создание таких описаний связано со значительными техническими и принципиальными трудностями. Данная проблема стала чрезвычайно актуальной в связи с повсеместным распространением электронных вычислительных машин (ЭВМ), часто используемых в качестве универсального исполнителя команд .
Описание последовательности действий, достаточно определенное для того, чтобы ее можно было выполнить при помощи некоторого автоматического устройства называют алгоритмом (algorithm) . Обычно эту последовательность записывают (кодируют) с помощью некоторых формальных обозначений. При этом формальная система, предназначенная для записи алгоритмов, называется алгоритмическим языком , сам текст алгоритма — программой , а процесс его создания — программированием .
Наука программирования (computer science) занимается исследованием свойств алгоритмов и разработкой методов построения программ. По своему положению и используемым методам она является областью прикладной математики. Все попытки подхода к программированию как к технической дисциплине, а к созданию программ как к промышленному производству, неизменно терпели неудачу.
Заметим, что данное выше "определение" алгоритма достаточно расплывчато и, фактически, определением не является. В математике существует несколько вполне четких определений алгоритма, эквивалентных между собой, и большинство из них не слишком трудны для понимания. Все они, однако, требуют хорошего знания определенных областей математики и поэтому в начале мы не будем отвлекаться на (весьма важные и интересные) подробности, необходимые для строгого изложения понятия алгоритма. Вместо этого мы рассмотрим пример алгоритма, а потом перечислим основные свойства, которыми должен обладать любой алгоритм.
Подход, когда некоторое не до конца четко определенное понятие активно используют, в науке весьма типичен. Например, точные определения натуральных и действительных чисел не рассматривают ни только в средней школе, но даже и в большинстве ВУЗов. Более того, говорят, что сороконожка даже ходить разучилась, когда задумалась над тем, в каком порядке она переставляет ноги.
Пример и свойства алгоритма
Пусть нам нужно решить задачу нахождения наименьшего простого делителя натурального числа , большего единицы. Напомним, что простым называется число, не имеющее делителей, отличных от единицы и его самого, причем единица в множество простых чисел не входит. Вот как в этой книге мы будем записывать формулировки задач и их решения:
Задача 1.1. Придумайте алгоритм, вводящий натуральное число, большее единицы,который находит наименьший простой делитель этого числа.
Алгоритм решения задачи.
П1: Положить целое число равным двум и перейти на шаг П2.
П2: Если делится нацело на , то завершить работу алгоритма, выдав в качестве результата ; иначе перейти на шаг П3.
П3: Увеличить значение на единицу и перейти на шаг П2.
Для того чтобы понять этот алгоритм, надо выступить в роли компьютера (или скорее даже универсального исполнителя команд ), выполняя вручную указанную в нем последовательность действий для некоторых небольших значений . Будем записывать значения величины после каждого шага алгоритма.
Подобное исследование дает основание полагать, что после завершения работы алгоритма переменная действительно будет содержать наименьший простой делитель исходного числа . В данном случае это не сложно доказать и совершенно строго. Обязательно сделайте это.
Основные свойства любого алгоритма — это конечность, определенность, вход (ввод), выход (вывод) и эффективность. Рассмотрим их последовательно более подробно.
Конечность . Алгоритм должен всегда заканчиваться после выполнения конечного числа шагов. Алгоритм П удовлетворяет этому условию, так как величина вначале меньше , ее значение увеличивается на единицу к каждому очередному выполнению шага П2, и поэтому выполнение алгоритма будет прекращено на шаге П2 при , если — простое число, или ранее при составном .
Определенность . Действия, которые необходимо произвести на каждом шаге, должны быть определены строго и недвусмысленно в каждом возможном случае. В данном примере применена достаточно определенная, хотя и не вполне формальная система обозначений. Чаще алгоритмы записывают с использованием более формальных алгоритмических языков, называемых также языками программирования , в которых каждое утверждение имеет точный смысл.
В настоящее время существует несколько тысяч языков программирования, десятки из них используется весьма активно. Такое большое число языков обусловлено разнообразием областей применения, различием в аппаратуре, для которой пишутся программы, и в уровне подготовки людей, их пишущих, а также существованием нескольких учений о том, как надо писать программы (так называемых парадигм программирования ).
Выход (output) . Алгоритм всегда обязан иметь одну или несколько выходных величин. В случае алгоритма П такой величиной является число . Алгоритмы, не имеющие выходных данных, бесполезны на практике, и мы не будем их изучать.
Эффективность . От алгоритма требуется, чтобы он был эффективным. Это означает, что все операции, которые необходимо произвести в алгоритме, должны быть достаточно простыми, чтобы их в принципе можно было выполнить точно и за конечное время с помощью карандаша и бумаги. В алгоритме П выполняются лишь следующие операции: сравниваются два целых числа, одно положительное число делится на другое, переменной присваивается значение целого числа два, ее значение увеличивается на единицу.
Все эти операции являются эффективными в указанном выше смысле, так как целые числа можно записать на бумаге конечным образом и существует по крайней мере по одному способу для деления и сложения двух целых чисел. Но те же самые операции не были бы эффективными, если бы значениями величин, фигурирующих в алгоритме, были бы произвольные действительные числа, выраженные бесконечными десятичными дробями, так как подобные величины нельзя даже записать на бумаге за конечное время.
Из вышесказанного следует, что на ЭВМ практически невозможно работать с действительными числами, что, по всей видимости, может показаться вам неправдоподобным. На самом деле это так. Более того, даже с настоящими целыми числами на компьютере работают не так уж и часто. Обычно вместо множеств целых " />
и действительных " />
чисел приходится работать с их заменителями _M" />
и _M" />
соответственно. Эти машинные аналоги часто вполне позволяют забыть о том, что мы имеем дело не с настоящими числами, но иногда особенности представления чисел в ЭВМ проявляются весьма неожиданным образом. Данной теме посвящена "лекция 4" курса.
Понятие эффективности алгоритма имеет и свои количественные характеристики. Различают временную и емкостную эффективности. Первая из них характеризует время выполнения алгоритма, а вторая — требуемый для этого объем памяти. Важнейшие для практики вопросы оценки временной эффективности или сложности (complexity) алгоритмов рассматриваются ниже, в "лекции 5" .
В данный момент вы не можете посмотреть или раздать видеоурок ученикам
Чтобы получить доступ к этому и другим видеоурокам комплекта, вам нужно добавить его в личный кабинет, приобрев в каталоге.
Получите невероятные возможности
Конспект урока "Этапы решение задачи на компьютере. Принцип последовательного конструирования алгоритма"
· Этапы решения задачи на компьютере.
· Принцип последовательного конструирования алгоритма.
Давайте подумаем, с чего начинается решение любой задачи, не обязательно связанной с компьютером. Решение любой задачи начинается с прочтения и уточнения её условия. Условия задач мы рассматривали в текстовой форме. Мы выделяли информацию, которая дана в условии – входные данные, а также информацию которую необходимо получить – выходные данные. Это начальный этап решения задачи, то есть её постановка.
После того, как мы определили входные и выходные данные задачи, нам нужно определиться со средствами, которые могут быть необходимы для получения выходных данных из входных. Для этого определяются отношения между ними и записываются на каком-нибудь формальном языке, например, с помощью математических формул. Результатом этих действий будет информационная модель задачи, записанная на некотором формальном языке. Этот этап называется формализацией задачи.
После того, как мы определились со средствами решения задачи, нужно понять, что необходимо сделать для того, чтобы получить выходные данные из входных, какие действия над информацией и в каком порядке для этого нужно произвести. То есть мы составляем алгоритм решения задачи и описываем его одним из известных нам способов, например, с помощью блок-схемы или в текстовой форме. Главное, чтобы было понятно, что должна делать программа и в каком порядке. Этот этап называется созданием алгоритма.
Далее мы записывали созданный алгоритм с помощью языка программирования или других инструментов. И получали компьютерную программу для решения задачи. Этот этап имеет простое название: программирование.
Получив компьютерную программу, мы обычно проверяли правильность её работы. Сначала пробовали запустить программу. После чего задавали несколько различных вариантов входных данных, для которых выходные данные уже были известны, и проверяли, совпадают ли они с теми, которые возвращает программа. Если данные совпадают – программа работает правильно и задача решена. Если же не совпадают – на каком-то из этапов была допущена ошибка. Этот процесс называется тестированием программы.
Ошибки в программе бывают двух видов: синтаксические и логические. Синтаксические ошибки связаны с записью программы на конкретном языке программирования и, как правило, находятся и исправляются средствами среды разработки. Логические ошибки обычно допускаются на более ранних этапах. После того, как ошибка была исправлена, снова проделываются все этапы, следующие за тем, на котором допущена ошибка. Так происходит до тех пор, пока правильность работы программы не подтверждается. Этот процесс называется отладкой.
Таким образом, мы выделили пять этапов решения задачи с помощью компьютера: постановка задачи, формализация задачи, создание алгоритма, программирование, тестирование и отладка. Все эти этапы мы выполняли при решении задач и раньше, но для экономии времени часто этапы формализации задачи и создания алгоритма мы объединяли между собой.
Но предположим, что у нас есть задача, для которой мы уже описали формальную информационную модель, однако придумать алгоритм для решения задачи у нас не выходит, потому что он получается слишком большим и сложным. Чтобы облегчить эту задачу, можно использовать принцип последовательного конструирования алгоритма, этот принцип также называется «разработкой сверху вниз» или методом «пошаговой детализации». Он состоит в том, что задача разбивается на несколько более простые подзадач, каждая из которых также может разбиваться на подзадачи. Так происходит до тех пор, пока не станет понятным, как решать каждую отдельную подзадачу. Для решения каждой задачи составляется вспомогательный алгоритм. После того, как мы составили вспомогательные алгоритмы для решения всех подзадач, нам остаётся лишь собрать их воедино. Таким образом, мы получим алгоритм для решения исходной задачи.
Рассмотрим задачу. Написать программу, вычисляющую наименьшее общее кратное двух целых положительных чисел a и b. Наименьшим общим кратным (НОК) двух натуральных чисел называется наименьшее целое число, которое без остатка делится на оба числа. Из курса математики нам известно, что наименьшее общее кратное двух натуральных чисел можно вычислить как их произведение, делённое на их наибольший общий делитель (НОД). Таким образом, исходную задачу мы можем разбить на 3 подзадачи: вычислить произведение введённых чисел, вычислить их наибольший общий делитель и разделить произведение чисел на их наибольший общий делитель.
Решение первой и третьей подзадач очевидно. Также ранее мы узнали, что наибольший общий делитель двух чисел можно найти, использовав усовершенствованный алгоритм Эвклида, который состоит в том, чтобы заменять большее число в паре его остатком от деления на другое до тех пор, пока одно из чисел не станет равным нулю. После этого ненулевое число будет равным наибольшему общему делителю исходных чисел.
print ('Программа, вычисляющая НОК a и b.')
while a != 0 and b != 0:
print ('НОК введённых чисел:', nok)
Сохраним написанную программу и протестируем её. Запустим программу на выполнение и зададим числа 2 и 3. Действительно, наименьшее число, которое без остатка делится и на 2, и на 3 – 6. Снова запустим программу и зададим числа 6 и 8. Действительно, наименьшее число, которое без остатка делится и на 6, и на 8 – 24. Программа работает правильно. Задача решена.
Рассмотрим ещё одну задачу. Выпуклый четырёхугольник задан положительными длинами своих сторон: a, b, c и d. Написать программу для вычисления его площади, если известно, что между сторонами a и b прямой угол.
Изобразим условие этой задачи в виде рисунка. Соединим противоположные концы сторон a и b отрезком, длину которого обозначим t. Таким образом мы разделили четырёхугольник на два треугольника со сторонами a, b, t и c, d, t соответственно. Площадь четырёхугольника равна сумме их площадей. Так как между сторонами a и b прямой угол, то площадь первого треугольника можно вычислить как полупроизведение a и b, а t – как гипотенузу первого треугольника. Зная значения c, d и t, мы можем вычислить площадь второго треугольника по формуле Герона. Таким образом, мы записали формулы, необходимые для решения задачи, получив математическую модель.
Также мы разобьём задачу на несколько подзадач. Вначале мы вычислим площадь первого треугольника, после чего определим длину стороны t. Далее мы вычислим площадь второго треугольника и в конце рассчитаем площадь четырёхугольника как сумму площадей треугольников, из которых он состоит. Так мы составили алгоритм решения задачи.
print ('Программа, вычисляющая площадь четырёхугольника по длинам его сторон. Угол между a и b прямой.')
from math import sqrt
t = sqrt (a ** 2 + b ** 2)
s2 = sqrt (p * (p - c) * (p - d) * (p - t))
print ('Площадь заданного четырёхугольника:', ''.format (s))
· Решение любой задачи с помощью компьютера состоит из пяти этапов: постановка задачи, её формализация, создание алгоритма, программирование, тестирование и отладка.
· Если алгоритм решения задачи сложно придумать сразу, то для этого можно использовать метод последовательного конструирования алгоритма, где задача разбивается на несколько более простых подзадач, каждая из которых также может делиться на подзадачи. Так происходит до тех пор, пока нам не станет понятно, каким образом решить все подзадачи. После этого решения всех подзадач соединяются воедино, образуя алгоритм решения исходной задачи.
АЛГОРИТМ - это последовательность команд, ведущих к какой-либо цели.
Это строго определенная процедура, гарантирующая получение результата за конечное число шагов. Это правило, указывающее действия, в результате цепочки которых происходит переход от исходных данных к искомому результату. Указанная цепочка действий называется алгоритмическим процессом, а каждое отдельное действие - его шагом. Пример: площадь прямоугольника S=a · b.
Виды алгоритмов: вычислительные, диалоговые, графические, обработки
данных, управления объектами и процессами и др.
Свойства алгоритмов - однозначность (и определенность), результативность (и выполнимость), правильность (и понятность), массовость или универсальность (т.е. применимость для целого класса задач, к различным наборам исходных данных).
Способы записи алгоритмов:
-
1. В виде блок-схем ,
Пример блок-схемы разветвленного алгоритма
Данная блок-схема соответствует задаче нахождения точки внутри окружности.
Эта блок-схема создана с помощью программы Algorithm, версия 1.01, фирмы CLC г. Дубна, 1992.
С помощью указанной программы очень удобно создавать любые блок-схемы несложных алгоритмов.
2. В виде программ ,
3. В виде текстовых описаний (рецепты, например, рецепты приготовления пищи, лекарств и др.).
Правила изображения блок-схем алгоритмов
-
Типы алгоритмов - структурированные, неструктурированные (т.е. с нарушением структуры - с операторами безусловного перехода) и вспомогательные.
Алгоритмы бывают:
1) линейными ,
2) с ветвлением ,
3) циклическими , т.е содержащими циклы,
4) с подпрограммами,
5) смешанные (т.е. содержащие и циклы, и подпрограммы, и ветвление).
-
1. Подпрограмм;
2. Стандартных функций;
3. Функций пользователя.
ЦИКЛЫ - это команды алгоритма, которые позволяют несколько раз повторить одну и ту же группу команд.
Алгоритмизация - это техника составления алгоритмов и программ для решения задач на компьютере.
Метод разработки сложных алгоритмов сверху вниз, с последующим уточнением, называется МЕТОДОМ ПОСЛЕДОВАТЕЛЬНОЙ ДЕТАЛИЗАЦИИ. При этом способе алгоритмы записываются в виде множества вспомогательных алгоритмов, решающих вспомогательные подзадачи. При составлении новых алгоритмов могут использоваться алгоритмы, составленные раньше.
Алгоритмы, целиком используемые в составе других алгоритмов, называют вспомогательными. Вспомогательный алгоритм на языке BASIC реализуется в виде:
Порядок составления диалоговых алгоритмов:
задача -> сценарий -> алгоритм -> программа.
Во все времена, ошибкой, всех начинающих разработчиков, становиться неверное расположение этапов решения поставленной ими задачи.
Стремясь сэкономить время, чаще всего программист сразу садятся за составление программы на определенном языке ,тем самым, пропуская при этом львиную долю работы.
Стремясь ускорить процесс разработки, на самом деле затягивая его на неопределенный срок.
Итогом такого подхода является снижение эффективности собственной работы в разы. И иногда приводит к плохим результатам в целом.
Любая решаемая задача должна выполняться по однозначно определенному алгоритму. И решается в несколько этапов.
Этап 1: Постановка задачи - данный этап является самым сложным. Чем кропотливее и внимательнее будет пройден данный этап тем правильнее будет решена задача в целом.
На данном этапе выполняются следующие действия:
1) При постановке задачи выясняется конечная цель и вырабатывается общий подход к решению задачи.
2) Выясняется сколько решений имеет задача и имеет ли их вообще.
3) Изучаются общие свойства рассматриваемого физического явления или объекта, анализируются возможности данной системы программирования.
Так же при постановке задачи необходимо выявить следующие данные:
a) Какие входные данные будут использоваться при решении задачи.
б) Какие результаты хочет увидеть заказчик (не обязательно что заказчик и исполнитель это разные люди)
в) Какие ограничения будут накладываться на решаемую задачу и как должен на них реагировать алгоритм.
2) Провести анализ вариантов решения данной задачи может есть готовые решения – это может сократить все к минимуму.
Последствиями неверно пройденного этапа может быть как неверное решение, либо испорченный проект и потраченные деньги которые нужно будет вернуть заказчику.
Этап 2: Выбор (или разработка) метода решения задачи.
Зачастую любая задача возникающая в жизни когда-то была уже решена кем то другим. Благодаря различным сообществам разработчиков можно найти решения в интернете или специализированных журналах и даже в книгах.
Если решения найдены то просто необходимо выбрать подходящее и адаптировать под те действия и данные которые были выяснены на первом этапе работ
Если решения не нашлось, то нужно разложить задачу на более простые действия, и реализовать каждое из них самостоятельно.
Не важно какой из вариантов будет выбран, в любом случае заказчику важен результат а не методы которые были использованы для достижения цели.
При разработке алгоритма используются специальные языки, позволяющие записать ход решения задачи в понятном для дальнейшего использования виде.
Во время составление программы – формируется текст программы на основе синтаксических правил языка, выбранного для реализации задачи, и перевод решения задачи из алгоритмического языка на языке понятной машине.
Задаются нужные данные в виде констант переменных и функций, и далее последовательно описываются действия алгоритма на языке программирования.
Даже идеально написанные программы иногда дают сбой, при выполнении каких то задуманных действий. на данном этапе выполняется поиск неправильного поведения приложения и исправление неверных участков реализации алгоритма в программном коде.
В настоящее время главным критериями работы программ являются скорость и надежность.
Поэтому эффективность и быстродействие приложений накладывают на разработчиков жесткие критерии. Если программа будет работать медленно то пользователи выключат ее не дожидаясь результатов и уйдут к конкурентам у которых приложение работает быстрее.
Таким образом необходимо не только писать эффективный код решающий задачу но и он должен быть максимально быстр и надежен.
Этот этап является основным при оценке выполненной работы разработчика программного обеспечения.
Никому не нужна программа которая правильно решает задачу за огромное количество времени, все хотят чтобы по работало быстро и точно.
Читайте также: