在 Java 中使用堆栈进行长减法的(递归或非递归)算法的示例是什么?
What would be an example of a (either recursive or not) algorithm used to do long subtraction using stacks in Java?
我以前问过这个问题,但方式更复杂,我想我可能没说清楚。
假设我有两堆整数,每个整数代表一个整数,从一个字符串中解析出来。每个中的第一个是 1 的位置,第二个是 10 的位置,第三个是 100 的位置,等等。我很难解决这个问题,因为我觉得我需要递归地做,递归算法让我困惑,尤其是在这种情况下。感谢您的帮助。
int difference, z;
for (i = 0; i < length; i++)
{
x = firstNum.pop();
y = secondNum.pop();
difference = x - y;
if (difference < 0)
{
z = firstNum.pop();
firstNum.push(z - 1);
firstNum.push(x + 10);
}
else
{
result.push(difference);
}
}
你不需要递归但是你有一个错误。
int difference, z;
while (!firstNum.isEmpty ())
{
x = firstNum.pop();
y = 0;
if (!secondNum.isEmpty ()) // account for the case when secondNum has less digits
y = secondNum.pop();
difference = x - y;
if (difference < 0)
{
z = firstNum.pop();
firstNum.push(z - 1);
result.push(difference + 10); // fixed this line, since you want to push the
// difference to the result
}
else
{
result.push(difference);
}
}
现在,您应该注意到 result
堆栈中的数字将以相反的顺序排列。在减法结束时,最高有效位将位于堆栈的顶部。
这是一个带有硬编码示例输入的完整方法:
public static void subtract ()
{
Stack<Integer> firstNum = new Stack<Integer>();
Stack<Integer> secondNum = new Stack<Integer>();
Stack<Integer> result = new Stack<Integer>();
// firstNum == 3002
firstNum.push (3);
firstNum.push (0);
firstNum.push (0);
firstNum.push (2);
// secondNum == 129
secondNum.push (1);
secondNum.push (2);
secondNum.push (9);
int difference, z;
while (!firstNum.isEmpty ())
{
int x = firstNum.pop();
int y = 0;
if (!secondNum.isEmpty ())
y = secondNum.pop();
difference = x - y;
if (difference < 0)
{
z = firstNum.pop();
firstNum.push(z - 1);
result.push(difference + 10);
}
else
{
result.push(difference);
}
}
while (!result.isEmpty ())
System.out.print (result.pop ());
System.out.println ();
}
输出
2873
请注意,此方法假定第一个数字大于第二个数字。对于第一个数字较小的情况,应该添加一些处理。
我以前问过这个问题,但方式更复杂,我想我可能没说清楚。
假设我有两堆整数,每个整数代表一个整数,从一个字符串中解析出来。每个中的第一个是 1 的位置,第二个是 10 的位置,第三个是 100 的位置,等等。我很难解决这个问题,因为我觉得我需要递归地做,递归算法让我困惑,尤其是在这种情况下。感谢您的帮助。
int difference, z;
for (i = 0; i < length; i++)
{
x = firstNum.pop();
y = secondNum.pop();
difference = x - y;
if (difference < 0)
{
z = firstNum.pop();
firstNum.push(z - 1);
firstNum.push(x + 10);
}
else
{
result.push(difference);
}
}
你不需要递归但是你有一个错误。
int difference, z;
while (!firstNum.isEmpty ())
{
x = firstNum.pop();
y = 0;
if (!secondNum.isEmpty ()) // account for the case when secondNum has less digits
y = secondNum.pop();
difference = x - y;
if (difference < 0)
{
z = firstNum.pop();
firstNum.push(z - 1);
result.push(difference + 10); // fixed this line, since you want to push the
// difference to the result
}
else
{
result.push(difference);
}
}
现在,您应该注意到 result
堆栈中的数字将以相反的顺序排列。在减法结束时,最高有效位将位于堆栈的顶部。
这是一个带有硬编码示例输入的完整方法:
public static void subtract ()
{
Stack<Integer> firstNum = new Stack<Integer>();
Stack<Integer> secondNum = new Stack<Integer>();
Stack<Integer> result = new Stack<Integer>();
// firstNum == 3002
firstNum.push (3);
firstNum.push (0);
firstNum.push (0);
firstNum.push (2);
// secondNum == 129
secondNum.push (1);
secondNum.push (2);
secondNum.push (9);
int difference, z;
while (!firstNum.isEmpty ())
{
int x = firstNum.pop();
int y = 0;
if (!secondNum.isEmpty ())
y = secondNum.pop();
difference = x - y;
if (difference < 0)
{
z = firstNum.pop();
firstNum.push(z - 1);
result.push(difference + 10);
}
else
{
result.push(difference);
}
}
while (!result.isEmpty ())
System.out.print (result.pop ());
System.out.println ();
}
输出
2873
请注意,此方法假定第一个数字大于第二个数字。对于第一个数字较小的情况,应该添加一些处理。