Как найти неизвестную систему счисления

Автор – Лада Борисовна Есакова.

Перед тем, как приступить к решению задач, нам нужно понять несколько несложных моментов.

Рассмотрим десятичное число 875. Последняя цифра числа (5) – это остаток от деления числа 875 на 10. Последние две цифры образуют число 75 – это остаток от деления числа 875 на 100. Аналогичные утверждения справедливы для любой системы счисления:

Последняя цифра числа – это остаток от деления этого числа на основание системы счисления.

Последние две цифры числа – это остаток от деления числа на основание системы счисления в квадрате.

Например, . Разделим 23 на основание системы 3, получим 7 и 2 в остатке (2 – это последняя цифра числа в троичной системе). Разделим 23 на 9 (основание в квадрате), получим 18 и 5 в остатке (5 = ).

Вернемся опять к привычной десятичной системе. Число = 100000. Т.е. 10 в степени k– это единица и k нулей.

Аналогичное утверждение справедливо для любой системы счисления:

Основание системы счисления в степени k в этой системе счисления записывается как единица и k нулей.

Например, .

1. Поиск основания системы счисления

Пример 1.

В системе счисления с некоторым основанием десятичное число 27 записывается в виде 30. Укажите это основание.

Решение:

Обозначим искомое основание x. Тогда .Т.е. x = 9.

Ответ: 9

Пример 2.

В системе счисления с некоторым основанием десятичное число 13 записывается в виде 111. Укажите это основание.

Решение:

Обозначим искомое основание x. Тогда

Решаем квадратное уравнение, получаем корни 3 и -4. Поскольку основание системы счисления не может быть отрицательным, ответ 3.

Ответ: 3

Пример 3

Укажите через запятую в порядке возрастания все основания систем счисления, в которых запись числа 29 оканчивается на 5.

Решение:

Если в некоторой системе число 29 оканчивается на 5, то уменьшенное на 5 число (29-5=24) оканчивается на 0. Ранее мы уже говорили, что число оканчивается на 0 в том случае, когда оно без остатка делится на основание системы. Т.е. нам нужно найти все такие числа, которые являются делителями числа 24. Эти числа: 2, 3, 4, 6, 8, 12, 24. Заметим, что в системах счисления с основанием 2, 3, 4 нет числа 5 (а в формулировке задачи число 29 оканчивается на 5), значит остаются системы с основаниями: 6, 8, 12,

Ответ: 6, 8, 12, 24

Пример 4

Укажите через запятую в порядке возрастания все основания систем счисления, в которых запись числа 71 оканчивается на 13.

Решение:

Если в некоторой системе число оканчивается на 13, то основание этой системы не меньше 4 (иначе там нет цифры 3).

Уменьшенное на 3 число (71-3=68) оканчивается на 10. Т.е. 68 нацело делится на искомое основание системы, а частное от этого при делении на основание системы дает в остатке 0.

Выпишем все целые делители числа 68: 2, 4, 17, 34, 68.

2 не подходит, т.к. основание не меньше 4. Остальные делители проверим:

68:4 = 17; 17:4 = 4 (ост 1) – подходит

68:17 = 4; 4:17 = 0 (ост 4) – не подходит

68:34 = 2; 2:17 = 0 (ост 2) – не подходит

68:68 = 1; 1:68 = 0 (ост 1) – подходит

Ответ: 4, 68

2. Поиск чисел по условиям

Пример 5

Укажите через запятую в порядке возрастания все десятичные числа, не превосходящие 25, запись которых в системе счисления с основанием четыре оканчивается на 11?

Решение:

Для начала выясним, как выглядит число 25 в системе счисления с основанием 4.

. Т.е. нам нужно найти все числа, не больше , запись которых оканчивается на 11. По правилу последовательного счета в системе с основанием 4,
получаем числа и . Переводим их в десятичную систему счисления:

Ответ: 5, 21

3. Решение уравнений

Пример 6

Решите уравнение:

Ответ запишите в троичной системе (основание системы счисления в ответе писать не нужно).

