Арифметические операции с целыми числами в восьмеричной и шестнадцатеричной системах счисления.

 

Как и в десятичной или двоичной системах счисления все арифметические операции с целыми числами в восьмеричной или шестнадцатеричной системах счисления основаны на таблицах сложения и умножения. Таблицы сложения и умножения в восьмеричной и шестнадцатеричной системах счисления приведены в таблицах 8, 9, 10 и 11.

Таблица 8.

Таблица сложения целых чисел в восьмеричной системе счисления.

 

Таблица 9.

Таблица умножения целых чисел в восьмеричной системе счисления.

 

Таблица 10.

Таблица сложения целых чисел в шестнадцатеричной системе счисления.

A

B

C

D

E

F

A

B

C

D

E

F

A

B

C

D

E

F

A

B

C

D

E

F

A

B

C

D

E

F

A

B

C

D

E

F

A

B

C

D

E

F

A

B

C

D

E

F

A

B

C

D

E

F

A

B

C

D

E

F

A

B

C

D

E

F

A

A

B

C

D

E

F

B

B

C

D

E

F

1A

C

C

D

E

F

1A

1B

D

D

E

F

1A

1B

1C

E

E

F

1A

1B

1C

1D

F

F

1A

1B

1C

1D

1E

 

Таблица 11.

Таблица сложения целых чисел в шестнадцатеричной системе счисления.

A

B

C

D

E

F

A

B

C

D

E

F

A

C

E

1A

1C

1E

B

F

1B

1E

2A

2D

B

1C

2C

3C

A

F

1E

2D

3C

4B

C

1E

2A

3C

4E

5A

E

1C

2A

3F

4D

5B

1B

2D

3F

