Имеется калькулятор, который выполняет три операции: прибавить к числу X единицу;
умножить число X на 2;
умножить число (X * 2) + 1.
Определите, какое наименьшее число операций необходимо для того, чтобы получить из числа 1 заданное число N.
Входные данные
Программа получает на вход одно число, не превосходящее 10^6.
Выходные данные
Требуется вывести одно число: наименьшее количество искомых операций.
def shortest_chains(n):
def next_chains(chain):
new_elems = set()
for i in range(len(chain)):
for j in range(i, len(chain)):
new_elem = chain[i] + chain[j]
if new_elem > chain[-1] and new_elem not in new_elems:
new_elems.add(new_elem)
yield chain + [new_elem]
current_stage = None
next_stage = [[1]]
answer = []
while len(answer) == 0:
current_stage = next_stage
next_stage = []
for chain in current_stage:
next_stage.extend(next_chains(chain))
answer = [chain[1:] for chain in next_stage if chain[-1] == n]
return answer
def print_solution(n):
answer = shortest_chains(n)
print("Для {} есть {} решений(-я, -е):".format(n, len(answer)))
for i in range(len(answer)):
print("{}. {}".format(i + 1, " ".join(map(str, answer[i]
print()
Запустив, можно получить все 5 возможных решений для числа 7, по 4 решения для 15 и 23 и 87 решений для 63.
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
double Ax, Bx, Cx;
Scanner sc = new Scanner(System.in);
try {
System.out.println("Waiting for input A, B and C...");
Ax = sc.nextDouble();
Bx = sc.nextDouble();
Cx = sc.nextDouble();
if (!(Cx > Math.min(Ax, Bx) && Cx < Math.max(Ax, Bx))) {
System.out.println("Неверные входные данные.");
return;
}
double AC = Math.abs(Cx - Ax);
double BC = Math.abs(Cx - Bx);
System.out.println("AC = " + AC);
System.out.println("BC = " + BC);
System.out.println("AC * BC = " + AC * BC);
} catch (RuntimeException e) {
System.out.println("Неверные входные данные.");
}
}
}
Проблемы, вопросы или предложения по работе программы в комментарии.