Лекция 2: Информация, ее представление и измерение 3 страница

 

6. Лекция: Логические вентили, схемы, структуры Рассматриваются основные теоретические (математические, логические) понятия и сведения, касающиеся базовых логических элементов и структур – логических вентилей, логических (переключательных) схем, логической базы аппаратуры ЭВМ и их оптимальной структуры, оптимизации их структур.
  Любой, самый примитивный компьютер – сложнейшее техническое устройство. Но даже такое сложное устройство, как и все в природе и в технике, состоит их простейших элементов. Любой компьютер, точнее, любой его электронный логический блок состоит из десятков и сотен тысяч так называемых вентилей (логических устройств, базовых логических схем), объединяемых по правилам и законам (аксиомам) алгебры вентилей в схемы, модули. Логический вентиль (далее – просто вентиль) – это своего рода атом, из которого состоят электронные узлы ЭВМ. Он работает по принципу крана (отсюда и название), открывая или закрывая путь сигналам. Логические схемы предназначены для реализации различных функций алгебры логики и реализуются с помощью трех базовых логических элементов (вентилей, логических схем или так называемых переключательных схем). Они воспроизводят функции полупроводниковых схем. Работу вентильных, логических схем мы, как и принято, будем рассматривать в двоичной системе и на математическом, логическом уровне, не затрагивая технические аспекты (аспекты микроэлектроники, системотехники, хотя они и очень важны в технической информатике). Логические функции отрицания, дизъюнкции и конъюнкции реализуют, соответственно, логические схемы, называемые инвертором, дизъюнктором и конъюнктором. Логическая функция "инверсия", или отрицание, реализуется логической схемой (вентилем), называемой инвертор. Принцип его работы можно условно описать следующим образом: если, например, "0" или "ложь" отождествить с тем, что на вход этого устройства скачкообразно поступило напряжение в 0 вольт, то на выходе получается 1 или "истина", которую можно также отождествить с тем, что на выходе снимается напряжение в 1 вольт. Аналогично, если предположить, что на входе инвертора будет напряжение в 1 вольт ("истина"), то на выходе инвертора будет сниматься 0 вольт, то есть "ложь" (схемы на рисунках 6.1 а, б). Рис. 6.1. Принцип работы инвертора Функцию отрицания можно условно отождествить с электрической схемой соединения в цепи с лампочкой (рис. 6.2), в которой замкнутая цепь соответствует 1 ("истина") или х = 1, а размыкание цепи соответствует 0 ("ложь") или х = 0. Из указанных простейших базовых логических элементов собирают, конструируют сложные логические схемы ЭВМ, например, сумматоры, шифраторы, дешифраторы и др. Большие (БИС) и сверхбольшие (СБИС) интегральные схемы содержат в своем составе (на кристалле кремния площадью в несколько квадратных сантиметров) десятки тысяч вентилей. Это возможно еще и потому, что базовый набор логических схем (инвертор, конъюнктор, дизъюнктор) является функционально полным (любую логическую функцию можно представить через эти базовые вентили), представление логических констант в них одинаково (одинаковы электрические сигналы, представляющие 1 и 0) и различные схемы можно "соединять" и "вкладывать" друг в друга (осуществлять композицию и суперпозицию схем). Таким способом конструируются более сложные узлы ЭВМ – ячейки памяти, регистры, шифраторы, дешифраторы, а также сложнейшие интегральные схемы. Пример. В двоичной системе таблицу суммирования цифры x и цифры y и получения цифры z с учетом переноса p в некотором разряде чисел x и y можно изобразить таблицей вида
x y z p

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

Логический элемент, соответствующий этим функциям, называется одноразрядным сумматором и имеет следующую схему (обозначим ее как – если мы хотим акцентировать именно выбранный, текущий i-й разряд)

Пример. "Черным ящиком" называется некоторое закрытое устройство (логическая, электрическая или иная схема), содержимое которого неизвестно и может быть определено (идентифицировано) только по отдельным проявлениям входа/выхода ящика (значениям входных и выходных сигналов). В "черном ящике" находится некоторая логическая схема, которая в ответ на некоторую последовательность входных (для ящика) логических констант выдает последовательность логических констант, получаемых после выполнения логической схемы внутри "черного ящика". Определим логическую функцию внутри "черного ящика" (рис. 6.10), если операции выполняются с логическими константами для входных последовательностей (поразрядно). Например, х = 00011101 соответствует последовательности поступающих значений: "ложь", "ложь", "ложь", "истина", "истина", "истина", "ложь", "истина".

