Тема 4. Алгоритмические решение задач. Лекция №11. Блок-схемы, разработка алгоритма, примеры. (1час)

1. Задача на построение блок-­схемы простого алгоритма, записанного на естественном языке.

 

ПОСТАНОВКА ЗАДАЧИ

 

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

 

Для нахождения НОД воспользуемся алгоритмом Евклида.

 

Суть алгоритма Евклида:

Словесная форма записи: Чтобы найти НОД двух натуральных чисел надо большее число заменять разностью большего и меньшего до тех пор, пока они не сравняются.

 

Формульный способ записи:

НОД(m,n) вычисляется через НОД(m-n,n) и так далее, до тех пор, пока m и n не сравняются в соответствии со следующим правилом:

НОД(m-n,n), если m>n

НОД(m,n)= НОД(n-m,m), если m<n

m, если m=n

т.е. если d является НОД(m,n), то это же число d будет являться НОД меньшего числа из этой пары и их разности.

 

Блок – схема

Программа на ЯП Basic   10 rem НОД (M,N)     20 input “Введите M,N”; M%, N%   30 A%=M% : B%=N% 40 if M% = N% then 70   50 if M%>N% then M%=M%-N% else N%=N%-M% 60 goto 40 70 print “НОД(“; A% ;”,”; B%; “=“; M% 80 end

Программа на ЯП Pascal   program NOD; var A,B,M,N: integer; begin write (‘M=‘); readln (M); write (‘N=‘); readln (N); A:=M; B:=N; while M< >N do begin if M>N then M:=M-N else N:=N-M end; write (‘НОД(‘, A, ’,’ , B, ‘)=‘, M); readln; end.

2. Задача на разработку алгоритма для исполнителя типа «робот» или «черепашка».

 

Постановка задачи

Написать программу для исполнителя «черепашка», которая рисует «паутинку». (См. рис. 2.2)

 

Математическая модель

 

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

Рис. 2.1

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

 

Технология решения

 

По команде ПОВТОРИ 3 [ВП 10 ПР 120] черепашка рисует треугольник с длиной стороны 10 шагов.

По команде ПОВТОРИ 3 [ВП 20 ПР 120] черепашка рисует треугольник с длиной стороны 20 шагов. Аналогично рисуется треугольник с длиной 30 шагов.

 

 

Перейдем в текстовый режим командой CTRL+F и научим черепашку новому слову –– СЕКТОР (См. рис. 2.1 )

ЭТО СЕКТОР

ПОВТОРИ 3 [ВП 10 ПР 120]

ПОВТОРИ 3 [ ВП 20 ПР 120]

ПОВТОРИ 3 [ ВП 30 ПР 120]

КОНЕЦ

 

Вся паутинка получается по команде:

ПОВТОРИ 6 [ СЕКТОР ПР 60]

 

Рис. 2.2

 

Постановка задачи

Разработать алгоритм перехода Робота из клетки А в клетку В при наличии препятствия на рабочем поле (См. рис 2.3).