Основные этапы решения задачи с помощью ЭВМ

Понятие алгоритма

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

Термин алгоритм происходит от имени средневекового узбекского математика Аль Хорезми (IX в.), который сформулировал правила выполнения четырех арифметических действий в десятичной системе счисления. Процесс выпол­нения арифметических действий был назван алгоризмом.

С середины ХVIII в. термин алгоризм заменили на «алго­рисмус», смысл которого состоял в комбинировании четырех арифметических операций. К середине ХХ в. стали употреблять термин алгорифм (от англ. algorithm), замененный позже в русском языке на «алгоритм». При этом смысл данного термина чаще всего связывался с алгорифмами Евклида (древнегреч. математик) – процессами нахождения наибольшего общего делителя двух натуральных чисел, наибольшей общей меры двух отрезков и т.д.

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

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

Алгоритмы, в которых решение поставленной задачи сводится к вы­полнению арифметических действий, называются численными. Алгоритмы, в которых решение поставленной задачи сводится к вы­полнению логических действий, называются логическими.

 

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

Любой алгоритм должен обладать следующими пятью свойствами:

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

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

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

4. Результативность (конечность) предполагает, что алгоритм дол­жен быть нацелен на получение конечного результата, т.е. исполнение алго­ритма должно закончиться за конечное число шагов.

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

 

Способы записи алгоритмов

 

Один и тот же алгоритм может быть записан разными способами. Их существует несколько, но основными являются следующие:

1. Словесный способ, т.е. описание алгоритма на естественном языке (словами).

2. Формульно-словесный способ, в котором кроме слов могут исполь­зоваться математические формулы.

3. Графический способ, т.е. в виде блок-схемы.

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

Стандартные алгоритмы

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

Алгоритмы сортировки

Сортировкой называют упорядочивание элементов по какому-либо признаку. Например, числовые данные можно упорядочить (отсортировать) либо по возрастанию, либо по убыванию их значений. А строковые данные – в алфавитном порядке, либо в порядке обратном алфавитному.

Наиболее известны два метода сортировки: 1) сортировка методом выбора, 2) пузырьковая сортировка.

 

Сортировка методом выбора

 

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

Рис. 11. Сортировка по возрастанию методом выбора

Пусть Х – одномерный массив из n элементов (чисел). Требуется отсортировать его по возрастанию значений элементов. Для реализации метода выбора потребуется организовать два цикла: один вложенный в другой. Поэтому потребуется два индекса: переменная i – для управления внешним циклом, переменная j – для управления внутренним циклом. Переменная М используется для поиска минимального (максимального) элемента. Необходима также дополнительная переменная А для обмена местами очередного минимума (максимума) с нужным элементом. В переменную k заносится номер очередного минимума (максимума).

На рисунке 11 изображена блок-схема сортировки по возрастанию элементов массива Х методом выбора. Сортировка по убыванию выполняется аналогично, только необходимо заменить знак «<» на знак «>» (чтобы заменить поиск минимумов на поиск максимумов).

 

Пузырьковая сортировка

 

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

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

Пусть Х – одномерный массив из n элементов (чисел). Требуется отсортировать его по возрастанию значений элементов. Для реализации пузырьковой сортировки потребуется организовать два цикла: один вложенный в другой.

Во внутреннем цикле (с управляющей переменной i) будет осуществляться сравнение пар соседних элементов X(i) и X(i+1) от начала и до конца массива. Для перестановки соседних элементов потребуется дополнительная переменная А.

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

В качестве переменной-признака окончания сортировки можно использовать либо переменную, логического типа (со значениями True и False), либо целочисленную переменную (со значениями 0 и 1). Будем использовать переменную В целого типа. Если при проверке условия В=0, то сортировка еще не завершена. Если В=1, то сортировка закончена.

На рисунке 12 изображена блок-схема сортировки по возрастанию элементов массива Х методом пузырьковой сортировки.

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

Рис.12. Пузырьковая сортировка по возрастанию

 

 

Понятие алгоритма

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

Термин алгоритм происходит от имени средневекового узбекского математика Аль Хорезми (IX в.), который сформулировал правила выполнения четырех арифметических действий в десятичной системе счисления. Процесс выпол­нения арифметических действий был назван алгоризмом.

С середины ХVIII в. термин алгоризм заменили на «алго­рисмус», смысл которого состоял в комбинировании четырех арифметических операций. К середине ХХ в. стали употреблять термин алгорифм (от англ. algorithm), замененный позже в русском языке на «алгоритм». При этом смысл данного термина чаще всего связывался с алгорифмами Евклида (древнегреч. математик) – процессами нахождения наибольшего общего делителя двух натуральных чисел, наибольшей общей меры двух отрезков и т.д.

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

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

Алгоритмы, в которых решение поставленной задачи сводится к вы­полнению арифметических действий, называются численными. Алгоритмы, в которых решение поставленной задачи сводится к вы­полнению логических действий, называются логическими.

 

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

Любой алгоритм должен обладать следующими пятью свойствами:

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

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

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

4. Результативность (конечность) предполагает, что алгоритм дол­жен быть нацелен на получение конечного результата, т.е. исполнение алго­ритма должно закончиться за конечное число шагов.

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

 

Основные этапы решения задачи с помощью ЭВМ

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

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

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

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

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

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

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

Так как от способа представления данных напрямую зависит способ их обработки, то этот этап тесно связан с предыдущим и может меняться с ним местами (структура данных может быть определена до разработки алго­ритма).

6. Программирование, т.е. запись алгоритма решения задачи в виде программы на каком-либо алгоритмическом языке.

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

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

 

Способы записи алгоритмов

 

Один и тот же алгоритм может быть записан разными способами. Их существует несколько, но основными являются следующие:

1. Словесный способ, т.е. описание алгоритма на естественном языке (словами).

2. Формульно-словесный способ, в котором кроме слов могут исполь­зоваться математические формулы.

3. Графический способ, т.е. в виде блок-схемы.

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