Иванова Г.С., Ничушкина Т.Н. - Разработка алгоритмов простейших программ

1Московский государственный технический университетимени Н. Э. БауманаФакультет Информатика и системы управленияКафедра Компьютерные системы и сети«УТВЕРЖДАЮ»Заведующий кафедрой ИУ-6_________ Сюзев В.В.Г. С. Иванова, Т.Н. НичушкинаРазработка алгоритмов простейших программМетодические указания по выполнению домашних заданий илабораторных работпо дисциплине Основы программированияМосква 20132АннотацияНастоящее учебное пособие предназначено для студентов 1 курса кафедрИУ6 и АК5, обучающихся по программе бакалавра техники и технологии направления «Информатика и вычислительная техника». В пособии рассмотрены основные приемы составления алгоритмов программ разветвленной и циклическойструктуры.

Кратко пояснены математические методы решения некоторых задачвычислительной математики, а также пояснены приемы обработки массивов иматриц.3ОглавлениеВВЕДЕНИЕ .................................................................................................................... 41РАЗВЕТВЛЯЮЩИЕСЯ ПРОЦЕССЫ .............................................................. 62 ЦИКЛИЧЕСКИЕ ПРОЦЕССЫ. АЛГОРИТМЫ РЕШЕНИЯ ЗАДАЧВЫЧИСЛИТЕЛЬНОЙ МАТЕМАТИКИ ............................................................... 102.1 Типы циклических процессов .....................................................................................................

102.2 Табулирование функции .............................................................................................................. 112.3 Нахождение суммы ряда .............................................................................................................. 122.4 Приближенное вычисление определенных интегралов ......................................................... 142.4.1 Метод прямоугольников ............................................................................................................

142.4.2 Метод трапеций .......................................................................................................................... 152.5 Определение корней уравнения .................................................................................................. 162.5.1 Метод половинного деления .....................................................................................................

162.5.2 Метод хорд.................................................................................................................................. 172.6 Нахождение длины кривой .......................................................................................................... 173МАССИВЫ ........................................................................................................... 193.1 Приемы обработки одномерных массивов ...............................................................................

193.1.1 Последовательная обработка элементов массива.................................................................... 193.1.2 Выборочная обработка элементов массива ............................................................................. 223.1.3 Изменение порядка следования элементов без изменения размеров исходного массива.Сортировка массива .............................................................................................................................

243.1.4 Переформирование массива с изменением его размеров ....................................................... 283.1.5 Одновременная обработка нескольких массивов или подмассивов ...................................... 313.1.6 Поиск в массиве единственного элемента, отвечающего некоторому условию (поисковыезадачи)....................................................................................................................................

323.2 Приемы обработки матриц .......................................................................................................... 333.2.1 Последовательная обработка элементов матрицы .................................................................. 343.2.2 Изменение порядка следования элементов без изменения размеров исходной матрицы. ..

35ЛИТЕРАТУРА ............................................................................................................. 364ВведениеУмение хорошо писать программы для компьютера предполагает не толькохорошее владение средствами разработки программ, но и хорошо развитое алгоритмическое мышление. Вся практика программирования говорит о том, чтоименно отсутствие алгоритмического мышления – причина неудач студентов приизучении программирования.Однако алгоритмическое мышление, как умение построить последовательность действий, приводящую к решению задачи, можно и нужно развивать. Дляэтого необходимо проработать алгоритмы многих небольших программ, накапливая приемы, используемые при их составлении.

