Перевод целого числа из десятичной системы счисления в двоичную
| Десятичное число/ целое частное | Делитель (основание системы) | Остаток (цифры двоичного числа) | Порядок считывания результата |
| 19 | 2 | 1 | 5 |
| 9 | 2 | 1 | 4 |
| 4 | 2 | 0 | 3 |
| 2 | 2 | 0 | 2 |
| 1 | 2 | 1 | 1 |
В результате получаем двоичное число: 1910 = 100112.
Перевод десятичных дробей в двоичную систему счисления:
1) последовательно выполнять умножение исходной десятичной дроби и получаемых дробей на основание системы (на 2) до тех пор, пока не получим нулевую дробную часть или не будет достигнута требуемая точность вычислений;
2) получить искомую двоичную дробь, записав полученные целые части произведений в прямой последовательности.
В табл. 1.4 приведен пример перевода десятичной дроби 0,7510 в двоичную систему.
Т а б л и ц а 1.4
Перевод дробного числа из десятичной системы счисления в двоичную
| Десятичная дробь/ дробная часть произведения | Множитель (основание системы) | Целая часть произведения | Порядок считывания результата |
| 0,75 | 2 | 1 | 1 |
| 0,5 | 2 | 1 | 2 |
| 0,0 |
В результате получаем двоичную дробь: 0,75= 0,112.
Перевод чисел, содержащих и целую, и дробную часть, производится в два этапа. Отдельно переводится по соответствующему алгоритму целая часть и отдельно – дробная. В итоговой записи полученного числа целая часть от дробной отделяется запятой. Кроме двоичной и десятичной в компьютерах используются также восьмеричная и шестнадцатеричная системы счисления (табл. 1.5).
|
|
|
Т а б л и ц а 1.5
Перевод цифр из двоичной системы счисления
В восьмеричную, шестнадцатеричную и десятичную и обратно
| Десятичное число | Двоичная триада | Восьмеричная цифра | Двоичная тетрада | Шестнадцатеричная цифра |
| 0 | 000 | 0 | 0000 | 0 |
| 1 | 001 | 1 | 0001 | 1 |
| 2 | 010 | 2 | 0010 | 2 |
| 3 | 011 | 3 | 0011 | 3 |
| 4 | 100 | 4 | 0100 | 4 |
| 5 | 101 | 5 | 0101 | 5 |
| 6 | 110 | 6 | 0110 | 6 |
| 7 | 111 | 7 | 0111 | 7 |
| 8 | 1 000 | 10 | 1000 | 8 |
| 9 | 1001 | 9 | ||
| 10 | 1010 | А | ||
| 11 | 1011 | В | ||
| 12 | 1100 | С | ||
| 13 | 1101 | D | ||
| 14 | 1110 | E | ||
| 15 | 1111 | F |
Для изображения цифр, бòльших 9, в шестнадцатеричной системе счисления применяются буквы латиницы: А = 10, В = 11, С = 12, D = 13, Е = 14, F = 15.
Так, например, десятичное число 6181910 может быть переведено в двоичную систему как 11110001011110112.
Если сгруппировать эту запись справа налево по триадам (см. табл. 1.5), можно получить восьмеричное представление
1 111 000 101 111 0112 = 1705738,
а сгруппировав по тетрадам − шестнадцатеричное число
1111 0001 0111 10112 = F17B16.
Аналогично производится обратный перевод чисел из восьмеричного и шестнадцатеричного представления в двоичное. В первом случае каждая цифра числа A8 заменяется соответствующей двоичной триадой, а во втором случае каждая цифра числа A16 заменяется соответствующей двоичной тетрадой из табл. 1.5.
|
|
|
Арифметические операции во всех позиционных системах счисления выполняются по аналогичным правилам.
Сложение. Рассмотрим сложение чисел в двоичной системе счисления. В его основе лежат правила сложения одноразрядных двоичных чисел
0 + 0 = 0; 0 + 1 = 1; 1 + 0 = 1; 1 + 1 = 10.
Обратим внимание на то, что при сложении двух единиц происходит переполнение разряда и производится перенос «1» в старший разряд. Переполнение разряда наступает тогда, когда величина числа в нем становится равной или большей основания системы счисления, для двоичной системы счисления − большей или равной 2.
Сложение многоразрядных двоичных чисел происходит в соответствии с правилом сложения (см. выше) с учетом возможных переносов из младших разрядов в старшие. В качестве примера сложим в столбик двоичные числа 1102 и 112. (табл. 1.6).
Т а б л и ц а 1.6
Примеры выполнения операций над двоичными числами
| Сложение | Вычитание | Сложение в обратном коде | Умножение | Деление |
| 
| 
| 
| 
|
Проверим правильность вычислений сложением в десятичной системе счисления. Переведем двоичные числа в десятичную систему счисления и затем их сложим.
|
|
|
1102 = 1 × 22 + 1 × 21 + 0 × 20 = 610; 112 = 1 × 21 + 1 × 20 = 310; 610 + 310 = 910 .
Теперь переведем результат двоичного сложения в десятичное число.
10012 = 1 × 23 + 0 × 22 + 0 × 21 + 1 × 20 = 910.
Сравнение результатов показывает, что сложение выполнено правильно.
Вычитание. Рассмотрим вычитание двоичных чисел. В его основе лежат правила вычитания одноразрядных двоичных чисел:
При вычитании из меньшего числа «0» большего «1» производится «заем» из старшего разряда. Здесь заем обозначен как 
.
Вычитание многоразрядных двоичных чисел происходит в соответствии с правилом вычитания (см. выше) с учетом возможных займов из старших разрядов. В качестве примера произведем вычитание двоичных чисел 1102 и 112 (табл. 1.6).
Поскольку сумматоры вычислительных машин, реализующие «заем единицы» из старших разрядов, схемотехнически значительно сложнее тех, которые используют «перенос единицы переполнения» из младших разрядов, в реальности обычно используют представление отрицательных чисел в обратном (инвертированном) коде или ему аналогичном.
|
|
|
В этом случае образом отрицательного числа является его обращение (инвертирование), при котором «1» заменяется на «0» и наоборот. Например, обратный код двоичного числа 112 равен 
. Тогда операция вычитания заменяется сложением в обратном коде. В табл. 1.6 приведен также пример вычитания как сложения, из которого, в частности, видно, что здесь единица переполнения переносится в младший разряд.
Умножение. В основе лежит следующее правило умножения одноразрядных двоичных чисел
Умножение многоразрядных двоичных чисел происходит по обычной схеме, применяемой в десятичной системе счисления с последовательным умножением множимого на очередную цифру множителя. В табл. 1.6 в качестве примера приведено умножение двоичных чисел 1102 и 112.
Деление. Операция деления выполняется по алгоритму, подобному алгоритму выполнения операции деления в десятичной системе счисления. В качестве примера произведем деление двоичного числа 1102 на 112 (см. табл. 1.6).
Помимо операций с числами в ЭВМ используются так называемые логические операции, которые будут рассмотрены в главе «Основы математики».
Вопросы для самопроверки
1. Почему при кодировании текстовой информации в компьютере в большинстве кодировок используется 256 различных символов, хотя русский алфавит включает только 33 буквы?
2. С какой целью ввели кодировку Unicode, которая позволяет закодировать 65 536 различных символов?
3. Переведите целое десятичное число 1310 в двоичную систему счисления.
4. Переведите десятичную дробь 0,2310 в двоичную систему счисления.
5. Выполните сложение, вычитание, умножение и деление двоичных чисел 10102 и 102.
Алгоритмы и программирование
Понятие алгоритма является одним из основных в современной науке и практике.
Алгоритм есть совокупность четко определенных правил, процедур или команд, обеспечивающих решение поставленной задачи обработки данных за конечное число шагов.
Данными называют все величины, участвующие в решении задачи. Данные, известные перед выполнением алгоритма, являются начальными, исходными данными. Результат решения задачи - это конечные (выходные, результирующие) данные.
Свойства алгоритмов:
- дискретность – разделение выполнения решения задачи на отдельные операции (выполняемые исполнителем по определенным командам). Поочередное выполнение команд алгоритма за конечное число шагов приводит к решению задачи, к достижению цели;
- определенность (точность) – каждая команда алгоритма должна определять однозначное действие исполнителя;
- понятность – алгоритм, составленный для конкретного исполнителя, должен включать только те команды, которые входят в его систему команд и не должен быть рассчитан на принятие каких-либо самостоятельных решений исполнителем;
- результативность (конечность) - исполнение алгоритма должно закончиться за конечное число шагов;
- требование массовости (вариативность). Поскольку разработка алгоритмов - процесс творческий, требующий умственных усилий и затрат времени, предпочтительно разрабатывать алгоритмы, обеспечивающие решения всего класса задач данного типа. Например, если составляется алгоритм решения кубического уравнения 
, то он должен бытьвариативен, т. е. обеспечивать возможность решения для любых допустимых исходных значений коэффициентов a, b, c, d.
Способы записи алгоритмов
Алгоритм должен быть понятен (доступен) пользователю и/или машине. Доступность пользователю означает, что он обязан отображаться посредством конкретных формализованных изобрази-тельных средств, понятных пользователю. В качестве таких изобразительных средств в основном используются следующие способы записи:
- словесный – содержание последовательных этапов алгоритма описывается в произвольной форме на естественном языке;
- графический – отображение алгоритмов в виде блок-схем, весьма наглядный и распространенный способ. Графические символы, отображающие выполняемые процедуры, стандартизованы. Наряду с основными символами используются и вспомогательные, поясняющие процедуры и связи между ними;
- на языке программирования – в виде последовательности команд какого-либо языка программирования.
Рассмотрим пример словесного описания алгоритма Эвклида – поиск наибольшего общего делителя 2-х чисел – НОД.
Исходными данными являются целые числа а и b.
1. Если 
, то работа алгоритма закончена (НОД = 
), иначе выполняется пункт 2.
2. Если 
, то переменной а присваивается значение 
, в противном случае ( 
) переменной b присваивается значение 
.
3. Осуществляется переход к пункту 1 данного алгоритма.
Запись алгоритмов в виде блок-схем.Схема алгоритма – графическое представление алгоритма, дополняемое элементами словесной записи. Каждый пункт алгоритма отображается на схеме некоторой геометрической фигурой или блоком. При этом правило выполнения схем алгоритмов регламентирует ГОСТ 19.002–80 «Единая система программной документации» (табл. 1.7).
Блоки на схемах соединяются линиями потоков информации. Основное направление потока информации идет сверху вниз и слева направо (стрелки могут не указываться), снизу вверх и справа налево − стрелка обязательна.
Та б л и ц а 1.7
Некоторые элементы блок-схем
| № | Символ | Наименование | Содержание |
| 1 | 
| Блок вычислений | Вычислительные действия или последовательность действий |
| 2 | 
| Логический блок | Выбор направления выполнения алгоритма в зависимости от некоторого условия |
| 3 | 
| Блоки ввода-вывода данных | 1. Общие обозначения ввода (вывода) данных (вне зависимости от физического носителя) 2. Вывод данных, носителем которых является документ |
| 4 | 
| Начало (конец) | Начало или конец алгоритма, вход или выход в программу |
Базовые структуры алгоритмов.Это определенный набор блоков и стандартных способов их соединения для выполнениятипичных последовательных действий. К основным структурам относятся следующие − линейные, разветвляющиеся, циклические (рис. 1.1).
Линейныминазываются алгоритмы, в которых действия осуществляются последовательно друг за другом.
Разветвляющимсяназывается алгоритм, в который, в отличие от линейных алгоритмов, входит условие, в зависимости от выполнения или невыполнения которого выполняется та или иная последовательность команд (серий).
В качестве условия в разветвляющемся алгоритме может быть использовано любое понятное исполнителю утверждение, которое может соблюдаться (быть истинно) или не соблюдаться (быть ложно). Такое утверждение может быть выражено как словами, так и формулой. Таким образом, команда ветвления состоит из условия и двух последовательностей команд.
Циклическим называется алгоритм, в котором некоторая последовательность операций (тело цикла) выполняется многократно. Однако «многократно» не означает «до бесконечности». Организация циклов, никогда не приводящая к остановке в выполнении алгоритма, является нарушением требования его результативности - получения результата за конечное число шагов.
а)
| 
б)
|
в)
| 
г)
|
Рис. 1.1. Базовые структуры алгоритмов и программ: а) - линейный алгоритм; б) - алгоритм с ветвлением; в) - алгоритм с циклом While (Пока); г) – алгоритм с циклом For (До).
Перед операцией цикла осуществляются операции начального присвоения значений тем переменным, которые используются в теле цикла. В цикл входят в качестве базовых следующие структуры: блок проверки условия и тело цикла. Если тело цикла расположено после проверки условий (цикл с предусловием), то может случиться, что при определенных условиях тело цикла не выполнится ни разу. Такой вариант организации цикла, управляемый предусловием, называется цикл Пока (While). Здесь условие – это условие продолжения цикла.
Возможен другой случай, когда тело цикла выполняется, по крайней мере, один раз и будет повторяться до тех пор, пока не станет истинным условие. Такая организация цикла, когда его тело расположено перед проверкой условия, носит название цикла с постусловием, или циклаДо (For). Современные языки программирования имеют достаточный набор операторов, реализующих как цикл Пока, так и цикл До.
На рис. 1.2 изображен алгоритм вычисления НОД (описанный выше в словесной форме).
Рис. 1.2. Графическое отображение алгоритма Эвклида
Популярные системы программирования – Turbo Basic, Quick Basic, Turbo Pascal, Turbo C.
На рис. 1.3 приведен пример отладки и запуска программы определения НОД 2-х целых чисел (блок-схема на рис.1.2) в СП Turbo Pascal, здесь элементы меню активируют следующие операции:
- File – создание, открытие, сохранение и т. д. текстового файла с программой;
- Edit – редактирование файла с текстом программы;
- Run – запуск программы на компиляцию и исполнение, и т. д.
В тексте программы (с именем NOD_1) объявляются целые переменные a, b, NOD; затем в операторных скобках begin...end располагается тело программы. Вначале осуществляется вывод строки vvod 2 naturalnih chisel a,b на экран монитора (оператор-функция вывода writeln, от write line), затем считывание 2-х чисел с клавиатуры (оператор-функция вывода readln, от read line). Цикл нахождения НОД (участок begin...end) управляется оператором цикла whilea <> b (до тех пор, пока a ¹ b, цикл типа ПОКА). Внутрь цикла помещен оператор условия if...then... else, который либо присваивает 
, либо 
.
По окончании цикла (т. е. когда a = b = НОД) осуществляется печать результата (функция writeln). Последний оператор readln осуществляет выход в окно просмотра результатов (рис. 1.3, 2).
Рис. 1.3. Система программирования Turbo Pascal: 1 – окно программы (текст программы определения НОД); 2 – окно просмотра результатов работы данной программы
Современные системы программирования позволяют удобно переходить от одного этапа к другому. Это осуществляется в рамках так называемых интегрированных сред программирования (IDE − Integrated Development Environment), которые включают текстовый редактор, компилятор, компоновщик, встроенный отладчик и в зависимости от системы или ее версии предоставляют программисту дополнительные удобства для написания и отладки программ.
Системы программирования и IDE являются компонентами программного обеспечения (ПО) ЭВМ.
Вопросы для самопроверки
1. Задан алгоритм вычисления факториала 
:
а) составить описание алгоритма в словесной форме;
б) изобразить блок-схему алгоритма;
в) написать программу на языке программирования Паскаль.
2. Задан алгоритм вычисления максимального (минимального) из 3-х чисел – a, b, c:
а) составить описание алгоритма в словесной форме;
б) изобразить блок-схему алгоритма;
в) написать программу на языке программирования Паскаль.
3. Задан алгоритм определения всех делителей числа N:
а) составить описание алгоритма в словесной форме;
б) изобразить блок-схему алгоритма;
в) написать программу на языке программирования Паскаль.
Дата добавления: 2018-05-12; просмотров: 1186; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!