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

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

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

Бейсик

Python

DIM X, L, M AS INTEGER

INPUT X

L = 1

M = 0

WHILE X > 0

M = M + 1

IF X MOD 2 = 0 THEN

L = L * (X MOD 6)

END IF

X = X \ 6

WEND

PRINT L

PRINT M

x = int(input())

L = 1

M = 0

while x > 0:

M = M + 1

if x % 2 == 0:

L = L * (x % 6)

x = x // 6

print(L)

print(M)

Алгоритмический язык	Паскаль
алг нач цел x, L, M ввод x L := 1 M := 0 нц пока x > 0 M := M + 1 если mod(x, 2) = 0 то L := L * mod(x, 6) все x := div(x, 6) кц вывод L, нс, M кон	var x, L, M: integer; begin readln(x); L := 1; M := 0; while x > 0 do begin M := M + 1; if x mod 2 = 0 then L := L * (x mod 6); x := x div 6 end; writeln(L); writeln(M) end.
С++
#include <iostream> using namespace std; int main(){ int x, L, M; cin >> x; L = 1; M = 0; while (x > 0) { M = M + 1; if(x % 2 == 0) { L = L * (x % 6); } x = x / 6; } cout << L << endl << M << endl; return 0; }

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

Ответ: 208

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

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

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

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

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

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

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

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

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