Из анализа входных значений (входных сигналов) х, у и поразрядного сравнения логических констант в этих сообщениях с константами в значении z – результате выполнения функции в "черном ящике", видно, что подходит, например, функция вида

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

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

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

Пример. Построим схему для логической функции

Пример. Определим логическую функцию , реализуемую логической схемой вида (рис. 6.13)

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

 

 

7. Лекция: Базовые алгоритмические структуры Рассматриваются основные понятия об алгоритме в программах и алгоритмизации решения задач.
  "Алгоритм" является базовым основополагающим понятием информатики, а алгоритмизация (программирование) – основным разделом курса информатики (ядром курса). Понятие алгоритма, как и понятие информации, точно определить невозможно. Поэтому встречаются самые разнообразные определения – от "наивно-интуитивных" ("алгоритм – это план решения задачи") до "строго формализованных" (нормальные алгоритмы Маркова). В качестве рабочего определения алгоритма возьмем следующее определение. Алгоритм – это упорядоченная совокупность точных (формализованных) и полных команд исполнителю алгоритма (человек, ЭВМ), задающих порядок и содержание действий, которые он должен выполнить для нахождения решения любой задачи из рассматриваемого класса задач. Алгоритм удовлетворяет следующим основным свойствам: 1. Конечность (дискретность) команд и выполняемых по ним действий алгоритма. 2. Выполнимость в определенной операционной среде (в определенном классе исполнителей). 3. Результативность отдельных команд и всего алгоритма. 4. Применимость алгоритма ко всем возможным входным данным конкретного класса задач. 5. Определенность (детерминированность) команд и всего алгоритма для всех входных данных. 6. Формализованное, конструктивное описание (представление) команд алгоритма. 7. Минимальная полнота системы команд алгоритм. 8. Непротиворечивость любых команд алгоритма на любом наборе входных данных. Любой алгоритм ориентирован на некоторый общий метод решения класса задач и представляет собой формализованную запись метода, процедуры. Алгоритм, записанный на некотором алгоритмическом, формальном языке, состоит из заголовка алгоритма (описания параметров, спецификаций класса задач) и тела алгоритма (последовательности команд исполнителя, преобразующих входные параметры в выходные). Для записи, исполнения, обмена и хранения алгоритмов существуют различные средства, языки, псевдокоды – блок-схемы, структурограммы (схемы Нэсси-Шнайдермана), Р-схемы, школьный алгоритмический язык (ШАЯ), различные языки программирования. В качестве языка описания алгоритмов нами используется далее язык программирования Паскаль, так как он наиболее подходит для целей обучения и часто (обоснованно) используется в обучении. На алгоритмическом языке Паскаль любой алгоритм простой (не модульной, не составной) структуры имеет следующий стандартный вид: Program <имя (заголовок) алгоритма>; Uses <список подключаемых библиотек, если они нужны>; { комментарии, если нужны } Label <список меток (имен участков программ), если они нужны>; { комментарии } Const <список констант (не изменяемых величин), если они нужны>; { комментарии } Type <список имен и типов структур данных, если они нужны>; { комментарии } Var <список имен и типов переменных, если они нужны>; { комментарии } { < условия задачи и применимости алгоритма > } { < цель составления и выполнения алгоритма > }Begin <команды ввода входных данных, если они нужны>; { комментарии } <тело алгоритма (команды управления и преобразования алгоритма)>; { комментарии } <команды вывода результатов (выходных данных), если они нужны>; { комментарии }End. Пример. Программа вычисления объема v правильного цилиндра с радиусом основания r и высотой h. Program VСil;Uses Crt { подключение библиотеки ввода/вывода на экран "в звуке и цвете" }Const pi = 3.14;Var r, h, v: real; { для правильного цилиндра с радиусом основания r и высотой h } { вычислить и выдать на экран значение его объема v }Begin ClrScr; { команда очистки экрана (от данных предыдущей задачи) } ReadLn (r, h); { ввод входных параметров } v:=pi*r*r*h; { вычисление объема по формуле для цилиндра } WriteLn (‘Вычисленный объем цилиндра равен ’, v) { вывод результата }End. Приведем таблицу наиболее часто используемых в языке Паскаль функций и процедур.