Таких приемов сравнительно немного, и их совокупность образует ту базу, которая позволит студентам научитьсяписать программы.В настоящем пособии представлены базовые алгоритмы, без изучения которых знания по данному предмету будут не полными.Совершенно сознательно авторы не приводят текстов программ, ограничившись схематическими представлениями алгоритмов. Тексты программ, изобилующие деталями средств программирования, отвлекали бы внимание от самихалгоритмов, что было бы крайне нежелательно.Для представления алгоритмов в пособии использованы графические обозначения основных алгоритмических блоков по ГОСТ 19.701–90 (см.

таблицу 1).Таблица 1Название блокаОбозначениеНазначение блока1. Терминатор2. Процесс3. Данные4. Решение5. Подготовка6. Граница циклаД ей ств и еНачало, завершение программы или подпрограммыД ей ств иеОбработка данных (вычисления, пересылки и т.п.)Д анныеУслови еД ей ств ияН ачалоОперации ввода-выводаВетвления, выбор, итерационные и поисковые циклыСчетные циклыЛюбые циклыК он ец7. Предопределенный процесс8. Соединитель9.

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

Если условие будет выполнено, то вычисления будут производиться по одному определенному правилу,если условие не выполняется – по другому. Такие вычислительные процессыназывают разветвляющимися (ветвящимися). Каждое отдельное направление вычислений называется ветвью.В качестве примера разветвляющегося вычислительного процесса рассмотрим алгоритм вычисления корней квадратного уравненияПример 1.1. Определение действительных корней квадратного уравнения:ax2+bx+c=0.В зависимости от значения дискриминанта D = b2 - 4ac, уравнение имеет либо два действительных корня, либо один, либо вообще не имеет действительныхкорней.

Поэтому, для того, чтобы найти корни квадратного уравнения, необходимо предварительно вычислить дискриминант D и проверить выполнение условийD<0 и D=0. Схема алгоритма вычисления корней квадратного уравнения приведена на рисунке 1.1.НачалоВводA, B, CD:=B2- 4ACда‘Нет действ.корней’нетD<0даD=0нетX:=-B/(2A)X1,2:=(-B±±ÖD)/2A‘Корниравны’,X‘X1=’,X1,‘X2=’,X2КонецРисунок 1.1 – Схема алгоритма вычисления действительных корней квадратного уравненияЕсли условий много, то процесс составления алгоритма, содержащего минимальное количество проверок, может вызвать некоторые трудности.

В этомслучае бывает удобным использовать, так называемые, таблицы решений.Таблицы решений. Таблица решений составляют следующим образом. Повертикали выписывают все условия, от которых зависят дальнейшие вычисления,а по горизонтали – все варианты вычислений. На пересечении каждого столбца истроки указывают: букву Y, если для данного варианта условие должно выполняться, букву N, если условие обязательно должно не выполняться, прочерк, если исход сравнения не важен.7Например, для алгоритма вычисления корней квадратного уравнения можносоставить следующую таблицу:Нет корнейx  -b/ 2 ax   (b D / 2aD 0YNND 0NYNСхему алгоритма строят по таблице. Сначала проверяют выполнение первого условия.

Из таблицы следует, что первое условие должно выполняться толькодля первого варианта решения, поэтому после его проверки ветвь «да» соответствует случаю «нет корней». В ветви «нет» необходимо проверить условие D=0 и,в зависимости от выполнения этого условия, указать оставшиеся два случая.Иногда, составленная таблица решений имеет сложный вид.

Рассмотрим,например, таблицу:Р1Р2Р3Р4У сл о ви е 1Y-NYУ сл о ви е 2NYNNУ сл о ви е 3Y--Nгде P1, P2, P3, P4 – варианты решений.Если сразу приступить к построению алгоритма, то будет получена схемаалгоритма, приведенная на рисунке 1.2.AнетдаP2Условие2Условие1нетдадаP3нетУсловие2даP2Условие3 нетP1P4BРисунок 1.2 – Неоптимальная схема фрагмента алгоритмаЭтот алгоритм не кажется простым, и его построение вызывает определенные трудности, но его можно существенно упростить, если в таблице поменятьместами проверяемые условия. Кроме того, для удобства построения алгоритма,целесообразно поменять местами столбцы таблицы:Р1Р4Р3Р2У сл о ви е 2NNNYУ сл о ви е 1YYN-У сл о ви е 3YN--Алгоритм, построенный по такой таблице, окажется значительно проще, ктому же его построение требует меньших усилий (см.