Позиционные системы счисления

• Название: Позиционные системы счисления
• Дата: 18.04.2022
• Размер: 0.83 Mb.
• Имя файла: ege14 3.doc
• Тип: Документы; #483521
• страница: 11 из 14

Еще пример задания:

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

Общий подход:

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

2 1 0 ← разряды

31 = k 1 1_N = k·N² + N¹ + N⁰ = k·N² + N + 1

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

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

31 = k₄ k₃ k₂ 1 1_N = k₄·N⁴ + k₃·N³ + k₂·N² + N¹ + N⁰

= k·N² + N + 1

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

Решение:

1. 
   итак, нужно найти все целые числа , такие что
   

(**)

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

2. 
   сложность в том, что и , и неизвестны, однако здесь нужно «играть» на том, что это натуральные числа
   
3. 
   из формулы (**) получаем , так что задача сводится к тому, чтобы найти все делители числа 30 и отобрать только те из них, для которых уравнение (**) разрешимо при целом , то есть, – целое число
   
4. 
   выпишем все делители числа 30, большие или равные 2: 2, 3, 5, 6, 10, 15, 30
   
5. 
   из всех этих делителей только для 2, 3, 5 и 30 значение – целое число (оно равно соответственно 7, 3, 1 и 0)
   
6. 
   таким образом, верный ответ – 2, 3, 5, 30.
   

Решение (программа на Python, А.Н. Носкин):

1. 
   можно решить задачу с помощью программы:
   

for i in range(3,50):# перебираем возможные основания

x = 23 # число по условию

x_N = ''

while x > 0:# перевод в N-ю систему

if x%i>9:break # пропускаем цифры в виде букв

else: x_N += str(x%i)

x //= i

x_N = x_N[::-1]# разворот числа

if x_N == '': pass

elif x_N[-1]== "2":

print(i, end=",")

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

Решение (программа на Python, Б.С. Михлин):

5. 
   полная программа:
   

for x in range(2, 101): # x - основание

# справа число 11 переведено в 10-ую систему

if 31 % x*x == x + 1:

print( x, end = ',' )

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

Еще пример задания:

Р-8. Укажите, сколько всего раз встречается цифра 2 в записи чисел 10, 11, 12, …, 17 в системе счисления с основанием 5.

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

1. 
   запишем первое и последнее число в заданном диапазоне в системе счисления с основанием 5:
   

10 = 20₅, 17 = 32₅ .

2. 
   заметим, что оба они содержат цифру 2, так что, 2 цифры мы уже нашли
   
3. 
   между 20₅ и 32₅ есть еще числа
   

21₅, 22₅, 23₅, 24₅, 30₅, 31₅.

4. 
   в них 5 цифр 2 (в числе 22₅ – сразу две двойки), поэтому всего цифра 2 встречается 7 раз
   
5. 
   таким образом, верный ответ – 7.
   

Возможные ловушки и проблемы: нужно не забыть, что в системе счисления с основанием 5 старшая цифра – 4, то есть, вслед за 245 следует 305 помните, что нужно определить не количество чисел, в которых есть двойка, а количество самих двоек можно не обратить внимание на то, что в числе 225 цифра 2 встречается 2 раза

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

1. 
   переведем все указанные числа в систему счисления с основанием 5:
   

10 = 20₅, 11 = 21₅, 12 = 22₅, 13 = 23₅, 14 = 24₅, 15 = 30₅, 16 = 31₅, 17 = 32₅ .

2. 
   считаем цифры 2 – получается 7 штук
   
3. 
   таким образом, верный ответ – 7 .
   

Решение (программа на Python, А.Н. Носкин):

1. 
   можно решить задачу с помощью программы:
   

k = 0

for i in range(10,17+1):

x = i

x5 = ''

while x > 0:# перевод в 5-ю систему

x5 += str(x%5)

x //= 5

x5 = x5[::-1]# разворот числа

k += x5.count("2")

print(k)

2. 
   ответ: 7.
   

Решение (программа на Python, Б.С. Михлин):

1. 
   ещё одна программа:
   

k = 0 # счетчик цифр 2

for x in range(10,17+1):

xw = x # xw - рабочая (work) копия x

while xw:

if xw % 5 == 2: # считаем цифры 2 в 5-ой системе

k += 1

xw //= 5

print( k )

2. 
   ответ: 7.
   

Еще пример задания:

Р-7. Укажите наименьшее основание системы счисления, в которой запись числа 30 трехзначна.

Решение:

1. 
   обозначим через неизвестное основание системы счисления, тогда запись числа 30 в этой системе имеет вид
   

2. 
   вспомним алгоритм перевода числа из системы счисления с основанием в десятичную систему: расставляем сверху номера разрядов и умножаем каждую цифру на основание в степени, равной разряду:
   

3. 
   поскольку запись трехзначная, , поэтому
   
4. 
   с другой стороны, четвертой цифры нет, то есть, в третьем разряде – ноль, поэтому
   
5. 
   объединяя последние два условия, получаем, что искомое основание удовлетворяет двойному неравенству
   

6. 
   учитывая, что – целое число, методом подбора находим целые решения этого неравенства; их два – 4 и 5:
   

7. 
   минимальное из этих значений – 4
   
8. 
   таким образом, верный ответ – 4 .
   

Решение (без подбора):

1. 
   выполним п.1-4 так же, как и в предыдущем варианте решения
   
2. 
   найдем первое целое число, куб которого больше 30; это 4, так как
   

3. 
   проверяем второе неравенство: , поэтому в системе счисления с основанием 4 запись числа 30 трехзначна
   
4. 
   таким образом, верный ответ – 4 .
   

Решение (программа на Python, А.Н. Носкин):

1. 
   можно решить задачу с помощью программы:
   

for i in range(2,100):# перебираем возможные основания

x = 30 # число по условию

x_N = ''

while x > 0:# перевод в N-ю систему

x_N += str(x%i)

x //= i

x_N = x_N[::-1]# разворот числа

if len(x_N)== 3:

print(i)

break

2. 
   ответ: 4.
   

Решение (программа на Python, Б.С. Михлин):

7. 
   полная программа:
   

for N in range(2, 10): # проверять основание N >=10 нет смысла

# (будет два или один разряд)

if N ** 2 <= 30 < N ** 3: # проверка на трёхзначность

print(N)

break

8. 
   Ответ: 4.
   

Еще пример задания:

Р-6. Укажите через запятую в порядке возрастания все десятичные числа, не превосходящие 30, запись которых в системе счисления с основанием 5 начинается на 3?

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

1. 
   нас интересуют числа от 1 до 30
   
2. 
   сначала определим, сколько цифр может быть в этих числах, записанных в системе счисления с основанием 5
   
3. 
   поскольку , в интересующих нас числах может быть от 1 до 3 цифр
   
4. 
   рассмотрим трехзначные числа, начинающиеся на 3 в системе с основанием 5:
   

все они заведомо не меньше , поэтому в наш диапазон не попадают;

5. 
   таким образом, остается рассмотреть только однозначные и двухзначные числа
   
6. 
   есть всего одно однозначное число, начинающееся на 3, это 3
   
7. 
   общий вид всех двузначных чисел, начинающихся на 3 в системе с основанием 5:
   

где – целое число из множества {0, 1, 2,3,4} (поскольку система счисления имеет основание 5 и цифр, больших 4, в записи числа быть не может)

8. 
   используя эту формулу, находим интересующие нас двузначные числа – 15, 16, 17, 18 и 19
   
9. 
   таким образом, верный ответ – 3, 15, 16, 17, 18, 19 .
   

Решение (вариант 2, предложен Сенькиной Т.С., г. Комсомольск-на-Амуре ):

1. 
   нас интересуют числа от 1 до 30; сначала определим, сколько цифр может быть в пятеричной записи эти чисел
   
2. 
   поскольку , в интересующих нас числах может быть не более 2 цифр (все трехзначные пятеричные числа, начинающиеся с 3, больше 30)
   
3. 
   есть всего одно однозначное число, начинающееся на 3, это 3
   
4. 
   выпишем все пятеричные двузначные числа, которые начинаются с 3, и переведем их в десятичную систему: 30₅ = 15, 31₅ = 16, 32₅ = 17, 33₅ = 18 и 34₅ = 19
   
5. 
   таким образом, верный ответ – 3, 15, 16, 17, 18, 19 .
   

Решение (программа на Python, А.Н. Носкин):

1. 
   можно решить задачу с помощью программы:
   

for i in range(1,31):# перебираем ответы

x = i

x5 = ''

while x > 0:# перевод в 5-ю систему

x5 += str(x%5)

x //= 5

x5 = x5[::-1]# разворот числа

if x5[0]== "3":

print(i, end=",")

2. 
   ответ: 3, 15, 16, 17, 18, 19.
   

Еще пример задания:

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

Решение (1 способ):