Обычная запись Паскаль
Квадрат числа х sqr(x)
Корень квадратный из x sqrt (x)
Модуль |х| abs (x)
sin x sin(x)
cos x cos(x)
tg x tg(x)
ctg x ctg(x)
arcsin x arcsin (x)
arccos x arccos(x)
arctg x arctg(x)
Натуральный логарифм ln x ln(x)
Степень числа е = 2, 7... или еx exp(x)
Остаток от деления целого х на целое у x mod y
Частное от деления целого х на целое y x div y
Целая часть числа х (вещественного) int(x)
Случайное число от 0 до х rnd(x)
Длина текста х в символах length (x)

Пример. Результаты применения этих функций: sqrt(9) = 3, abs(–5) = 5, sin(0) = 0, cos(0) = 1, ln(1) = 0, exp(1 ) =e, 23 mod 5 = 3, 20 mod 5 = 0, 23 div 5 = 4, 20 div 5 = 4, int(2.7) = 2, int(2) = 2, rnd(0) = 0.231356, length(‘информ’) = 6.

Порядок выполнения операций (старшинство операций – по убыванию) в языке Паскаль:

1. вычисление выражений в скобках;

2. вычисление стандартных функций;

3. умножение и деление (обозначаются "*" и "/");

4. сложение и вычитание (обозначаются "+" и "–").

Пример. Выражение b*c + (d/t*(v/n/m))*sin(x) вычисляется в следующем порядке (слева направо): v/n, (v/n)/m, d/t, (d/t)*(v/n/m), sin(x), b*c, (d/t*(v/n/m))*sin(x), b*c+(d/t*(v/n/m))*sin(x) и эквивалентно математическому выражению: .

Рассмотрим базовые простые команды языка Паскаль.

1. Команда описания (заголовка) алгоритма (программы) :

Program <имя алгоритма>;,

где <имя алгоритма> – имя, задаваемое составителем программы (краткое, полное, грамотное отражение сути алгоритма).

2. Ввод – команда ввода в рассмотрение (в тело алгоритма) тех или иных входных параметров:

Read (<список вводимых параметров>);

или

ReadLn (<список вводимых параметров>);.

Первая команда вводит данные с текущей позиции экрана (где стоит курсор), вторая – с новой строки экрана.

3. Вывод – команда вывода на экран тех или иных входных или выходных параметров алгоритма:

Write (<список выводимых параметров>);

или

WriteLn (<список выводимых параметров>);.

Первая команда выводит данные с текущей позиции экрана (где стоит курсор), вторая – с новой строки экрана.

4. Присваивание – команда изменения текущего значения переменной вида:

<идентификатор> := <выражение>;,

где <идентификатор> соответствует имени переменной, <выражение> – корректно записанное выражение. Знак ":=" означает последовательное выполнение двух действий: определение текущего значения <выражения> и замена текущего значения переменной, имя которой задано <идентификатором>, на новое значение, равное значению <выражения>.

5. Команда начала алгоритма (блока) – команда Begin.

6. Команда завершения алгоритма (блока) – команда End.

7. Команда вставки комментариев в текст алгоритма имеет вид:

<комментируемое в программе> <текст комментария>.

Комментировать можно любой объект в программе. Обычно комментируют переменную, структуру данных, команду, группу команд.

Различают три базовые алгоритмические структуры: следование, ветвление, повторение.

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

2. 3. <команда – предшественник>;4. <команда – преемник>.

5. Структура типа ветвления в полной форме состоит из некоторого условия, проверяемого на истинность при выполнении структуры, команды, выполняемой при выполнении проверяемого условия, и команды, выполняемой при невыполнении условия. Структура имеет вид

6. 7. if <условие>8. then <команда, выполняемая при выполнении условия>9. else <команда, выполняемая при невыполнении условия>;.

