二进制乘法--农民算法
二进制乘法--农民算法
提问于 2011-11-05 16:11:36
我尝试了十进制数的二进制乘法技术。
算法：
要将两个十进制数x和y相乘，请将它们放在一起，如下例所示。然后重复以下步骤:将第一个数字除以2，向下舍入结果(即，如果数字是奇数，则去掉:5 )，然后将第二个数字加倍。继续下去，直到第一个数字降到1。然后删除第一个数字为偶数的所有行，并将第二列中剩余的行相加。
11 13
5 26
2 52
1104
.
143 (答案)
代码：
class Multiply
{
static int temp;
static int sum;
public static void main(String[] args)
{
int x = Integer.parseInt(args[0]);
int y = Integer.parseInt(args[1]);
int ans = multiply(x , y);
System.out.println(ans);
}
public static int multiply(int x, int y)
{
if(x==1)
{
System.out.println(x+" : "+y);
return y;
}
temp = multiply(x/2, y*2);
if(x%2==0)
{
System.out.println(x+" : "+y);
return temp;
}
else
{
System.out.println(x+" : "+y);
sum = sum+temp;
return sum;
}
}
}我认为递归有问题，但我找不到它是什么！！
回答 6
Stack Overflow用户
回答已采纳
发布于 2011-11-05 16:26:01
你的递归应该是这样的-
public class Multiply {
static int temp = 0;
static int sum = 0;
public static void main(String[] args) {
int x = Integer.parseInt("11");
int y = Integer.parseInt("9");
int ans = multiply(x, y);
System.out.println(ans);
}
public static int multiply(int x, int y) {
if (x == 1) {
System.out.println(x + " : " + y);
return sum + y;
}
if (x % 2 == 0) {
System.out.println(x + " : " + y);
} else {
System.out.println(x + " : " + y);
sum = sum + y;
}
return multiply(x / 2, y * 2);
}
}Stack Overflow用户
发布于 2011-11-05 16:26:55
当使用递归时，不要使用递归方法之外的变量。这太令人困惑了。我的意思是递归方法应该是自包含的。以下是您的程序的工作版本：
public class Main {
public static void main(String[] args) {
int x = 11;
int y = 13;
int ans = multiply(x, y);
System.out.println(ans);
}
public static int multiply(int x, int y) {
if (x == 1) {
return y;
}
int temp = multiply(x / 2, y * 2);
if (x % 2 != 0) {
temp += y;
}
return temp;
}
}Stack Overflow用户
发布于 2011-11-05 16:43:25
我忍不住把它放在一行中。
public static int multiply(int x, int y) {
return ((x & 1) > 0 ? y : 0) + ((x & ~1) > 0 ? multiply(x >> 1, y << 1) : 0);
}页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/8018986
复制相关文章
相似问题
腾讯云开发者