1. 
   Если число в системе с основанием оканчивается на 13, то
   
   1. 
      , потому что в системах с меньшим основанием нет цифры 3
      
   2. 
      это число можно представить в виде , где – целое неотрицательное число
      
2. 
   определим наибольшее возможное с учетом условия . Из уравнения следует .
   
3. 
   очевидно, что чем меньше , тем больше , поэтому значение не превышает
   

здесь мы подставили – наименьшее допустимое значение

4. 
   остается перебрать все допустимые значения (от 0 до ), решая для каждого из них уравнение
   

или равносильное

относительно , причем нас интересуют только натуральные числа

5. 
   получаем
   
   1. 
      при :
      
   2. 
      при : решения – не целые числа
      
   3. 
      при : и , второе решение не подходит
      
6. 
   таким образом, верный ответ: 4, 68.
   

Решение (2 способ, М.В. Кузнецова и её ученики):

1. 
   запись числа71 в системе с основанием оканчивается на 13, т.е. в разряде единиц – 3, это значит, что остаток от деления 71 на равен 3, то есть для некоторого целого имеем
   

2. 
   таким образом, искомые основания – делители числа 68; остается выбрать из них те, которые соответствуют другим условиям задачи
   
3. 
   среди чисел, оканчивающихся на 13 в системе счисления с основанием ,минимальное – это само число ; отсюда найдем максимальное основание:
   

так что первый ответ: 68.

4. 
   остальные числа, окачивающиеся в этой системе на 13, имеют не менее 3-х знаков ( , …), т.е. все они больше
   
5. 
   поэтому , следовательно,
   
6. 
   по условию в записи числа есть цифра 3, поэтому (в системах с основанием  3 цифры 3 нет)
   
7. 
   итак: , и при этом – делитель 68; единственное возможное значение (на 5,6,7 и 8 число 68 не делится)
   
8. 
   таким образом, верный ответ: 4, 68.
   

Возможные ловушки и проблемы: на шаге 1 нужно вычесть из числа только число единиц, то есть младшую из двух заданных цифр (в примере – 3) можно забыть рассмотреть двузначное число, записанное заданными в условии цифрами (в примере – 13x ), и пропустить максимальное основание нужно помнить, что максимальная цифра на 1 меньше основания системы счисления 100 в системе с основанием p равно p2

Решение (программа на Python, А.Н. Носкин):

1. 
   можно решить задачу с помощью программы:
   

for i in range(4,100):# перебираем возможные основания

x = 71 # число по условию

x_N = ''

while x > 0:# перевод в N-ю систему

if x%i>9:break # пропускаем цифры в виде букв

else: x_N += str(x%i)

x //= i

x_N = x_N[::-1]# разворот числа

if x_N[-2:]== "13":

print(i, end=",")

2. 
   ответ: 4, 68.
   

Решение (программа на Python, Б.С. Михлин):

1. 
   полная программа:
   

for x in range(4, 72): # x - основание от 4 до 71

# (дальше перебирать нет смысла)

# справа число 13 переведено в 10-ую систему

if 71 % (x*x) == x + 3:

print( x, end = ',' )

2. 
   Ответ: 4, 68.
   

Еще пример задания:

Р-04. Укажите через запятую в порядке возрастания все основания систем счисления, в которых запись числа 86 оканчивается на 22.

Решение (1 способ):

1. 
   Если число в системе с основанием оканчивается на 22, то
   
   1. 
      , потому что в системах с меньшим основанием нет цифры 2
      
   2. 
      это число можно представить в виде , где – целое неотрицательное число
      
2. 
   определим наибольшее возможное с учетом условия . Из уравнения следует .
   
3. 
   очевидно, что чем меньше , тем больше , поэтому значение не превышает
   

здесь мы подставили – наименьшее допустимое значение

4. 
   остается перебрать все допустимые значения (от 0 до ), решая для каждого из них уравнение
   

или равносильное

относительно , причем нас интересуют только натуральные числа

5. 
   получаем
   
   1. 
      при :
      
   2. 
      при : решения – не целые числа
      
   3. 
      при : и , второе решение не подходит
      
   4. 
      при : решения – не целые числа
      
6. 
   таким образом, верный ответ: 6, 42.
   

Решение (2 способ, М.В. Кузнецова и её ученики):

1. 
   запись числа 86 в системе с основанием оканчивается на 22, т.е. в разряде единиц – 2, это значит, что остаток от деления 86 на равен 2, то есть для некоторого целого имеем
   

2. 
   таким образом, искомые основания – делители числа 84; остается выбрать из них те, которые соответствуют другим условиям задачи
   