Ключевые (служебные) слова Паскаля – if (если), then (то), else (иначе). Ключевые слова нельзя изменять, заменять, так как их эталоны закреплены в переводчике с языка Паскаль (о нем подробнее – ниже).

Пример. Команда вида

if (х>y) { если текущее значение х больше текущего значения y, } then у := х { то текущее значение у полагаем равным текущему значению х, } else x:= y; { иначе (при х <= y) текущее значение x заменяем на текущее значение y }.

Структура типа ветвления в неполной форме – частный случай ветвления в полной форме, в которой, при невыполнении условия, управление просто передается следующей команде и больше никаких действий команда ветвления не осуществляет. Эта структура имеет вид

if <условие> then <команда, выполняемая при исполнении условия>; .

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

Структура повторения типа "пока (while)" записывается в виде:

while <условие продолжения повторения> do <повторяемая команда>;

или

while <условие продолжения повторения> do begin <повторяемая команда номер 1>; <повторяемая команда номер 2>; . . . <повторяемая команда номер N> end;.

Ключевые слова Паскаля – while (пока), do (выполнять), begin (начало), end (конец).

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

Часть команды цикла "while <условие продолжения повторения>" – заголовок цикла.

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

Пример. Пусть необходимо находить сумму всех нечетных элементов натурального ряда чисел до тех пор, пока эта сумма не превысит значение n. Слагаемое, при котором эта сумма превысит n – включать в сумму.

"Забудем" временно чисто математическое решение этой задачи – с использованием суммы арифметической прогрессии с шагом 2. Алгоритмпрограмма) имеет вид

Program Summa;Uses Crt; { подключение библиотеки ввода/вывода на экран "в звуке и цвете"}Var i, n, s: real; { для ряда чисел 1, 3, 5, …, } { найти и выдать сумму s всех первых чисел ряда, для которых впервые s > n }Begin ClrScr; { команда очистки экрана (от данных предыдущей задачи) } ReadLn (n); { ввод входного параметра } s:=1; { начальное значение суммы до входа в цикл } i:=1; { количество просуммированных чисел в начале } while (s<=n) do { заголовок цикла (проверка условия выхода из цикла) } begin i:=i+2; { находим новое слагаемое } s:=s+i { добавили к предыдущему значению суммы новое слагаемое } end; WriteLn (‘Вычисленная сумма равна ’, s); { вывод результата }End.

Вторая форма повторения – цикл типа "до" (for), которая имеет вид

for <переменная> := <начальное значение переменной> to <конечное ее значение> do <команда>;

или

for <переменная> := <начальное значение переменной> to <конечное ее значение> do begin <повторяемая команда номер 1>; <повторяемая команда номер 2>; . . . <повторяемая команда номер N> end;.

Здесь <переменная> – имя, идентификатор пересчитываемой переменной.

Ключевые слова Паскаля – for (для), to (к).

Этот цикл выполняется по правилу: для начального значения переменной выполняются команды тела цикла по порядку и затем проверяется, превысило ли текущее значение переменной ее заданного конечного значения; если превысило – цикл заканчивается, иначе значение переменной увеличивается на единицу и снова повторяется тело цикла и т.д.

Пример. Необходимо вычислить среднюю стоимость единицы всех n видов товаров (единица измерения – одна и та же, например, тонна), если стоимость единицы каждого товара увеличивается на 10, а наименьшая стоимость единицы товара равна 2. Если "забыть" временно лучшее, "чисто математическое" решение этой задачи, то алгоритм будет иметь вид

Program ST;Uses Crt { подключение библиотеки ввода/вывода на экран "в звуке и цвете"}Var i, n, s: real; { стоимость единицы товара дается рядом n чисел вида: 2, 12, 22, 32, … } { найти и выдать среднюю стоимость s всех n товаров s }Begin ClrScr { команда очистки экрана (от данных предыдущей задачи) } ReadLn (n); { ввод входного параметра } s:=0; { начальное значение суммы до входа в цикл } x:=2; { начальное значение стоимости товара – стоимость первого товара } for i:=1 to n do { заголовок цикла (проверка условия выхода из цикла) } begin s:=s+x; { находим новую сумму товаров } x:=x+10 { находим стоимость следующего товара } end; WriteLn (‘Вычисленная средняя стоимость товаров равна ’, s/n, f: 5:5); { вывод результата }End.

