Общее·количество·просмотров·страницы

Java Dev Notes - разработка на Java (а также на JavaScript/Python/Flex и др), факты, события из АйТи

Архив блога

четверг, 30 сентября 2010 г.

Задачка на динамическое программирование: Minimum steps to one

Формулировка задачи на английском:

On a positive integer, you can perform any one of the following 3 steps.
1.) Subtract 1 from it. ( n = n - 1 ) ,
2.) If its divisible by 2, divide by 2. ( if n % 2 == 0 , then n = n / 2 ) ,
3.) If its divisible by 3, divide by 3. ( if n % 3 == 0 , then n = n / 3 ).

Now the question is, given a positive integer n, find the minimum number of steps that takes n to 1
eg:
1.)For n = 1 , output: 0
2.) For n = 4 , output: 2 ( 4 /2 = 2 /2 = 1 )
3.) For n = 7 , output: 3 ( 7 -1 = 6 /3 = 2 /2 = 1 )


Теперь формулировка на русском языке (в моем переводе):

Дано натуральное число n (не равное нулю). Над ним можно совершить одну из трех операций:
1) вычесть единицу из него (n-1)
2) разделить на два (n/2)
3) разделить на три (n/3)

Для данного числа n найти минимальное число операций, в результате которых получается единица.
Пример:
1) n=1, ответ: 0
2) n=4, ответ: 2 (/2, /2)
3) n=7, ответ: 3 (-1, /3, /2)


Рассмотрим решение.

Для каждого данного n непонятно, какая из операций приведет к минимальному числу шагов. Поэтому нужно попробовать все варианты и выбрать из них вариант с минимальным числом шагов.
Если n == 1, то F(n) = 0.
Иначе (если n>1):
F(n) = 1 + min(F(n-1),F(n/2),F(n/3)).
При этом каждый раз нужно проверять, делится ли n без остатка на два или на три.

Решение в коде на Java:

public class Problem {
 
static int getMinSteps(int n) {
if (n==1) return 0;
else if (n==2 || n==3) return 1;
else if (n==4) return 2;
else {
int[] steps = new int[n+1];
steps[0] = -1;
steps[1] = 0;
steps[2] = steps[3] = 1;
steps[4] = 2;
for (int i=5; i<=n; i++) {
steps[i] = steps[i-1]+1;
if (i%2==0) {
steps[i] = min(steps[i],steps[i/2]+1);
}
if (i%3==0) {
steps[i] = min(steps[i],steps[i/3]+1);
}
}
return steps[n];
}
}
 
static int min(int a, int b) {
return a < b ? a : b;
}
 
public static void main(String[] args) {
int n = Integer.parseInt(args[0]);
System.out.println(getMinSteps(n));
}
}


Задачка простенькая, но как вводный пример в динамическое программирование сгодится.
В коде нет, конечно, проверки на допустимые значения n (не проверяется, чтобы n было больше нуля), также нет проверки на отсутствие аргумента в командной строке. Главное здесь - познакомиться с подходом, который предлагает динамическое программирование для решения такого рода задач.

Комментариев нет:

Отправить комментарий

Постоянные читатели