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

Лекция: Основные этапы решения задач на компьютере

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

Рассмотрим эти этапы на таком простейшем примере: пусть требуется вычислить сумму двух целых чисел и вывести на экран видеомонитора результат.

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

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

Третий этап – алгоритмизация задачи. На основе математического описания необходимо разработать алгоритм решения.

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

Алгоритм должен обладать рядом свойств.

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

• Однозначность алгоритма, под которой понимается единственность толкования исполнителем правил и порядка выполнения действий. Для этого алгоритм должен быть записан командами из системы команд исполнителя. Для нашего примера исполнитель должен понимать такую запись действий, как А + В.
• Конечность алгоритма –обязательность завершения каждого из действий и всего алгоритма в целом. Наш алгоритм обладает этим свойством, так как после выполнения действий ввода исходных данных, вычисления суммы и вывода результата алгоритм завершается.
• Результативность алгоритма, предполагающая, что его выполнение завершится получением определённых результатов. В нашем примере всегда для целых чисел А и В может быть вычислена сумма.
• Массовость, т.е. возможность применения алгоритма к целому классу задач, отвечающих общей постановке задачи. Для того, чтобы алгоритм обладал свойством массовости, следует составлять его с использованием обозначения величин и избегая конкретных значений. Наш алгоритм позволяет правильно посчитать сумму не только для чисел 2 и 3, но и для любой пары целых чисел.
• Правильность алгоритма,под которой понимается способность алгоритма выдавать правильные результаты решения поставленной задачи. В нашем примере используется формула сложения целых чисел, и для любой пары целых чисел результат выполнения алгоритма будет равен их сумме, что и требуется.

Существует несколько типов алгоритмов:

а) Линейный алгоритм – это алгоритм, содержащий несколько шагов, все шаги выполняются последовательно друг за другом от начала до конца.

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

в) Циклический алгоритм– это алгоритм, содержащий многократное выполнение одних и тех же шагов при различных значениях промежуточных данных.

Четвёртый этап – программирование.Программой называют план действий, подлежащих выполнению исполнителем, в качестве которого может выступать компьютер. От алгоритма программа отличается тем, что записывается на языке понятном для исполнителя. Если исполнителем является компьютер, то программа записывается на одном из языков программирования. В компьютере данные и команды представляются в виде последовательности нулей и единиц. Поэтому, когда говорят о “понятности” языка программирования для компьютера подразумевают наличие специальной программы, способной перевести инструкции языка программирования в последовательность двоичных компьютерных команд. Язык программирования выполняет функции посредника между человеком и ЭВМ и поэтому с одной стороны должен быть удобен для записи алгоритмов в понятной для человека форме, а с другой стороны легко преобразовываться в машинные коды.

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

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

Шестой этап – тестирование и отладка программы. На этом этапе происходит исполнение программы на ЭВМ, поиск и исправление логических ошибок, то есть ошибок приводящих к неправильной работе программы. При этом программисту приходится выполнять анализ работы программы. Для сложных программ этот этап, как правило, требует гораздо больше времени и сил, чем написание первоначального текста программы.

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

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

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

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

9.7. Этапы решения задачи на ЭВМ.

Рассмотрим теперь подробнее все этапы решения задач на ЭВМ.

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

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

Второй этап — формальная (математическая) постановка задачи, т.е. представление ее в виде уравнений, соотношений, ограничений и т. п. При этом некоторые задачи, решаемые в настоящее время на ЭВМ, либо не допускают, либо не требуют математической постановки (например, задачи обработки текстов).

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

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

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

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

Шестой этап — собственно программирование, т. е. запись разработанного алгоритма на языке программирования. Вопросы выбора подходящего языка здесь не рассматриваются.

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

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

Универсальная программа должна обрабатывать вырожденные случаи (например, число элементов вектора равно 0 или 1) и печатать сообщение об ошибке, если размер массива превысил допустимое значение (использованное в описании массива).

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

3. Некоторые простые приемы позволяют повысить эффективность программы (т. е. уменьшить количество выполняемых операций и время работы программы). К таким приемам относятся:

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

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

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

Седьмой этап — тестирование и отладка программы — это проверка правильности работы программы и исправление обнаруженных ошибок.

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

Далее даются некоторые рекомендации по тестированию и отладке.

1. Проверьте работу программы (или отдельных ее частей) вручную до выхода на машину.
2. Проводите тестирование и отладку отдельно для логически самостоятельных частей программы.
3. Используйте отладочную печать в наиболее ответственных местах программы. Операторы печати для отладки располагайте в отдельных строках так, чтобы можно было легко убрать их из программы после окончания отладки.
4. При тестировании, если это возможно, используйте меньшие объемы данных, чем те, на которые рассчитана программа.

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

Этапы подготовки и решения задач на компьютере

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