Рассмотрим примеры алгоритмизации (программирования) задач на языке Паскаль.

Пример. Составим алгоритм вычисления факториала заданного натурального числа n, то есть произведения n! = 1 • 2 • 3 • … • (n – 1)•n c использованием рекуррентной формулы n! = (n – 1)! • n. Опишем метод решения. Для этого заметим цепочку справедливых равенств:

1! = 1, 2! = 1 • 2 = 1! • 2, 3! = 1 • 2 • 3 = 2! • 3, …, m ! =1 • 2 • 3 • … • (m – 1)•m = (m – 1)! •m.

Следовательно, для вычисления факториала m! необходимо факториал (m – 1)! домножить на m, где m = 1, 2, …, n. Программа на Паскале имеет вид

Program Factorial;Uses Crt;Var n, f, i: integer; { дано натуральное число n } { найти и выдать произведение всех натуральных чисел до n включительно }Begin ClrScr; WriteLn('Введите число n : '); { приглашение к вводу входного параметра } ReadLn(n); { ввод входного параметра } f:=1; { начальному значению f присваивается 1, то есть 1!=1 } for i:=1 to n do { цикл умножения текущего произведения f на текущее i } f:=f*i; { предыдущее значение факториала умножаем на текущее значение i } WriteLn('Полученный результат f : ',f); { вывод результата }End.

Пример. Составим алгоритм перевода заданного десятичного натурального числа n в двоичную систему. Метод решения определяется процедурой перевода – последовательными делениями числа n на 2 и последующим сбором остатков от деления. Если последовательно выдавались с равные 1,0,1,0,0,1, то двоичное изображение c равно 100101. Алгоритм имеет вид

Program S10-S2;Uses Crt;Var n, a, i, c: integer; { дано десятичное натуральное число } { выдать последовательно цифры его двоичного изображения }Begin ClrScr; WriteLn('Введите переводимое число : '); { приглашение к вводу входного параметра } ReadLn(n); { ввод входного параметра } WriteLn('Полученное двоичное число от конца :'); { выдача "шапки" к результату } i:=0; { начинаем с младшего, нулевого разряда } while (n>0) do { цикл деления числа и получаемых частных (пока делится) } begin i:=i+1; { переход к следующему делению } c:=n mod 2; { находим очередной остаток от деления на 2} n:=n div 2; { находим очередное частное от целочисленного деления } write(c) { выдаем новую двоичную цифру } end;End.

 

 

