Задание 5

В этом задании нужно просто реализовать тот или иной несложный алгоритм, описанный словами.

Пример 1

Задача

На вход алгоритма подаётся натуральное число N. Алгоритм строит по нему новое число R следующим образом.

1. Строится двоичная запись числа N.

2. К этой записи дописываются справа ещё два разряда по следующему правилу:

   а) складываются все цифры двоичной записи числа N, и остаток от деления суммы на 2 дописывается в конец числа (справа). Например, запись 11100 преобразуется в запись 111001;

   б) над этой записью производятся те же действия – справа дописывается остаток от деления суммы её цифр на 2.

Полученная таким образом запись (в ней на два разряда больше, чем в записи исходного числа N) является двоичной записью искомого числа R. Укажите такое наименьшее число N, для которого результат работы данного алгоритма больше числа 77. В ответе это число запишите в десятичной системе счисления.

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

Число после пункта a) гарантированно будет иметь чётное число единиц. Тогда в пункте б) всегда будет прибавляться ноль.

Это означает, что нам нужно найти первое число, которое будет:

1. больше 77
2. иметь чётное число единиц
3. иметь 0 в младшем разряде

Проще всего перевести исходное число в двоичную систему в калькуляторе Windows и после этого просто прибавлять по единице, сверяясь требованиями к числу.

Чтобы прибавить к числу единицу, нажмите на +

Потом на 1

Теперь на =

В новом числе чётное число единиц и последний 0

Оно удовлетворяет всем требованиям, значит мы нашли ответ.

Ответ: 78

Если бы это число не подошло, следовало бы просто прибавить ещё единицу, проверить число, если не подошло, то снова прибавить и т.д.

Пример 2

Задача

Автомат обрабатывает натуральное число N по следующему алгоритму:

1. Строится двоичная запись числа N.
2. Удаляются первая слева единица и все следующие непосредственно за ней нули. Если после этого в числе не остаётся цифр, результат этого действия считается равным нулю.
3. Полученное число переводится в десятичную запись.
4. Новое число вычитается из исходного, полученная разность выводится на экран.

Пример: дано число N = 11. Алгоритм работает следующим образом:

1. Двоичная запись числа N: 1011.
2. Удаляется первая единица и следующий за ней ноль: 11.
3. Десятичное значение полученного числа 3.
4. На экран выводится число 11 – 3 = 8.

Сколько разных значений будет показано на экране автомата при последовательном вводе всех натуральных чисел от 500 до 5000?

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

Поэтому достаточно просто взять подстроку от той, что получена из перебираемого значения и просто перевести обратно в число.

Java

public class Example3 {
    public static void main(String[] args) {
        // перебираем значения
        for (int i = 500; i <= 5000; i++) {
            // создаём строку с двоичным представлением перебираемого значения
            String s = Integer.toString(i,2);
            // обрезаем строку
            s = s.substring(1);
            // переводим обрезанную строку обратно в число, второй
            // аргумент указывает, в какой системе счисления записано число
            int r = Integer.parseInt(s, 2);
            // выводим разность
            System.out.println(i - r);
        }
    }
}

C++

#include <iostream>
#include <cstdlib>

// главный метод программы
int main() {
    // перебираем значения
    for (int i = 500; i <= 5000; i++) {
        // создаём строку с двоичным представлением перебираемого значения
        char p[17];
        // отправляем в буфер p строковое представление числа с заданным основанием
        itoa(i, p, 2);
        // создаём строку на основе буффера
        std::string s(p);
        // обрезаем строку
        s = s.substr(1, s.length() - 1);
        // переводим обрезанную строку обратно в число, второй
        // аргумент указывает, в какой системе счисления записано число
        int r = std::stoi(s, nullptr, 2);
        // выводим разность
        std::cout << i - r << std::endl;
    }
}

Python

# преобразование в строку с произвольным основанием
def number_to_base(n, b):
    base36 = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ"
    # если полученное число 0
    if n == 0:
        # сразу возвращаем строку "0"
        return "0"
    # строка - результат
    s = ""
    # пока число больше нуля
    while n:
        # получаем остаток от деления числа на основание
        r = n % b
        # добавляем в строку символ, соответствующий остатку
        s = s + base36[r]
        # делим нацело число на основание
        n //= b
    # возвращаем результат
    return s[::-1]

