ЗАДАНИЯ ДЛЯ САМОСТОЯТЕЛЬНОГО ВЫПОЛНЕНИЯ. 1. Построить неориентированный граф, вычислить все возможные пути и длину каждого пути от одной из вершин ко всем остальным

1. Построить неориентированный граф, вычислить все возможные пути и длину каждого пути от одной из вершин ко всем остальным. Заполнить матрицу смежности.

2. Построить ориентированный граф, вычислить все возможные пути и длину каждого пути от одной из вершин ко всем остальным. Заполнить матрицу смежности.

3. Построить взвешенный граф, вычислить все возможные пути и длину каждого пути от одной из вершин ко всем остальным. Заполнить матрицу смежности.

Список основной и дополнительной литературы: 2,3,5,7,8,9,12,14

 

 

ПРАКТИЧЕСКОЕ ЗАНЯТИЕ №4 (1 час)

Тема: «Системы счисления»

 

Цель занятия: изучить правила перевода чисел из одной системы счисления в другую.

Форма проведения:индивидуальное задание

Задание:

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

2. Произвести арифметические операции в двойной и восьмеричной системах счисления

3. Выполнить индивидуальное задание

4. Составить отчет

 

МЕТОДИЧЕСКИЕ РЕКОМЕНДАЦИИ

Система счисления – это способ представления любого числа с помощью определенного набора символов, называемых цифрами.

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

Непозиционными называются системы счисления, в которых значение цифры не зависит от ее места (позиции) в записи числа.

Непозиционной системой счисления является, например, римская. Правила выполнения арифметических операций в непозиционных системах счисления совсем иные.

Позиционными называются системы счисления, в которых значение цифры зависит от ее места (позиции) в записи числа.

Позиционной является привычная для нас в повседневной жизни десятичная система счисления, в которой значение (вес) цифры зависит от ее позиции в записи числа. В числе 1111 одна и та же цифра 1 означает последовательно единицу, десяток, сотню, тысячу.

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

В 2-ной системе основание равно 2, т.е. используется всего 2 цифры - 0 и 1.

В 8-ной основание равно 8, используются цифры от 0 до 7.

В 16-ной системе основание равно 16, используются цифры от 0 до 15. Использование цифр 10, 11, 12, 13, 14, 15 в записи чисел неудобно, т. к. трудно отличить, например, цифру 12 от двух цифр – 1 и 2. Поэтому условились цифры от 10 до 15 обозначать латинскими буквами в порядке алфавита A, B, C, D, E, F.

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

Чтобы перевести целое число Х из 10-ной системы в любую другую с основанием Q:

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

2) если полученная целая часть частного меньше Q, переходим к шагу 3. Если равно или больше Q, снова делим целую часть частного на Q, как описано в шаге 1. Внимание: делится только целая часть, остаток в делении не участвует (он пригодится позже).

3) все полученные остатки и последняя целая часть частного (меньшая, чем Q) преобразуются в соответствии с таблицей перевода в цифры той системы счисления, в которую выполняется перевод. Иными словами, если, к примеру, при переводе в 16-ную систему у вас получился остаток 12, то его нужно преобразовать в 16-ную цифру С.

4) Получаем ответ. Его первая (старшая) цифра - последнее частное, а остальные - остатки от деления, записанные в порядке, обратном порядку их получения.

 

Пример 1: 2610 ® Х2 Пример 2: 18110® Х8 Пример 3: 62210 ® Х16

2610 ® 0110102 18110® 265 8 62210 ® 26Е16

 

Перевод правильной дроби из 10-ной системы счисления в любую другую

Чтобы перевести правильную дробь X из 10-ной систему счисления в любую другую с основанием Q:

1. X умножаем на Q.

2. в полученном произведении целая часть (может быть равной нулю) преобразуется в цифру системы с основанием Q по таблице перевода цифр. Каждая из этих целых частей будет цифрой в ответе.

3. если дробная часть произведения равна нулю, переходим к шагу 4. Если не равна нулю, умножаем дробную часть произведения на Q, как написано в шагах 1 и 2. Обратите внимание: умножается только дробная часть, целая в умножении не участвует.

4. Получаем ответ: пишем "0,", а после десятичной запятой - преобразованные по таблице целые части произведений в порядке их получения (сверху вниз).

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

Пример 1: Пример 2: Пример 3:


Перевод смешанных чисел (неправильных дробей)

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

Если число Х имеет целую и дробную часть, то переводим целую часть по правилу для целых чисел, а дробную (вместе с нулем и десятичной запятой "0,") по правилу для дробей. Потом к переведенной целой части "приклеиваем" справа переведенную дробную (убрав из нее "0,").

Пример 1: 30,2510 ® Х2

Перевод числа (целого или дроби) из 2, 8, 16 системы счисления в 10-ную

Чтобы перевести число из системы счисления с основанием Q в 10-ную:

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

Примеры полиномов:

Пример 1: 45610 = 4*100 + 4*10 + 6 = 4*102 + 5*101 + 6*100

Пример 2: 0,72410 = 7*10-1 + 2*10-2 + 4*10-3

Пример перевода чисел в 10-ную систему:

Пример 1: 1011,012 ® Х10

1011,012 = 1*23 + 0*22 + 1*21 + 1*20 + 0*2-1 + 1*2-2 = 8 + 0 + 2 + 1 + 0 + 1/22 = 11 + 1/4 = 11 + 0,25 = 11,2510

Пример 2: 13,58 ® Х10

13,58 = 1*81 + 3*80 + 5*8-1 = 8 + 3 + 5*1/8 = 11 + 5/8 = 11,62510

Пример 3: А1416 ® Х10

А1416 = 10*162 + 1*161 + 4*16 = 10*256 + 16 + 4 = 258010

Перевод числа (целого или дроби) из 2-ной системы счисления в 8-ную и 16-ную

Вообще, это правило работает для перевода из 2-ной системы счисления в любую, основание которой представляет собой целую степень двойки, но мы рассмотрим его на примере 8-ной и 16-ной.

Напомню: 8=23, 16=24.

Чтобы перевести число из 2-ной в 8-ную систему счисления:

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

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

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


 

2-ная
8-ная

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

2-ная
16-ная
2-ная
16-ная A B C D E F

Пример 1: 1101111001,11012 ® Х8 Пример 2: 11111111011,1001112 ® Х16

       
 
   
 


 

Перевод числа из 8-ной и 16-ной систем счисления в 2-ную

Такой перевод выполняется обратно предыдущему случаю. Обучающее видео дано выше.

Рассмотрим для 8-ной системы счисления. Чтобы перевести 8-ное число в 2-ную систему счисления:

1. По таблице перевода цифр заменяем каждую 8-ную цифру триадой (группой из трех) 2-ных цифр. Если 8-ная цифра соответствует группе из двух 2-ных цифр (например, 38=112), то двоичная группа дополняется нулями слева так, чтобы получилось три двоичных цифры (0112).

2. Если в целой части получившегося 2-ного числа есть крайние слева нули в старших разрядах, убираем их (00512). Так же поступаем с крайними нулями справа в дробной части в младших разрядах (15,124000).

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

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

Пример 1: 305,48 ® Х2 Пример 2: 7B2,E16 ® Х2

       
   


 

Перевод числа (целого или дроби) из 8-ной в 16-ную и обратно

Такой перевод выполняется через 2-ную систему: 8-ное число сначала переводится в 2-ную, а потом из 2-ной в 16-ную. Из 16-ной в 8-ную переводим аналогично через 2-ную.

Пример 1: 175,248 ® Х16

Результат: 175,248 = 7D,516.

 

Арифметические операции в позиционных системах счисления

 

Таблица 4.1 Двоичная таблица Таблица 4.2 Двоичная таблица

сложения умножения


Арифметические операции в двоичной системе счисления выполняются с помощью Таблиц 1.4, 2.4 по тем же правилам, что и в десятичной системе счисления.

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

Восьмеричная система счисления. В восьмеричной системе счисления используются цифры 0, 1, 2, 3, 4, 5, 6, 7. Основание записывается в виде 8(10) = 8·100 = 1·81 + 0·80 = 10(8)

 

Таблица 4.3 Двоичная таблица Таблица 4.4 Двоичная таблица

сложения умножения

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

Шестнадцатеричная система счисления. В шестнадцатеричной системе счисления используются цифры 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 и буквы A, B, C,D, E, F. Основание шестнадцатеричной системы записывается в виде:

 

Таблица 5.5 Шестнадцатеричная Таблица 5.6 Шестнадцатеричная таблица

таблица сложения умножения

 

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