8. Лекция: Данные, их типы, структуры и обработка Рассматриваются основные понятия о данных к алгоритмам, их базовые типы и структуры, вопросы их использования в алгоритмизации задач.
  Любая актуализация информации опирается на какие-то данные, любые данные могут быть каким-то образом актуализированы. Данные – это некоторые сообщения, слова в некотором заданном алфавите. Пример. Число 123 – данное, представляющее собой слово в алфавите из десяти натуральных цифр; число 12,34 – данное, представляющее собой слово в алфавите из десяти натуральных цифр и десятичной запятой; текст "математика и информатика – нужные дисциплины", – данное в алфавите из символов русского языка и знаков препинания, включая пробел. Текущее (то есть рассматриваемое в данный момент времени) состояние данных называют текущим значением данных или просто значением . До разработки алгоритма (программы) необходимо выбрать оптимальную для реализации задачи структуру данных. Неудачный выбор данных и их описания может не только усложнить решаемую задачу и сделать ее плохо понимаемой, но и привести к неверным результатам. На структуру данных влияет и выбранный метод решения. Пример. При решении системы линейных алгебраических уравнений можно воспользоваться методом Крамера (с помощью определителей) или методом Гаусса (с помощью последовательных исключений неизвестных). Метод Крамера потребует при реализации примерно в 3 раза больше операций, чем метод Гаусса, и поэтому им никогда не пользуются при расчетах на ЭВМ. Тип данных характеризует область определения значений данных. Задаются типы данных простым перечислением значений типа, например как в простых типах данных , либо объединением (структурированием) ранее определенных каких-то типов – структурированные типы данных . Пример. Зададим простые типы данных "специальность", "студент", "вуз" следующим перечислением: специальность = (филолог, историк, математик, медик); студент = (Петров, Николаев, Семенов, Иванова, Петрова); вуз = (МГУ, РГУ, КБГУ). Значением типа "студент" может быть Петров. Пример. Опишем структурированный тип данных "специальность_студента": специальность_студента=(специальность, студент). Значением типа "специальность_студента" может быть пара (историк, Семенов). Для обозначения текущих значений данных используются константы – числовые, текстовые, логические. Часто (в зависимости от задачи) рассматривают данные, которые имеют не только "линейную" (как приведенные выше), но и иерархическую структуру. Пример. Структуру "вуз" можно задать иерархической структурой, состоящей, например, из следующих уровней: "Ректорат", "Деканаты и подразделения", "Кафедры", "Отделы", "Преподаватели и сотрудники". В алгоритмических языках есть стандартные типы, например, целые, вещественные, символьные, тестовые и логические типы. Они в этих языках не уточняются (не определяются, описываются явно) и имеют соответствующие описания с помощью служебных слов. Пример. В школьном алгоритмическом языке (ШАЯ), например, целые, вещественные, символьные, текстовые (литерные, стринговые) и логические типы данных описываются ключевыми словами цел, вещ, сим, лит, лог. В языке Паскаль – аналогичными ключевыми словами integer, real, char, string, boolean. Каждый тип данных допускает использование определенных операций со значениями типа ("с типом"). Пример. Для целого типа данных назовем операции ":=", "+", "–", "*", "=" (сравнение на равенство), "", "<", ">", "", "".. Для вещественного типа данных еще и операция "/" (деление). Для символьного типа данных – только ":=", "=", "", "<", ">", "", "". Например, сравнение "а"<"b" означает, что символ "а" предшествует символу "b" то есть код буквы "a" меньше кода буквы "b" (коды символов приводятся, например, в таблице ASCII – Аmerican Standard Code for Information Interchange, американский стандарт кодирования для обмена данными). Для текстового (литерного) типа данных можно использовать еще и операцию конкатенации (присоединения справа) текстов "+". Например, "аб"+"ба" даст новый текст "абба". Для данных логического типа определены логические операции и отношения сравнения. Например, на Паскале для логических переменных a, b, c можно записать корректное выражение: a and b or (c not a). Для описания переменных, значениями которых могут быть лишь символы, тексты, используются соответствующие ключевые слова: на ШАЯ – сим, лит, на Паскале – char, string. Текстовые (символьные) константы обычно заключают в апострофы. Пример. Составим алгоритм подсчета числа несовпадающих символов (на одинаковых позициях текстов) в двух заданных текстах a и b. Метод решения: "вырезаем" и сравниваем символы на одинаковых позициях в текстах на совпадение. Program EquSimb;Uses Crt;Var i, k, j: integer; a, b: string;Begin ClrScr; WriteLn('Введите строку a = '); { приглашение к вводу входного параметра } ReadLn(a); { ввод первого входного параметра } WriteLn('Введите строку b='); { приглашение к вводу второго параметра } ReadLn(b); { ввод второго входного параметра } k:=abs(length(a)–length(b)); { вычисление разницы длин текстов } if (length(a)<length(b)) { если текст b длиннее текста a,} then j:=length(a) { то проверять нужно до длины a, } else j:=length(b); { иначе – до длины b } for i:=1 to j do { цикл проверки на совпадение символов } if (a[i]<>b[i]) { если символы тестов на одинаковых позициях не равны, } then k:=k+1; { то увеличиваем счетчик количества таких символов } WriteLn('k = ',k); { вывод результата }End. Наиболее часто используемая структура данных – массив. Одномерный массив (вектор, ряд, линейная таблица) – это совокупность значений некоторого простого типа (целого, вещественного, символьного, текстового или логического типа), перенумерованных в каком-то порядке и имеющих общее имя. Для выделения конкретного элемента массива необходимо указать его порядковый номер в этом ряду. Пример. Последовательность чисел 89, –65, 9, 0, –1.7 может образовывать одномерный вещественный массив размерности 5, например, с именем x вида: x[1] = 89, x[2] = –65, x[3] = 9, x[4] = 0, x[5] = –1.7. Значение порядкового номера элемента массива называется индексом элемента. Пример. Можно ссылаться на элемент х[4], элемент х[i], элемент x[4+j] массива х. При текущих значениях переменных i = 2 и j = 1 эти индексы определяют, соответственно, 4-й, 2-й и 5-й элементы массива. Для обозначения (нового типа объектов) массивов в алгоритмических языках обычно вводится специальное служебное слово. Пример. В ШАЯ – это слово "таб", после которого приводится имя массива и в квадратных скобках его размерность, например, для одномерного массива – в виде [m:n], где m – номер первого элемента массива (часто 1), n – номер последнего элемента (шаг перебора элементов равен 1). На Паскале имеется соответствующее слово array. Вышеуказанная последовательность из пяти чисел описывается на ШАЯ в виде: вещ таб x[1:7], а на Паскале (в рамках рассматриваемого нами его ядра) необходимо указывать предельную величину размерности: x: array [1..100] of real;. Двумерный массив (матрица, прямоугольная таблица) – совокупность одномерных векторов, рассматриваемых либо "горизонтально" (векторов-строк), либо "вертикально" (векторов-столбцов) и имеющих одинаковую размерность, одинаковый тип и общее имя. Матрицы, как и векторы, должны быть в алгоритме описаны служебным словом (например, таб или array), но в отличие от вектора, матрица имеет описание двух индексов, разделяемых запятыми: первый определяет начальное и конечное значение номеров строк, а второй – столбцов. Пример. Если матрица x описана в виде x: array [1..5, 1..3] of real; , то определяется таблицу из 5 строк (от 1-й до 5-й строки) и 3 столбцов (от 1-го до 3-го столбца) вида:
(столбец 1) (столбец 2) (столбец 3)  
x11 x12 х13 (строка 1)
x21 x22 х23 (строка 2)
х31 х32 х33 (строка 3)
х41 x42 х43 (строка 4)
х51 x52 х53 (строка 5)

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

Пример. Элемент х[3,2] – элемент на пересечении 3-й строки и 2-го столбца массива х.

Рассмотрим ряд задач, решаемых с помощью массивов.

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

Program SPM1;Uses Crt;Var x: array [1..100] of real; n, i: integer; s, р: real;Begin ClrScr; WriteLn('Введите размерность массива :'); { приглашение к вводу входного параметра } ReadLn(n); { ввод входного параметра } WriteLn('Введите элементы массива:'); { приглашение к вводу массива } for i:=1 to n do { цикл ввода элементов массива } begin write('x[',i,']='); { приглашение к вводу текущего элемента массива} readln(x[i]) { ввод текущего элемента массива } end; s:=0; { начальное значение суммы – нуль } p:=1; { начальное значение произведение – единица [u1]} for i:=1 to n do { цикл вычисления суммы и произведения } begin s:=s+x[i]; { добавление к сумме очередного слагаемого } p:=p*x[i] { домножение произведения на очередной множитель } end; WriteLn('Полученная сумма равна ', s: 3:3); { вывод полученной суммы } WriteLn('Полученное произведение равно ', p: 3:3); { вывод полученного произведения }End.

Пример. Составим алгоритм вычисления суммы бесконечного ряда чисел а[1], а[2], а[3], ... с точностью е, при условии, что точность всегда достигается для номера члена ряда не более 1000000 (это "неестественное" ограничение нужно для того, чтобы в Паскале было проще объявить размерность массива а). Метод решения: сравниваем две суммы – одна сумма была получена на предыдущем шаге суммирования, а вторая – добавлением к ней очередного слагаемого (то есть их разность и равна очередному добавленному элементу ряда); процесс суммирования продолжается до тех пор, пока разность по модулю не станет меньше точности суммирования. Алгоритм (программа) имеет вид

