Задача
В арифметическом выражении разрешается использовать число [latex]1[/latex], операции сложения, умножения и скобки. Какое наименьшее количество единиц нужно использовать, чтобы получить заданное натуральное число [latex]n[/latex]?
Входные данные
Одно число [latex]n[/latex] [latex](1 \leqslant n \leqslant 5000).[/latex]
Выходные данные
Искомое количество единиц.
Тесты
| # | Входные данные | Выходные данные |
|---|---|---|
| 1 | 7 | 6 |
| 2 | 22 | 10 |
| 3 | 90 | 13 |
| 4 | 157 | 16 |
| 5 | 985 | 21 |
Код программы
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 |
import java.util.*; import java.lang.*; import java.io.*; import java.lang.Math; class Main { public static int max = 5001; static int [] x = new int[max]; public static void main (String[] args) throws java.lang.Exception { Scanner in = new Scanner(System.in); int n = in.nextInt(); int k; x[1] = 1; x[2] = 2; for (int i = 3; i <= n; i++) { x[i] = x[i-1]+1; for (int j = 2; j <= Math.sqrt(n); j++) { if(i % j == 0) { k = x[j] + x[i/j]; if( k < x[i]) x[i] = x[j] + x[i/j]; } } } System.out.println(x[n]); } } |
Решение задачи
Нам нужно найти минимальное количество [latex]1,[/latex] с помощью которых можно составить заданное число. Если последней операцией будет сложение, то первое слагаемое будет состоять из [latex]f(i)[/latex] единиц, а второе — из [latex]f(n-i).[/latex] Значение [latex]i[/latex] будем выбирать таким, чтобы сумма этих двух слагаемых была минимальной. Если [latex]n[/latex] нацело делится на [latex]i[/latex], то последней операцией будет умножение. Первый множитель будет состоять из [latex]f(i)[/latex] единиц, а второй — [latex]\displaystyle f \left (\frac{n}{i} \right).[/latex] Тогда значение [latex]i[/latex] будем перебирать до [latex]\sqrt{n},[/latex] чтобы сумма этих слагаемых была минимальной. Затем выводим искомое количество единиц на экран. Задача решена.