Министерство образования и науки Российской Федерации
Федеральное агентство по образованию
Южно-Российский государственный технический университет
(Новочеркасский политехнический институт)
Шахтинский институт (филиал) ЮРГТУ (НПИ)
МЕТОДИЧЕСКИЕ УКАЗАНИЯ
К ПРАКТИЧЕСКИМ ЗАНЯТИЯМ
по дисциплине
«АЛГОРИТМИЗАЦИЯ И ПРОГРАММИРОВАНИЕ»
Новочеркасск 2007
УДК 681.3(076.5)
Рецензент – доцент В.В. Луценко
Составитель Бондаренко А.И.
Методические указания к практическим занятиям
по дисциплине «Алгоритмизация и программирование»
/ Сост. А.И. Бондаренко; Шахтинский ин-т (филиал) ЮРГТУ (НПИ). – Новочеркасск: ЮРГТУ, 2007. - 16 с. – 50 экз.
Методические указания содержат теоретический материал и задачи для разработки алгоритмов.
Предназначены для студентов первого курса специальностей 230201«
Информационные системы и технологии»
и 0808001 «Прикладная информатика».
УДК 681.3(076.5)
© Шахтинский институт ЮРГТУ, 2007
© Бондаренко А.И., 2007
Содержание
1. Общие сведения об алгоритмах........................................................... 4
2. Линейные вычислительные алгоритмы.............................................. 7
3. Разветвляющиеся алгоритмы............................................................... 8
4. Циклы................................................................................................... 10
5. Массивы............................................................................................... 12
6. Разработка типовых алгоритмов........................................................ 14
Библиографический список.....................................................................15
1. ОБЩИЕ СВЕДЕНИЯ ОБ АЛГОРИТМАХ
Одним из основных этапов решения задачи на ЭВМ является разработка алгоритма, т.е. сведение её к последовательности конечного числа операций, которую необходимо выполнить в определённом порядке, чтобы получить нужный результат. Именно последовательность действий обозначается ёмким словом - алгоритм. Это порядок решения задачи. Этим понятием мы часто пользуемся и в повседневной жизни. Например, в кулинарии, при приготовлении лекарств и т.д. Алгоритмы представляют самостоятельную ценность как интеллектуальные ресурсы общества.
Строгое математическое определение термина “алгоритм” принадлежит математикам А. Н. Колмогорову и А. А. Маркову. Проблемы, связанные с изучением самого понятия алгоритма, выросли в настоящее время в отдельную “теорию алгоритмов”. Потребность такой теории вызвана бурным развитием ЭВМ, а также средств автоматизированного проектирования промышленных роботов, автоматизированных линий, систем управления. Во всех случаях требуется создание алгоритмов выполнения тех или иных операций разной степени сложности. Что же мы называем алгоритмом?
В соответствии с ГОСТ 19. 004-80 “алгоритм – точное предписание, определяющее вычислительный процесс, ведущий от варьируемых начальных данных к искомому результату”. В литературе встречаются различные трактовки термина “алгоритм”. Приведем их.
Алгоритм
– система формальных правил, четко и однозначно определяющая процесс выполнения заданной работы в виде конечной последовательности действий.
Основными изобразительными средствами алгоритмов являются следующие способы их записи: словесная, формульно – словесная, графическая, на языках программирования.
Словесный
– содержание этапов вычислений задается на естественном языке в произвольной форме. Достоинства этого способа: общедоступность, возможность описывать алгоритм с любой степенью детализации.
Например, в "Началах" древнегреческого математика Евклида (III век до н.э.) описан алгоритм нахождения наибольшего общего
4
делителя (НОД) двух заданных чисел двух чисел. Евклид писал:
а) «обозревай два числа и переходи к следующему указанию;
б) если числа равны, то каждое из них есть НОД, если нет –
переходи к следующему указанию;
в) вычитай из большего числа меньшее и обозревай два числа:
вычитаемое и разность. Переходи к указанию б)».
Формульно-словесный
способ описания алгоритмов основан на записи содержания выполняемых действий с использованием изобразительных возможностей языка математики, дополненного с целью указания необходимых пояснений средствами естественного языка.
Например, требуется написать алгоритм вычисления площади треугольника по трем сторонам.
п.1 Вычислить полупериметр треугольника p=(a+b+c)/2
Þ п.2
п.2 Вычислить S
= Þ п.3
п.3 Вывести на печать значение S
, как искомый результат и прекратить вычисления.
При использовании этого способа может быть достигнута любая степень детализации.
Блок-схемный способ
- это графическое изображение логической структуры алгоритма, в котором каждый этап процесса переработки данных представляется в виде геометрических фигур (блоков), имеющих строгую конфигурацию в соответствии с характером выполняемых действий (рис.1).
Составление блок-схем алгоритмов осуществляется в соответствии с требованиями ГОСТ 19701–90 “Схемы алгоритмов, программ, данных и систем. Условные обозначения и правила выполнения”.
Изображение схем алгоритмов осуществляется по определенным правилам. Каждая схема должна начинаться и заканчиваться символами, обозначающими начало и окончание алгоритма. Все блоки в схеме располагаются в последовательности сверху вниз и слева направо. Отдельные блоки соединяются между собой линиями потоков информации. Направление линий потока сверху вниз и справа налево принимаются за основные и стрелками не обозначают.
5
Рис.1.
Условные обозначения блоков выполняемых действий
Алгоритм – точный порядок действий, определяющий процесс перехода от исходных данных к искомому результату.
Алгоритм должен обладать следующими свойствами:
· детерминированностью - однозначностью получаемого результата при одних и тех же исходных данных;
· массовостью - возможностью получения искомого результата при различных исходных данных для некоторого класса задач;
· результативностью - для любых допустимых исходных данных алгоритм должен через конечное число шагов завершить свою работу, либо подать сигнал о том, что данный алгоритм неприменим для решения поставленной задачи;
· дискретностью - возможностью разбиения определенного алгоритмического процесса на отдельные элементарные этапы, выполнение которых человеком или ЭВМ не вызывает сомнения, а результат выполнения каждого элементарного этапа определен и понятен.
6
Алгоритм, записанный на языке программирования, называется программой. В этом случае алгоритм представляется в виде последовательности операторов языка. Языки программирования - изобразительные средства для непосредственной реализации программы на ЭВМ.
Каждая машина имеет свой собственный язык (машинный язык) и может выполнять программы только на этом языке. Это последовательность машинных команд. Писать программы на машинном языке очень сложно и утомительно. Для повышения производительности труда программистов применяются искусственные языки программирования. При этом требуется перевод программы, написанной на таком языке, на машинный язык. Этот перевод выполняет транслятор. Наиболее часто встречающимся транслятором интерпретирующего типа является транслятор с языка Бейсик, где команды читаются, преобразуются и выполняются сразу. Итогом работы такого транслятора являются требуемые результаты.
Транслятор с Паскаля – компилирующего типа: сначала весь текст программы на языке Паскаль переводится в текст на машинном языке (получается, так называемый, объектный модуль программы), который затем обрабатывается Редактором межпрограммных связей и только после этого программа будет готова к выполнению.
Текст программы на исходном языке переводится в текст на ма-шинном языке и получается так называемый объектный модуль. Затем объектный модуль должен быть обработан программой Редактором межпрограммных связей и только после этого программа будет готова к выполнению.
2. ЛИНЕЙНЫЕ ВЫЧИСЛИТЕЛЬНЫЕ АЛГОРИТМЫ
Алгоритмы бывают чрезвычайно сложными, многоступенчатыми по своей структуре и состоят из тысяч отдельных операций. При всем многообразии алгоритмов решения задач в них можно выделить три основных (канонических) вида алгоритмических структур: линейную, ветвящуюся, циклическую. С помощью этих трех видов структур можно построить алгоритм любой сложности.
Доказано, что любую программу можно написать, используя
7
комбинации этих трех базовых канонических структур алгоритмов.
Линейным
называется алгоритмический процесс, при котором все этапы решения задачи выполняются в порядке следования записи этих этапов. Порядок выполнения этапов не зависит ни от исходных данных, ни от результатов выполнения предыдущих этапов.
В следующих задачах составить блок-схемы алгоритмов, реализующих линейные вычислительные процессы.
1. Найти абсциссу точки O(x,0), одинаково удаленной от точек А(0,a) и B(b, 0).
2. Определить сумму цифр заданного трехзначного числа.
3. Для заданного q
найти один из корней уравнения Ln(ctgx-1)=q
.
4. Вычислить периметр, площадь и углы (в градусах) прямоугольного треугольника по заданным длинам катетов.
5. По заданным длинам сторон треугольника вычислить периметр,
площадь, углы (в градусах) и высоты.
6. Решить относительно х уравнение (x-a2
)(x+b2
)=c2
.
7. Треугольник задан координатами вершин. Найти его площадь и расстояние от центра его тяжести до вершин.
8. Кривая (Аx) 2
+(By) 2
=C2
пересекается прямой y=Dx
в точках M и N. Точку K(C/A ,0) соединили с точками M и N. Найти периметр
D MNK и угол (в градусах) при вершине K.
9. Найти отношение радиусов вписанной и описанной окружностей около треугольника, заданного длинами сторон.
10. Идет k-я секунда суток. Найти сколько полных часов (h), полных минут (m) и секунд (s) прошло к этому моменту времени ? Задать k=13257.
3. Разветвляющиеся алгоритмы
Вычислительный процесс, который в зависимости от выполнения определенных условий реализуется по одному из нескольких заранее предусмотренных (возможных) направлений, называется разветвляющимся
. Каждое направление вычислений называется ветвью. Выбор ветви осуществляется в результате проверки некоторого логического условия.
8
Каждое отдельное направление обработки информации называется ветвью и ведет к общему выходу, так что работа алгоритма продолжается независимо от того, какая ветвь будет выбрана. Базовая структура ветвления
приведена на рис. 2.
Рис. 2. Базовая структура Рис. 3. Структура ветвления
ветвления “обход”
В частном случае может оказаться, что для одного из выбранных путей никаких действий выполнять не надо (рис.3). Такая структура получила название обход.
В следующих задачах составить блок-схемы алгоритмов, реализующих разветвляющиеся вычислительные процессы.
1. Решить уравнение (неравенство). При отсутствии решения или бесчисленном множестве решений должен быть напечатан соответ- ствующий текст.
а) ax2
+b=0
б) ax2
+b > 0
в) ax2
+bx + c < 0
2. Проверить, принадлежит ли точка A(x,y) отрезку KM, заданному координатами точек K(x1
,y1
) и M(x2
,y2
).
3. Проверить, существует ли треугольник, заданный координатами
вершин. Является ли он прямоугольным ( равносторонним) ?
4. Решить уравнение (x-a)(x-b)=c
.
5. Найти число точек пересечения прямой y=kx+p
с окружностью
радиуса R и центром в точке (a,b).
6. Найти первый отрицательный член последовательности
xn
=
sin
(
p
n
/17)
+ cos
(
p
n
/12)
.
7. Составить блок-схему алгоритма Евклида нахождения НОД(a,b).
9
8. Решить биквадратное уравнение ax
4
+
bx
2
+
c
= 0.
9. Дано натуральное число N<100, определяющее возраст человека
(в годах). Дать для этого числа наименования "год", "года" или "лет".
Например, 1 год, 23 года, 45 лет и т.д.
10. Представить алгоритмы решения следующих задач.
· Определить какой четверти принадлежит точка T(x,y).
· Выяснить, является ли данное число k
чётным ?
· Принадлежит ли точка O(x,y) треугольнику, заданному координатами вершин.
· Принадлежит ли точка O(x,y) области, границы которой заданы уравнениями:
а) y=x(5-x)
и y=x-1
;
б) y
-2
x
=2,
y
+
x
=2,
x
+
y
=1,
x
-2
y
=2
.
11. Найти отрицательные значения функции y=x-sinx
при изменении х
Î[0,3] с шагом h
=0,2.
12. Даны четыре точки на плоскости А(x1
,y1
), B(x2
,y2
), C(x3
,y3
), D(x4
,y4
). Является ли четырехугольник ABCD параллелограммом ?
13. Лежат ли точки А(x1
,y1
); B(x2
,y2
); C(x3
,y3
) на одной прямой. Если нет, найти угол АВС.
14. Будут ли прямые A
1
x
+
B
1
y
+
C
1
=0
и A
2
x
+
B
2
y
+
C
2
=0
пересекаться. Если да, то найти угол между ними.
4. ЦИКЛЫ
Решение многих задач содержит повторяющиеся действия. Например, нужно вычислить значение функции при десяти различных значениях аргумента. Вычислительные процессы, в которых возникает необходимость многократного повторения одних и тех же действий, но над различными значениями переменных, определяющих эти действия, называются циклическими, а многократно повторяемые участки – циклами.
Различают циклы арифметические (с заранее известным числом повторений) и итерационные (число повторений которых заранее не известно и выход из которых осуществляется по выполнению некоторого условия).
10
Рассмотрим алгоритм вычисления значений функции y=
F
(x)
при изменении xo
£
x
£
xk
с шагом h
. Количество повторений цикла
определяется по формуле k=[(xk
-xo
)/h]+1
, где [ ] - целая часть частного. Значения аргумента могут быть заданы формулой x=xo
+h(i-1)
,
где 1
£
i
£
k
. Переменную i называют счетчиком цикла. Блок-схемы алгоритмов для решения этой задачи имеют вид:
Рис. 4. Цикл с логическим Рис. 5. Алгоритм с известным
условием конца цикла числом повторений
11
На блок-схеме (рис. 4) последовательность операторов, составляющая тело цикла, будет повторяться до тех пор пока логическое условие не
будет выполняться. В блок-схеме (рис. 5) сразу определено число повторений цикла, которое вычисляется перед входом в тело цикла.
Представить алгоритмы решения следующих задач.
1. Указать значения переменных после выполнения фрагмента программы
for i:=2 to 5 DO
x:=i; y:=x+i;
write(x,y)
2. Найти все делители заданного числа N.
3. Последовательность задана формулой общего члена Xn=1/(n2
+5n).
При каком наименьшем n
будет выполняться неравенство Xn < 0,02
4. Вывести на экран отрицательные значения функции y=4x(5-3х2
)
при изменении x
от 1 до 2 с шагом 0,1.
5. Найти десять решений уравнения 5sinx=2
, выразив углы в градусах.
6. Последовательность задана формулой общего члена Xn=5n2
-4n-1
.
Определить (из первых двадцати) члены последовательности:
а) являющиеся нечетными числами;
б) имеющие четные порядковые номера и делящиеся на 3.
7. Пусть x1
=y1
=1, xi
= 3xi-1
, yi
= xi-1
+ yi-1
.
Найти x11
+ y11
.
8. Вывести на печать значения функции z=esinx
(1+сos
p
/y)
, удовлетворяющие условию z>1
при изменении -1
£
x
£
2
c шагом 0,2 и 1
£
y
£
3
с шагом 0,25.
9. Составить таблицу умножения натуральных чисел 1
£
N
£
9
.
10. Составить программу-генератор чисел Пифагора a
,
b
,
c
(
c
2
=
a
2
+
b
2
)
. В основу положить формулы: a
=
m
2
–
n
2
,
b
= 2
m
×
n
,
c
=
m
2
+
n
2
(m
,
n
– натуральные, 1 <
m
<
k
, 1 <
n
<
k
,
k
– данное число).
11. На прямой расположены точки M1
(x1
), M2
(x2
), … M5
(x5
).
Найти расстояния между всевозможными парами точек.
12. Дано натуральное число N. Определить, является ли оно простым или составным ?
12
5. МАССИВЫ
Иногда удобно присвоить имя не одной переменной, а целой группе или, как говорят, массиву переменных. Пусть, например, задана числовая последовательность с общим членом an
=2n+3
. Тогда каждому натуральному n
(номеру члена) соответствует число - член последовательности. Так, a1
=5, a2
=7 и т.д. В программировании такую последовательность задают массивом A(n) =2n+3
, а для обращения к отдельному элементу массива достаточно после его имени
написать в скобках его порядковый номер (индекс). Так,
A
(1)=5,
A
(2)=7
. Элемент массива - это переменная с индексом.
Количество индексов у массива определяет его размерность. Рассмотренный массив A, представляющий строку, - это одномерный массив. Если рассматривать числовые таблицы (матрицы), то положение числа в ней будет определяться двумя числами (номер строки и номер столбца). Такие массивы называются двумерными. Например, B(2,5) - элемент двумерного массива, расположенный во второй строке и пятом столбце. В памяти ЭВМ двумерные массивы располагаются по строкам.
Представить алгоритмы решения следующих задач.
1. Заданы два одномерных массива различных размеров. Объединить
их в один массив, включив второй массив между k-м и (k+1)-м элементами первого.
2. Разместить вычисленные значения функции y=1+sin(
p
/8-x)
для х
Î[0,2] с шагом h
=0,2 в одномерный массив Y.
3. “Cжать” числовой массив, выбросив из него отрицательные числа.
4. Определить, является ли заданный массив упорядоченным.
5. В массиве М(10) содержатся числа 0,1,2 и ничего кроме них. Упорядочить массив по возрастанию.
6. Дан массив целых чисел. Найти сколько в нем пар одинаковых со-
седних элементов.
7. Даны целые числа a1
, a2
, a3
, a4
.
Получить целочисленную квадрат-
ную матрицу [bi j
], у которой bi j
=ai
-3aj
(i,j
=1,2,3,4).
8. В одномерном массиве все отрицательные элементы переместить в начало массива, а остальные – в конец с сохранением порядка следования. Дополнительный массив не заводить.
13
9. В квадратной матрице заменить нулями все ее элементы, распо-
ложенные на главной диагонали и выше нее.
10. В целочисленной последовательности есть нулевые элементы. Создать массив из номеров этих элементов.
11. Задан целочисленный массив размерности N. Есть ли среди его элементов простые числа ? Если да, то вывести номера этих элементов.
12. Найти k
-й член последовательности хn
=n
×
хn-1
+1/n
, если х0
=1.
13. Дан целочисленный массив X(50). Нечетные элементы заменить нулями.
6. РАЗРАБОТКА ТИПОВЫХ АЛГОРИТМОВ
Очень часто встречаются задачи, в которых используются алгоритмы нахождения сумм, произведений, наибольших и наименьших значений.
При вычислении произведения перед циклом задают начальное значение произведения, равное P=1, а внутри цикла накапливают произведение, используя оператор присваивания вида P:=P*X, где X – сомножитель, P - промежуточное произведение.
При вычислении суммы вычисляют слагаемые Х и накапливают сумму S в цикле, используя оператор S:=S+X. Начальное значение суммы, как правило, полагают равным нулю.
Нахождение наибольшего (наименьшего) значений выполняется в цикле. При этом текущее значение сравнивается с наибольшим из всех предыдущих значений. Если оно окажется больше, то его надо считать новым наибольшим значением. В противном случае, наибольшее значение остается прежним. Выбор начального наибольшего значения зависит от условия задачи.
Разработать алгоритмы решения следующих задач
1. Найти наибольшее значение функции y=6e-x
+sin2x+x
при 0£ x
£ 2,5.
2. Определить число отрицательных, положительных и нулевых элементов массива T(12).
3. Найти сумму произведений элементов первой строки на второй
столбец матрицы А(6,6), где аij
=(2i-j)(i+2j).
14
4. Заданы два одномерных массива различных размеров. Объединить их в один массив, записав второй массив после максимально- го элемента первого массива.
5. Дана матрица S(4,5), где sij
=1-sin(i-2/j)
. Найти разность между наи- большим её элементом и суммой элементов второй строки.
6. В матрице P(6,5), где pij
=1+ 2(i-3j)2
найти среднее арифметическое каждого из столбцов.
7. Дана матрица M(5,6), где mij
=(i+j)(2i+3j)
. Найти сумму чётных элементов.
8. Найти в каждой строке матрицы максимальный элемент и помес-
тить его на место первого элемента строки.
9. Найти сумму диагональных элементов квадратной матрицы.
10. На плоскости заданы N точек. Найти номера точек с максимальным расстоянием между ними.
11. На интервале [2;N] найти натуральное число с максимальной суммой делителей.
12. Действительно ли все значения функции натурального аргумента y
=
x
2
+
x
+ 17
при 0 £ х
£ 17 являются простыми числами ?
13. В одномерном массиве поменять местами наибольший и наименьший элементы.
14. В одномерном массиве найти сумму элементов, расположенных между максимальным и минимальным элементами.
15. Найти произведение двух заданных матриц.
БИБЛИОГРАФИЧЕСКИЙ СПИСОК
1. Н.Вирт. Алгоритмы+структуры данных=программы. -М.: Мир, 1985.
2. Федоренко Ю. Алгоритмы и программы на Turbo Pascal. -СПб.:
Питер, 2001г.
3. Иванова Г.С. Основы программирования. -М.: МГТУ им. Н.Э. Баумана, 2002.
4. Кнут Д.Э. Искусство программирования. -М.: Вильямс, 2000.
5. Керниган Б. Практика программирования. -СПб.: Невский Диалект, 2001. 6. Камаев В.А.Технологии программирования. -М.: Высш. Школа, 2005.
15
Учебно-практическое издание
Методические указания
к практическим занятиям по дисциплине
«Алгоритмизация и программирование»
Составитель Бондаренко Александр Иванович
Редактор И.И.
Кузнецова
Темплан 2007 г
.
Подписано в печать 8.11.2007 г.
Формат 60х841
/16
. Бумага офсетная. Ризография.
Усл.-печ.л. 0,93.
Уч.-изд. л. 1,0 .
Тираж 50 .
Южно-Российский государственный технический университет
Адрес ун-та: 346428, г. Новочеркасск, ул. Просвещения, 132
Шахтинский институт (филиал) ЮРГТУ (НПИ)
Адрес ин-та: 346500, г. Шахты, пл. Ленина, 1