Решение:

Переведем все числа в десятичную систему счисления:

Квадратное уравнение имеет корни -8 и 6. (т.к. основание системы не может быть отрицательным). .

Ответ: 20

4. Подсчет количества единиц (нулей) в двоичной записи значения выражения

Для решения этого типа задач нам нужно вспомнить, как происходит сложение и вычитание «в столбик»:

При сложении происходит поразрядное суммирование записанных друг под другом цифр, начиная с младших разрядов. В случае, если полученная сумма двух цифр больше или равна основанию системы счисления, под суммируемыми цифрами записывается остаток от деления этой суммы на основание системы, а целая часть от деления этой суммы на основание системы прибавляется к сумме следующих разрядов.

При вычитании происходит поразрядное вычитание записанных друг под другом цифр, начиная с младших разрядов. В случае, если первая цифра меньше второй, мы «занимаем» у соседнего (большего) разряда единицу. Занимаемая единица в текущем разряде равна основанию системы счисления. В десятичной системе это 10, в двоичной 2, в троичной 3 и т.д.

Пример 7

Сколько единиц содержится в двоичной записи значения выражения: ?

Решение:

Представим все числа выражения, как степени двойки:

В двоичной записи двойка в степени n выглядит, как 1 и n нулей. Тогда суммируя и , получим число, содержащее 2 единицы:

Теперь вычтем из получившегося числа 10000. По правилам вычитания занимаем у следующего разряда.

Теперь прибавляем к получившемуся числу 1:

Видим, что у результата 2013+1+1=2015 единиц.

Ответ: 2015.

Решение задач по системе счисления. Часть 2

Главная > Решение

Информация о документе
Дата добавления:
Размер:
Доступные форматы для скачивания:

Решение задач по системе счисления. Часть 2.

Учитель информатики Батракова Л.В.

11. Решите уравнение .
Ответ запишите в четверичной системе счисления. Основание системы счисления указывать не нужно.

Решение: Надо перевести все числа в десятичную систему, решить уравнение и результат перевести в четверичную систему:

1)

из уравнения получаем

переводим 22 в четверичную систему счисления:

12. Запись натурального числа в системах счисления с основанием 4 и 6 заканчивается на 0. Найдите минимальное натуральное число, удовлетворяющее этим условиям.

Решение: если запись числа в системе счисления с основанием N заканчивается на 0, то это число делится на N нацело, поэтому в данной задаче требуется найти наименьшее натуральное число, которое делится одновременно на 4 и на 6, то есть это число12.

13. Укажите, сколько всего раз встречается цифра 3 в записи чисел 13, 14, 15, …, 23 в системе счисления с основанием 4.

Решение (вариант 1):

При решении задачи надо помнить, что в 4-ой системе счисления самая старшая цифра – 3.

Запишем первое и последнее число в заданном диапазоне в системе счисления с основанием 4:

13 = 31 4 , 23 = 113 4 .

Оба они содержат цифру 3, так что, 2 цифры мы уже нашли.

Между 31 4 и 113 4 есть еще числа:

32 4 , 33 4 , 100 4 , 101 4 , 102 4 , 103 4, 110 4 , 111 4 , 112 4 .

В них 4 цифры 3, поэтому всего цифра 3 встречается 6 раз.

Решение (вариант 2):

Можно перевести все указанные числа в систему счисления с основанием 4 и подсчитать количество 3:

13 =31 4 , 14 =32 4 , 15 =33 4 , 16 =100 4 , 17 =101 4 , 18 =102 4 , 19 =103 4 , 20 =110 4 , 21 = 111 4 , 22=112 4 , 23 = 113 4 .

Получается 6 штук.

14. Укажите наименьшее основание системы счисления, в которой запись числа 50 двузначна.

Решение: Так как число по условию двухзначное, то достаточно найти первое целое число, квадрат которого больше 50; это – 8, так как:

Так как , следовательно, в системе счисления с основанием 7 запись числа 50 будет трехзначна, а в 8-ой системе счисления – двузначной.

