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

а) вариант с ошибкой б) исправленный вариант

Рис. 8. Блок-схема алгоритма поиска в символьном массиве слова максимальной длины.

Таблица 6. Таблица трассировки.

K	A(K)	K=N	A(K)=" "	M>MAX	M	MAX	S	Новое S
1	Д	нет	нет		1	0	1	1
2	у	нет	нет		2
3	л	нет	нет		3
4	" "	нет	да	да	0	3	3	4
5	т	нет	нет		1
6	е	нет	нет		2
7	п	нет	нет		3
8	л	нет	нет		4
9	ы	нет	нет		5
10	й	нет	нет		6
11	" "	нет	да	да	0	6	10	11
12	в	нет	нет		1
13	е	нет	нет		2
14	т	нет	нет		3
15	е	нет	нет		4
16	р	да	нет	нет	5

Рассмотрите результат, приведенный в табл. 6, для конкретного входного символьного массива "Дул теплый ветер" без последнего столбца. Однако, после выполнения приведенного на рис. 8 алгоритма для предложения "Дул теплый ветер" будет выведено слово из 7 символов, начинающихся с пробела: " теплый". Значит, формулу определения номера символа s = k-1, с которого начинается слово с максимальной длиной, следует изменить на s = k. При этом надо будет изменить содержание блока вывода результата: вместо A(s-max), …, A(s) следует использовать A(s-max), …, A(s-1). Таким образом, таблица трассировки показала наличие ошибок в алгоритме, изображенном на рис. 8, а). После внесения изменений этот алгоритм будет работать правильно (модернизированный алгоритм поиска в символьном массиве слова с максимальной длиной приведен на рисунке 8, б).

Рекомендуется [3] стр. 113-127, [5] стр.349-351.

Задания для самостоятельного выполнения

Составить циклические алгоритмы в виде блок-схем для следующих задач обработки символьных одномерных массивов.

1.  Найти и вывести слово, содержащее наибольшее количество гласных букв.

2.  В слове, в котором обнаружено наибольшее количество шипящих букв, заменить их на символ "*".

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

4.  Подсчитать количество слов и количество символов во всех словах, отличных от заглавных латинских букв.

5.  Вывести все слово, содержащее наибольшее количество цифр и вывести число цифр в каждом слове.

6.  Слово с минимальной длиной удалить из данного предложения.

7.  Перенести в конец предложения все встречающиеся в тексте цифры.

8.  В предложении расставить все слова в алфавитном порядке.

Рекомендуется выполнить [6] стр. 354-359, [5] стр.351.

Алгоритмы обработки двумерных массивов

Двумерный массив – это структура однотипных элементов, расположенных в виде таблицы значений. Такое представление значений соответствует математическому понятию двумерный массив. Каждый элемент в двумерном массиве идентифицируется номером строки и номером столбца, на пересечении которых он расположен.

Например, в двумерном массиве А= элемент со значением 5 расположен на пересечении третьей строки и второго столбца. Этот элемент будет обозначаться как А(3,2) = 5. А элемент А(1,4)=0. Такое представление набора значений позволяет выполнять обработку как отдельных значений в двумерном массиве, так и последовательности значений, расположенных в строках или столбцах. В дальнейшем будем считать, что для двумерного массива A(N, М) в обозначении элемента А(i, j) первое значение i соответствует номеру строки и изменяется от1 до N, а j – номеру столбца и изменяется от 1 до М. В отличие от одномерного массива, в котором использовался только один номер для определения местоположения элемента и требовался только один цикл для ввода элементов, в двумерном массиве для обработки элементов необходимы два вложенных друг в друга цикла. Внешний цикл предназначен для изменения номера строки i, а второй, внутренний, – для изменения номера столбца j в текущей строке i.

Пример 12. Разработать алгоритм заполнения двумерного массива.

Решение: На рис. 9 представлен простой алгоритм ввода элементов, построенный в виде структуры из вложенных циклов.

Рис. 9. Алгоритм ввода элементов двумерного массива

Рекомендуется [3] стр.77-87, практикум в [3] стр.104-113.

Задания для самостоятельного выполнения

Составить циклические алгоритмы для следующих задач обработки двумерных массивов.