3. 
   среди чисел, оканчивающихся на 22 в системе счисления с основанием ,минимальное – это само число ; отсюда найдем максимальное основание:
   

так что первый ответ: 42.

4. 
   остальные числа, окачивающиеся в этой системе на 22, имеют не менее 3-х знаков ( , …), т.е. все они больше
   
5. 
   поэтому , следовательно,
   
6. 
   по условию в записи числа есть цифра 2, поэтому
   
7. 
   итак: , и при этом – делитель 84; возможные значения (на 5,8 и 9 число 84 не делится)
   
8. 
   переводя число 86 в системы счисления с основаниями , находим, что только для основания 6 запись числа оканчивается на 22 (при делении на 3, 4 и 7 «вторые» остатки не равны 2):
   

   8	6		3				Дальше делить нет смысла	8	6		4							8	6		6					8	6		7
   8	4		2	8		3		8	4		2	1			4			8	4		1	4		6		8	4		1	2		7
   	2		2	7		9…			2		2	0			5…				2		1	2		2			2			7		1
   				1								1										2								5

9. 
   таким образом, верный ответ: 6, 42.
   

Решение (программа на Python, А.Н. Носкин):

1. 
   можно решить задачу с помощью программы:
   

for i in range(3,100):# перебираем возможные основания

x = 86 # число по условию

x_N = ''

while x > 0:# перевод в N-ю систему

if x%i>9:break # пропускаем цифры в виде букв

else: x_N += str(x%i)

x //= i

x_N = x_N[::-1]# разворот числа

if x_N[-2:]== "22":

print(i, end=",")

2. 
   ответ: 6, 42.
   

Решение (программа на Python, Б.С. Михлин):

9. 
   полная программа:
   

for x in range(3, 86): # x - основание от 3 до 85

# (дальше перебирать нет смысла)

# справа число 22 переведено в 10-ую систему

if 86 % (x * x) == 2 * x + 2:

print( x, end = ',' )

10. 
    Ответ: 6, 42.
    

Еще пример задания:

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

Решение:

1. 
   Из условия сразу видно, что искомое основание не меньше 4 (в записи есть цифра 3).
   
2. 
   Если запись числа 94 в некоторой системе счисления с основанием двузначна (94 = 23_x), то справедливо равенство ; нас интересуют натуральные решения этого уравнения, такие что , таких решений нет.
   
3. 
   Предположим, что число четырехзначное. Минимальное допустимое четырехзначное число – 2300_x, где . При минимальном основании ( ) оно равно , поэтому запись нужного нам числа имеет не больше трех знаков.
   
4. 
   На основании (2) и (3) делаем вывод, что число трехзначное, то есть , где – целое неотрицательное число, такое что .
   
5. 
   Максимальное можно определить как решение уравнения (при ); получаем одно из решений – 6,15; поэтому
   
6. 
   Если мы знаем , то определится как ; пробуем подставлять в эту формулу , пытаясь получить
   
7. 
   Минимальное будет при : , а при получается
   
8. 
   Таким образом, верный ответ: 6.
   

Решение (программа на Python, А.Н. Носкин):

1. 
   можно решить задачу с помощью программы:
   

for i in range(4,100):# перебираем возможные основания

x = 94 # число по условию

x_N = ''

while x > 0:# перевод в N-ю систему

x_N += str(x%i)

x //= i

x_N = x_N[::-1]# разворот числа

if x_N[:2]== "23":

print(i, end=",")

2. 
   ответ: 6.
   

Еще пример задания:

Р-2. Найти сумму восьмеричных чисел 17₈ +170₈ +1700₈ +...+1700000₈, перевести в 16-ую систему счисления. Найдите в записи числа, равного этой сумме, третью цифру слева.

Решение:

1. 
   Несложно выполнить прямое сложение восьмеричных чисел, там быстро обнаруживается закономерность:
   

17₈ + 170₈ = 207₈

17₈ + 170₈ + 1700₈ = 2107₈

17₈ + 170₈ + 1700₈ + 17000₈ = 21107₈

17₈ + 170₈ + 1700₈ + 17000₈ + 170000₈ = 211107₈

17₈ + 170₈ + 1700₈ + 17000₈ + 170000₈ + 1700000₈ = 2111107₈

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

10001001001001000111₂

3. 
   Теперь разбиваем цепочку на тетрады (группы из 4-х двоичных цифр), начиная справа, и каждую тетраду представляем в виде шестнадцатеричной цифры
   

10001001001001000111₂

