Задача: реализовать в эмуляторе диаграммера (машины) Тьюринга перевод числа из четверичной (4-ой) системы счисления (СС) в шестнадцатеричную (16-ую). Алгоритм перевода должен быть логарифмической сложности.
Реализация:
Логарифмическая сложность алгоритма – это когда количество шагов в алгоритме логарифмически зависит от объема входных данных. Т.е. если объем данных увеличивается в n раз, то время работы увеличивается ln(n).
Рассмотрим такой алгоритм перевода:
1) Каждое число в 4-ой СС разбиваем на пары с конца. Каждая пару чисел можно перевести в одно 16-ое число по таблице соответствия:
10 4 16
0 0 0
1 1 1
2 2 2
3 3 3
4 10 4
5 11 5
6 12 6
7 13 7
8 20 8
9 21 9
10 22 A
11 23 B
12 30 C
13 31 D
14 32 E
15 33 F
2) Например, для числа 1324 будут пары «1» («01») и «32», что соответствует 1E в 16 СС.
3) С точки зрения программы перемещаемся в конец первой пары и смотрим первую цифру – 2 – и ограничиваем какие варианты могут быть с ней в 16 СС:
10 4 16
0 0 0
1 1 1
2 2 2
3 3 3
4 10 4
5 11 5
6 12 6
7 13 7
8 20 8
9 21 9
10 22 A
11 23 B
12 30 C
13 31 D
14 32 E
15 33 F
4) Получили 4 варианта. Смотрим вторую цифру – 3 – значит подходит один вариант с Е:
10 4 16
0 0 (00) 0
1 1 (01) 1
2 2 (02) 2
3 3 (03) 3
4 10 4
5 11 5
6 12 6
7 13 7
8 20 8
9 21 9
10 22 A
11 23 B
12 30 C
13 31 D
14 32 E
15 33 F
5) Также с «1» - подходит вариант в 16-ой СС с цифрой 1.
Реализованная программа будет выполнять две задачи – перевод исходного числа и формирование нового числа без пробелов между числами. Алфавитом будем выступать цифры 16-ой СС + пробел:
Основная программа делится на четыре части – копирование исходного слова (1), подпрограмма перевода в 16-ую СС первой пары чисел с конца (2), перевод каретки на один символ влево (3), подпрограмма перевода в 16-ую СС остальных пар чисел (4):
- Курсовая работа
- Дипломная работа
- Контрольная работа
- Реферат
- Отчет по практике
- Магистерская работа
- Статья
- Эссе
- Научно-исследовательская работа
- Доклад
- Глава диплома
- Ответы на билеты
- Презентация
- Тезисный план
- Чертёж
- Диаграммы, таблицы
- ВАК
- Перевод
- Бизнес план
- Научная статья
- Рецензия
- Лабораторная работа
- Решение задач
- Диссертация
- Доработка заказа клиента
- Аспирантский реферат
- Монография
- ВКР
- Дипломная работа MBA
- Компьютерный набор текста
- Речь к диплому