1.  Ввести двумерный массив А(N, M).Составить алгоритм замены всех нулевых элементов на минимальный элемент.

2.  Ввести двумерный массив А(N. N). Составить алгоритм подсчета среднего арифметического значений двумерного массива. Найти отклонение от среднего у элементов первой строки.

3.  Ввести двумерный массив А(N, N). Составить алгоритм подсчета среднего арифметического значения двумерного массива. Вычислить отклонение от среднего для всех элементов двумерного массива.

4.  Ввести двумерный массив А(N, N). Составить алгоритм замены всех отрицательных элементов на среднее арифметическое значение элементов двумерного массива.

5.  Составить алгоритм нахождения числа строк двумерного массива А(N, N), количество отрицательных элементов в которых больше Р.

6.  Ввести двумерный массив размером 7´4. Найти наибольший элемент двумерного массива. Удалить строку с максимальным элементом.

7.  Ввести двумерный массив размером 7´4. Поменять столбец с максимальным элементом с первым столбцом двумерного массива.

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

9.  Ввести двумерный массив размером 7´4. Найти наименьший элемент двумерного массива. Перенести строку, содержащую этот элемент в конец.

10.  Ввести двумерный массив размером 7´4. Найти максимальный элемент двумерного массива. Поменять столбец, содержащий этот элемент с последним столбцом двумерного массива.

11.  Ввести двумерный массив размером 6*4. Найти минимальный элемент двумерного массива. Переставляя строки и столбцы, добиться того, чтобы он оказался в правом нижнем углу.

Рекомендуется выполнить задания из [6] стр.346-354.

Реализация

На этом этапе осуществляется:

1. Кодирование – перевод на язык программирования конструкций, записанных на языке проектирования.

2. Тестирование – всесторонняя проверка программ.

3. Отладка – процесс локализации и устранения ошибок.

4. Создание необходимой документации для пользователя.

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

Язык программирования – это формальный язык, специально созданный для общения человека с компьютером.

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

Рис. 10. Классификация языков программирования.

Нетрудно заметить, что алгоритмического языка высокого уровня (ЯВУ), который был бы идеальным для всех случаев, не существует. Наиболее важная задача программного обеспечения заключается в том, чтобы определить, какой язык является «наилучшим» в каждой конкретной ситуации. Во многих случаях такой выбор диктуется очень простыми причинами — доступностью того или иного транслятора и умением составлять программы на данном языке. Если же в распоряжении имеется достаточно большой выбор языков программирования, то необходимо учитывать следующие обстоятельства:

·  назначение разрабатываемой программы (будет ли она использоваться временно или постоянно, будет ли она модернизироваться и развиваться);

·  время выполнения программы (имеется в виду соотношение вычислительных процедур и процедур ввода-вывода);

·  ожидаемый размер программы (хватит ли памяти для реализации целиком всей программы или следует ее разделить на отдельные взаимодействующие модули);

·  необходимость сопряжения разрабатываемой программы с другими пакетами или программами, в том числе составленными на других языках программирования;

·  предусматривается ли возможность переноса программы на другие типы ЭВМ;

·  основные типы данных, с которыми будет работать программа (целые и вещественные числа, строки, списки и другие типы структур);

·  характер и уровень использования аппаратных средств (дисплея, клавиатуры и др.);

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

С учетом этих критериев возможности языков могут весьма сильно различаться, поэтому правильный выбор ЯВУ является непростой задачей. Для начинающего программиста характерно начинать использование ПЭВМ с языка Бейсик или Паскаль.

Каждый язык программирования, равно как и «естественный» язык (русский, английский и т. д.), имеет алфавит, словарный запас, свои грамматику, синтаксис и семантику.

Алфавит – фиксированный для данного языка набор основных символов, допускаемых для составления текста программы на этом языке.

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

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

Взаимодействие синтаксических и семантических правил определяют операторы, идентификаторы, переменные, функции и процедуры, модули и т. д.

Пример 13. Алфавит Borland Pascal 7.0 включает:

·  строчные, прописные буквы латинского алфавита (которые не различаются) и знак ‘_’ (подчеркивание), который во многих случаях считается буквой;

·  цифры (0…9);

·  специальные знаки, состоящие из одного и двух символов (., ; : { } [ ] < ^ := и т. д.)