# перебираем значения от 500 до 5000, чтобы 5000 тоже было проверено,
# в качестве верхней границы я указал следующее за ним число
for i in range(500, 5001):
    # переводим строку в двоичную систему счисления
    s = number_to_base(i, 2)
    # обрезаем строку
    s = s[1:]
    # переводим обрезанную строку обратно в число, второй
    # аргумент указывает, в какой системе счисления записано число
    r = int(s, 2)
    # выводим разность
    print(i - r)

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

Их будет пять:

256
512
1024
2048
4096

В Java, чтобы перевести число в строку, используется метод Integer.toString(). Можно просто передать в него число:

    String s = Integer.toString(4351);

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

В С++ преобразование строки к числу выполняется с помощью метода std::stoi(). Первый аргумент - это строка, из которой необходимо получить число, второй должен быть nullptr, третий - основание системы счисления.

Чтобы преобразовать число в строку, используется метод itoa(), правда, он заполняет символами массив, переданный в качестве аргументов, поэтому необходимо сначала создать массив(буфер), потом записать в него строковое представление числа в заданном основании, после чего создать строку на его основе.

В Python нет готового метода перевода числа в строку с произвольным основанием, поэтому я дописал метод

# преобразование в строку с произвольным основанием
def number_to_base(n, b):
    base36 = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ"
    # если полученное число 0
    if n == 0:
        # сразу возвращаем строку "0"
        return "0"
    # строка - результат
    s = ""
    # пока число больше нуля
    while n:
        # получаем остаток от деления числа на основание
        r = n % b
        # добавляем в строку символ, соответствующий остатку
        s = s + base36[r]
        # делим нацело число на основание
        n //= b
    # возвращаем результат
    return s[::-1]

Правда, если требуется перевести число в строку с основанием 2, 8 или 16, можно воспользоваться готовым методом, формирующим соответствующую строку.

В таблице приведено сопоставление системы счисления и функций

2	8	16
bin(x)	oct(x)	hex(x)

В нашем случае код python можно переписать таким образом:

# перебираем значения от 500 до 5000, чтобы 5000 тоже было проверено,
# в качестве верхней границы я указал следующее за ним число
for i in range(500, 5001):
    # переводим строку в двоичную систему счисления
    s = bin(i)
    # обрезаем строку
    s = s[1:]
    # переводим обрезанную строку обратно в число, второй
    # аргумент указывает, в какой системе счисления записано число
    r = int(s, 2)
    # выводим разность
    print(i - r)

Оптимизация

Если задача будет более сложной, то найти все уникальные значения можно с помощью множества.

Множества - это особые структуры, которые могут содержать каждый элемент в единичном экземпляре. Причём множество

Java

import java.util.HashSet;

public class Example4 {
    public static void main(String[] args) {
        // множество значений
        HashSet<Integer> values = new HashSet<>();
        // перебираем значения
        for (int i = 500; i <= 5000; i++) {
            // создаём строку с двоичным представлением перебираемого значения
            String s = Integer.toString(i, 2);
            // обрезаем строку
            s = s.substring(1);
            // переводим обрезанную строку обратно в число, второй
            // аргумент указывает, в какой системе счисления записано число
            int r = Integer.parseInt(s, 2);
            // добавляем разность
            values.add(i - r);
        }
        // перебираем все значения множества
        for (Integer value : values) {
            // выводим каждое с новой строки
            System.out.println(value);
        }
    }
}

C++

#include <iostream>
#include <set>

// главный метод программы
int main() {
    // множество значений
    std::set<int> values;
    // перебираем значения
    for (int i = 500; i <= 5000; i++) {
        // создаём строку с двоичным представлением перебираемого значения
        char p[17];
        // отправляем в буфер p строковое представление числа с заданным основанием
        itoa(i, p, 2);
        // создаём строку на основе буффера
        std::string s(p);
        // обрезаем строку
        s = s.substr(1, s.length() - 1);
        // переводим обрезанную строку обратно в число, второй
        // аргумент указывает, в какой системе счисления записано число
        int r = std::stoi(s, nullptr, 2);
        // добавляем разность в множество
        values.insert(i - r);
    }
    // перебираем значения множества
    for (int v: values) {
        // и выводим их
        std::cout << v << std::endl;
    }
}

Python

# множество значений
values = set()