15. Укажите через запятую в порядке возрастания все десятичные числа, не превосходящие 25, запись которых в системе счисления с основанием 6 начинается на 4?

Решение: Поскольку , в интересующих нас числах может быть не более 2 цифр. Есть всего одно однозначное число, начинающееся на 4, это 4. Выпишем все числа в шестеричной системе счисления, которые являются двузначными, начинаются с 4 и не превосходят 25 в десятичной системе. Это числа: 40 6 = 24, 41 6 = 25. Ответ: 4, 24, 25

16. Запись числа 65 8 в некоторой системе счисления выглядит так: 311 N . Найдите основание системы счисления N.

Решение: Из условия задачи следует, что 65 8 = 311 N . Переведем 65 8 в десятичную систему счисления:

,

Второе число разложим по основанию счисления N:

Так как что 65 8 = 311 N , то можно записать: .

Решаем это уравнение и получаем, что N = 4.

17. Даны 4 числа, они записаны с использованием различных систем счисления. Укажите среди этих чисел то, в двоичной записи которого содержится ровно 5 единиц. Если таких чисел несколько, укажите наибольшее из них.

1) 31 10 * 8 10 + 1 10 2) F0 16 + 1 10 3) 351 8 4) 11100011 2

Решение: Нужно перевести все заданные числа в двоичную систему, подсчитать число единиц и выбрать наибольшее из чисел, в которых ровно 5 единиц.

Для первого варианта переведем оба сомножителя в двоичную систему:

31­ 10 = 11111­ 2 8 10 = 1000­ 2

В первом числе ровно 5 единиц, умножение на второе добавляет в конец три нуля:

31­ 10 * 8 10 = 11111­ 2 * 1000­ 2 = 111110­00 2

то есть в этом числе 5 единиц, но надо добавить еще одну единицу в конец, получим число 11111001, в котором 6 единиц. Так как нам нужны числа с 5-ю единицами, то это число не рассматриваем.

Для второго варианта воспользуемся двоичным представлением 16-ричных чисел: каждую цифру шестнадцатеричного числа можно переводить отдельно в тетраду (4 двоичных цифры):

F­0 16 = 1111­0000 2

после добавления единицы F0 16 + 1 = 1111 0001 2 получаем число, содержащее ровно 5 единиц.

Для третьего варианта используем связь между восьмеричной и двоичной системами: каждую цифру восьмеричного числа переводим отдельно в триаду (группу из трёх) двоичных цифр:

351 8 = 11101001­ 2

это число тоже содержит 5 единиц, но меньше, чем число во втором варианте ответа.

Последнее число 11100011 2 уже записано в двоичной системе, оно тоже содержит ровно 5 единиц, но меньше второго и третьего числа.

Таким образом, только 3 числа, указанные в вариантах ответов, содержат ровно 5 единиц, но наибольшее из них – второе.

18. Даны 4 целых числа, записанные в двоичной системе:
10001011, 10111000, 10011011, 10110100.
Сколько среди них чисел, больших, чем А4 16 +20 8 ?

1) 1 2) 2 3) 3 4) 4

Решение: Надо перевести А4 16 +20 8 в двоичную систему счисления, разложив их по тетрадам для 16-х чисел и по триадам для 8-х чисел: А4 16 – 10100100 2 и 20 8 – 10000 2 и поразрядно сложить: 10100100 2 + 10000 2 = 10110100 2 .

Сравнив с заданными числами, видим, что только одно число больше полученного, это: 10111000.

19. К записи натурального числа в восьмеричной системе счисления справа приписали два нуля. Во сколько раз увеличилось число? Ответ запишите в десятичной системе счисления.

Решение: Так как приписали 2 нуля, то для решения задачи достаточно вычислить 8 2 =64.

20. Десятичное число 109 в некоторой системе счисления записывается как «214». Определите основание системы счисления.

Решение: Обозначим искомое основание системы счисления через x , тогда можно записать выражение:

109 = 2 x 2 + x +4 или 2 x 2 + x -105 = 0. Решив это уравнение, получим x =7.

Дополнительно (для самых умных):

Запись числа N в системе счисления c основанием 6 содержит две цифры, запись этого числа в системе счисления c основанием 5 содержит три цифры, а запись в системе счисления c основанием 11 заканчивается на 1. Чему равно N? Запишите ответ в десятичной системе счисления.

Решение: Из первых двух условий задачи следует, что 5 2 = 25 ≤ N 2 = 36, следовательно, значение N надо искать из следующего набора чисел: 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35.

Из третьего условия находим число, которое при делении на 11 дает остаток 1, это число 34.

Проверка: 34 = 54 6 =5· 6 1 + 4 · 6 0 , 34 = 114 5 = 1· 5 2 + 1 · 5 1 + 4 · 5 0 , 34 = 31 11 = 3 · 11 1 + 1 · 11 0 .

Найдите основание системы счисления, в которой выполнено сложение: 144 + 24 = 201.

Решение: Так как старшая цифра в выражении 4, то надо рассматривать системы счисления, начиная с 5-ной.

Пятеричная система не подходит, т.к. 4 + 4 в пятеричной системе даст нам последнюю цифру в ответе 3. Шестеричная система так же не подходит – последняя цифра в ответе будет 2. А вот семеричная система подойдет для всех цифр ответа.

Дополнительно (для самых-самых умных):

1. Укажите через запятую в порядке возрастания все основания систем счисления, в которых запись числа 31 оканчивается на 11.

неизвестно основание системы счисления, мы обозначим его через

пока будем считать, что запись числа 31 в системе с основанием состоит из трех цифр, причем две младшие (11) нам даны, а одну (обозначим ее через ) нужно найти:

31 = k 1 1 N = k · N 2 + N 1 + N 0 = k· N 2 + N + 1

можно показать, что при большем количестве разрядов эта формула также верна, то есть, число 31 можно представить как при некотором целом ; например, для числа с пятью разрядами получаем:

4 3 2 1 0 ← разряды

31 = k 4 k 3 k 2 1 1 N = k 4 ·N 4 + k 3 · N 3 + k 2 · N 2 + N 1 + N 0

для (из первых трех слагаемых вынесли общий множитель )

Решение: Нужно найти все целые числа , такие что

(**)

где – целое неотрицательное число (0, 1, 2, …).

Сложность в том, что и , и неизвестны, однако здесь нужно «играть» на том, что это натуральные числа.

Из формулы (**) получаем , так что задача сводится к тому, чтобы найти все делители числа 30 и отобрать только те из них, для которых уравнение (**) разрешимо при целом , то есть, – целое число.

Выпишем все делители числа 30, большие или равные 2: 2, 3, 5, 6, 10, 15, 30.

Из всех этих делителей только для 2, 3, 5 и 30 значение – целое число (оно равно соответственно 7, 3, 1 и 0)

Ответ : 2, 3, 5, 30.

Замечание: Можно, конечно, решить задачу и методом подбора.

31 = 2 5 – 1 = 11111 2

2. Укажите через запятую в порядке возрастания все основания систем счисления, в которых запись числа 94 начинается на 23.

Решение: Из условия задачи видно, что искомое основание не меньше 4 (в записи есть цифра 3).

Если запись числа 94 в некоторой системе счисления с основанием двузначна (94 = 23 x ), то справедливо равенство .

Нас интересуют натуральные решения этого уравнения, такие что , но таких решений нет.

Предположим, что число четырехзначное. Минимальное допустимое четырехзначное число – 2300 x , где . При минимальном основании () оно равно.

Следовательно, запись нужного нам числа имеет три знака.

Можно записать: , где – целое неотрицательное число, такое что .

Максимальное можно определить как решение уравнения (при ).

Получаем одно из решений – 6,15. Отсюда: 4≤.

определится как: .

Подставим поочередно в эту формулу , пытаясь получить .

Минимальное = 4 будет при , т.е условиевыполняется, а при получается .

