0B12E4 — Выполнение и анализ программы: ответ и решение

Впишите правильный ответ.

Ниже на пяти языках программирования записан алгоритм. Получив на вход натуральное десятичное число x, этот алгоритм печатает два числа: L и M. Укажите наибольшее число x, при вводе которого алгоритм выводит
сначала 2, а потом 3.

Бейсик	Python
DIM X, L, M AS INTEGER INPUT X L = 0 M = 0 WHILE X > 0 M = M + 1 IF X MOD 2 = 0 THEN L = L + X MOD 8 END IF X = X \ 8 WEND PRINT L PRINT M	x = int(input()) L = 0 M = 0 while x > 0: M = M + 1 if x % 2 == 0: L = L + x % 8 x = x // 8 print(L) print(M)
Алгоритмический язык	Паскаль
алг нач цел x, L, M ввод x L := 0 M := 0 нц пока x > 0 M := M + 1 если mod(x, 2) = 0 то L := L + mod(x, 8) все x := div(x, 8) кц вывод L, нс, M кон	var x, L, M: integer; begin readln(x); L := 0; M := 0; while x > 0 do begin M := M + 1; if x mod 2 = 0 then L := L + x mod 8; x := x div 8 end; writeln(L); writeln(M) end.

С++

#include <iostream>

using namespace std;

int main(){

int x, L, M;

cin >> x;

L = 0;

M = 0;

while (x > 0) {

M = M + 1;

if(x % 2 == 0) {

L = L + x % 8;

}

x = x / 8;

}

cout << L << endl << M << endl;

return 0;

}

Решение задания EGEINF0B12E4

Ответ: 506

Каждый проход берёт остаток от деления текущего x на 8 и затем отбрасывает эту последнюю цифру целочисленным делением на 8. Поэтому M равно количеству цифр исходного числа в системе с основанием 8. Нужно ровно 3 цифр, первая из которых ненулевая.
Основание чётное, поэтому чётность текущего x совпадает с чётностью его последней цифры. Значит, L накапливает сумму чётных цифр. Начальное L = 0, требуемое конечное L = 2.
Найдём наибольшее число, выбирая цифры слева направо. Допустимость цифры проверяем по всем продолжениям, а не только по её собственному значению.
Для проверки обозначим Cᵣ(v) число способов дописать r цифр, когда накопитель равен v. При r = 0 получаем 1 способ, если v = 2, и 0 в остальных случаях. При r > 0 складываем Cᵣ₋₁(T(v,d)) по всем цифрам d от 0 до 7. Здесь T оставляет v для цифры другой чётности, а для нужной чётности прибавляет d к v.
Начинаем с v = 0. В первой позиции запрещён ноль. Для каждой следующей позиции сохраняем уже выбранное начало. Перечислим все цифры с ненулевым числом подходящих продолжений; после двоеточия указано их количество.
Позиция 1: 1: 10, 2: 25, 3: 10, 5: 10, 7: 10. Выбираем 7.
Позиция 2: 0: 1, 1: 1, 2: 5, 3: 1, 5: 1, 7: 1. Выбираем 7.
Позиция 3: 2: 1. Выбираем 2.
Получаем 772 (основание 8). Выбранная на каждом шаге крайняя допустимая цифра даёт наибольшее число: более выгодная первая отличающаяся цифра не имеет подходящего продолжения.
Переведём запись в десятичную систему: 7 · 8² + 7 · 8¹ + 2 · 8⁰ = 506.
Проверка: цифр 3, учитываемые цифры — 2. Их сумма равно 2. Значит, программа выводит 2, затем 3.
Ответ: 506.

Помочь улучшить сайт

Напишите пожелание к сайту или решению либо сообщите о найденной неточности в задании EGEINF0B12E4.

Сообщение увидит только команда сайта: на странице оно не публикуется.

КЭС:	3.1 Формализация понятия алгоритма. Машина Тьюринга как универсальная модель вычислений
Тип ответа:	Краткий ответ

Задание EGEINF0B12E4: Выполнение и анализ программы

Решение задания EGEINF0B12E4

Помочь улучшить сайт

Комментарии к решению