# перебираем значения от 500 до 5000, чтобы 5000 тоже было проверено,
# в качестве верхней границы я указал следующее за ним число
for i in range(500, 5001):
    # переводим строку в двоичную систему счисления
    s = bin(i)
    # обрезаем строку
    s = s[1:]
    # переводим обрезанную строку обратно в число, второй
    # аргумент указывает, в какой системе счисления записано число
    r = int(s, 2)
    # выводим разность
    values.add(r)

# перебираем значения множества
for v in values:
    # и выводим их
    print(v)

Получим:

256
512
1024
2048
4096

В Java множество создаётся с помощью конструкции

    HashSet<Integer> values = new HashSet<>();

Обратите внимание: в угловых скобках нужно писать именно тип данных с большой буквы.

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

Integer	Double	Long	Boolean	Character	Byte	Float
int	double	long	boolean	char	byte	float

Чтобы добавить элемент a=10 в множество s, необходимо вызвать метод s.add().

Чтобы перебрать элементы множества, используется модификация цикла for. Она называется for each - для каждого.

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

В C++ множество создаётся с помощью команды

    std::set<int> values;

В угловых скобках указывается тип элементов множества. Чтобы добавить элемент, используется команда .insert. Перебор выполняется с помощью конструкции for...each.

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

В Python множество создаётся с помощью команды

values = set()

Чтобы добавить элемент, используется команда .add()

Пример 3

Задача

Автомат получает на вход натуральное число X. По этому числу строится трёхзначное число Y по следующим правилам:

1. Первая цифра числа Y (разряд сотен) – остаток от деления X на 2.
2. Вторая цифра числа Y (разряд десятков) – остаток от деления X на 3.
3. Третья цифра числа Y (разряд единиц) – остаток от деления X на 5.

Пример. Исходное число: 55. Остаток от деления на 2 равен 1; остаток от деления на 3 равен 1; остаток от деления на 5 равен 0. Результат работы автомата: 110.

Укажите наименьшее двузначное число, при обработке которого автомат выдаёт результат 104.

обозначим искомое число через N

остаток от деления на 2, равный 1, говорит о том, что число нечётное

таким образом, нужно найти нечётное число, которое делится на 3 и при делении на 5 даёт остаток 4

перебираем нечётные двузначные числа, которые при делении на 5 дают остаток 4 и находим для каждого остаток от деления на 3:

N	19	29	39	...
N mod 3	1	2	0	...

Ответ: 39

Пример 4

Задача

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

Пример. Исходные цифры: 6, 3, 9. Суммы: 6 + 3 = 9; 3 + 9 = 12.

Результат: 129. Укажите, какая из следующих последовательностей символов может быть получена в результате.

1) 1915

2) 1815

3) 188

4) 1518

Эта задача решается примерно так же, как и четвёртая, правда здесь всего три цифры. Вычислим все значения и посмотрим, какие из заданных встретились.

Чтобы решить эту задачу, воспользуемся кодом, переводящим число в массив цифр. Только число мы будем не читать с клавиатуры, а перебирать в цикле

Java

package problem5;

public class Example5 {
    public static void main(String[] args) {
        // перебираем все четырёхзначные числа
        for (int n = 100; n < 1000; n++) {
            // инициализируем переменную цикла
            int i = n;
            // номер читаемого разряда
            int r = 0;
            // пока есть хотя бы одна цифра в числе
            while (i > 0) {
                // увеличиваем номер текущего разряда
                r++;
                // отбрасываем младший разряд числа
                i /= 10;
            }
            // создаём массив цифр по кол-ву разрядов
            int[] d = new int[r];
            // инициализируем переменную цикла
            i = n;
            // номер читаемого разряда
            r = 0;
            // пока есть хотя бы одна цифра в числе
            while (i > 0) {
                // получаем цифру младшего разряда
                d[r] = i % 10;
                // увеличиваем номер текущего разряда
                r++;
                // отбрасываем младший разряд числа
                i /= 10;
            }

            // в массиве цифры расположены по разрядам,
            // поэтому элементы для сумм берутся в обратном порядке
            int s12 = d[2] + d[1];
            int s23 = d[1] + d[0];

            int res;
            // формируем число так, чтобы суммы шли в порядке невозрастания
            if (s23 > s12)
                res = s23 * 100 + s12;
            else
                res = s12 * 100 + s23;

            // если результат равен одному из заданных, выведем его
            if (res == 1915 || res == 1815 || res == 188 || res == 1518)
                // выводим перебираемое число
                System.out.println(res);

        }

    }
}