1. Постановка задачи — формулируется цель решения задачи, подробно описывается ее содержание; проводится анализ условий, при которых решается поставленная задача, выявляется область определения входных параметров задачи.
2. Формальное построение модели задачи — предполагает построение модели с характеристиками, адекватными оригиналу, на основе какого-либо его физического или информационного принципа; анализируется характер и сущность величин, используемых в задаче.
3. Построение математической модели задачи — характеризуется математической формализацией задачи, при которой существующие взаимосвязи между величинами выражаются с помощью математических соотношений. Как правило, математическая модель строится с определенной точностью, допущениями и ограничениями.
4. Выбор и обоснование метода решения — модель решения задачи реализуется на основе конкретных приемов и методов решения. В большинстве случаев математическое описание задачи трудно перевести на машинный язык. Выбор и использование метода решения позволяет свести решение задачи к конкретному набору машинных команд. При обосновании метода решения рассматриваются вопросы влияния различных факторов и условий на конечный результат, в том числе на точность вычислений, время решения задачи на компьютере, требуемый объем памяти и др.
5. Построение алгоритма — на данном этапе составляется алгоритм решения задачи, в соответствии с выбранным методом решения. Процесс обработки данных разбивается на отдельные относительно самостоятельные блоки, определяется последовательность выполнения этих блоков.
6. Составление программы — алгоритм решения переводится на конкретный язык программирования. — процесс устранения синтаксических и логических ошибок в программе. В процессе трансляции программы с помощью синтаксического и семантического контроля выявляются недопустимые конструкции и символы (или сочетания символов) для данного языка программирования. Компьютер выдает сообщение об ошибках в форме, соответствующей этому языку. Затем проверяется логика работы программы в процессе ее выполнения с конкретными исходными данными. Для этого используются специальные методы. Например, в программе выбираются контрольные точки, для них подбираются тестирующие примеры и вручную находятся значения в этих точках, которые затем и сверяются со значениями, получаемыми компьютером на этапе отладки. Кроме того, используются отладчики, выполняющие специальные действия на этапе отладки, такие как удаление, замена или вставка отдельных операторов или целых фрагментов программы, вывод промежуточных результатов, изменение значений заданных переменных и др.
7. Решение задачи на компьютере и анализ результатов. Теперь программу можно использовать для решения поставленной задачи. Первоначально выполняется многократное решение задачи на компьютере для различных наборов исходных данных.

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

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

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

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

Как быстро выучить стихотворение наизусть? Запоминание стихов является стандартным заданием во многих школах.

Как научится читать по диагонали? Скорость чтения зависит от скорости восприятия каждого отдельного слова в тексте.

Как быстро и эффективно исправить почерк? Люди часто предполагают, что каллиграфия и почерк являются синонимами, но это не так.

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

СТРУКТУРА ПРОЦЕССА РЕШЕНИЯ ЗАДАЧ. ПОИСК СПОСОБА РЕШЕНИЯ ЗАДАЧ

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

Рассмотрим все этапы, составляющие весь процесс решения любой задачи.

При получении задачи первое, что нужно сделать, — это разобраться в том, что представляет собой задача, а именно, — каковы условия задачи, в чем состоит вопрос (требование) задачи, то есть, проводится анализ задачи.

Это первый этап решения задачи.

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

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

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

решения есть четвертый этап.

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

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

Следующим — седьмым этапом является четкая формулировка ответа задачи.

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

Так весь процесс решения задачи можно разделить на восемь этапов:

1-й этап — анализ задачи;

2-й этап — построение модели задачи;

3-й этап — поиск способа решения задачи;

4-й этап — осуществление решения задачи;

5-й этап — проверка решения задачи;

6-й этап — исследование задачи;

7-й этап — формулирование ответа задачи;

8-й этап — познавательный анализ задачи и ее решения.

Эвристический метод решения задачи направлен на 3 этап — на то, как осуществляется поиск способа решения любой задачи. Отметим, что такой этап решения всегда должен присутствовать в решении любой задачи: для самой элементарной и тем более для той, которая сложнее. Также заметим, что при решении более сложных задач поиск способа решения является самым трудным и основным этапом решения.

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

Задача 1. Решить систему неравенств:

Решение. 1) Для решения системы неравенств с одной переменной существует определение решения, которое является свернутым алгоритмом.

2) Алгоритм существует, поэтому в построении модели задачи необходимости нет.

3) Способ решения дан в определении решения системы неравенств с одной переменной: решением системы неравенств с одной переменной является значение неизвестной, при которой верно каждое из неравенств системы.

4) Данное определение развернем в пошаговую программу алгоритма, применяя которую к нашей системе, найдем ее решение:

1 шаг — решаем первое неравенство системы:

2 шаг — решаем второе неравенство системы:

3 шаг — решаем третье неравенство системы:

4 шаг — находим пересечение числовых промежутков

5) Проверку решения и исследование задачи в данном случае не проводим.

6) Ответ задачи: решением системы неравенств является промежуток изменения x равен (2;3].

Следующий пример также иллюстрирует осуществление поиска решения задачи.

Задача 2. Выписать первые пять членов арифметической прогрессии, если а=10, d=4.

1) В задаче указан ее вид: имеем задачу на нахождение членов арифметической прогрессии.

2) Ищем способ решения задачи:

вспоминаем определение арифметической прогрессии:

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

на основе этого определения составляем программу решения задачи: нам известно, поэтому находить будем используя определение: и т.д.