Logo GenDocs.ru

Поиск по сайту:  

Загрузка...

Практические занятия по теории автоматов - файл 1.doc


Практические занятия по теории автоматов
скачать (858.3 kb.)

Доступные файлы (7):

1.doc326kb.17.02.2006 07:42скачать
2.doc198kb.15.03.2007 10:03скачать
3_4.doc530kb.25.02.2006 20:22скачать
5.doc637kb.04.05.2005 12:29скачать
6.doc727kb.27.06.2005 08:51скачать
7.doc603kb.27.06.2005 09:22скачать
8.doc144kb.21.06.2007 21:09скачать

содержание
Загрузка...

1.doc

Реклама MarketGid:
Загрузка...

Материалы разработаны в НИУ МЭИ, факультат АВТИ, кафедра ВМСиС (Вычислительные машины, системы и сети)

Семинар 1
Системы счисления. Перевод из одной системы счисления в другую. Выполнение сложения в разных системах счисления.
Системы счисления (с/с) бывают позиционными и непозиционными.

Пример непозиционной с/с – римская.

В непозиционных системах вес цифры (т.е. тот вклад, который она вносит в значение числа) не зависит от ее позиции в записи числа. Так, в римской системе счисления в числе ХХХII (тридцать два) вес цифры Х в любой позиции равен просто десяти.

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

Запись числа 757,7 означает сокращенную запись выражения

700 + 50 + 7 + 0,7 = 7•102 + 5•101 + 7•100 + 7•10-1 = 757,7.

Любая позиционная система счисления характеризуется своим основанием.

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

,

где a – разрядная цифра, q – основание с/с, n – количество целых разрядов, m – количество дробных разрядов.

Например:


Пример. Представить число 124,5378 в виде многочлена.


Пример. Представить число 21223 в виде многочлена.


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

  1. Перевод подбором коэффициентов ("вручную")

  2. Перевод целых чисел делением на основание

  3. Перевод дробных чисел умножением на основание

  4. Использование промежуточной системы счисления


Рассмотрим все варианты подробнее.
1. Перевод подбором коэффициентов ("вручную")



Метод сводится к задаче определения коэффициентов нового ряда.

Правило: выбрать максимальную степень, которая содержится в числе . Все операции выполняются по правилам исходной системы счисления.
Пример. Перевести число 9610 в троичную с/с, т.е. 9610  Х3.

  1. Подбор максимальной степени для 3, чтобы полученное число было как можно ближе к 96, но не больше.

81 ближе к 96, 81 содержится в 96 – 1 раз, следовательно коэффициент при будет равняться 1.

Записывается многочлен с первым слагаемым, содержащим 3 в найденной степени и определенным коэффициентом, далее записываются слагаемые, содержащие 3 в степенях от 3 до 0. Отрицательная степень не используется, так как число целое.

.

На месте еще не найденных коэффициентов стоит троеточие.

Далее определяем остаток 96-81=15 для поиска неизвестных коэффициентов.

  1. Определение неизвестных коэффициентов слагаемых многочлена.

Определяем остаток 96-81=15, во втором слагаемом , что больше полученного остатка 15, следовательно коэффициент при будет равен 0.

Получаем:

В следующем слагаемом , что меньше остатка 15. 9 используется для получения 15 один раз, значит коэффициент будет равен 1. Новый остаток 15-9=6.

Многочлен принимает вид: .

Далее, , в остатке 6 3 встречается 2 раза, следовательно коэффициент при будет равен 2. Новый остаток равен 0, значит, у последнего слагаемого коэффициент будет равен 0.

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

.

  1. Для получения числа в троичной системе из выражения для многочлена выписываются коэффициенты. Получаем: .

Ответ:
Задача 1. Перевести .

Задача 2. Перевести .
^ 2. Перевод целых чисел делением на основание
Действия выполняются по правилам исходной системы счисления. Деление происходит на основание новой системы счисления, записанное в исходной системе счисления. Результат записывается перечислением остатков от деления, начиная с последнего.

Пример. Перевести делением на основание.

Получаем

Ответ:
Пример. Перевести делением на основание.

. Получаем

Ответ:
Задача 3. Перевести .

Задача 4. Перевести .

Задача 5. Перевести .
^ 3. Перевод дробных чисел умножением на основание.
Действия выполняются по правилам исходной системы счисления. Умножение происходит на основание новой системы счисления, записанное в исходной системе счисления. Результат записывается перечисление целых частей произведений, начиная с первого. Умножение производится либо с заданной точностью, либо до получения нулевого остатка.

Пример. Перевести умножением на основание.


Стрелка показывает направление записи результата перевода.
Ответ:

Пример: Перевести число 0,35 из десятичной системы в двоичную, восьмеричную и шестнадцатеричную:



Ответ: 0,3510 = 0,010112 = 0,2638 = 0,5916 .

Пример. Перевести умножением на основание.



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

Ответ:
Задача 6. Перевести с точностью 5 знака после запятой.