Как решать уравнения с неизвестной системой счисления

В системе счисления с некоторым основанием десятичное число 18 записывается в виде 30. Укажите это основание.

Составим уравнение: где n — основание этой системы счисления. Исходя из уравнения,

Ответ запишите в троичной системе (основание системы счисления в ответе писать не нужно).

Основание системы счисления равно 6₁₀ = 20₃.

Корни квадратного уравнения: 8 и −10. Следовательно, основание системы счисления равно 8.

Переведём все числа в десятичную систему счисления:

Составим новое уравнение и решим уже его:

Чему равно наименьшее основание позиционной системы счисления x, при котором 225_x = 405_y?

Ответ записать в виде целого числа.

Поскольку в левой и в правой частях есть цифра 5, оба основания больше 5, то есть перебор имеет смысл начинать с

Для каждого x вычисляем значение и решаем уравнение , причем нас интересуют только натуральные

Для и нужных решений нет, а для получаем так что

Ответ:

Задача №16. Поиск основания системы по окончанию числа, уравнения и различные кодировки, арифметические действия в различных системах.

Перед тем, как приступить к решению задач, нам нужно понять несколько несложных моментов.

Рассмотрим десятичное число 875. Последняя цифра числа (5) – это остаток от деления числа 875 на 10. Последние две цифры образуют число 75 – это остаток от деления числа 875 на 100. Аналогичные утверждения справедливы для любой системы счисления:

Последняя цифра числа – это остаток от деления этого числа на основание системы счисления.

Последние две цифры числа – это остаток от деления числа на основание системы счисления в квадрате.

Например, . Разделим 23 на основание системы 3, получим 7 и 2 в остатке (2 – это последняя цифра числа в троичной системе). Разделим 23 на 9 (основание в квадрате), получим 18 и 5 в остатке (5 = ).

Вернемся опять к привычной десятичной системе. Число = 100000. Т.е. 10 в степени k– это единица и k нулей.

Аналогичное утверждение справедливо для любой системы счисления:

Основание системы счисления в степени k в этой системе счисления записывается как единица и k нулей.

1. Поиск основания системы счисления

Пример 1.

В системе счисления с некоторым основанием десятичное число 27 записывается в виде 30. Укажите это основание.

Решение:

Обозначим искомое основание x. Тогда .Т.е. x = 9.

Пример 2.

В системе счисления с некоторым основанием десятичное число 13 записывается в виде 111. Укажите это основание.

Решение:

Обозначим искомое основание x. Тогда

Решаем квадратное уравнение, получаем корни 3 и -4. Поскольку основание системы счисления не может быть отрицательным, ответ 3.

Ответ: 3

Пример 3

Укажите через запятую в порядке возрастания все основания систем счисления, в которых запись числа 29 оканчивается на 5.

Решение:

Если в некоторой системе число 29 оканчивается на 5, то уменьшенное на 5 число (29-5=24) оканчивается на 0. Ранее мы уже говорили, что число оканчивается на 0 в том случае, когда оно без остатка делится на основание системы. Т.е. нам нужно найти все такие числа, которые являются делителями числа 24. Эти числа: 2, 3, 4, 6, 8, 12, 24. Заметим, что в системах счисления с основанием 2, 3, 4 нет числа 5 (а в формулировке задачи число 29 оканчивается на 5), значит остаются системы с основаниями: 6, 8, 12,

Ответ: 6, 8, 12, 24

Пример 4

Укажите через запятую в порядке возрастания все основания систем счисления, в которых запись числа 71 оканчивается на 13.

Если в некоторой системе число оканчивается на 13, то основание этой системы не меньше 4 (иначе там нет цифры 3).

Уменьшенное на 3 число (71-3=68) оканчивается на 10. Т.е. 68 нацело делится на искомое основание системы, а частное от этого при делении на основание системы дает в остатке 0.

Выпишем все целые делители числа 68: 2, 4, 17, 34, 68.

2 не подходит, т.к. основание не меньше 4. Остальные делители проверим:

68:4 = 17; 17:4 = 4 (ост 1) – подходит

68:17 = 4; 4:17 = 0 (ост 4) – не подходит

68:34 = 2; 2:17 = 0 (ост 2) – не подходит

68:68 = 1; 1:68 = 0 (ост 1) – подходит

2. Поиск чисел по условиям

Пример 5

Укажите через запятую в порядке возрастания все десятичные числа, не превосходящие 25, запись которых в системе счисления с основанием четыре оканчивается на 11?

Решение:

Для начала выясним, как выглядит число 25 в системе счисления с основанием 4.

. Т.е. нам нужно найти все числа, не больше , запись которых оканчивается на 11. По правилу последовательного счета в системе с основанием 4,
получаем числа и . Переводим их в десятичную систему счисления:

3. Решение уравнений

Пример 6

Ответ запишите в троичной системе (основание системы счисления в ответе писать не нужно).

Переведем все числа в десятичную систему счисления:

Квадратное уравнение имеет корни -8 и 6. (т.к. основание системы не может быть отрицательным). .

Ответ: 20

4. Подсчет количества единиц (нулей) в двоичной записи значения выражения

Для решения этого типа задач нам нужно вспомнить, как происходит сложение и вычитание «в столбик»:

При сложении происходит поразрядное суммирование записанных друг под другом цифр, начиная с младших разрядов. В случае, если полученная сумма двух цифр больше или равна основанию системы счисления, под суммируемыми цифрами записывается остаток от деления этой суммы на основание системы, а целая часть от деления этой суммы на основание системы прибавляется к сумме следующих разрядов.

При вычитании происходит поразрядное вычитание записанных друг под другом цифр, начиная с младших разрядов. В случае, если первая цифра меньше второй, мы «занимаем» у соседнего (большего) разряда единицу. Занимаемая единица в текущем разряде равна основанию системы счисления. В десятичной системе это 10, в двоичной 2, в троичной 3 и т.д.

Пример 7

Сколько единиц содержится в двоичной записи значения выражения: ?

Представим все числа выражения, как степени двойки:

В двоичной записи двойка в степени n выглядит, как 1 и n нулей. Тогда суммируя и , получим число, содержащее 2 единицы:

Теперь вычтем из получившегося числа 10000. По правилам вычитания занимаем у следующего разряда.

Теперь прибавляем к получившемуся числу 1:

Видим, что у результата 2013+1+1=2015 единиц.

[spoiler title=”источники:”]

http://inf-ege.sdamgia.ru/test?theme=248

http://ege-study.ru/ru/ege/materialy/informatika/zadacha-16-razbor-razlichnyx-tipov-zadach/

[/spoiler]

Это ж всё брутфорс, это ж несерьезно 🙂

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

350214_х = 118924₁₀

Это означает, что

3x⁵ + 5x⁴ + 0x³ + 2x² + 1x + 4 = 118924₁₀

или

3x⁵ + 5x⁴ + 2x² + x – 118920 = 0

Классический многочлен пятой степени. И теперь нужно просто решить полиномиальное уравнение. По основной теореме алгебры у него будет пять комплексных корней, нас, правда, интересует только действительный, хорошо бы положительный, и хорошо бы целый 🙂

Из теоремы Абеля-Руффини известно, что аналитически мы такое уравнение не решим в общем случае, но я бы даже и пробовать не стал: на то придуманы численные методы, которых всяких есть многатыщ — выбрать можно по вкусу, начиная хоть с метода товарища Ньютона. Решаем, и получаем:

x = 8

Хорошо и красиво. Ну можете еще добить преподавателя комплексными корнями, сказав, что это же число записывается точно так же в системе счисления с основанием (-7.07949 – 4.865i) 🙂

Формулировка задания: Запись числа в некоторой системе счисления выглядит так. Найдите основание системы счисления q.

Задание входит в ЕГЭ по информатике для 11 класса под номером 16 (Кодирование чисел. Системы счисления).

Рассмотрим, как решаются подобные задания на примере.