Информатика_Ч1

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

Чтобы подготовить какой-либо алгоритм для решения задачи на ЭВМ, необходимо его записать по определенным правилам в формализованном виде на конкретном алгоритмическом языке.

Задачи на ЭВМ решаются по заранее составленной программе. В соответствии с ГОСТ 19781–83 программа – это данные, предназначенные для управления конкретными компонентами системы обработки данных в целях реализации определенного алгоритма.

В более простом понимании программой называют алгоритм, записанный на каком-либо алгоритмическом языке. Если говорить о программе для ЭВМ, то такая запись представляет собой наряду с описаниями типов и структуры данных задаваемые для ЭВМ инструкции: в какой последовательности, над какими данными и какие операции должна выполнять машина и в какой форме выдавать результат. Задание для ЭВМ таких инструкций обеспечивают операторы.

Оператор – это совокупность символов, указывающих операцию и значения или местонахождение ее операндов (данных, к которым применяется эта операция).

Общая характеристика изобразительных средств алгоритмов

Чтобы довести алгоритмы до пользователя, их необходимо формализовать по некоторым правилам (соглашениям) посредством конкретных изобразительных средств, которые в конечном итоге формируют определенные вычислительные схемы этих алгоритмов. К основным изобразительным средствам алгоритмов относятся следующие способы их записи:

–словесный;

–формульно-словесный;

–блок-схемный;

–на языке операторных схем;

–на псевдокоде;

–на алгоритмическом языке.

Любое более или менее формализованное представление алгоритма независимо от используемых изобразительных средств должно содержать следующие элементы:

–начало и конец вычислительной схемы;

–объекты (данные), над которыми выполняются действия, и результаты выполнения алгоритма;

31

–этапы (шаги) преобразования данных с формализованной записью их содержания;

–указания о последовательности выполнения этапов и отдельных шагов алгоритмического процесса.

При словесном способе записи алгоритма содержание последовательных этапов вычислений задается в произвольной форме на естественном языке.

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

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

взависимости от характера выполняемых операций. Данный способ является строго формальным и наглядным (см. рис. 2.1). Разработаны ГОСТы для построения блок-схем алгоритмов (ГОСТ 19.002–80 содержит условные графические обозначения, размеры и отображаемые ими функции). Эти ГОСТы входят в состав единой системы программной документации под названием «Схемы алгоритмов и программ».

Пример. Блок-схема вычисления наибольшего общего делителя (НОД) двух чисел A и B (рис. 15).

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

(А) и логического оператора ( Р). Схему дополняют специальными операторами управления: ввод данных (В), печать результатов (П), останов процесса (Я) и т. д. Каждый оператор имеет порядковый номер в виде индекса. Введены минимальные правила формализации управления логических схем программ: операторы выполняются

вестественном порядке слева направо; если от оператора слева нет передачи управления оператору справа, то между ними ставится точка с запятой; при выполнении условия логического оператора очередным становится оператор, записанный справа от него, иначе подлежащий выполнению оператор указывается стрелкой. Операторный метод ввел математик А. А. Ляпунов в 1954 г. Данное изобразительное средство положило начало автоматизации программирования.

32

Начало

Ввод A, B

M=A; N=B

	нет
	M ≠ N
	да
да	нет
	M > N
M = M – N	N = N – M

Вывод «НОД=», M

Конец

Рис. 15. Блок-схема алгоритма нахождения НОД

Пример. Алгоритм вычисления НОД двух чисел.

Н В1 А2 А3 Р4 ( M < > N) P5 ( M > N) A6; A7 П8 Я

Здесь В1 – ввод значений А и В; А2, А3 – присваивание их переменным M и N; Р4 , Р5 – проверка условий; А6, А7 – вычисление выражений M – N и N – M с последующим их присваиванием переменным M и N; П8 – печать результата.

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

33

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

Пример. Алгоритм вычисления НОД двух чисел.

Начало Ввод значений А, В

M = A; N = B

ВЫПОЛНИТЬ ПОКА (M < > N) ЕСЛИ M > N ТО

M = M–N