Задача 7. Перевести с точностью 8 знака после запятой.
^ 4. Перевод с использованием промежуточной системы счисления.
Используется для систем с основанием , k=1,2,3,…, т.е для 2, 8, 16 с/с.

Промежуточной с/с является двоичная.

Каждая цифра числа, записанного в исходной с/с с основанием , записывается в двоичной с/с с использованием k количества разрядов. Для записи числа в новой с/с с основанием в двоичном представлении выделяется по k1 разрядов, начиная от запятой влево для целой части числа и вправо – для дробной. Затем выделенные части переводятся в числа новой с/с. Запись подряд полученных цифр и будет являться результатом перевода.
Рассмотрим на примере преобразования последовательно.

  1. Преобразование числа, записанного в 8 или 16 с/с в двоичную



  1. Преобразование двоичного числа в 16 или 8 с/с соответственно.


Пример. Перевести

Исходная с/с - 8, что соответствует , т.е. k=3. Следовательно, цифры исходного числа записываются в двоичной с/с тремя разрядами (триадами).



Новая с/с – 16, что соответствует , т.е. k1=4. В записанном двоичном представлении, начиная от запятой выделяется по 4 разряда (тетрада). Если разрядов для выделения не хватает, то они дописываются нулями. Затем каждая тетрада переводится в цифру 16 с/с. Запись подряд полученных цифр является результатом перевода:



Ответ: .
Пример. Перевести



Ответ:
Задача 8. Перевести .

Задача 9. Перевести .

Задача 10. Перевести .

Задача 11. Перевести .
^ Сложение чисел в разных системах счисления.
Существует общий способ – сложение с выделением основания.

Является ручным способом. Для работы используется 10 с/с. Сложение выполняется поразрядно, если при этом возникает избыток, то он переносится влево.

Пример.


Выделение основания


Ответ:
Пример. Сложить числа 15, 7 и 3.





Шестнадцатеричная: F16+716+316



Проверка:

110012 = 24 + 23 + 20 = 16+8+1=25,

318 = 3*81 + 1*80 = 24 + 1 = 25,

1916 = 1*161 + 9*160 = 16+9 = 25.

Ответ: 5+7+3 = 2510 = 110012 = 318 = 1916.

Пример 3. Сложить числа 141,5 и 59,75.









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

11001001,012 = 27 + 26 + 23 + 20 + 2-2 = 201,25

311,28 = 3*82 + 1•81 + 1*80 + 2*8-1 = 201,25

C9,416 = 12*161 + 9*160 + 4*16-1 = 201,25

Ответ: 141,5 + 59,75 = 201,2510 = 11001001,012 = 311,28 = C9,416
Задача 12. Сложить .

Задача 13. Сложить .

Задача 14. Сложить .
Домашнее задание.

1. Перевести подбором коэффициентов многочлена.

2. Перевести подбором коэффициентов многочлена.

3. Перевести делением на основание.

4. Перевести делением на основание.

5. Перевести делением на основание.

6. Перевести делением на основание.

7. Перевести умножением на основание. Точность 6 знаков после запятой.

8. Перевести умножением на основание. Точность 5 знаков после запятой.

9. Перевести умножением на основание. Точность 4 знака после запятой.

10. Перевести умножением на основание. Точность 7 знаков после запятой.

11. Перевести делением и умножением на основание. Точность 5 знаков после запятой.

12. Перевести делением и умножением на основание. Точность 4 знака после запятой.

13. Перевести с использованием промежуточной системы счисления.

14. Перевести с использованием промежуточной системы счисления.

15. Перевести с использованием промежуточной системы счисления.

16. Перевести с использованием промежуточной системы счисления.

17. Перевести с использованием промежуточной системы счисления.

18. Перевести с использованием промежуточной системы счисления.

Решение задач 1 - 14.

Задача 1. Перевести .

, выбираем , в 136 число 64 содержится 2 раза. Следовательно множитель при будет равен 2. Остаток . Для второго слагаемого множитель равен 0, и его множитель равен 1, остаток равняется 0 и при множитель равен 0.

Получаем:

Ответ:
Задача 2. Перевести .

, выбирается , множитель будет равен 1. Остаток 539-343=196. Далее, , содержится в 196 4 раза, т.е. . При остальных слагаемых множители равны 0.

Получаем:

Ответ:

Задача 3. Перевести .

. Получаем

Ответ:
Задача 4. Перевести делением на основание.

Получаем

Ответ:
Задача 5. Перевести делением на основание.

Получаем

Ответ:
Задача 6. Перевести с точностью 5 знака после запятой.



Ответ:
Задача 7. Перевести с точностью 8 знака после запятой.



Ответ:
Задача 8. Перевести .



Ответ:
Задача 9. Перевести .



Ответ:
Задача 10. Перевести .



Ответ:
Задача 11. Перевести .



Ответ:
Задача 12. Сложить .



Ответ:
Задача 13. Сложить .



Ответ:
Задача 14. Сложить .



Ответ:


Скачать файл (858.3 kb.)

Поиск по сайту:  

© gendocs.ru
При копировании укажите ссылку.
обратиться к администрации