Program SumND;Uses Crt;Var a: array [1..1000000] of real; i: integer; e, p, s: real;begin ClrScr; WriteLn('Введите точность :'); { приглашение к вводу входного параметра } ReadLn(e); { ввод входного параметра } i:=1; { начальный номер члена ряда } WriteLn(‘введите первые два элемента :’); { приглашение к вводу входных параметров } ReadLn(a[1], a[2]); { ввод входных параметров } р:=а[1]; { запоминаем начальную сумму – сумму одного элемента } s:=р+a[2]; { запоминаем начальную следующую сумму – сумму двух элементов } while (abs(s–p)>e) do { цикл суммирования, пока слагаемые влияют на сумму } begin i:=i+1; { переход к следующему элементу } p:=s; { "старую" сумму заменяем "новой", полученной добавлением еще одного } s:=s+а[i]; { вычисляем "новую" сумму } WriteLn(‘введите a[‘, i, ‘]=’); { приглашение к вводу очередного элемента ряда } ReadLn(a[i]); { ввод очередного элемента ряда } end; WriteLn('Полученная сумма равна ', s: 3:3); { вывод результата }End.

Пример. Составим алгоритм вычисления значения полинома Pn(x) = а0хn + а1хn–1 + ... + аn для заданного значения x. Метод решения – метод (схема) Горнера. Опишем его. Заметим, что:

1) при n = 0, P0(x) = a0 ;

2) при n = 1, P1(x) = a0x + a1 = P0(x) x + a1 ;

3) при n = 2, P2(х) = a0x2 + a1x + a2 = (a0x + a1)x + a2 = P1(x)x + a2 ;

. . .

n) Pn(x) = a0xn + a1xn–1 + ... + an–1x + an = (a0xn–1 + a1xn–2 + ... + an–1)x + an = Pn–1(x)x + an .

Таким образом, всегда верно рекуррентное соотношение Горнера:

Текущее Р := Предыдущее Р*x + Текущий коэффициент полинома.

Эту схему реализуем в алгоритме (программе) вида:

Program Gorner;Uses Crt;Var a: array [0..100] of real; n, i: integer; p, x: real;Begin ClrScr; WriteLn('Введите порядок полинома :'); { приглашение к вводу входного параметра } ReadLn(n); { ввод первого входного параметра } WriteLn('Введите число x :'); { приглашение к вводу второго входного параметра } ReadLn(x); { ввод второго входного параметра } for i:=0 to n do { цикл схемы Горнера } begin WriteLn('a[',i,']='); { приглашение к вводу очередного коэффициента полинома} ReadLn(a[i]); { ввод очередного коэффициента полинома } end; p:=a[0]; { начальное (для n=0) значение полинома – см. схему Горнера} for i:=1 to n do { цикл накапливания значения полинома по схеме Горнера } p:=p*x+a[i]; { находим полином текущей степени i используя предыдущий } WriteLn('Полученнoe значение p = ', p:3:3); { вывод результата }End.

Пример. Составим алгоритм вычисления суммы и произведения всех элементов a[i,j], i = 1, 2, ..., n; j = 1, 2, ..., m заданной матрицы. Метод решения: построчно проходя все элементы массива, добавляем к предыдущему значению суммы новый элемент матрицы и умножаем предыдущее значение произведения на этот же элемент. Алгоритм (программа) имеет вид

Program SPM2;Uses Crt;Var a: array [1..100,1..100] of real; n, m, i, j: integer; s, p: real;Begin ClrScr; WriteLn('Введите количество строк:'); { приглашение к вводу входного параметра } ReadLn(n); { ввод первого входного параметра } WriteLn('Введите количество столбцов:'); { приглашение к вводу второго параметра } ReadLn(m); { ввод второго входного параметра } for i:=1 to n do { цикл ввода – перебора строк } for j:=1 to m do { цикл перебора элементов текущей строки } begin WriteLn('a[',i,',',j,']='); { приглашение к вводу очередного элемента массива } ReadLn(a[i,j]); { ввод очередного элемента массива } end; s:=0; { начальное значение суммы – нуль } p:=1; { начальное значение произведения – единица } for i:=1 to n do { цикл перебора строк для суммирования } for j:=1 to m do { цикл перебора элементов строки (столбцов) для суммирования } begin s:=s+a[i,j]; { добавление очередного элемента к текущему значению суммы} p:=p*a[i,j]; { умножение текущего значения произведения на новый элемент } end; WriteLn('Сумма равно : ', s:3:3); { вывод первого результата } WriteLn('Произведение равно : ', p:3:3); { вывод второго результата }End.