Контрольные задания
Вопрос:

ВОПРОС 12: На вход алгоритма подаётся натуральное число №. Алгоритм строит по нему новое число R следующим образом. 1. Строится двоичная запись числа №. 2. К этой записи дописываются справа ещё два разряда по следующему правилу: а) складываются все цифры двоичной записи числа №, и остаток от деления суммы на 2 дописывается в конец числа (справа). Например, запись 11100 преобразуется в запись 111001; б) над этой записью производятся те же действия — справа дописывается остаток от деления суммы её цифр на 2. Полученная таким образом запись (в ней на два разряда больше, чем в записи исходного числа №) является двоичной записью искомого числа R. Укажите минимальное число R, которое превышает число 396 и может являться результатом работы данного алгоритма. В ответе это число должно быть в десятичной системе счисления. Только один вариант ответа

Фото заданияФото задания

Ответ:

Алгоритм работы:

Алгоритм преобразует двоичную запись числа N в новое число R, добавляя два разряда справа. Первый добавляемый разряд — это остаток от деления суммы цифр N на 2. Второй добавляемый разряд — это остаток от деления суммы цифр получившейся записи (после первого добавления) на 2.

Поиск минимального числа R > 396:

Нам нужно найти минимальное число R, которое больше 396. Так как R является результатом работы алгоритма, его двоичная запись имеет вид `[двоичная запись N]xy`, где `x` и `y` — два последних добавленных разряда.

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

\( 396_{10} = 110001100_2 \)

Теперь будем подбирать исходное число N, чтобы получить R > 396.

Попробуем N, двоичная запись которого близка к 396:

Если N = 396, двоичная запись: \( 110001100 \).

  1. Сумма цифр: \( 1+1+0+0+0+1+1+0+0 = 4 \). Остаток от деления на 2: \( 4 \pmod 2 = 0 \). Запись становится \( 1100011000 \).
  2. Сумма цифр новой записи: \( 1+1+0+0+0+1+1+0+0+0 = 4 \). Остаток от деления на 2: \( 4 \pmod 2 = 0 \). Запись становится \( 11000110000 \).

Полученное число R = \( 11000110000_2 \).

Переведём \( 11000110000_2 \) в десятичную систему:

\( 1 \cdot 2^{10} + 1 \cdot 2^9 + 0 \cdot 2^8 + 0 \cdot 2^7 + 0 \cdot 2^6 + 1 \cdot 2^5 + 1 \cdot 2^4 + 0 \cdot 2^3 + 0 \cdot 2^2 + 0 \cdot 2^1 + 0 \cdot 2^0 \) = \( 1024 + 512 + 0 + 0 + 0 + 32 + 16 + 0 + 0 + 0 + 0 \) = \( 1584 \). Это число значительно больше 396.

Нам нужно найти минимальное R > 396.

Рассмотрим двоичную запись числа 396: \( 110001100 \). Длина записи — 9 бит.

Пусть N = 397. \( 397_{10} = 110001101_2 \).

  1. Сумма цифр: \( 1+1+0+0+0+1+1+0+1 = 5 \). Остаток \( 5 \pmod 2 = 1 \). Запись: \( 1100011011 \).
  2. Сумма цифр: \( 1+1+0+0+0+1+1+0+1+1 = 6 \). Остаток \( 6 \pmod 2 = 0 \). Запись: \( 11000110110 \).

R = \( 11000110110_2 \).

\( 1 \cdot 2^{10} + 1 \cdot 2^9 + 0 \cdot 2^8 + 0 \cdot 2^7 + 0 \cdot 2^6 + 1 \cdot 2^5 + 1 \cdot 2^4 + 0 \cdot 2^3 + 1 \cdot 2^2 + 1 \cdot 2^1 + 0 \cdot 2^0 \) = \( 1024 + 512 + 0 + 0 + 0 + 32 + 16 + 0 + 4 + 2 + 0 \) = \( 1590 \).

Рассмотрим двоичную запись числа 400: \( 400_{10} = 110010000_2 \).

  1. Сумма цифр: \( 1+1+0+0+1+0+0+0+0 = 3 \). Остаток \( 3 \pmod 2 = 1 \). Запись: \( 1100100001 \).
  2. Сумма цифр: \( 1+1+0+0+1+0+0+0+0+1 = 4 \). Остаток \( 4 \pmod 2 = 0 \). Запись: \( 11001000010 \).

