Алгоритм - Свойства алгоритма

Угринович, 2009,
© БИНОМ. Лаборатория знаний, 2009
Основы алгоритмизации и объектно-ориентированного программирования

Линейные алгоритмы, ветвление.
Урок №3* Урок одной задачи – поиск НОД

действительности хотим"
Франсуа де Ларошфуко
Приготовление завтрака


2. Решение квадратного уравнения


3. Определение рода

от исходных данных к искомому результату.

древнегреческий математик, известный прежде всего как автор «Начал», самого знаменитого

— сын зороастрийского жреца, прозванный за это ал-Маджуси (маг). Заведовал

на плиту
Ждать, пока вода не закипит
Поднести спичку к горелке
Зажечь спичку
Выключить

газовой горелки
Поднести спичку к горелке
Ждать, пока вода не закипит
Выключить газ

приводит к конечному результату за конечное число шагов
массовость: может применяться

и однозначно задающая процесс решения задач какого-либо типа во всех

и капусту. Лодка может выдержать только старика и одного “пассажира”.

выполнять определенный набор команд.
Набор команд – СКИ (Система Команд Исполнителя).
Алгоритм

…формального или неформального?

к нему 2.
Результат умножьте на 2.
К полученному произведению прибавьте 3.
От

обойдя поле ходом шахматного коня»?
Ответ:
Не игла шьёт,
а руки
A B

1
2345678

Неформальный исполнитель

Система команд Исполнителя алгоритма:
«Вперед N»
«Назад M»
Переменные N и M могут

«Вперед», тогда
х+(х+12)=50;
х=19;
19+12=31 – количество команд «Назад»
2. Будем вести отсчет от

из великих математиков Европы позднего Средневековья. Числовой ряд, который назван

В этом ряду каждое следующее число, начиная с третьего, равно сумме двух предыдущих.
Составьте словесный алгоритм проверки принадлежности введенного числа n ряду Фибоначчи.

1,1,2.
3. Пока введенное число N больше очередного числа Фибоначчи, взять

схем;
На языке программирования.
Блок-схема – это графическое изображение алгоритма в виде определенным

Язык программирования — формальная знаковая система, предназначенная для записи компьютерных программ.

времени, друг за другом.

и периметр треугольника.
Решение:
Входные данные: a, b, c.
Выходные данные:

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

выходные данные:

Решение:
Известны плотность и геометрические размеры цилиндрического слитка, полученного в

которого обеспечивается переход на один из двух возможных шагов, называется

граница H≤100, а нижняя h≥60 и H-h≥30.










Составьте алгоритм, который в

Начало

H, h

H≤100

Нет

Нет

Нет

повышенное

Да

Да

Да

h≥60

пониженное

H-h≥30

не норма

нормальное

Результат

Конец

b, c
D=b²-4*a*c
D

Конец

алгоритма?









Начало
X,Y
Z:=0
X>0
Y>0
Z:=1
Z:=2
Z
Конец
А) Х=1, Y=1

Б) X=1, Y=-1




В) X=-1, Y=1

Z=1
Z=2
Z=0
Нет
Нет
Да
Да

Что бы ты предпочел - два целых яблока или четыре

Алгоритм Евклида – это алгоритм нахождения НОД двух целых положительных чисел

различные методы нахождения НОД двух натуральных чисел:

множители.
2. Разложить число n на простые множители.
3. Выбрать все одинаковые

НОД (5390; 2310) =
= 2*5*7*11=770;

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

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

к шагу 3, иначе перейти к шагу 8.
Если M>N, то

Применим алгоритм для нахождения НОД(238,544) =

НОД(238, 306) =

=НОД(238,68) =

НОД(170,68)=

НОД(102,68)=

НОД(34,68)=

НОД(34,34) = 34

M=238
N=544

остаток целочисленного деления меньше второго числа. Если остаток равен нулю,

от деления M нацело на N.
3. Если R=0, то перейдем

Ввод M,N

Вычислить R – остаток от деления M на N

R=0

M:= N
N:= R

Вывод N

M=238
N=544

N:=544

[238/544]=0 (ост. 238), заменяем: M:=544, N:=238
[544/238]=2 (ост. 68),

чисел постройте их блок-схемы и напишите пошаговый алгоритм.

Метод 1: Даны

слова:
2. Алгоритм, в котором команды выполняются последовательно друг за другом,

1. Алгоритм – это последовательность…

команд, допустимых для исполнителя;

линейным;

3. Алгоритмическая структура выполняющая выбор при истинности или ложности условия называется …

структурой «ветвление».

в следующих отрывках из его произведений?
«Уж небо осенью

«Приходите в половине двенадцатого. Ступайте прямо на лестницу. Коли вы найдете кого в передней, то спросите, дома ли графиня. Вам скажут нет, - делать нечего. Вы должны будете воротиться. Но, вероятно, вы не встретите никого… Из передней ступайте налево, идите все прямо до графининой спальни. В спальне за ширмами увидите две двери: справа в кабинет;… слева в коридор, и тут же узенькая витая лестница, она ведет в мою комнату.»

значение будет иметь переменная Х после выполнения алгоритма при начальном

Начало

Ввод Y,Z

Y<5

ДА

НЕТ

Y:=Y+Z

Y:=Y-Z

Y:=Y+Z

Конец

Ответ:

Y1= -1;

Y2= 3.

I
Конец
Ответ: I= 12
Сколько раз выполнится вывод текста в алгоритме?
Ответ: 6

Изменим условие: I:=I*2

I:=I*2

Сколько раз выполнится вывод текста в алгоритме?

Ответ: бесконечно.

Произойдет "зацикливание" алгоритма, т.е. не будет выполняться основное свойство алгоритма — результативность.

структуры бывают двух типов:
Цикл со счетчиком, в котором тело цикла

Такая последовательность
команд называется
«телом цикла».

из его произведений?

«Жил старик со своею старухой
У самого

Вот пошел он к синему морю;
Видит, — море слегка разыгралось.
Стал он кликать золотую рыбку,
Приплыла к нему рыбка и спросила:
«Чего тебе надобно, старче?»
…

Вот пошел он к синему морю,
(Помутилося синее море.)
Стал он кликать золотую рыбку,
Приплыла к нему рыбка, спросила:
«Чего тебе надобно, старче?»

вариант
II вариант
Х=13; Y=20
Х=30; Y=20