5`

5A

6C

7E

A

A

1E

3C

5A

6E

8C

B

B

2C

4D

6E

8F

9A

A5

C

C

3C

6C

9C

A8

B4

D

D

1A

4E

5B

8F

9C

A9

B6

C3

E

E

1C

2A

7E

8C

9A

A8

B6

C4

D2

F

F

1E

2D

3C

4B

5A

A5

B4

C3

D2

E1

 

 

Арифметические операции с вещественными числами в двоичной системе счисления.

 

Арифметические операции с вещественными числами в двоичной системе счисления аналогичны операциям в десятичной системе счисления. Рассмотрим процесс выполнения действий на примерах.

 

Пример 1.

Дано A₍₂₎=10011,01. B₍₂₎=1,0101 представленные в форме записи с фиксированной запятой. Найти C₍₂₎= A₍₂₎+B₍₂₎.

Решение:

Выравниваем количество знаков после запятой: A₍₂₎=10011,0100. B₍₂₎=1,0101

Выполняем операцию сложения

10011,0100 +1,0101

10100,1001

 

Ответ C₍₂₎=10100,1001

 

Пример 2.

Дано A₍₂₎=0,1001101*10¹⁰¹. B₍₂₎=0,10101*10¹ представленные в форме записи с плавающей запятой. Найти C₍₂₎= A₍₂₎+B₍₂₎.

Решение:

Выравниваем порядки чисел:

A₍₂₎=0,1001101*10¹⁰¹.

B₍₂₎=0,10101*10¹=0,000010101*10¹⁰¹.

Складываем мантиссы:

Для этого выравниваем количество знаков после запятой: A₍₂₎=0,100110100, B₍₂₎= 0,000010101

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

0,100110100 +0,000010101

0,101001001

В результате сложения мантисс получили результат: 0,101001001. Дописываем показатель и получаем ответ.

Ответ C₍₂₎=0,101001001*10¹⁰¹.

 

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

 

Логические операции.

 

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

Существует три основных закона логического сравнения величин это И(and), ИЛИ(or) и НЕ(not). Схематическое представление элементов выполняющих логические операции и соответствующие им таблицы истинности представлено в таблице 12.

 

Таблица 12. Описание логических элементов вычислительной техники.

Операция	Элемент	Таблица истинности
Логическое произведение (конъюнкция). Операция «И». Результат логической суммы совпадает с результатом арифметического произведения. Результат будет равен истина, только в случае, если оба аргумента равны единице.		A	B	A И Б
Логическая сумма (дизъюнкция). Операция «ИЛИ». Результат логической суммы, отличается от результата суммы двух одноразрядных двоичных чисел. Результатом будет истина, если хотя бы один входной аргумент равен единице.		A	B	A ИЛИ B
Логическое отрицание(инверсия). Операция «НЕ» Результатом логической операции отрицание будет изменение значения входного аргумента: истина на лож и обратно.		A	НЕ A

 

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

Под сдвигом понимается смещение разрядов двоичного числа в право или в лево, в зависимости от указанного направления. Освободившееся после сдвига место заполняется нулями. В любой позиционной системе счисления сдвиг в лево(<<) на один разряд означает умножение на основание системы счисления, а сдвиг в право(>>) на один разряд - деление на основание системы счисление.

 

Пример 1.

Дано A₍₁₀₎=123. Умножить число с помощью операции сдвига на 100₍₁₀₎.

Решение:

100=10² следовательно для умножения заданного числа на 100 необходимо выполнить сдвиг на два разряда в лево

A₍₁₀₎=123*100=123 << 2=12300

Ответ A₍₁₀₎=12300.

 

Пример 2.

Дано A₍₁₀₎=345. Разделить число с помощью операции сдвига на 1000₍₁₀₎.

Решение:

Для выполнения операции деления на 1000 необходимо умножить исходное число на 1/1000

1/1000=0,001=10^-3 следовательно для деления заданного числа на 1000 необходимо выполнить сдвиг на три разряда в право

A₍₁₀₎=345/1000=345 >> 3=0,345

Ответ A₍₁₀₎=0,345.

 

Пример 3.

Дано A₍₂₎=11010. Умножить число с помощью операции сдвига на 100₍₂₎.

Решение:

100=2² следовательно для умножения заданного числа на 100 необходимо выполнить сдвиг на два разряда в лево

A₍₁₀₎= 11010*100=11010 << 2=1101000

Ответ A₍₂₎= 1101000.

 

Пример 4.

Дано A₍₂₎=11010. Разделить число с помощью операции сдвига на 10 ₍₂₎.

Решение:

Для выполнения операции деления на 10 необходимо умножить исходное число на 1/10

1/10=0,1=10^-1 следовательно для деления заданного числа на 10 необходимо выполнить сдвиг на один разряда в право

A₍₁₀₎=11010/10=11010 >> 1=1101

Ответ A₍₂₎=1101.

Поскольку двоичная система счисления состоит всего из двух чисел {0,1} принято считать, что 0₍₂₎ в логических функциях представляет собой лож, а 1₍₂₎ истину. Исходя из этого при помощи логических элементов можно организовать любой вычислительный процесс. Рассмотрим процесс сложения двоичных чисел на примере двухразрядного сумматора рисунок 9.

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

 

Таблица 13. Процессы происходящие в двухразрядном сумматоре.

X	Y	(не X)	(не Y)	(Y и 1)	(X и 2)	(XиY)	(3или4)	S	P

 

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

 

Таблица 14.

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

X	Y	PS

 

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

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

 

Введение в алгоритмизацию.

 

Понятие алгоритма.

 

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

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

Первым свойством алгоритма, является то, что он носит пошаговый(дискретный) характер определяемого им процесса.

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

Например, для того, чтобы сложить два числа 15 и 17 используется алгоритм сложения в столбик.

 

+17

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

1. Текущий разряд - крайний правый;
2. Складываем значения цифр текущего разряда;
3. Если значение суммы больше 9, добавляем единицу при сложении значений следующего разряда;
4. Записываем значение правого разряда суммы;
5. Если текущий разряд является последним, то сложение завершено, если нет, то текущим разрядом становиться следующий слева;
6. Если сложение не завершено, то повторяем начиная со второго пункта.

Попробуем проделать операцию сложения тех же чисел (15 и 17) по представленному алгоритму:

1. Текущий разряд - крайний правый (будем складывать 5 и 7);
2. Складываем значение цифр текущего разряда 5+7=12;
3. Значение суммы больше 9? Да, больше, при сложении значений следующего разряда будим добавлять единицу;
4. Записываем значение сумм правого разряда 2;
5. Текущий разряд не последний, переходим к следующему разряду;
6. Складываем значение цифр следующего разряда 1+1=2 и дописываем единицу, так как значение суммы чисел предыдущего разряда было больше 9: 2+1=3.
7. Значение суммы не больше 9, записываем значение суммы чисел разряда 3;
8. Этот разряд является последним, поэтому сложение завершено. Получили результат 32.

Заметим, что алгоритм сложения является одним и тем же для любой пары чисел, что и определяет его массовость.

Аналогичным образом можно составить алгоритм умножения, деления, вычитания и так далее.

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

Если применять один и тот же алгоритм к одним и тем же исходным данным, то мы всегда должны получать один и тот же результат. Например сколько бы раз мы не складывали числа «15» и «17», всегда будем получать один и тот же результат «32». И если при этом сравнивать результаты на каждом шаге выполнения алгоритма, то они так же будут идентичны. Таким образом можно говорить об однозначности алгоритмов.

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

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

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

Существует три основных вида шагов алгоритмов это:

1. действие(процесс) – выполнение какой либо операции, например вычисление суммы a=15+17 или положить монету в телефон автомат или набрать номер телефона, эти операции называются шагами действия – требуется что либо сделать.

2. условие(развилка) – сравнение каких либо исходных данных и определение на основе результата сравнения дальнейших действий, например если после набора номера телефон, по которому вы звонили занят, то появляется шаг условия повторить или нет, если повторить, то следует повторно набрать номер, а если нет, то перестать звонить.

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

 

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

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

 

Таблица 15.

Основные элементы графического изображения алгоритма.

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

 

 

Алгоритмические системы.

 

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

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

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

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

1. множество типов объектов, которыми могут являться исходные данные, подлежащих обработки алгоритмами данной системой;
2. свойства исполнителя алгоритмов, то есть набор инструментов(средств, действий), которыми может пользоваться исполнитель для выполнения алгоритмов;
3. множество типов объектов, которыми могут являться результаты выполнения алгоритмов данной системы;
4. язык, на котором определяются правила адресованные исполнителю.

 

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

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

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

В алгоритмической системе можно строить самые разнообразные алгоритмы, но не всегда, конкретный алгоритм построенный в выбранной алгоритмической системе будет пригоден для работы со всеми ее входными объектами. Например, в алгоритмической системе, объектами которой является числовая информация, нужно исключить возможность возникновения неопределенности, такой как деление на 0, тангенс 90^о, вычисление квадратного корня отрицательного числа и т.п. Если с конкретными исходными данными на каком то шаге возникает неопределенность, то эти данные считаются недопустимыми для данного алгоритма.

Еще одним параметром алгоритмической системы является требуемая точность конечного результата. Например, в алгоритмической системе предназначенной для обработки числовой информации, при определенных исходных данных на каком либо шаге может появиться необходимость деления единицы на тройку. Из арифметики известно, что результатом выполнения этой операции будет 0,33333…. То есть операцию деления единицы на тройку не возможно выполнить за конечное число шагов, возникает неопределенной или зацикливание процесса. Для того, чтобы избежать этой ситуации необходимо ввести параметр, определяющий требуемую точность, в данном случае количество знаков после запятой.

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

Один алгоритм является эквивалентным другому, если:

1. Множество допустимых исходных данных одного алгоритма является множеством допустимых исходных данных другого алгоритма, из возможности применения к каким либо исходным данным одного алгоритма следует возможность применения к этим же исходным данным другого алгоритма;

2. Применение к одним и те же исходным данным одного алгоритма дает то же самый результат, что и применение к этим же исходным данным другого алгоритма.

 

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

И так, алгоритмическая система это набор типов исходных и результирующих объектов, а так же методов и средств их обработки, описанных на языке понятном исполнителю.

 

Введение в математическое моделирование.

 

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

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

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

Процесс построения математической модели объектов состоит из трех этапов. Первый этап состоит в том, что определяются основные свойства и закономерности поведения объекта, процесса или явления. Обычно эти свойства и закономерности строятся на основе предположений или экспериментальных данных.

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

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

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

 

Алгоритмизация.

 

Алгоритмизацией называется процесс разработки алгоритма для решения какой либо задачи. Процесс разработки алгоритма какой либо задачи обычно связан с определенными трудностями. Для примера возьмем задачу: составить алгоритм отыскивания максимального числа среди последовательности из N чисел. Подобные задачи зачастую носят только психологические трудности, «что выбирать? Посмотрел и выбрал», при этом редко задумываемая о том, как мы это делаем. Хотя алгоритм решения очень простой:

1. Считаем что максимальным является первое число;
2. Сравниваем то число, которое считаем максимальным со следующим, и если оно окажется больше, то считаем что максимальным стало следующее число;
3. Повторяем второй пункт до тех пор пока не переберем все числа.

По окончании перебора получим максимальное число в заданной последовательности.

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

Разработка алгоритма неразрывно связана с математическим моделированием. То есть алгоритм решения задачи, это заключительная фаза математического моделирования. Этот процесс отражен на рисунке 10.

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

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

Третьим этапом идет разбивка математической модели на шаги, которые предусмотрены в выбранной алгоритмической системе.

И последним этапом алгоритмизации идет процесс разработки пошаговых правил, то есть перевод пошагового выполнения модели на язык понятный исполнителю.

 

Пример 1.

Рассмотрим процесс алгоритмизации на том же примере поиска максимального числа из последовательности из N чисел.

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

1. N - количество элементов последовательности. В качестве типа объектов, представляющих исходных данных определяем множество целых чисел. Сразу заметим, что количество должно быть положительным, то есть строго больше нуля.
2. M – сама последовательность чисел. В качестве типа объектов, представляющих исходных данных определяем множество вещественных чисел.

Далее определимся с результатами, которые будут получены в процессе выполнения алгоритма результаты выполнения алгоритма у нас будут представлены как:

1. M_max – максимальное число из заданной последовательности.

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

Построим математическую модель, то есть опишем процесс поиска языком математических формул:

Математическая модель процесса поиска максимального числа из последовательности вещественных чисел M размерностью N построена.

Разрабатываем алгоритм в виде описательных инструкций:

1. Начало алгоритма;
2. Получить количество элементов последовательности N и саму последовательность M.
3. Присвоить значению M_max, значение элемента последовательности M₁.
4. Присвоить счетчику элементов i – значение равное двум. Начинаем перебор со второго элемента, так как первый у нас уже и так считается максимальным.
5. Если не дошли до конца массива, то есть i<=N, то:
1. Если M_i > M_max, то считаем это элемент максимальным M_max = M_i.
2. Переходим к следующему элементу, для этого увеличиваем значение номера элемента i на единицу.
3. Переходим к пункту 5.
6. Записываем результат работы алгоритма M_max;
7. Конец алгоритма.

Итак, мы разработали алгоритм, с помощью которого можно найти максимальное число в последовательности M имеющей количество элементов N.

Следующим этапом идет проверка правильности работы алгоритм. Для этого возьмем произвольную последовательность {1,6,2} размерностью 3 и «проиграем» этот алгоритм пошагово, заранее зная ответ (M_max=6):

ü Начало алгоритма;

ü Получаем количество элементов последовательности N=3 и саму последовательность M={1,6,2};

ü Присваиваем M_max значение первого элемента M_max= M₁=1;

ü Присваиваем счетчику элементов значение номера второго элемента i=2;

ü Не дошли до конца последовательности? 2<=3? «да»;

ü Сравниваем текущий элемент с максимальным M_i> M_max? или 6>1? «да», значит тот элемент который мы считали максимальным таковым не является. Теперь будем считать максимальным второй элемент последовательности M_max= M_i= M₂=6;

ü Увеличиваем значение счетчика элементов на единиц i=i+1, то есть теперь значение счетчика равно 3;

ü Не дошли до конца последовательности? 3<=3? «да»;

ü Сравниваем текущий элемент с максимальным M_i> M_max? или 2>6? «нет», не выполняем никаких действий;

ü Увеличиваем значение счетчика элементов на единиц i=i+1, то есть теперь значение счетчика равно 4;

ü Не дошли до конца последовательности? 4<=3? «нет»;

ü Записываем результат работы алгоритма. На данном шаге получили, что M_max=6.

ü Конец алгоритма.

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

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

Итак, задание по разработке алгоритма, поиска максимального числа из последовательности чисел размерности N выполнено.