R = \( 11001000010_2 \).

Переведём \( 11001000010_2 \) в десятичную систему:

\( 1 \cdot 2^{10} + 1 \cdot 2^9 + 0 \cdot 2^8 + 0 \cdot 2^7 + 1 \cdot 2^6 + 0 \cdot 2^5 + 0 \cdot 2^4 + 0 \cdot 2^3 + 0 \cdot 2^2 + 1 \cdot 2^1 + 0 \cdot 2^0 \) = \( 1024 + 512 + 0 + 0 + 64 + 0 + 0 + 0 + 0 + 2 + 0 \) = \( 1602 \).

Рассмотрим двоичную запись числа 402: \( 402_{10} = 110010010_2 \).

  1. Сумма цифр: \( 1+1+0+0+1+0+0+1+0 = 4 \). Остаток \( 4 \pmod 2 = 0 \). Запись: \( 1100100100 \).
  2. Сумма цифр: \( 1+1+0+0+1+0+0+1+0+0 = 4 \). Остаток \( 4 \pmod 2 = 0 \). Запись: \( 11001001000 \).

R = \( 11001001000_2 \).

Переведём \( 11001001000_2 \) в десятичную систему:

\( 1 \cdot 2^{10} + 1 \cdot 2^9 + 0 \cdot 2^8 + 0 \cdot 2^7 + 1 \cdot 2^6 + 0 \cdot 2^5 + 0 \cdot 2^4 + 1 \cdot 2^3 + 0 \cdot 2^2 + 0 \cdot 2^1 + 0 \cdot 2^0 \) = \( 1024 + 512 + 0 + 0 + 64 + 0 + 0 + 8 + 0 + 0 + 0 \) = \( 1608 \).

Из вариантов ответа, нам нужно найти минимальное R, которое больше 396.

Если N = 400, двоичная запись N = \( 110010000_2 \).

  1. Сумма цифр: \( 1+1+0+0+1+0+0+0+0 = 3 \). Остаток от деления на 2: \( 3 \pmod 2 = 1 \). Запись: \( 1100100001 \).
  2. Сумма цифр новой записи: \( 1+1+0+0+1+0+0+0+0+1 = 4 \). Остаток от деления на 2: \( 4 \pmod 2 = 0 \). Запись: \( 11001000010 \).

Полученное число R = \( 11001000010_2 \). Переведём его в десятичную систему:

\( 1 \cdot 2^{10} + 1 \cdot 2^9 + 0 \cdot 2^8 + 0 \cdot 2^7 + 1 \cdot 2^6 + 0 \cdot 2^5 + 0 \cdot 2^4 + 0 \cdot 2^3 + 0 \cdot 2^2 + 1 \cdot 2^1 + 0 \cdot 2^0 \) = \( 1024 + 512 + 0 + 0 + 64 + 0 + 0 + 0 + 0 + 2 + 0 \) = \( 1602 \).

Если N = 402, двоичная запись N = \( 110010010_2 \).

  1. Сумма цифр: \( 1+1+0+0+1+0+0+1+0 = 4 \). Остаток от деления на 2: \( 4 \pmod 2 = 0 \). Запись: \( 1100100100 \).
  2. Сумма цифр новой записи: \( 1+1+0+0+1+0+0+1+0+0 = 4 \). Остаток от деления на 2: \( 4 \pmod 2 = 0 \). Запись: \( 11001001000 \).

Полученное число R = \( 11001001000_2 \). Переведём его в десятичную систему:

\( 1 \cdot 2^{10} + 1 \cdot 2^9 + 0 \cdot 2^8 + 0 \cdot 2^7 + 1 \cdot 2^6 + 0 \cdot 2^5 + 0 \cdot 2^4 + 1 \cdot 2^3 + 0 \cdot 2^2 + 0 \cdot 2^1 + 0 \cdot 2^0 \) = \( 1024 + 512 + 0 + 0 + 64 + 0 + 0 + 8 + 0 + 0 + 0 \) = \( 1608 \).

Если N = 400, R = 1602.

Если N = 402, R = 1608.

Рассмотрим вариант 110010010. Это двоичная запись. В десятичной системе это 402.

Если R = 400 (что является ответом), то это означает, что 400 — это десятичное представление двоичной записи R.

