ЛИНЕЙНЫЕ ВЫЧИСЛИТЕЛЬНЫЕ АЛГОРИТМЫ

 

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

Доказано, что любую программу можно написать, используя

 

7

комбинации этих трех базовых канонических структур алгоритмов.

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

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

 

1. Найти абсциссу точки O(x,0), одинаково удаленной от точек А(0,a) и B(b, 0).

2. Определить сумму цифр заданного трехзначного числа.

3. Для заданного q найти один из корней уравнения Ln(ctgx-1)=q.

4. Вычислить периметр, площадь и углы (в градусах) прямоугольного треугольника по заданным длинам катетов.

5. По заданным длинам сторон треугольника вычислить периметр,

площадь, углы (в градусах) и высоты.

6. Решить относительно х уравнение (x-a²)(x+b²)=c²_.

7. Треугольник задан координатами вершин. Найти его площадь      и расстояние от центра его тяжести до вершин.

8. Кривая (Аx) ²+(By) ²=C²  пересекается прямой y=Dx в точках M  и N. Точку K(C/A ,0) соединили с точками M и N. Найти периметр

D MNK и угол (в градусах) при вершине K.

9. Найти отношение радиусов вписанной и описанной окружностей
около треугольника, заданного длинами сторон.

10. Идет k-я секунда суток. Найти сколько полных часов (h), полных
минут (m) и секунд (s) прошло к этому моменту времени ?  Задать
k=13257.

 

Разветвляющиеся алгоритмы

 

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

 

8

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

 

   Рис. 2. Базовая структура               Рис. 3. Структура ветвления

         ветвления                                           “обход”

 

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

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

1. Решить уравнение (неравенство). При отсутствии решения или
бесчисленном множестве решений должен быть напечатан соответ-
ствующий текст.

   а) ax²+b=0     б) ax²+b > 0      в) ax²+bx + c < 0

2. Проверить, принадлежит ли точка A(x,y) отрезку KM, заданному координатами точек K(x₁,y₁) и M(x₂,y₂).

3. Проверить, существует ли треугольник, заданный координатами

вершин. Является ли он прямоугольным ( равносторонним) ?

4. Решить уравнение (x-a)(x-b)=c.

5. Найти число точек пересечения прямой y=kx+p с окружностью

радиуса R и центром в точке (a,b).

6. Найти первый отрицательный член последовательности

 x_n = sin ( p n /17)+ cos ( p n /12).

7. Составить блок-схему алгоритма Евклида нахождения НОД(a,b).

 

9

8. Решить биквадратное уравнение ax ⁴ + bx ² + 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. Даны четыре точки на плоскости А(x₁,y₁), B(x₂,y₂), C(x₃,y₃),
 D(x₄,y₄). Является ли четырехугольник ABCD параллелограммом ?

 13. Лежат ли точки А(x₁,y₁); B(x₂,y₂); C(x₃,y₃) на одной прямой. Если
 нет, найти угол АВС.

 14. Будут ли прямые A ₁ x + B ₁ y + C ₁ =0 и A ₂ x + B ₂ y + C ₂ =0 пересекаться.
 Если да, то найти угол между ними.

 

ЦИКЛЫ

 

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

Различают циклы арифметические (с заранее известным числом повторений) и итерационные (число повторений которых заранее не известно и выход из которых осуществляется по выполнению некоторого условия).

 

10

Рассмотрим алгоритм вычисления значений функции y= F (x) при изменении x_o £ x £ x_k с шагом h. Количество повторений  цикла 

определяется по формуле k=[(x_k-x_o)/h]+1, где [ ] - целая часть частного. Значения аргумента могут быть заданы формулой x=x_o+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/(n²+5n).
При каком наименьшем n будет выполняться неравенство Xn < 0,02

4. Вывести на экран отрицательные значения функции y=4x(5-3х²)

при изменении x от 1 до 2 с шагом 0,1.

5. Найти десять решений уравнения 5sinx=2, выразив углы в градусах.

6. Последовательность задана формулой общего члена Xn=5n²-4n-1.

Определить (из первых двадцати) члены последовательности:

   а) являющиеся нечетными числами;

   б) имеющие четные порядковые номера и делящиеся на 3.

7. Пусть x₁=y₁=1, x_i = 3x_i-1, y_i = x_i-1 + y_i-1.

Найти x₁₁ + y₁₁.

8. Вывести на печать значения функции z=e^sinx(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 ² = a ² + b ² ). В основу положить формулы: a = m ² – n ² , b = 2 m × n , c = m ² + n ²  (m , n – натуральные, 1 < m < k , 1 < n < k , k – данное число).

11. На прямой расположены точки M₁(x₁), M₂(x₂), … M₅(x₅).

Найти расстояния между всевозможными парами точек.

12. Дано натуральное число N. Определить, является ли оно простым
или составным ?

 

12

МАССИВЫ

 

Иногда удобно присвоить имя не одной переменной, а целой группе или, как говорят, массиву переменных. Пусть, например, задана числовая последовательность с общим членом a_n=2n+3. Тогда каждому натуральному n (номеру члена) соответствует число - член последовательности. Так, a₁=5, a₂=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. Даны целые числа a₁, a₂, a₃, a_{4 .} Получить целочисленную квадрат-

ную матрицу [b_{i j}], у которой b_{i j} =a_i -3a_j  (i,j=1,2,3,4).

8. В одномерном массиве все отрицательные элементы переместить в начало массива, а остальные – в конец с сохранением порядка следования. Дополнительный массив не заводить.

 

13

9. В квадратной матрице заменить нулями все ее элементы, распо-

ложенные на главной диагонали и выше нее.

10. В целочисленной последовательности есть нулевые элементы.
Создать массив из номеров этих элементов.

11. Задан целочисленный массив размерности N. Есть ли среди его элементов простые числа ? Если да, то вывести номера этих элементов.

12. Найти k-й член последовательности х_n=n × х_n-1+1/n , если  х₀=1.

13. Дан целочисленный массив X(50). Нечетные элементы заменить нулями.