|
RIP
#02
29 ноября 1997 |
|
Школа хаккера - Цикл "БАЗА -1": Укращение Дракона, Атака Дракона.
┌────────────────────────────────┐
│ БАЗА-1 │
│ Семинар Первый. Основание. │
│ (Продолжение, начало в RIP #1) │
└────────────────────────────────┘
Все права на методические материалы Хэкерской Школы
принадлежат Арви Хаккеру (Илье Васильеву), г. Москва,
2:5020/287@fidonet, arvi@hsys.msk.ru, ath@verte.dnntm.rssi.ru.
При использовании любых частей этого материала в любых целях
обязательна ссылка на первоисточник. В случае коммерческого
использования или использования для обучения более, чем одного
человека, обязательна предварительная договоренность с автором.
Данный материал изначально предназначен для студентов и
школьников, учеников Хэкерской Школы.
B1:3 Укрощение Дракона.
=======================
Алгоритм перевода из любой системы в десятичную мы называем
алгоритмом Укрощения Дракона: X_n->Y_10. Hазываем потому, что
длинная строчка вычисления напоминает спину лежащего дракона, а
ответ - голову смирившегося дракона. Он основан на наблюдении,
что:
34947 = 30000+4000+900+40+7 = 3*10^4 + 4*10^3 + 9*10^2 + 4*10 +7
То есть, число равно сумме его цифр, умноженных на
соответствующие степени основания. Переводы чисел 1210_3 и
C00L_22:
1210_3 = 1*3^3 + 2*3^2 + 1*3 + 0 = 27 + 18 + 3 = 48_10
C00L_22 = 12*22^3 + 0*22^2 + 0*22 + 21 = 127776 + 21 = 127797
Многие книги эту версию алгоритма Укрощения Дракона
используют для определения, что такое системы счисления.
Попробуйте попереводить побольше чисел из самых различных систем
счисления. Желательно без использования калькулятора, выполняя
все арифметические действия в уме или на листочке. Побольше
двоичных чисел - они нам еще пригодятся!
>>>
Применив схему Горнера (B1:1), мы получим намного более
эффективную версию алгоритма Укрощения Дракона.
1210_3 = ((1*3+2)*3+1)*3+0 = 16*3 = 48
C00L_22 = (((12*22+0)*22+0)*22+21 = 127776 + 21 = 127797
В чем его эффективность? Теперь не требуется операций
возведения в степень! При программировании на ассемблере -это
просто блеск! Даже на языках высокого уровня программа перевода
получается значительно быстрее и короче. Попробуйте составить
эту программу, переводящую числа из любой системы счисления на
привычный вам десятичный язык. Она почти дублирует программу для
схемы Горнера.
Хэкеру нужно постоянно быть в боевой готовности -- кто
знает, где ему придется демонстрировать Искусство. Вполне
возможно, что вас попросят починить или удалить вирус из
компьютера в самом странном месте -в супермаркете или дома у
вашей девушки. (В фильме "War Games" молодой хэкер Дэвид,
подсоединив случайно оказавшийся диктофон к кодовому замку,
сумел записать и повторить сигналы открытия двери и убежать из
под ареста.)
Если под рукой есть только примитивный калькулятор, лишь с
четырьмя арифметическими действиями (типа вделанного в часы), то
по традиционному методу вам придется где-то записывать, а потом
набирать промежуточные результаты. По новому методу вам
потребуется лишь набирать между цифрами знак умножения,
основание системы счисления и знак сложения.
Если под рукой не оказалось даже примитивнейшего
калькулятора, то новый алгоритм Укрощения Дракона можно
использовать для перевода числа столбиком. Результат одного
примера является начальным значением для следующего.
1 12
*3 *22
--- ----
3 24
+2 24
--- ----
5 264
*3 +0 Конечно, нули я здесь прибавляю лишь для обучения,
--- ---- в реальной жизни это делать необязательно. :-)
15 264
+1 *22
--- ----
16 528
*3 528
--- ----
18 5808
3 +0
--- ----
48 5808
+0 *22
--- ----
48 11616
11616
------
127776
+21
------
127797
Здесь мы Укрощенного Дракона ставим вертикально, мордой
вниз. Hаверное, чтобы их больше поместилось...
<<<
B1:4 Атака Дракона.
===================
Обратное действие, перевод из десятичной системы счисления в
произвольную, мы называем Атакой Дракона: Y_10->X_n. Это
действие обычно выполняется, когда мы хотим ввести информацию
внутрь компьютера. Мы живем в десятичном мире, а компьютер - в
каком-нибудь шестнадцатеричным. И для того, чтобы ввести
что-нибудь наше в его мир, "Атаковать", нам придется перевести
это в чужую систему счисления.
Тут надо уметь делить. :-) Переведем числа, полученные при
Укрощении Дракона, обратно, в "родные" системы счисления,
последовательно деля их на основание, пока не получится число,
меньшее самого основания. Это число столбиком уже не разделишь.
:-)
48 | 3 127797| 22
-3 +-----+ -110 +------+
-- | 16 | 3 --- | 5808| 22
18 -15 +----+ 177 -44 +------+
-18 -- | 5 | 3 -176 -- | 264 | 22
-- 1 -3 +---- --- 140 -22 +----
0 -- | 1 197 -132 -- | 12=C
2 -176 --- 44
--- 88 -44
21=L -88 --
-- 0
0
Результат считывается из последнего частного и остатков,
собираемых в обратном порядке. Так в первом случае получаем
1210_3, а во втором - C00L_22.
Попробуйте перевести числа, получившиеся при самостоятельной
практике Укрощения, обратно, в их исходные системы счисления.
Попробуйте несколько десятичных чисел перевести во всякие
странные системы счисления и обратно.
>>>
Если вы умеете хорошо делить в уме (или используете
калькулятор), то удобнее использовать другую запись:
48|0 127797|21=L
16|1 5808| 0
5|2 264| 0
1| 12=C
Здесь при каждом делении остаток записывается справа от
черты, а частное -внизу. Как всегда, при Атаке ответ считывается
в обратном порядке -снизу вверх.
Составьте программу, выполняющую автоматический перевод в
любую систему счисления.
<<<
(Продолжение следует...)
Другие статьи номера:
Похожие статьи:
В этот день... 21 ноября