Уравновешенные системы счисления. Задача «о взвешивании» Какое наименьшее число гирь нужно иметь, чтобы с их помощью можно было взвесить на чашечках равноплечных. - презентация

1 Уравновешенные системы счисления

2 Задача «о взвешивании» Какое наименьшее число гирь нужно иметь, чтобы с их помощью можно было взвесить на чашечках равноплечных весов любой груз массой от 1 до 40 ед. включительно. Гири можно располагать на любой из чашек весов. Эта задача была известна еще Фибоначчи в 1215 г. Иногда эту задачу называют задачей Баше и задачей Менделеева.

3 Оптимальным оказался набор гирь: 1, 3, 9, 27 ед.

4 Для того чтобы взвесить груз в n г, надо представить число n в виде суммы a 0 + 3·a 1 + 9·a ·a 3, где a i = 0, ±1 (i = 0, 1, 2, 3). При взвешивания достаточно на чашку вместе с грузом положить все гири, массы которых входят в эту сумму со знаком минус, а на противоположную чашку положить все гири, массы которых входят в эту сумму со знаком плюс.

5 Например Для того чтобы взвесить груз в 5 г, надо представить число 5 в виде суммы: (-1) + 3·(-1) + 9·(1) Для того чтобы взвесить груз в 29 г, надо представить число 29 в виде суммы: (-1) + 3·(1) + 9·(0) + 27·(1)

6 27931ВЕС (ед.) …………… …………… Таблица результатов взвешиваний:

7 Выводы: – позиционная система с основанием q = 3; – цифры 0, 1, 1; – цифра 1 означает минус единицу в соответствующем разряде.

8 Определение Уравновешенной троичной системой счисления или троичной системой с симметричным основанием называется система с основанием q = 3 и цифрами, принадлежащими множеству [ 1, 0, 1 ], где цифра 1 означает –1 (минус единицу).

9 Отрицательные числа в уравновешенной троичной системе счисления = (-1)· ·3 2 +1·3 + 1 = = ; = (-1)· ·3 2 + (-1)·3 +(-1) = = Числа, начинающиеся с цифры 1 – положительные; Числа, начинающиеся с цифры 1 – отрицательные;

10 3-я ур. отриц10-я отриц я полож.3-я ур. полож

11 Арифметика в троичной уравновешенной системе счисления х х Проверьте результат в 10-ой системе счисления

12 Достоинства уравновешенной троичной системы счисления: алгоритм получения отрицательных чисел: число 1 заменить на 1 и наоборот: = число противоположное: = вычитание сводится к сложению со сменой знака у вычитаемого. доступны операции с дробями.

13 Умножение, как и деление, тоже сводится к перемене знака и сложению. Запись в троичной системе имеет длину на одну треть меньше, чем в двоичной. Для выполнения округления в этой системе достаточно просто отбросить лишние цифры.

14 Эти достоинства привлекают внимание конструкторов вычислительной техники В 1958 г. в Советском союзе экспериментальная ЭВМ «Сетунь» на базе троичной уравновешенной системы счисления. К 1965 г. выпущено более 50 экземпляров. Можно рассматривать уравновешенные системы счисления с основаниями q = 5, q = 7 или q = 9 и т. д.

15 «Гирьки» для практической работы