ИНАЧЕ

N = N–M

КОНЕЦ ЦИКЛА

Вывод: «Значение НОД равно» M Конец вычислительного процесса

Все формы записи алгоритмов, кроме алгоритмических языков, являются вспомогательными. Конечная цель такой формализации алгоритма – зафиксировать его на конкретном алгоритмическом языке. При записи алгоритмов на языках программирования учитываются строгие правила конкретного языка.

Основные типы вычислительных процессов

Общая совокупность вычислительных процессов делится на три типа:

–линейные;

–ветвящиеся;

–циклические.

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

Линейным называется такой вычислительный процесс, в котором самостоятельные (отдельные) этапы вычислений выполняются в линейной последовательности их записи, т. е. в естественном порядке. На блок-схеме линейный вычислительный процесс представляется последовательностью блоков, выражающих автономные

34

шаги вычислений. Блоки размещаются сверху вниз в порядке их выполнения (рис. 16, а).

	а	б		в
	S1	да	нет	да
		P		P
				нет
	S2	S1	S2	S1
	S3	S3		S2

Рис. 16. Структура линейной композиции

Вычислительный процесс называется ветвящимся, если в зависимости от исходных условий или промежуточных результатов он реализуется по одному из нескольких заранее предусмотренных (возможных) направлений. Каждое отдельное направление называется ветвью вычислений. Выбор той или иной ветви вычислений осуществляется проверкой выполнения заданного условия, определяющего свойства исходных данных или промежуточных результатов. Схемы алгоритмов ветвящихся процессов задаются с помощью управляющей канонической структуры выбора (рис. 16, б – полная, в – неполная). В случае, например, использования полной схемы управляющей структуры выбора последовательность операторов S1 выполняется, если соблюдается заданное условие P (иначе говоря, значение логического выражения P истинно). При ложности P выполняется другая последовательность операторов S2. После этого управление передается на выход к внешнему оператору S3.

Для составления алгоритма ветвлений по трем или более направлениям используются управляющие структуры выбора с двухуровневой вложенностью и более.

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

35

висимости от значения заданного выражения (рис. 17). Особенность этой структуры в том, что выбор решения здесь не осуществляется в зависимости от истинности или ложности условия, а является вычисляемым.

К

K=1	K=2	K=N

S1			S2		SN

Рис. 17. Структура переключателя

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

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

Из схемы видно, что при соблюдении условия в блоке логики Р выполняется тело цикла и управление передается на проверку окончания цикла. Если цикл не окончен, т. е. условие Р выполняется, то повторно выполняется тело цикла S.

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

36

а	б
нет	S
P	Тело цикла
	да
S	P
Тело цикла

нет

Выход из Выход из цикла цикла

Рис. 18. Структура повторения

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

Взависимости от типа структуры циклы разбиваются на простые

исложные (вложенные). Простыми называются такие циклы, которые не содержат других циклов. Сложные циклы – это циклы, содержащие один или несколько других циклов. Циклы, охватывающие другие циклы, называются внешними; циклы, входящие в другие, – вложенными или внутренними.

2.2. Системы счисления

Системой счисления называется совокупность приемов наименования и записи чисел.

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

37

мире наиболее распространенным является представление чисел посредством арабских цифр 0, 1, 2, …9. Системы счисления различаются выбором базисных чисел и правилами образования из них остальных чисел. Например, в римской системе счисления базисными являются числа 1, 5, 10, 50, 100, 500, 1000, обозначаемые I, V, X, L, C, D, M, а другие числа получаются путем сложения и вычитания базисных. Системы счисления, в которых любое число получается путем сложения или вычитания базисных чисел, называются аддитивными.

Позиционные системы счисления

Для представления чисел в настоящее время используются

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

водну единицу старшего разряда:

354 = 3 · 102 + 5 · 101 + 4 · 100 .

Таким образом, десятичная запись любого числа X основана на представлении этого числа в виде полинома:

X = am·10m + am-1·10m-1 + …+ a1·101 + a0 · 100 + a -1·10 -1 … + a–m·10 –m, (2.1)

