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 Шестнадцатеричная таблица
таблица сложения умножения
Приведем некоторые примеры выполнения основных операций в шестнадцатеричной системе счисления.
