InformatikaMetodicheskieUkazania

Вариант 25

1.Построить таблицу истинности для формулы В (С А С) В

2.Построить логическую схему по формуле ( A D) (B D) .

3.Определить логическую функцию, реализуемую логической схемой

41

ПРАКТИЧЕСКОЕ ЗАНЯТИЕ 4 АЛГОРИТМИЗАЦИЯ

Цель занятия – научиться читать блок-схемы простых алгоритмов.

4.1. Определение алгоритма Основные алгоритмические конструкции

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

Графические обозначения блоков, которые используются в блок-схеме, стандартизованы. Некоторые из часто используемых блоков приведены в табл.

4.1.

Таблица 4.1

Изображение основных блоков на блок-схеме

Обозначение блока

Пояснение

Процесс (вычислительное действие, реализованное операцией присваивания)

Решение (проверка условия, реализующая условный переход)

Начало, конец алгоритма

Ввод исходных данных, вывод результатов

Основные алгоритмические конструкции – следование, ветвление и цикл. Алгоритм, в котором действия выполняются последовательно, одно за дру-

гим, называется линейным (рис. 4.1).

Алгоритм, при выполнении которого порядок следования команд определяется в зависимости от результатов проверки некоторых условий, называют раз-

ветвляющимся.

42

Рис. 4.1. Блок-схема и пример линейного алгоритма Запись на псевдокоде линейного алгоритма

Действие	1	a	=	5; i =	1;
Действие	2	S	=	a * (i	+ 1)

Если условие является истинным, то выполнение алгоритма происходит по ветке «да», если условие является ложным, то выполнение алгоритма происходит по ветке «нет» (рис. 4.2). Ветвление может быть неполным, тогда по выходу «Нет» никакие действия не выполняются.

Рис. 4.2. Блок-схема и пример разветвляющегося алгоритма Запись на псевдокоде разветвляющегося алгоритма

	Полное ветвление		Неполное ветвление
Если условие		Если (a>0)	Если (a>0)
То	Действия 1	То а=а-1	То а=а-1
Иначе	Действия 2	Иначе а=а+1	Все если
Все если		Все если

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

1. Цикл с предусловием, или цикл «пока». Цикл работает следующим образом. Сначала проверяется условие. Если оно истинно, то выполняется последовательность команд, которая идет по ветке «да». После выполнения этих действий алгоритм вновь возвращается на проверку условия. Если на каком-либо шаге оно станет ложным, то выполняются те действия, которые записаны по ветке «нет». Цикл заканчивается. Блок-схема такого цикла показана на рис. 4.3.

Рис. 4.3. Блок-схема и пример цикла с предусловием Запись на псевдокоде цикла с предусловием

нц	нц
Пока условие повторять	Пока (a<5)повторять
Серия действий	b=b-k
кц	кц

2. Цикл с постусловием (или цикл «до») работает следующим образом. Сначала выполняются действия, которые стоят перед проверкой условия. Затем

43

проверяется условие выхода из цикла. Если условие «ложно» (выход «нет»), то серия команд опять выполняется. Выполнение цикла продолжается до тех пор, пока условие не станет истинным. Тогда выполняются те действия, которые стоят по ветке «да». Блок-схема такого цикла показана на рис. 4.4.

Рис. 4.4. Блок-схема и пример цикла с постусловием

Запись на псевдокоде цикла с постусловием

нц	нц
До Серия действий	До b = b - k
Пока (условие)	Пока(a < 5)
кц	кц

4.2. Чтение алгоритма

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

Пример 4.1. Определите значение переменной c после выполнения фрагмента алгоритма (рис. 4.6).

b=0;

c=0;

нц

Пока (b=11) повторять c=c+b;

b=b+1;

кц

Рис. 4.6. Блок-схема и псевдокод примера 4.1 Составим таблицу выполнения алгоритма (табл. 4.2).

					Таблица 4.2