где каждый коэффициент ai может быть одним из чисел 0, 1, 2, …9. Число К единиц какого-либо разряда, объединяемых в единицу более старшего разряда, называют основанием позиционной системы счисления, а сама система счисления называется К-ичной. Запись произвольного числа в К-ичной позиционной системе счисле-

ния основывается на представлении этого числа в виде полинома:

X = am·Km + am-1·Km-1 +…+ a1·K1 + a0·K0 + a-1·К-1 + … + a-m·K–m , (2.2)

где каждый коэффициент ai может быть одним из чисел 0, 1, 2, … К – 1.

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

В современной вычислительной технике, в устройствах автоматики и связи широко применяется двоичная система счисления. Это

38

связано с тем, что в таких устройствах используются элементы с двумя устойчивыми состояниями (например, есть заряд на конденсаторе или нет). Двоичная система – это система с наименьшим возможным основанием. В ней для изображения числа используются только две цифры: 0 и 1.

Произвольное число в двоичной системе счисления представляется в виде полинома:

X = am·2m + am-1 · 2m-1 + … + a1 · 21 + a0·20 + a-1· 2-1 + … + a -m·2 –m (2.3)

Примеры чисел в двоичной системе счисления:

1 = 12

2 = 102

3 = 112

4 = 1002

5 = 1012

0,5 = 0,12

0,25 = 0,012 Таблица сложений чисел в двоичной системе счисления имеет

вид 0 + 0 = 0

0 + 1 = 1

1 + 0 = 1

1 + 1 = 10 Таблица умножений чисел в двоичной системе счисления име-

ет вид 0 · 0 = 0

0 · 1 = 0

1 · 0 = 0

1 · 1 = 1

Ввычислительной технике используются и другие позиционные системы: восьмеричная или шестнадцатеричная. В восьмеричной системе счисления базисными числами являются 0, 1, 2, 3, 4, 5, 6, 7. Запись любого числа в этой системе основывается на его разложении по степеням числа восемь с коэффициентами из базисного набора.

Вшестнадцатеричной системе счисления базисными являются числа от нуля до пятнадцати. Для обозначения первых девяти чисел используются арабские числа от нуля до девяти, остальные обозначаются латинскими буквами a, b, c, d, e, f.

39

Смешанные системы счисления

В ряде случаев числа, записанные в системе счисления с основанием P, приходится изображать с помощью цифр другой системы счисления с основанием Q, где Q < P. Такая ситуация возникает, например, когда в ЭВМ, которая воспринимает только двоичные числа, необходимо изобразить десятичные числа. В этих случаях используются смешанные системы счисления, в которых каждый коэффициент P-ичного разложения числа записывается в Q-ичной системе.

Втакой системе P называется старшим основанием, а Q – младшим основанием системы, а сама смешанная система называется (P – Q)- ичной. Для того чтобы запись числа в смешанной системе счисления была однозначной, для представления любой P-ичной цифры отводится одно и то же количество Q-ичных разрядов, достаточное для представления любого базисного числа P-ичной системы. Так, в смешанной двоично-десятичной системе счисления для изображения каждой десятичной цифры отводится четыре двоичных разряда. Например, десятичное число х = 925 в двоично-десятичной системе запишется в виде 1001 0010 0101.

Будем изображать принадлежность числа к (P – Q)-ичной системе

счисления с помощью нижнего индекса: 92510 = 1001 0010 01012-10 . Аналогично двоично-десятичной системе можно использовать

и другие смешанные системы при различных значениях P и Q. Отметим ситуацию, когда P = Qn, где n – целое положительное число.

Вэтом случае запись какого-либо числа в смешанной системе счисления тождественно совпадает с изображением этого числа в системе с основанием Q (что не имеет места в двоично-десятичной системе в общем случае).

Перевод чисел из одной системы счисления в другую

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

Ограничимся рассмотрением систем счисления, у которых базисными числами являются последовательные числа 0, 1, …Р–1, где Р – основание системы. Задача перевода заключается в следующем.

Пусть известна запись числа х в системе счисления с основанием Р:

40