8 9 2 4 7

4. 
   Таким образом, верный ответ (третья цифра слева): 2.
   

Решение (программа на Python, А.Н. Носкин):

1. 
   решение задачи с помощью программы:
   

a = "17"

b = "1700000"

summa = 0

while a <= b:

  summa += int(a,8) # перевод в 10ю систему

  a += "0" # добавляем 0 к числу-строке

n16 = hex(summa)[2:] # перевод суммы в 16ю систему

print(n16[2])

2. 
   Ответ: 2.
   

Решение (программа на Python, Б.С. Михлин):

1. 
   полная программа:
   

x = 15 # 17 в 8-ой системе

s = x # s - сумма в 10-ой системе

for z in range( 1, 6 ): # z (zero) - количество нулей от 1 до 5

x *= 8 # добавление справа нуля к восьмеричному числу

# увеличивает его в 8 раз

s += x

print( hex( s )[4] ) # с учетом префикса '0x' третий символ

# (цифра) будет пятым с индексом 4

# print( hex( s ) ) # можно также найти третью цифру слева

2. 
   Ответ: 2.
   

Еще пример задания:

Р-01. Чему равно наименьшее основание позиционной системы счисления , при котором 225_x = 405_y? Ответ записать в виде целого числа.

Решение:

1. 
   Поскольку в левой и в правой частях есть цифра 5, оба основания больше 5, то есть перебор имеет смысл начинать с .
   
2. 
   Очевидно, что , однако это не очень нам поможет.
   
3. 
   Для каждого «подозреваемого» вычисляем значение и решаем уравнение , причем нас интересуют только натуральные .
   
4. 
   Для и нужных решений нет, а для получаем
   

так что .

5. 
   Таким образом, верный ответ (минимальное значение ): 8.
   

Решение (программа на Python, А.Н. Носкин):

1. 
   можно решить задачу перебором с помощью программы (перебор начинаем с 6, так как цифра 5 есть в записи 225_x, так и в записи 405_y):
   

for x in range(6,20):# перебираем основания X

for y in range(6,20):# перебираем основания Y

if (2*x**2+2*x+5) == (4*y**2+0*y+5):

print(x)

break

2. 
   ответ: 8.
   

Еще пример задания:

Р-00. Запись числа 30₁₀ в системе счисления с основанием N оканчивается на 0 и содержит 4 цифры. Чему равно основание этой системы счисления N?

Решение (1 способ, подбор):

1. 
   запись числа 30 в системе с основанием N длиннее, чем в десятичной (4 цифры против двух), поэтому основание N меньше 10
   
2. 
   это дает шанс решить задачу методом подбора, переводя в разные системы, начиная с N = 2 до N = 9
   
3. 
   переводим:
   

30 = 11110₂ = 1010₃ = …

4. 
   дальше можно не переводить, поскольку запись 1010₃ удовлетворяет условию: заканчивается на 0 и содержит 4 цифры
   
5. 
   можно проверить, что при N ≥ 4 запись числа 30 содержит меньше 4 цифр, то есть не удовлетворяет условию
   
6. 
   Ответ: 3.
   

Решение (2 способ, неравенства):

1. 
   запись числа 30 в системе с основанием N содержит ровно 4 цифры тогда и только тогда, когда старший разряд – третий, то есть
   

2. 
   первая часть двойного неравенства дает (в целых числах)
   
3. 
   вторая часть неравенства дает (в целых числах)
   
4. 
   объединяя результаты пп. 2 и 3 получаем, что N = 3
   
5. 
   заметим, что условие «оканчивается на 0» – лишнее, ответ однозначно определяется по количеству цифр
   
6. 
   Ответ: 3.
   

Решение (программа на Python, А.Н. Носкин):

1. 
   можно решить задачу перебором с помощью программы:
   

for i in range(2,36):# перебираем возможные основания

x = 30 # число по условию

x_N = ''

while x > 0:# перевод в N-ю систему

x_N += str(x%i)

x //= i

x_N = x_N[::-1]# разворот числа

if x_N[-1]== "0" and len(x_N) == 4:

print(i)

break

2. 
   Ответ: 3.
   

Решение (программа на Python, Б.С. Михлин):

1. 
   полная программа:
   

for N in range(2, 10): # проверять основание N >=10 нет смысла

# (будет два или один разряд)

# проверка на четырёхзначность (в этой задаче проверка

# окончания на ноль не обязательна)

if N**3 <= 30 < N**4 and 30 % N == 0:

print(N)

2. 
   Ответ: 3.