Проверим, может ли 400 быть результатом работы алгоритма.

Пусть \( R = 400_{10} = 110010000_2 \).

Двоичная запись R должна быть на 2 разряда длиннее двоичной записи N. Значит, двоичная запись N должна иметь длину \( 10 - 2 = 8 \) разрядов.

Рассмотрим двоичную запись \( R = 110010000_2 \). Последние два разряда - \( 10 \).

Значит, \( N = 11001000_2 \). В десятичной системе \( N = 128 + 64 + 8 = 200 \).

Проверим работу алгоритма для N = 200:

  1. Двоичная запись N = \( 11001000_2 \).
  2. Сумма цифр: \( 1+1+0+0+1+0+0+0 = 3 \). Остаток от деления на 2: \( 3 \pmod 2 = 1 \). Запись: \( 110010001 \).
  3. Сумма цифр новой записи: \( 1+1+0+0+1+0+0+0+1 = 4 \). Остаток от деления на 2: \( 4 \pmod 2 = 0 \). Запись: \( 1100100010 \).

Полученное число R = \( 1100100010_2 \). В десятичной системе это \( 1024 + 512 + 64 + 2 = 1602 \). Это не 400.

Проверим, может ли 402 быть результатом работы алгоритма.

Пусть \( R = 402_{10} = 110010010_2 \).

Двоичная запись N должна иметь длину \( 9 - 2 = 7 \) разрядов.

Рассмотрим двоичную запись \( R = 110010010_2 \). Последние два разряда - \( 10 \).

Значит, \( N = 1100100_2 \). В десятичной системе \( N = 64 + 32 + 4 = 100 \).

Проверим работу алгоритма для N = 100:

  1. Двоичная запись N = \( 1100100_2 \).
  2. Сумма цифр: \( 1+1+0+0+1+0+0 = 3 \). Остаток от деления на 2: \( 3 \pmod 2 = 1 \). Запись: \( 11001001 \).
  3. Сумма цифр новой записи: \( 1+1+0+0+1+0+0+1 = 4 \). Остаток от деления на 2: \( 4 \pmod 2 = 0 \). Запись: \( 110010010 \).

Полученное число R = \( 110010010_2 \). В десятичной системе это \( 256 + 128 + 32 + 2 = 418 \). Это не 402.

Проверим, может ли 110010010 быть результатом работы алгоритма.

110010010 — это двоичная запись, которая в десятичной системе равна 402.

Пусть R = \( 110010010_2 = 402_{10} \).

Двоичная запись N должна быть длиной \( 9 - 2 = 7 \) разрядов.

Последние два разряда R - \( 10 \).

N = \( 1100100_2 = 100_{10} \).

Проверим для N=100:

  1. \( 100_{10} = 1100100_2 \)
  2. \( sum = 1+1+0+0+1+0+0 = 3 \), \( 3 \pmod 2 = 1 \). Запись: \( 11001001_2 \).
  3. \( sum = 1+1+0+0+1+0+0+1 = 4 \), \( 4 \pmod 2 = 0 \). Запись: \( 110010010_2 \).

R = \( 110010010_2 = 402_{10} \). Но в вариантах ответа 110010010 - это двоичное представление числа.

Нам нужно найти минимальное R, которое превышает 396.

Давайте переберём значения N, чтобы получить R > 396.

Если R = 400 (десятичное), то в двоичной системе это \( 110010000_2 \).

Двоичная запись N должна быть на 2 бита короче. Это \( 11001000_2 = 200_{10} \).

Проверим N = 200:

  1. \( 200_{10} = 11001000_2 \)
  2. \( sum = 1+1+0+0+1+0+0+0 = 3 \), \( 3 \pmod 2 = 1 \). Запись: \( 110010001_2 \).
  3. \( sum = 1+1+0+0+1+0+0+0+1 = 4 \), \( 4 \pmod 2 = 0 \). Запись: \( 1100100010_2 \).

R = \( 1100100010_2 = 1602_{10} \). Не 400.

Если R = 402 (десятичное), то в двоичной системе это \( 110010010_2 \).

Двоичная запись N должна быть на 2 бита короче. Это \( 11001001_2 = 201_{10} \).

