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

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

Ниже на пяти языках программирования записан алгоритм. Получив на вход натуральное десятичное число x, этот алгоритм печатает два числа: L и M. Укажите наименьшее число x, при вводе которого алгоритм выводит сначала 8, а потом 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;

}

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

Ответ: 86

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

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

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

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

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

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

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

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

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