c= с +b	b=b + 1	b = 11?	c= с +b	b=b + 1	b = 11?
0	0	0 = 11? Нет	10 + 5 = 15	5 + 1 = 6	6 = 11? Нет
0 + 0 = 0	0 + 1 = 1	1 = 11? Нет	15 + 6 = 21	6 + 1 = 7	7 = 11? Нет
			44

0	+ 1	= 1	1 + 1 = 2	2 = 11? Нет	21	+ 7 = 28	7	+ 1	= 8	8 = 11? Нет
1	+ 2	= 3	2 + 1 = 3	3 = 11? Нет	28	+ 8 = 36	8	+ 1	= 9	9 = 11? Нет
3	+ 3	= 6	3 + 1 = 4	4 = 11? Нет	36	+ 9 = 45	9	+ 1	= 10	10	= 11? Нет
6	+ 4	= 10	4 + 1 = 5	5 = 11? Нет	45	+ 10 = 55	10 + 1 = 11			11	= 11? Да

Ответ: с = 55

Пример 4.2. Определите значение переменной m после выполнения фрагмента алгоритма, изображенного на рис. 4.7.

m=54;

n=16;

нц

Пока (m = n) повторять Если (m > n)

То n = n - m

Иначе m = m - n

кц

Рис. 4.7. Блок-схема и псевдокод примера 4.2 Составим таблицу выполнения алгоритма (табл. 4.3).

							Таблица 4.3
	m = n?		m > n?		m = m – n			n = n – m
				54			16
54 = 17? Нет		54 > 16? Да		54	– 16	= 38
38 = 17? Нет		38 > 16? Да		38	– 16	= 22
22 = 17? Нет		22 > 16? Да		22	– 16	= 6
6	= 17? Нет	6	> 16? Нет				16	– 6 = 10
6	= 10? Нет	6	> 10? Нет				10	– 6 = 4
6	= 4? Нет	6	> 4? Да	6 – 4 = 2
2	= 4? Нет	2	> 4? Нет				4 – 2 = 2
2	= 2? Да

Ответ: m = 2

4.3. Задания для самостоятельного выполнения

Указания к выполнению задания

1.Прочитайте теоретический раздел и разберите примеры 4.1–4.2.

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

45

3. Неаккуратно оформленные задания приниматься не будут.

Вариант 1	Вариант 2
Дано n = 10. Вычислить n-е значение	Дано n = 12. Вычислить n-е значение
переменной b.	переменной d.

Вариант 3	Вариант 4
Дано n = 8. Вычислить n-е значение	Дано n = 12. Вычислить n-е значение
переменной z.	переменной c.

Вариант 5	Вариант 6
Дано n = 8. Вычислить n-е значение	Дано n = 10. Вычислить n-е значение
переменных z и w.	переменных c и d.

46

Вариант 7	Вариант 8
Дано n = 12. Вычислить n-е значение	Дано n = 14. Вычислить n-е значение
переменной с.	переменной y2 при х = 4.

Вариант 9	Вариант 10
Дано n = 10. Вычислить n-е значение	Дано n = 12. Вычислить n-е значение
переменной х.	переменной y при х = 6.

Вариант 11	Вариант 12
Дано n = 10. Вычислить n-е значение	Дано n = 11. Вычислить n-е значение
переменных х и y.	переменной с.

47

Вариант 13	Вариант 14
Дано n = 11. Вычислить n-е значение	Дано n = 10. Вычислить n-е значение
переменной z.	переменной y.

Вариант 15	Вариант 16
Дано n = 5. Определить значение це-	Определить значение целочисленной
лочисленной переменной S.	переменной S.

Вариант 17	Вариант 18
Определить значение целочисленной	Определить значение целочисленной
переменной S.	переменной S.
	48

Вариант 19	Вариант 20
Определить значение целочисленной	Определить значение целочисленной
переменной S.	переменной S.

Вариант 21	Вариант 22
Определить значение целочисленной	Определить значение целочисленной
переменной S.	переменной S.

Вариант 23	Вариант 24
Определить значение целочисленной	Определить значение целочисленной
переменной S.	переменной S.

49

50