ЗАДАНИЯ ДЛЯ САМОСТОЯТЕЛЬНОГО ВЫПОЛНЕНИЯ. 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: 26₁₀ ® Х₂ Пример 2: 181₁₀® Х₈ Пример 3: 622₁₀ ® Х₁₆

26₁₀ ® 011010₂ 181₁₀® 265 ₈ 622₁₀ ® 26Е₁₆

Перевод правильной дроби из 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,25₁₀ ® Х₂

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

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

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

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

Пример 1: 456₁₀ = 4*100 + 4*10 + 6 = 4*10² + 5*10¹ + 6*10⁰

Пример 2: 0,724₁₀ = 7*10^-1 + 2*10^-2 + 4*10^-3

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

Пример 1: 1011,01₂ ® Х₁₀

1011,01₂ = 1*2³ + 0*2² + 1*2¹ + 1*2⁰ + 0*2^-1 + 1*2^-2 = 8 + 0 + 2 + 1 + 0 + 1/2² = 11 + 1/4 = 11 + 0,25 = 11,25₁₀

Пример 2: 13,5₈ ® Х₁₀

13,5₈ = 1*8¹ + 3*8⁰ + 5*8^-1 = 8 + 3 + 5*1/8 = 11 + 5/8 = 11,625₁₀

Пример 3: А14₁₆ ® Х₁₀

А14₁₆ = 10*16² + 1*16¹ + 4*16 = 10*256 + 16 + 4 = 2580₁₀

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

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

Напомню: 8=2³, 16=2⁴.

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

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

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

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

2-ная
8-ная

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

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

Пример 1: 1101111001,1101₂ ® Х₈ Пример 2: 11111111011,100111₂ ® Х₁₆

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

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

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

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

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

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

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

Пример 1: 305,4₈ ® Х₂ Пример 2: 7B2,E₁₆ ® Х₂

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

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

Пример 1: 175,24₈ ® Х₁₆

Результат: 175,24₈ = 7D,5₁₆.

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

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

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

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

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

Восьмеричная система счисления. В восьмеричной системе счисления используются цифры 0, 1, 2, 3, 4, 5, 6, 7. Основание записывается в виде 8₍₁₀₎ = 8·10⁰ = 1·8¹ + 0·8⁰ = 10₍₈₎

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

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

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

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

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

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

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