·  служебные слова – эти сочетания считаются единым целым и их нельзя использовать в программе в другом качестве (in, for, file, label, mod, string и т. д.)

Таблица 7. Соответствие алгоритмических и программных фрагментов на Pascal.

Фрагменты блок-схем алгоритмов	Назначение	Соответствующие фрагменты программ на языке Pascal
	Начало и конец алгоритма.	Begin и End
X := A + B	Блок обработки (в нем вычисляются новые значения или производится вызов подпрограмм).	X := A + B
	Ввод исходных данных или вывод результатов.	Read (x, y) или write (x, y)
	Ветвление полное. Если значение переменной а больше b, то выполняется x:=a, иначе x:=b.	if a > b then x := a else x := b
	Ветвление неполное. Если значение переменной a больше b, то выполняется x:=a.	if a > b then x := a
	Цикл с предусловием. Пока значение условия i < 6 истино выполняется тело цикла, то есть действия k=k+1 и i = i+2. Переменная i определяет количество повторений и называется счетчиком цикла.	i := 1;  while i < 6 do begin  k := k + 1;  i := i + 2;  end; write (k);
	Цикл с постусловием.Пока значение условия i > 6 ложно выполняется тело цикла, то есть действия k = k+1 и i = i+0,1.Переменная i определяет количество повторений в цикле и называется счетчиком цикла.	i := 1;  repeat  k:=k+1;  i:=i+0.1;  until i < 6; write (k);
	Цикл с постоянным приращением счетчика. В этом цикле изменение счетчика цикла i происходит только на единицу. Пока значение счетчика цикла меньше или равно 6 выполняется тело цикла, то есть действия k = k+s и i = i+1.	for i := 1 to 6 do  k := k+s;   write (k);

Рекомендуется изучать язык программирования Pascal в [3] стр. 28-179, [4] стр. 169-220, [5] стр. 258-282, [6] стр. 29-119; язык программирования Си /Си++ в [5] стр. 358-396, [6] стр. 170-265; язык программирования Бейсик в [5] стр. 339-357.

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

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

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

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

Правило 1. Сложение и вычитание выполняются быстрее, чем умножение и деление, а они – быстрее чем возведение в степень. Целочисленная арифметика быстрее арифметики вещественных чисел. Таким образом, Х+Х лучше, чем I·X, а г+0,5 хуже, чем (i+i+j)·0,5. При выполнении операций над целыми числами следует помнить, что благодаря применению двоичной системы счисления умножение на числа, кратные двум, можно заменить соответствующим количеством сдвигов влево.

Правило 2. Удаление избыточных вычислений. Если некоторое арифметическое выражение встречается в вычислениях несколько раз, то его следует вычислить заранее и хранить в памяти ЭВМ.

Правило 3. Некоторые компиляторы способны прекращать вычисления логических выражений тогда, когда результат становится очевидным. Например, в выражении A or В or С, если А имеет значение «истина», то переменные В и С уже не проверяются. Таким образом, можно сэкономить время, разместив переменные А, В, С так, чтобы первой стояла переменная, которая вероятнее всего будет истинной, а последней та, которая реже всего принимает истинное значение. Однако следует быть осторожным в следующем примере: Rool (A) or В or С, (где Rool (A) –может и чаще принимает значение «истина», но представляет собой вызов функции, возможно выполняющей сложные и длительные вычисления). Тогда может оказаться, что запись В or С or Rool {А) является более эффективной.

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

Правило 5. Развертывание циклов.

Пример 14. Повысить эффективность алгоритма.

for i: = 1 to 1000 do

for j: = 1 to 3 do A[i]: =A[i] + C[i, j];

Решение: Алгоритм можно переписать так:

for i: = 1 to 1000 do A[i]: =A[i] + C[i, 1] + C[i,2] + C[i,3].

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

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

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

Задания для самостоятельного выполнения

Перевести на языки программирования Pascal, Си/Си++ и Бейсик алгоритмы, составленные при выполнении заданий, описанных ранее.

Сопровождение