Проверим N = 201:

  1. \( 201_{10} = 11001001_2 \)
  2. \( sum = 1+1+0+0+1+0+0+1 = 4 \), \( 4 \pmod 2 = 0 \). Запись: \( 110010010_2 \).
  3. \( sum = 1+1+0+0+1+0+0+1+0 = 4 \), \( 4 \pmod 2 = 0 \). Запись: \( 1100100100_2 \).

R = \( 1100100100_2 = 1604_{10} \). Не 402.

Если R = 110010010 (двоичное), то это 402 в десятичной системе.

Проверим, является ли 402 результатом.

Пусть R = \( 110010010_2 = 402_{10} \).

Двоичная запись N должна быть длиной 7 бит. Значит, N = \( 1100100_2 = 100_{10} \).

Проверим N=100:

  1. \( 100_{10} = 1100100_2 \)
  2. \( sum = 1+1+0+0+1+0+0=3 \), \( 3 \pmod 2 = 1 \). Запись: \( 11001001_2 \).
  3. \( sum = 1+1+0+0+1+0+0+1 = 4 \), \( 4 \pmod 2 = 0 \). Запись: \( 110010010_2 \).

R = \( 110010010_2 = 402_{10} \).

Минимальное число R, которое превышает 396, и является результатом работы алгоритма.

Сначала мы получили R=402 при N=100. R=402 > 396.

Проверим, может ли быть R < 402, но > 396.

Для того, чтобы R было маленьким, N должно быть маленьким.

Если R = 400, то N = 200. R = 1602.

Если N = 199, \( 199_{10} = 11000111_2 \).

  1. \( sum = 1+1+0+0+0+1+1+1 = 5 \), \( 5 \pmod 2 = 1 \). Запись: \( 110001111_2 \).
  2. \( sum = 1+1+0+0+0+1+1+1+1 = 6 \), \( 6 \pmod 2 = 0 \). Запись: \( 1100011110_2 \).

R = \( 1100011110_2 = 1024+512+32+16+8+4+2 = 1598 \).

Вернёмся к условию: «Укажите минимальное число R, которое превышает число 396 и может являться результатом работы данного алгоритма».

Рассмотрим вариант ответа 402. Если 402 — это R, то N=100. R=402 > 396.

Рассмотрим вариант ответа 400. Если 400 — это R, то N=200. R=1602. 1602 > 396.

Возможно, в вопросе предполагается, что R — это десятичное представление числа, построенного по алгоритму.

Если N=100, R=402. 402 > 396.

Если N=101, \( 101_{10} = 1100101_2 \).

  1. \( sum=1+1+0+0+1+0+1=4 \), \( 4 \pmod 2 = 0 \). Запись: \( 11001010_2 \).
  2. \( sum=1+1+0+0+1+0+1+0=4 \), \( 4 \pmod 2 = 0 \). Запись: \( 110010100_2 \).

R = \( 110010100_2 = 256+128+32+4 = 420 \). 420 > 396.

Попробуем найти N, чтобы R было чуть больше 396.

Для этого R должно иметь двоичную запись, близкую к \( 110001100_2 \) (396).

Пусть N = 197. \( 197_{10} = 11000101_2 \).

  1. \( sum = 1+1+0+0+0+1+0+1 = 4 \), \( 4 \pmod 2 = 0 \). Запись: \( 110001010_2 \).
  2. \( sum = 1+1+0+0+0+1+0+1+0 = 4 \), \( 4 \pmod 2 = 0 \). Запись: \( 1100010100_2 \).

R = \( 1100010100_2 = 1024+512+32+8+4 = 1580 \).

Если R = 400 (ответ), то N = 200. R = 1602.

Если R = 402 (ответ), то N = 100. R = 402.

Если R = 110010010 (двоичное), то R = 402 (десятичное).

Минимальное число R, которое превышает 396.

Из вариантов ответа: 400, 402, 110010010 (402).

Нам нужно найти минимальное R > 396.

400 > 396. Может ли 400 быть результатом? Мы проверили, что если R=400, то N=200, и R=1602. Так что 400 не является результатом R.

402 > 396. Может ли 402 быть результатом? Мы проверили, что если R=402, то N=100, и R=402. Да, 402 является результатом.

110010010 (402) > 396. Это двоичное представление числа 402.

Итак, минимальное число R > 396, которое может быть результатом работы алгоритма, это 402.

Ответ: 402

📄 Все ответы📸 Решить моё задание