C++

#include <iostream>

// главный метод программы
int main() {

    // перебираем все четырёхзначные числа
    for (int n = 100; n < 1000; n++) {
        // инициализируем переменную цикла
        int i = n;
        // номер читаемого разряда
        int r = 0;
        // пока есть хотя бы одна цифра в числе
        while (i > 0) {
            // увеличиваем номер текущего разряда
            r++;
            // отбрасываем младший разряд числа
            i /= 10;
        }

        // сохраняем кол-во разрядов
        int cnt = r;
        // создаём массив цифр по кол-ву разрядов
        int d[cnt];
        // инициализируем переменную цикла
        i = n;
        // номер читаемого разряда
        r = 0;
        // пока есть хотя бы одна цифра в числе
        while (i > 0) {
            // получаем цифру младшего разряда
            d[r] = i % 10;
            // увеличиваем номер текущего разряда
            r++;
            // отбрасываем младший разряд числа
            i /= 10;
        }

        // в массиве цифры расположены по разрядам,
        // поэтому элементы для сумм берутся в обратном порядке
        int s12 = d[2] + d[1];
        int s23 = d[1] + d[0];

        int res;
        // формируем число так, чтобы суммы шли в порядке невозрастания
        if (s23 > s12)
            res = s23 * 100 + s12;
        else
            res = s12 * 100 + s23;

        // если результат равен одному из заданных, выведем его
        if (res == 1915 || res == 1815 || res == 188 || res == 1518)
            // перехожим на новую строку
            std::cout << res << std::endl;
    }

    return 0;
}

Python

# перебираем все четырёхзначные числа
for n in range(100, 1000):
    # номер читаемого разряда
    r = 0
    # создаём список цифр
    d = list()
    i = n
    # пока есть хотя бы одна цифра в числе
    while i > 0:
        d.append(i % 10)
        # увеличиваем номер текущего разряда
        r = r + 1
        # отбрасываем младший разряд числа
        i = i // 10

    # в массиве цифры расположены по разрядам,
    # поэтому элементы для сумм берутся в обратном порядке
    s12 = d[2] + d[1]
    s23 = d[1] + d[0]

    # формируем число так, чтобы суммы шли в порядке неубывания
    if s23 < s12:
        res = s23 * 100 + s12
    else:
        res = s12 * 100 + s23

    # если результат равен 511
    if res == 1915 or res == 1815 or res == 188 or res == 1518:
        # перехожим на новую строку
        print(res)

Программы выведет список всех подходящих чисел:

1815
1815

Нам останется только найти среди них самое маленькое и самое большое.

Ответ: 2

Пример 5

Задача

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

Например, к слову 110011 справа будет добавлен 0, а к слову 101100 – 1. После приёма слова производится его обработка. При этом проверяется сумма его разрядов, включая контрольный. Если она нечётна, это означает, что при передаче этого слова произошёл сбой, и оно автоматически заменяется на зарезервированное слово 0000000. Если она чётна, это означает, что сбоя не было или сбоев было больше одного. В этом случае принятое слово не изменяется.

Исходное сообщение

$1100101~1001011~0011000$

было принято в виде

$1100111~1001110~0011000$

Как будет выглядеть принятое сообщение после обработки?

1) $1100111~1001011~0011000$

2) $1100111~1001110~0000000$

3) $0000000~0000000~0011000$

4) $0000000~1001110~0011000$

По условию в правильно принятом блоке число единиц должно быть чётное.

В принятом сообщении $1100111~1001110~0011000$ нечётное число единиц (5) только в первом блоке, поэтому он будет заменён на нули

Ответ: 4

Обратите внимание

не нужно сравнивать полученное сообщение с исходным; если при передаче блока произошло чётное число ошибок, то приёмник не сможет обнаружить ошибку и будет считать этот блок правильным

Пример 6

Задача

Автомат получает на вход четырёхзначное натуральное число и строит новое число по следующему алгоритму:

1) вычисляются суммы первой и второй, второй и третьей и третьей и четвёртой цифр;

2) из полученных сумм отбрасывается наименьшая;

3) остальные записываются в порядке неубывания.

Пример: исходное число: $1284$. Суммы: 1 + 2 = 3; 2 + 8 = 10; 8 + 4 = 12. Отбрасывается наименьшая сумма 3. Результат: 1012. Укажите наименьшее и наибольшее число, при вводе которого автомат выдаёт значение 511.

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