Это этап эксплуатации системы. Каким бы тщательным ни было тестирование программ, к сожалению, в больших программных комплексах чрезвычайно тяжело устранить абсолютно все ошибки. Устранение обнаруженных при эксплуатации ошибок — первейшая задача этого этапа. Однако это далеко не все, что выполняется при сопровождении. Выполняемый в ходе сопровождения анализ опыта эксплуатации программы позволяет обнаруживать «узкие места» или неудачные проектные решения в тех или иных частях программного комплекса. В результате такого анализа может быть принято решение о проведении работ по совершенствованию разработанной системы. Кроме описанного выше сопровождение может включать в себя проведение консультаций, обучение пользователей системы, оперативное снабжение пользователей информацией о новых версиях системы и т. п. Качественное проведение этапа сопровождения в большой степени определяет коммерческий успех программного продукта.

Модификация

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

Причинами выпуска новых версий являются:

1. Необходимость исправления ошибок, выявленных в процессе эксплуатации.

2. Необходимость совершенствования, например, улучшения интерфейса или расширения состава выполняемых функций.

3. Изменение среды (появление новых технических средств и/или программных продуктов).

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

Контрольные вопросы

1.  Назовите основные этапы разработки программного обеспечения.

2.  Что такое данные? Виды данных.

3.  Назовите основные методы разработки алгоритмов, их особенности.

4.  Что называют алгоритмом? Основные свойства алгоритма.

5.  Способы задания алгоритмов.

6.  Основные алгоритмические структуры.

7.  Блок-схемы. Виды блоков. Правила составления блок-схем.

8.  В чем отличие и что общего между ветвлением и циклом?

9.  Какие ветвления Вы знаете? Приведите примеры.

10.  Какие существуют виды циклов?

11.  Какой этап разработки программного обеспечения самый важный? Почему?

12.  Чем физическое проектирование отличается от логического?

13.  Как можно повысить эффективность программы?

14.  Что называют рекурсией?

15.  Массив. Виды массивов.

16.  Языки программирования. Алфавит. Реализация основных структур. Примеры.

17.  В чем заключается этап сопровождения?

18.  Как Вы думаете, можно ли исключить этап модификации? Почему?

19.  Для чего нужны таблицы трассировки?

20.  Существуют ли нормативные документы, регламентирующие деятельность разработчиков программ?

21.  Приведите примеры математических моделей для заданий из этих методических указаний.

Список литературы

1. ГОСТ 19.201-78 ЕСПД. Техническое задание. Требование к содержанию и оформлению (с изм. 1).

2. ГОСТ 19.701-90. Схемы алгоритмов, программ, данных и систем.

(ИСО–5807-85) Обозначения условные и правила выполнения.

3. Иванова программирования: Учебник для вузов. – М.: Изд-во МГТУ им. , 2001. – 392 с.

4.  Информатика // Под. ред. . – Ростов н/Д.: Феникс, 2002. – 448 с.

5.  Могилев А. В. и др. Учеб. пособие для студ. пед. вузов. – М.: Издательский центр «Академия», 2003. – 432 с.

6.  Основы программирования: Учебник для сред. проф. образования /, . – М.: Издательский центр «Академия», 2003. – 432 с.

7.  Острейковский : Учеб. пособие для студентов сред. проф. учеб. заведений. – М.: Высш. шк., 2001. – 319 с.

Составители: Александр Александрович Эпов,

Елена Васильевна Морозова,

АЛГОРИТМИЗАЦИЯ РЕШЕНИЯ ТИПОВЫХ ЗАДАЧ

И ОСНОВЫ ПРОГРАММИРОВАНИЯ НА ЯЗЫКЕ

ВЫСОКОГО УРОВНЯ

Методические указания к самостоятельной работе студентов

Издано в редакции авторов.

Темплан 2004 г., Поз. № 000.

Лицензия ИД № 000 от 01.01.2001

Подписано в печать

Формат . Бумага потребительская.

Усл. печ. л. 2,25. Усл. авт. л. 2,06.

Тираж 100 экз. Заказ

Волгоградский государственный технический университет

400131 Волгоград, просп. им. , 28.

РПК «Политехник»

Волгоградского государственного технического университета

400131 Волгоград, ул. Советская, 35

Отпечатано в муниципальном унитарном предприятии

”Камышинская типография“

Лицензия ИД № 000 от 01.01.01 г.