Определите, какое наименьшее число операций необходимо, чтобы получить из числа 1 число N - Turbo Pascal
Формулировка задачи:
Имеется калькулятор, который выполняет три операции:
1. Прибавить к числу X единицу.
2. Умножить число X на 2.
3. Умножить число X на 3.
Определите, какое наименьшее число операций необходимо для того, чтобы получить из числа 1 заданное число N. Также вывести последовательность операций, например 1,2,3.
Входные данные: Число N, не превосходящее 106.
Выходные данные: Наименьшее количество искомых операций.
Решение задачи: «Определите, какое наименьшее число операций необходимо, чтобы получить из числа 1 число N»
textual
Листинг программы
- var n , i , am : longint;
- a , res : array[1..1000000] of longint;
- begin
- read(n);
- a[1] := 0;
- for i := 2 to n do
- a[i] := maxint;
- for i := 2 to n do begin
- if a[i] > a[i - 1] + 1 then
- a[i] := a[i - 1] + 1;
- if i mod 2 = 0 then
- if a[i] > a[i div 2] + 1 then
- a[i] := a[i div 2] + 1;
- if i mod 3 = 0 then
- if a[i] > a[i div 3] + 1 then
- a[i] := a[i div 3] + 1;
- end;
- writeln(a[n]);
- am := 0;
- i := n;
- while i <> 1 do begin
- inc(am);
- if (i mod 3 = 0) and (a[i div 3] + 1 = a[i]) then begin
- res[am] := 3;
- i := i div 3;
- end else if (i mod 2 = 0) and (a[i div 2] + 1 = a[i]) then begin
- res[am] := 2;
- i := i div 2;
- end else begin
- res[am] := 1;
- i := i - 1;
- end;
- end;
- for i := am downto 1 do
- writeln(res[i]);
- end.
Объяснение кода листинга программы
- Переменные n, i, am объявлены как longint.
- Создается массив a[1..1000000] of longint, где каждый элемент массива инициализируется значением максимальной возможной целочисленной величины.
- Число n считывается с помощью функции read.
- Первый элемент массива a[1] устанавливается равным 0.
- Для i от 2 до n выполняется цикл for.
- Внутри цикла проверяется, больше ли значение a[i] значения a[i-1] + 1. Если это условие истинно, то значение a[i] устанавливается равным a[i-1] + 1.
- Если i делится на 2 без остатка, то проверяется, больше ли значение a[i] значения a[i/2] + 1. Если это условие истинно, то значение a[i] устанавливается равным a[i/2] + 1.
- Если i делится на 3 без остатка, то проверяется, больше ли значение a[i] значения a[i/3] + 1. Если это условие истинно, то значение a[i] устанавливается равным a[i/3] + 1.
- После завершения цикла for, значение a[n] равно 1.
- Переменная am инициализируется значением 0.
- Цикл while начинается.
- Для i от n до 1 выполняется цикл while.
- Внутри цикла выполняется проверка: если i делится на 3 без остатка и значение a[i/3] + 1 равно a[i], то значение res[am] устанавливается равным 3, i устанавливается равным i/3, и цикл while завершается.
- Если i делится на 2 без остатка и значение a[i/2] + 1 равно a[i], то значение res[am] устанавливается равным 2, i устанавливается равным i/2, и цикл while завершается.
- Если i не делится на 3 или 2 без остатка, то значение res[am] устанавливается равным 1, i устанавливается равным i - 1, и цикл while завершается.
- После завершения цикла while, значение res[am] содержит результат вычисления.
- Для i от am до 1 выполняется цикл for.
- Внутри цикла выполняется проверка: если i равно am, то значение res[i] устанавливается равным 0, и цикл for завершается.
- Если i меньше am, то значение res[i] устанавливается равным значению res[i+1].
- Код завершается.
ИИ поможет Вам:
- решить любую задачу по программированию
- объяснить код
- расставить комментарии в коде
- и т.д