Java

public class Example6 {
    public static void main(String[] args) {
        // перебираем все четырёхзначные числа
        for (int n = 1000; n < 10000; n++) {
            // инициализируем переменную цикла
            int i = n;
            // номер читаемого разряда
            int r = 0;
            // пока есть хотя бы одна цифра в числе
            while (i > 0) {
                // увеличиваем номер текущего разряда
                r++;
                // отбрасываем младший разряд числа
                i /= 10;
            }
            // создаём массив цифр по кол-ву разрядов
            int[] d = new int[r];
            // инициализируем переменную цикла
            i = n;
            // номер читаемого разряда
            r = 0;
            // пока есть хотя бы одна цифра в числе
            while (i > 0) {
                // получаем цифру младшего разряда
                d[r] = i % 10;
                // увеличиваем номер текущего разряда
                r++;
                // отбрасываем младший разряд числа
                i /= 10;
            }

            // в массиве цифры расположены по разрядам,
            // поэтому элементы для сумм берутся в обратном порядке
            int s12 = d[3] + d[2];
            int s23 = d[2] + d[1];
            int s34 = d[1] + d[0];

            // итоговое число
            int res;
            // если сумма первой и второй цифры меньше или равна остальным
            if (s12 <= s23 && s12 <= s34) {
                // формируем число так, чтобы суммы шли в порядке неубывания
                if (s23 < s34)
                    res = s23 * 100 + s34;
                else
                    res = s34 * 100 + s23;
            // если сумма второй и третьей цифры меньше или равна остальным
            } else if (s23 <= s12 && s23 <= s34) {
                // формируем число так, чтобы суммы шли в порядке неубывания
                if (s12 < s34)
                    res = s12 * 100 + s34;
                else
                    res = s34 * 100 + s12;
            // если сумма третьей и четвёртой цифры меньше или равна остальным
            } else {
                // формируем число так, чтобы суммы шли в порядке неубывания
                if (s23 < s12)
                    res = s23 * 100 + s12;
                else
                    res = s12 * 100 + s23;
            }

            // если результат равен 511
            if (res == 511)
                // выводим перебираемое число
                System.out.println(n);

        }

    }
}

C++

#include <iostream>

// главный метод программы
int main() {

    // перебираем все четырёхзначные числа
    for (int n = 1000; n < 10000; n++) {
        // инициализируем переменную цикла
        int i = n;
        // номер читаемого разряда
        int r = 0;
        // пока есть хотя бы одна цифра в числе
        while (i > 0) {
            // увеличиваем номер текущего разряда
            r++;
            // отбрасываем младший разряд числа
            i /= 10;
        }

        // сохраняем кол-во разрядов
        int cnt = r;
        // создаём массив цифр по кол-ву разрядов
        int d[cnt];
        // инициализируем переменную цикла
        i = n;
        // номер читаемого разряда
        r = 0;
        // пока есть хотя бы одна цифра в числе
        while (i > 0) {
            // получаем цифру младшего разряда
            d[r] = i % 10;
            // увеличиваем номер текущего разряда
            r++;
            // отбрасываем младший разряд числа
            i /= 10;
        }

        // в массиве цифры расположены по разрядам,
        // поэтому элементы для сумм берутся в обратном порядке
        int s12 = d[3] + d[2];
        int s23 = d[2] + d[1];
        int s34 = d[1] + d[0];

        // итоговое число
        int res;
        // если сумма первой и второй цифры меньше или равна остальным
        if (s12 <= s23 && s12 <= s34) {
            // формируем число так, чтобы суммы шли в порядке неубывания
            if (s23 < s34)
                res = s23 * 100 + s34;
            else
                res = s34 * 100 + s23;
            // если сумма второй и третьей цифры меньше или равна остальным
        } else if (s23 <= s12 && s23 <= s34) {
            // формируем число так, чтобы суммы шли в порядке неубывания
            if (s12 < s34)
                res = s12 * 100 + s34;
            else
                res = s34 * 100 + s12;
            // если сумма третьей и четвёртой цифры меньше или равна остальным
        } else {
            // формируем число так, чтобы суммы шли в порядке неубывания
            if (s23 < s12)
                res = s23 * 100 + s12;
            else
                res = s12 * 100 + s23;
        }

        // если результат равен 511
        if (res == 511)
            // перехожим на новую строку
            std::cout << n <<std::endl;
    }
    
    return 0;
}

