一步的最小步骤 [英] Minimum Steps to One
问题描述
问题陈述:
在正整数上,您可以执行以下3个步骤中的任何一个。
On a positive integer, you can perform any one of the following 3 steps.
- 从中减去1。 (n = n - 1)
- 如果它可被2整除,则除以2.(如果n%2 == 0,则n = n / 2)
- 如果它可被3整除,则除以3.(如果n%3 == 0,则n = n / 3)。
现在的问题是,给定正整数n,找到n到1的最小步数
Now the question is, given a positive integer n, find the minimum number of steps that takes n to 1
例如:
- 对于n = 1,输出:0
- 对于n = 4,输出:2(4/2 = 2 / 2 = 1)
- 对于n = 7,输出:3(7 -1 = 6/3 = 2/2 = 1)
我知道使用动态编程并具有整数数组的解决方案。这是代码。
I know the solution using dynamic programming and having a integer array. here is the code.
public int bottomup(int n) {
//here i am defining an integer array
//Exception is thrown here, if the n values is high.
public int[] bu = new int[n+1];
bu[0] = 0;
bu[1] = 0;
for(int i=2;i<=n;i++) {
int r = 1+bu[i-1];
if(i%2 == 0) r = Math.min(r,1+bu[i/2]);
if(i%3 == 0) r = Math.min(r,1+bu[i/3]);
bu[i] = r;
}
return bu[n];
}
但是我想用更少的空间解决这个问题。这个解决方案在java中抛出OutofMemoryError如果n = 100000000。我不想增加我的堆空间。任何人都有使用更少空间的解决方案吗?
But i want to solve this using less space.This solution throws OutofMemoryError in java if n=100000000.I don't want to increase my heap space.Does anyone has solution using less space?
请注意使用greedy algorthm无法解决此问题。使用一个while循环并检查可被3整除并可被2整除。你必须使用动态编程。请指出是否有任何解决方案使用更少的空间。
Please note this problem cannot be solved using greedy algorthm.Using one while loop and check for divisible by 3 and divisible by 2 wont work.you have to use dynamic programming.please suggest if any has a solution using less space.
例如:
对于n = 10,贪心算法是10/2 = 5 -1 = 4/2 = 2/2 = 1需要4步。其中作为解决方案应该是10-1 = 9/3 = 3/3 = 1,3步。
For n = 10 greedy algo is 10 /2 = 5 -1 = 4 /2 = 2 /2 = 1 which takes 4 steps.where as the solution should be 10-1 = 9 / 3 = 3 / 3 = 1, 3 steps.
我甚至试过自上而下的解决方案。
I even tried topdown solution.
public int[] td = null;
public int topdown(int n) {
if(n <= 1) return 0;
int r = 1+topdown(n-1);
if(td[n] == 0) {
if(n%2 == 0) r = Math.min(r,1+topdown(n/2));
if(n%3 == 0) r = Math.min(r,1+topdown(n/3));
td[n] = r;
}
return td[n];
}
在n = 10000时失败。
it is failing at n=10000.
推荐答案
一个想法是,在任何迭代中,您只需要 r / 3
到<$ c的值$ C> - [R 。所以你可以继续丢弃数组的 1/3
。
One idea is that at any iteration you need the values only for r/3
to r
. So you can keep discarding 1/3rd
of the array.
我不熟悉 Java
,但是使用 C ++
,您可以使用双端队列(deque)
:
I'm not familiar with Java
, but with C++
you can use a double ended queue (deque)
:
你继续从后面添加双端队列。
当 i = 6
,你不需要 bu [0]
和 bu [1]
。所以你从队列的前面弹出两个元素。
You keep adding to the deque from the back.
When i = 6
, you do not need bu[0]
and bu[1]
. So you pop out two elements from the front of the queue.
deque容器支持随机访问 []
。
Random access [ ]
is supported with deque container.
编辑:同样如评论中所建议的那样,您应该将数据类型更改为较小的数据类型,因为最大步数应为<$ c的顺序$ c>((log N)到基数2)
Also as suggested in the comments, you should change your datatype to a smaller sized one since the maximum number of steps shall be of the order of ( (log N) to base 2)
EDIT2:正如Dukeling指出的那样,似乎在Java中没有准备好 - 制作非常适合deque的实现,不会影响时间复杂度。您可以考虑像C ++一样以自己的方式实现它(我听说它是作为向量的向量实现的,内部向量的大小与元素的总数相比较小)。
As Dukeling pointed out, it seems that in Java there is no ready-made well-suited implementation for deque that would not compromise on time complexity. You can think of implementing it in your own way as C++ does (I heard it is implemented as a vector of vectors with the size of inner vectors being small as compared to the total number of elements).
这篇关于一步的最小步骤的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!