如何改善这种code？ [英] how to improve this code?
问题描述
我已经开发了code为前pressing在2动力方面的数量，我附上下同code。
但问题是，pssed前$ P $输出应该最小长度。
我正在为输出3 ^ 2 + 1 ^ 2 + 1 ^ 2 + 1 ^ 2 这是不是最小长度。
我需要的输出格式为：
包com.algo;
进口java.util.Scanner中;
公共类GetInputFromUser {
公共静态无效的主要（字串[] args）{
// TODO自动生成方法存根
INT N;
扫描仪在=新的扫描仪（System.in）;
的System.out.println（输入一个整数）;
N = in.nextInt（）;
的System.out.println（结果是：）;
algofunction（N）;
}
公共静态INT algofunction（INT N1）
{
INT R1 = 0;
INT R2 = 0;
INT R3 = 0;
//System.out.println("n1：+ N1）;
R1 =（int）的的Math.sqrt（n1）的;
R2 =（int）的Math.pow（R1，2）;
//的System.out.println（R1+ R1）;
//System.out.println("r2：+ R2）;
System.out.print（R1 +^ 2）;
R3 = N1-R2;
//System.out.println("r3：+ R3）;
如果（R3 == 0）
返回1;
如果（r3的== 1）
{
System.out.print（+ 1 ^ 2）;
返回1;
}
其他 {
System.out.print（+）;
algofunction（R3）;
返回1;
}
}
}
动态编程是所有关于这样一种方式，如果你知道答案，原来的缩小版本，你可以用它来回答这个定义问题主要的问题更快速/直接。这就像应用数学归纳法。
在你的问题中，我们可以定义MinLen（N）为N的最小长度再presentation。其次，说，既然我们要解决MinLen（12），假设我们已经知道了答案MinLen（1），MinLen（2），MinLen（3），...，MinLen（11）。我们怎么能使用的答案，这些小问题搞清楚MinLen（12）？这是动态编程的另一半 - 找出如何使用较小的问题，解决了更大的一个。它不会帮你，如果你想出一些小问题，但都没有办法把它们合并到一起的。
对于这个问题，我们可以简单的表述，为12，它的最小长度再presentation肯定有是1 ^ 2，2 ^ 2，或3 ^ 2在里面。而在一般情况中，n的最小长度重新presentation将有一些方小于或等于n，作为它的一部分。有可能是一个更好的语句可以使，这将提高运行时，但我会说，这是不够好现在。
该语句的意思是MinLen（12）= 1 ^ 2 + MinLen（11）或2 ^ 2 + MinLen（8），或3 ^ 2 + MinLen（3）。你检查所有这些，选择最好的一个，现在您保存为MinLen（12）。现在，如果你想解决MinLen（13），你可以做到这一点。
当独奏建议： 我想测试这种程序的方式我是插在1，2，3，4，5，等，并在第一时间看到它出错。此外，我发生的任何假设，还以为是个好主意，我问：难道真的是大于n的最大平方数少会在MinLen（n）的再presentation？
您code：
R1 =（INT）的Math.sqrt（N1）;
R2 =（int）的Math.pow（R1，2）;
体现了这一假设（贪婪的假设），但它是错误的，因为你已经清楚地看到与MinLen答案（12）。
相反，你想要更多的东西是这样的：
公开的ArrayList＆LT;整数GT; minLen（INT N）
{
//基地递归的情况下，
如果（N == 0）
返回新的ArrayList＆LT;整数GT;（）;
ArrayList的＆LT;整数GT;最好= NULL;
INT bestInt = -1;
的for（int i = 1; I * I＆LT; = N; ++ I）
{
//检查如果我们用什么发生了，我^ 2作为我们重新presentation部分
ArrayList的＆LT;整数GT;猜= minLen（N - I * I）;
//如果我们没有选择一个最佳，但（最好== NULL）
//如果我们的新的猜测是比目前更好的选择（guess.size（）＆LT; best.size（））
//更新我们的选择最好的
如果（最好== NULL || guess.size（）＆LT; best.size（））
{
最好=猜测;
bestInt =我;
}
}
best.add（bestInt）;
最好回报;
}
然后，一旦你有你的列表，你可以对它进行排序（不能保证它排在排序顺序），打印出来你想要的方式。
最后，你可能会注意到，对于n，你在插入上述递归，它会开始进行得非常缓慢的较大值（1000可能过大）。这是因为我们在不断地重新计算所有的小的子问题 - 例如，我们计算出MinLen（3）当我们调用MinLen（4），因为4 - 1 ^ 2 = 3，但我们弄清楚两次MinLen（7） - > 3 = 7 - 2 ^ 2，但3还为7 - 1 ^ 2 - 1 ^ 2 - 1 ^ 2 - 1 ^ 2。而且它还有更糟糕的更大，你走了。
要解决这个，它可以让你解决高达N = 1,000,000以上，速度非常快，是使用一种被称为的记忆化。这意味着，一旦我们弄清楚MinLen（3），我们将其保存的地方，比方说，一个全球性的位置，以方便。然后，每当我们试图重新计算，我们检查了全局缓存先来看看，如果我们已经做到了。如果是这样，那么我们就使用，而不是重做所有的工作的。
进口的java.util。*;
类SquareRe presentation
{
私有静态HashMap的＆LT;整数，ArrayList的＆LT;整数GT;＆GT; cachedSolutions;
公共静态无效的主要（字串[] args）
{
cachedSolutions =新的HashMap＆LT;整数，ArrayList的＆LT;整数GT;＆GT;（）;
对于（INT J = 100000; J＆LT; 100001; ++ j）条
{
ArrayList的＆LT;整数GT;答案= minLen（J）;
Collections.sort（答案）;
Collections.reverse（答案）;
的for（int i = 0; I＆LT; answer.size（）; ++ I）
{
如果（ⅰ！= 0）
System.out.printf（+）;
System.out.printf（％D ^ 2，answer.get（I））;
}
的System.out.println（）;
}
}
公共静态的ArrayList＆LT;整数GT; minLen（INT N）
{
//基地递归的情况下，
如果（N == 0）
返回新的ArrayList＆LT;整数GT;（）;
//新的基本情况：问题之前就已经得到了彻底解决
如果（cachedSolutions.containsKey（n））的
{
//这是一个有点棘手，但因为我们必须要小心！
//见下文如何，我们正在修改的猜测阵列我们进去呢？
//这意味着我们将修改我们的previous的解决方案！不好！
//所以在这里我们需要返回副本
ArrayList的＆LT;整数GT; ANS = cachedSolutions.get（N）;
ArrayList的＆LT;整数GT;复制=新的ArrayList＆LT;整数GT;（）;
对（INT I：ANS）copy.add（ⅰ）;
返回副本;
}
ArrayList的＆LT;整数GT;最好= NULL;
INT bestInt = -1;
//这是错误的，你可以弄清楚为什么它不工作？：
//的for（int i = 1; I * I＆LT; = N; ++ I）
的for（int i =（INT）的Math.sqrt（N）; I＆GT; = 1; --i）
{
//检查如果我们用什么发生了，我^ 2作为我们重新presentation部分
ArrayList的＆LT;整数GT;猜= minLen（N - I * I）;
//如果我们没有选择一个最佳，但（最好== NULL）
//如果我们的新的猜测是比目前更好的选择（guess.size（）＆LT; best.size（））
//更新我们的选择最好的
如果（最好== NULL || guess.size（）＆LT; best.size（））
{
最好=猜测;
bestInt =我;
}
}
best.add（bestInt）;
//检查...没有必要，除非你codeD错误
INT总和= 0;
的for（int i = 0; I＆LT; best.size（）; ++ I）
{
总和+ = best.get（ⅰ）* best.get（ⅰ）;
}
如果（总和！= N）
{
抛出新的RuntimeException（的String.Format（N =％D，和=％D，编曲=％s的\ N，N，总之，最好））;
}
//新步：保存解决方案的全局缓存
cachedSolutions.put（N，最好的）;
像以前一样......如果你不回一个副本，你最终修改你的previous解决方案//同样处理
//
ArrayList的＆LT;整数GT;复制=新的ArrayList＆LT;整数GT;（）;
对于（INT I：最好）copy.add（我）;
返回副本;
}
}
它带走了我的项目之一〜5秒运行的N = 100,000。显然，如果我们希望它是更快，来解决更大的n还有更多的工作要做。主要的问题是，现在在存储previous回答结果的完整列表，我们使用了大量的内存。和所有的复制！还有更多的可以做，像只存储一个整数和一个指向子问题，但我会告诉你这样做。
和靠了靠，1000 = 30 ^ 2 + 10 ^ 2。
I have developed a code for expressing the number in terms of the power of the 2 and I am attaching the same code below.
But the problem is that the expressed output should of minimum length.
I am getting output as 3^2+1^2+1^2+1^2 which is not minimum length.
I need to output in this format:
package com.algo;
import java.util.Scanner;
public class GetInputFromUser {
public static void main(String[] args) {
// TODO Auto-generated method stub
int n;
Scanner in = new Scanner(System.in);
System.out.println("Enter an integer");
n = in.nextInt();
System.out.println("The result is:");
algofunction(n);
}
public static int algofunction(int n1)
{
int r1 = 0;
int r2 = 0;
int r3 = 0;
//System.out.println("n1: "+n1);
r1 = (int) Math.sqrt(n1);
r2 = (int) Math.pow(r1, 2);
// System.out.println("r1: "+r1);
//System.out.println("r2: "+r2);
System.out.print(r1+"^2");
r3 = n1-r2;
//System.out.println("r3: "+r3);
if (r3 == 0)
return 1;
if(r3 == 1)
{
System.out.print("+1^2");
return 1;
}
else {
System.out.print("+");
algofunction(r3);
return 1;
}
}
}
Dynamic programming is all about defining the problem in such a way that if you knew the answer to a smaller version of the original, you could use that to answer the main problem more quickly/directly. It's like applied mathematical induction.
In your particular problem, we can define MinLen(n) as the minimum length representation of n. Next, say, since we want to solve MinLen(12), suppose we already knew the answer to MinLen(1), MinLen(2), MinLen(3), ..., MinLen(11). How could we use the answer to those smaller problems to figure out MinLen(12)? This is the other half of dynamic programming - figuring out how to use the smaller problems to solve the bigger one. It doesn't help you if you come up with some smaller problem, but have no way of combining them back together.
For this problem, we can make the simple statement, "For 12, it's minimum length representation DEFINITELY has either 1^2, 2^2, or 3^2 in it." And in general, the minimum length representation of n will have some square less than or equal to n as a part of it. There is probably a better statement you can make, which would improve the runtime, but I'll say that it is good enough for now.
This statement means that MinLen(12) = 1^2 + MinLen(11), OR 2^2 + MinLen(8), OR 3^2 + MinLen(3). You check all of them and select the best one, and now you save that as MinLen(12). Now, if you want to solve MinLen(13), you can do that too.
Advice when solo: The way I would test this kind of program myself is to plug in 1, 2, 3, 4, 5, etc, and see the first time it goes wrong. Additionally, any assumptions I happen to have thought were a good idea, I question: "Is it really true that the largest square number less than n will be in the representation of MinLen(n)?"
Your code:
r1 = (int) Math.sqrt(n1);
r2 = (int) Math.pow(r1, 2);
embodies that assumption (a greedy assumption), but it is wrong, as you've clearly seen with the answer for MinLen(12).
Instead you want something more like this:
public ArrayList<Integer> minLen(int n)
{
// base case of recursion
if (n == 0)
return new ArrayList<Integer>();
ArrayList<Integer> best = null;
int bestInt = -1;
for (int i = 1; i*i <= n; ++i)
{
// Check what happens if we use i^2 as part of our representation
ArrayList<Integer> guess = minLen(n - i*i);
// If we haven't selected a 'best' yet (best == null)
// or if our new guess is better than the current choice (guess.size() < best.size())
// update our choice of best
if (best == null || guess.size() < best.size())
{
best = guess;
bestInt = i;
}
}
best.add(bestInt);
return best;
}
Then, once you have your list, you can sort it (no guarantees that it came in sorted order), and print it out the way you want.
Lastly, you may notice that for larger values of n (1000 may be too large) that you plug in to the above recursion, it will start going very slow. This is because we are constantly recalculating all the small subproblems - for example, we figure out MinLen(3) when we call MinLen(4), because 4 - 1^2 = 3. But we figure it out twice for MinLen(7) -> 3 = 7 - 2^2, but 3 also is 7 - 1^2 - 1^2 - 1^2 - 1^2. And it gets much worse the larger you go.
The solution to this, which lets you solve up to n = 1,000,000 or more, very quickly, is to use a technique called Memoization. This means that once we figure out MinLen(3), we save it somewhere, let's say a global location to make it easy. Then, whenever we would try to recalculate it, we check the global cache first to see if we already did it. If so, then we just use that, instead of redoing all the work.
import java.util.*;
class SquareRepresentation
{
private static HashMap<Integer, ArrayList<Integer>> cachedSolutions;
public static void main(String[] args)
{
cachedSolutions = new HashMap<Integer, ArrayList<Integer>>();
for (int j = 100000; j < 100001; ++j)
{
ArrayList<Integer> answer = minLen(j);
Collections.sort(answer);
Collections.reverse(answer);
for (int i = 0; i < answer.size(); ++i)
{
if (i != 0)
System.out.printf("+");
System.out.printf("%d^2", answer.get(i));
}
System.out.println();
}
}
public static ArrayList<Integer> minLen(int n)
{
// base case of recursion
if (n == 0)
return new ArrayList<Integer>();
// new base case: problem already solved once before
if (cachedSolutions.containsKey(n))
{
// It is a bit tricky though, because we need to be careful!
// See how below that we are modifying the 'guess' array we get in?
// That means we would modify our previous solutions! No good!
// So here we need to return a copy
ArrayList<Integer> ans = cachedSolutions.get(n);
ArrayList<Integer> copy = new ArrayList<Integer>();
for (int i: ans) copy.add(i);
return copy;
}
ArrayList<Integer> best = null;
int bestInt = -1;
// THIS IS WRONG, can you figure out why it doesn't work?:
// for (int i = 1; i*i <= n; ++i)
for (int i = (int)Math.sqrt(n); i >= 1; --i)
{
// Check what happens if we use i^2 as part of our representation
ArrayList<Integer> guess = minLen(n - i*i);
// If we haven't selected a 'best' yet (best == null)
// or if our new guess is better than the current choice (guess.size() < best.size())
// update our choice of best
if (best == null || guess.size() < best.size())
{
best = guess;
bestInt = i;
}
}
best.add(bestInt);
// check... not needed unless you coded wrong
int sum = 0;
for (int i = 0; i < best.size(); ++i)
{
sum += best.get(i) * best.get(i);
}
if (sum != n)
{
throw new RuntimeException(String.format("n = %d, sum=%d, arr=%s\n", n, sum, best));
}
// New step: Save the solution to the global cache
cachedSolutions.put(n, best);
// Same deal as before... if you don't return a copy, you end up modifying your previous solutions
//
ArrayList<Integer> copy = new ArrayList<Integer>();
for (int i: best) copy.add(i);
return copy;
}
}
It took my program around ~5s to run for n = 100,000. Clearly there is more to be done if we want it to be faster, and to solve for larger n. The main issue now is that in storing the entire list of results of previous answers, we use up a lot of memory. And all of that copying! There is more you can do, like storing only an integer and a pointer to the subproblem, but I'll let you do that.
And by the by, 1000 = 30^2 + 10^2.
这篇关于如何改善这种code？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