Python

# перебираем все четырёхзначные числа
for n in range(1000, 10000):
    # номер читаемого разряда
    r = 0
    # создаём список цифр
    d = list()
    i = n
    # пока есть хотя бы одна цифра в числе
    while i > 0:
        d.append(i % 10)
        # увеличиваем номер текущего разряда
        r = r + 1
        # отбрасываем младший разряд числа
        i = i // 10

    # в массиве цифры расположены по разрядам,
    # поэтому элементы для сумм берутся в обратном порядке
    s12 = d[3] + d[2]
    s23 = d[2] + d[1]
    s34 = d[1] + d[0]

    # если сумма первой и второй цифры меньше или равна остальным
    if s12 <= s23 and s12 <= s34:
        # формируем число так, чтобы суммы шли в порядке неубывания
        if s23 < s34:
            res = s23 * 100 + s34
        else:
            res = s34 * 100 + s23
        # если сумма второй и третьей цифры меньше или равна остальным
    elif s23 <= s12 and s23 <= s34:
        # формируем число так, чтобы суммы шли в порядке неубывания
        if s12 < s34:
            res = s12 * 100 + s34
        else:
            res = s34 * 100 + s12
        # если сумма третьей и четвёртой цифры меньше или равна остальным
    else:
        # формируем число так, чтобы суммы шли в порядке неубывания
        if s23 < s12:
            res = s23 * 100 + s12
        else:
            res = s12 * 100 + s23

    # если результат равен 511
    if res == 511:
        # перехожим на новую строку
        print(n)

Программы выведет список всех подходящих чисел:

1056
1147
1238
1329
...
9205
9214
9223
9230
9231
9232

Нам останется только найти среди них самое маленькое и самое большое.

*Ответ: максимальное число равно 9232, минимальное - 1056

Пример 7

Задача

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

1. Вычисляются два шестнадцатеричных числа – сумма старших разрядов полученных чисел и сумма младших разрядов этих чисел.
2. Полученные два шестнадцатеричных числа записываются друг за другом в порядке возрастания (без разделителей).

Пример. Исходные числа: 66, 43. Поразрядные суммы: A, 9. Результат: 9A.

Определите, какое из следующих чисел может быть результатом работы автомата.

1) 9F

2) 911

3) 42

4) 7A

Java

public class Example7 {

    // получить массив цифр числа
    static int[] getDigits(int n) {
        // инициализируем переменную цикла
        int i = n;
        // номер читаемого разряда
        int r = 0;
        // пока есть хотя бы одна цифра в числе
        while (i > 0) {
            // увеличиваем номер текущего разряда
            r++;
            // отбрасываем младший разряд числа
            i /= 16;
        }
        // создаём массив цифр по кол-ву разрядов
        int[] d = new int[r];
        // инициализируем переменную цикла
        i = n;
        // номер читаемого разряда
        r = 0;
        // пока есть хотя бы одна цифра в числе
        while (i > 0) {
            // получаем цифру младшего разряда
            d[r] = i % 16;
            // увеличиваем номер текущего разряда
            r++;
            // отбрасываем младший разряд числа
            i /= 16;
        }
        return d;
    }


    public static void main(String[] args) {
        // перебираем все числа, которые в шетнадцатеричной
        // системе будут представлены двумя цифрами
        // первое число - это 10, последнее - FF
        for (int n1 = 16; n1 < 256; n1++) {
            // получаем массив цифр первого числа
            int[] d1 = getDigits(n1);
            // если одна из цифр больше семи,
            if (d1[0] > 6 || d1[1] > 6)
                // переходим к следующему шагу цикла
                continue;
            for (int n2 = 16; n2 < 256; n2++) {
                // получаем массив цифр первого числа
                int[] d2 = getDigits(n2);
                // если одна из цифр больше семи,
                if (d2[0] > 6 || d2[1] > 6)
                    // переходим к следующему шагу цикла
                    continue;

                // рассчитываем поразрядные суммы
                int s1 = d1[0] + d2[0];
                int s2 = d1[1] + d2[1];


                int res;
                // формируем число так, чтобы суммы шли в порядке невозрастания
                // т.к. обе цифры не больше шести, то их сумма точно займёт всего один разряд
                // в шестнадцатеричном представлении
                if (s1 > s2)
                    res = s2 * 16 + s1;
                else
                    res = s1 * 16 + s2;

                String answ = Integer.toString(res,16);

                // если результат равен одному из заданных, выведем его
                if (answ.equals("9f") || answ.equals("911") || answ.equals("42") || answ.equals("7a"))
                    // выводим перебираемое число
                    System.out.println(answ);
            }
        }

    }
}

