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

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

Ниже на пяти языках программирования записан алгоритм. Получив на вход натуральное десятичное число x, этот алгоритм печатает два числа: L и M. Укажите наибольшее число x, при вводе которого алгоритм печатает сначала 2, а потом 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 8) END IF X = X \ 8 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 % 8) x = x // 8 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,8) все x := div(x,8) кц вывод 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 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 = 1; 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; }

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

Ответ: 506

Каждый проход берёт остаток от деления текущего x на 8 и затем отбрасывает эту последнюю цифру целочисленным делением на 8. Поэтому M равно количеству цифр исходного числа в системе с основанием 8. Нужно ровно 3 цифр, первая из которых ненулевая.
Основание чётное, поэтому чётность текущего x совпадает с чётностью его последней цифры. Значит, L накапливает произведение чётных цифр. Начальное L = 1, требуемое конечное L = 2.
Найдём наибольшее число, выбирая цифры слева направо. Допустимость цифры проверяем по всем продолжениям, а не только по её собственному значению.
Для проверки обозначим Cᵣ(v) число способов дописать r цифр, когда накопитель равен v. При r = 0 получаем 1 способ, если v = 2, и 0 в остальных случаях. При r > 0 складываем Cᵣ₋₁(T(v,d)) по всем цифрам d от 0 до 7. Здесь T оставляет v для цифры другой чётности, а для нужной чётности умножает v на d.
Начинаем с v = 1. В первой позиции запрещён ноль. Для каждой следующей позиции сохраняем уже выбранное начало. Перечислим все цифры с ненулевым числом подходящих продолжений; после двоеточия указано их количество.
Позиция 1: 1: 8, 2: 16, 3: 8, 5: 8, 7: 8. Выбираем 7.
Позиция 2: 1: 1, 2: 4, 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.

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

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

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

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

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

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

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

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