Алгоритмы неформально. Инструкция для начинающих питонистов - [10]
Столбец деления
Столбец умножения
89
18
44
Деление на 2 продолжается, пока не будет получен результат 1. При этом каждый раз остаток отбрасывается, а результат записывается в следующую строку. Половина от 44 равна 22, половина от 22 равна 11, половина от 11 (с потерей остатка) равна 5, затем 2, затем 1. Записав эти числа в столбец деления, мы получаем табл. 2.3.
Таблица 2.3. Таблица деления/умножения, часть 3
Столбец деления
Столбец умножения
89
18
44
22
11
5
2
1
Столбец деления готов. Каждый элемент столбца умножения равен удвоенному предыдущему элементу. Так как 18 × 2 = 36, вторая строка столбца умножения содержит 36 (табл. 2.4).
Таблица 2.4. Таблица деления/умножения, часть 4
Столбец деления
Столбец умножения
89
18
44
36
22
11
5
2
1
Далее мы продолжаем добавлять элементы в столбец умножения по тому же правилу: предыдущее значение удваивается. Это продолжается до тех пор, пока столбец умножения не сравняется по количеству элементов со столбцом деления (табл. 2.5).
Таблица 2.5. Таблица деления/умножения, часть 5
Столбец деления
Столбец умножения
89
18
44
36
22
72
11
144
5
288
2
576
1
1152
На следующем шаге из таблицы удаляются все строки, у которых столбец деления содержит четное число. Результат показан в табл. 2.6.
Таблица 2.6. Таблица деления/умножения, часть 6
Столбец деления
Столбец умножения
89
18
11
144
5
288
1
1152
Остается сложить все оставшиеся числа в столбце умножения. Результат равен 18 + 144 + 288 + 1152 = 1602. Правильность ответа можно проверить на калькуляторе: 89 × 18 = 1602. Умножение было реализовано с помощью операций деления надвое, удвоения и сложения, и нам не пришлось запоминать большую часть скучной таблицы умножения, которую так не любят дети.
Чтобы понять, почему работает этот метод, попробуйте переписать столбец умножения в виде множителей 18 — умножаемого числа (табл. 2.7).
Таблица 2.7. Таблица деления/умножения, часть 7
Столбец деления
Столбец умножения
89
18 × 1
44
18 × 2
22
18 × 4
11
18 × 8
5
18 × 16
2
18 × 32
1
18 × 64
В столбце умножения следует серия множителей 1, 2, 4, 8 и т.д. до 64. Все эти числа являются степенями 2, и их также можно записать в виде 20, 21, 22 и т.д. Когда мы вычисляем итоговую сумму (складываем строки столбца умножения, у которых столбец деления содержит нечетное значение), в действительности вычисляется следующая сумма:
18 × 20 + 18 × 23 + 18 × 24 + 18 × 26 = 18 × (20 + 23 + 24 + 26) = 18 × 89.
Работа RPM зависит от следующего факта:
(20 + 23 + 24 + 26) = 89.
Внимательно присмотревшись к столбцу деления, можно понять, почему данное уравнение истинно. Этот столбец тоже можно записать в степенях 2 (табл. 2.8).
Таблица 2.8. Таблица деления/умножения, часть 8
Столбец деления
Столбец умножения
(25 + 23 + 22) × 21 + 20 = 26 + 24 + 23 + 20
18 × 20
(25 + 23 + 22) × 21 + 20 = 26 + 24 + 23 + 20
18 × 21
(23 + 21 + 20) × 21 = 24 + 22 + 21
18 × 22
(22 + 20) × 21 + 20 = 23 + 21 + 20
18 × 23
21× 21 + 20 = 22 + 20
18 × 24
20× 21 = 21
18 × 25
20
18 × 26
При этом проще начать с наименьшего числа и двигаться снизу вверх. Стоит напомнить, что 20 = 1, а 21 = 2. В каждой строке значение умножается на 21, а в строках, в которых делимое число нечетно, также добавляется 20. При продвижении по строкам выражение начинает все больше напоминать наше уравнение. К моменту достижения верхней строки таблицы мы получаем выражение, которое упрощается в точности до 26 + 24 + 23 + 20.
Если мы пронумеруем строки столбца деления (верхняя строка обозначается как строка 0, затем 1, 2 и вплоть до нижней строки 6), то увидим, что нечетные значения в столбце деления содержатся в строках 0, 3, 4 и 6. Теперь заметим важнейшую закономерность: номера этих строк в точности совпадают с показателями степеней в найденном нами выражении для 89: 26 + 24 + 23 + 20. И это совпадение не случайно; способ построения столбца деления означает, что нечетные значения всегда находятся в строках, номера которых равны показателям степени в сумме степеней 2, равной нашему исходному числу. Когда мы вычисляем сумму элементов столбца умножения с этими индексами, мы фактически суммируем произведения 18 на степени 2, дающие в сумме 89, поэтому результат будет равен 89 × 18.
Почему же эта схема работает? В действительности RPM является алгоритмом внутри алгоритма. Сам столбец деления может считаться реализацией алгоритма, который находит сумму степеней 2, равную числу в первой ячейке столбца. Сумма степеней 2 также называется двоичным разложением числа 89. Двоичная система представляет собой альтернативную схему записи чисел с использованием только 0 и 1; она стала играть особенно важную роль в последние десятилетия, поскольку компьютеры хранят информацию в двоичном виде. В двоичной записи число 89 записывается в виде 1011001, с единицами в нулевой, третьей, четвертой и шестой позиции (справа налево); номера позиций соответствуют номерам нечетных строк столбца деления, а также степеням нашего уравнения. 1 и 0 в двоичном представлении можно рассматривать как коэффициенты в сумме степеней 2. Например, двоичное число 100 интерпретируется следующим образом:
1 × 22 + 0 × 21 + 0 × 20
или 4 в обычной (десятичной) записи. Двоичное число 1001 интерпретируется так:
В учебно-методическом пособии рассматриваются основы языка программирования PL/SQL, реализованного в системе управления базами данных Oracle Database Server. Приводятся сведения о поддерживаемых типах данных, структуре программ PL/SQL и выполнении SQL-предложений в них. Отдельно рассмотрено создание хранимых в базах данных Oracle программ PL/SQL – процедур, функций, пакетов и триггеров.
Рассмотрено все необходимое для разработки, компиляции, отладки и запуска приложений Java. Изложены практические приемы использования как традиционных, так и новейших конструкций объектно-ориентированного языка Java, графической библиотеки классов Swing, расширенной библиотеки Java 2D, работа со звуком, печать, способы русификации программ. Приведено полное описание нововведений Java SE 7: двоичная запись чисел, строковые варианты разветвлений, "ромбовидный оператор", NIO2, новые средства многопоточности и др.
В книге рассматриваются базисные теоретические основы, необходимые для построения компиляторов, основные технологические приемы и методы их реализации. В ней приведены различные варианты заданий для выполнения лабораторного практикума по курсу «Системное программное обеспечение», а также примеры выполнения этих заданий. В каждом примере подробно рассматриваются все особенности его выполнения, как на этапе подготовки необходимой математической базы, так и на этапе программной реализации. В лабораторных работах автор обращает внимание на основные сложности, связанные с ее выполнением, а также на возможные типичные ошибки и недочеты, дает рекомендации по возможностям программной реализации, отличным от кода, приводимого в примерах.Книга ориентирована на студентов, обучающихся в технических вузах по специальностям, связанным с вычислительной техникой.
Книга известного специалиста по программированию (Югославия), содержащая основы языка Пролог и его приложения для решения задач искусственного интеллекта. Изложение отличается методическими достоинствами — книга написана в хорошем стиле, живым языком. Книга дополняет имеющуюся на русском языке литературу по языку Пролог.Для программистов разной квалификации, специалистов по искусственному интеллекту, для всех изучающих программирование.
РАССЫЛКА ЯВЛЯЕТСЯ ЧАСТЬЮ ПРОЕКТА RSDN, НА САЙТЕ КОТОРОГО ВСЕГДА МОЖНО НАЙТИ ВСЮ НЕОБХОДИМУЮ РАЗРАБОТЧИКУ ИНФОРМАЦИЮ, СТАТЬИ, ФОРУМЫ, РЕСУРСЫ, ПОЛНЫЙ АРХИВ ПРЕДЫДУЩИХ ВЫПУСКОВ РАССЫЛКИ И МНОГОЕ ДРУГОЕ.
В этой книге содержится описание базовых принципов функционирования платформы .NET, системы типов .NET и различных инструментальных средств разработки, используемых при создании приложений .NET. Представлены базовые возможности языка программирования C# 2005, включая новые синтаксические конструкции, появившиеся с выходом .NET 2.0, а также синтаксис и семантика языка CIL. В книге рассматривается формат сборок .NET, библиотеки базовых классов .NET. файловый ввод-вывод, возможности удаленного доступа, конструкция приложений Windows Forms, доступ к базам данных с помощью ADO.NET, создание Web-приложений ASP.NET и Web-служб XML.