C++

#include <iostream>
#include <vector>

// получить массив цифр числа
std::vector<int> getDigits(int n) {
    std::vector<int> d;
    // номер читаемого разряда
    int r = 0;
    // пока есть хотя бы одна цифра в числе
    while (n > 0) {
        // получаем цифру младшего разряда
        d.push_back(n % 16);
        // увеличиваем номер текущего разряда
        r++;
        // отбрасываем младший разряд числа
        n /= 16;
    }
    return d;
}


// главный метод программы
int main() {
    // перебираем все числа, которые в шетнадцатеричной
    // системе будут представлены двумя цифрами
    // первое число - это 10, последнее - FF
    for (int n1 = 16; n1 < 256; n1++) {
        std::vector<int> d1 = getDigits(n1);
        // если одна из цифр больше семи,
        if (d1[0] > 6 || d1[1] > 6)
            // переходим к следующему шагу цикла
            continue;
        for (int n2 = 16; n2 < 256; n2++) {
            // получаем массив цифр первого числа
            std::vector<int> d2 = getDigits(n2);
            // если одна из цифр больше семи,
            if (d2[0] > 6 || d2[1] > 6)
                // переходим к следующему шагу цикла
                continue;

            // рассчитываем поразрядные суммы
            int s1 = d1[0] + d2[0];
            int s2 = d1[1] + d2[1];


            int res;
            // формируем число так, чтобы суммы шли в порядке невозрастания
            // т.к. обе цифры не больше шести, то их сумма точно займёт всего один разряд
            // в шестнадцатеричном представлении
            if (s1 > s2)
                res = s2 * 16 + s1;
            else
                res = s1 * 16 + s2;

            // создаём строку с двоичным представлением перебираемого значения
            char p[17];
            // отправляем в буфер p строковое представление числа с заданным основанием
            itoa(res, p, 16);
            // создаём строку на основе буффера
            std::string answ(p);
            // если результат равен одному из заданных, выведем его
            if (answ == "9f" || answ == "911" || answ == "42" || answ == "7a")
                // перехожим на новую строку
                std::cout << answ << std::endl;
        }
    }

    return 0;
}

Python

# получить массив цифр числа
def getDigits(n):
    # номер читаемого разряда
    r = 0
    # создаём список цифр
    d = list()
    # пока есть хотя бы одна цифра в числе
    while n > 0:
        d.append(n % 10)
        # увеличиваем номер текущего разряда
        r = r + 1
        # отбрасываем младший разряд числа
        n = n // 10
    return d


# перебираем все числа, которые в шетнадцатеричной
# системе будут представлены двумя цифрами
# первое число - это 10, последнее - FF
for n1 in range(16, 256):
    d1 = getDigits(n1)
    if d1[0] > 6 or d1[1] > 6:
        continue
    for n2 in range(16, 256):
        d2 = getDigits(n2)
        if d2[0] > 6 or d2[1] > 6:
            continue

        #  рассчитываем поразрядные суммы
        s1 = d1[0] + d2[0]
        s2 = d1[1] + d2[1]

        # формируем число так, чтобы суммы шли в порядке невозрастания
        # т.к. обе цифры не больше шести, то их сумма точно займёт всего один разряд
        # в шестнадцатеричном представлении
        if s1 > s2:
            res = s2 * 16 + s1
        else:
            res = s1 * 16 + s2
        # переводим результат в шестнадцатеричную строку
        answ = hex(res)
        # если результат равен одному из заданных, выведем его
        if answ == "0x9f" or answ == "0x911" or answ == "0x42" or answ == "0x7a":
            # перехожим на новую строку
            print(answ)

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

Сами цифры должны быть шестнадцатеричными. Поэтому в алгоритме я поменял все числа 10 на 16.

На выходе получим множество строк с числом $7a$

Ответ: 4)

В Python преобразование к шестнадцатеричной строке добавляет в её начале два символа: 0x, поэтому проверка немного отличается.

Задания для самостоятельного выполнения