Multiplication binaire - algorithme paysan - java, algorithme, récursivité

J'ai essayé la technique de multiplication binaire sur des nombres décimaux.

Algorithme:

Pour multiplier deux nombres décimaux x et y, écriseux à côté de chacun autre, comme dans l'exemple ci-dessous. Répétez ensuite les étapes suivantes: divisez le premier nombre par 2, arrondir le résultat (c’est-à-dire supprimer le: 5 si le nombre était impair) et doubler le deuxième numéro. Continuez jusqu'à ce que le premier nombre descende à 1. Puis biffez toutes les lignes. dans lequel le premier nombre est pair, et additionnez ce qui reste dans la deuxième colonne.

11 13

5 26

2 52

1 104

........

143 (réponse)

Code:

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;
}
}
}

Quelque chose ne va pas avec la récursion je pense mais je ne pouvais pas "trouver ce que c'est !!

Réponses:

4 pour la réponse № 1

Votre récursivité devrait être comme ça -

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);
}
}

---

5 pour la réponse № 2

Lors de la récursivité, n'utilisez pas de variables en dehors de la méthode récursive. C'est trop déroutant. Je veux dire que la méthode récursive doit être autonome. Voici une version de travail de votre programme:

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;
}
}

---

3 pour la réponse № 3

Je n'ai pas pu résister à le poster sur une seule ligne

public static int multiply(int x, int y) {
return ((x & 1) > 0 ? y : 0) + ((x & ~1) > 0 ? multiply(x >> 1, y << 1) : 0);
}

---

2 pour la réponse № 4

Je n'ai pas pu résister à ajouter une solution itérative: rapide, simple et valable également pour les arguments négatifs:

int product(int x, int y) {
boolean positive = x >= 0;
int p = 0;
while (x != 0) {
if (x % 2 != 0) p += y;
x /= 2;
y *= 2;
}
return positive ? p : -p;
}

---

2 pour la réponse № 5

Voici une implémentation Java simple qui multiplie sans opérateur de multiplication.

public static int multiply(int a, int b) {
int p = 0;
// If a is odd number.
if ((a & 1) > 0) {
p = b;
} //else use the default value in the p.

// If "a" contains any number larger than one
// than continue recursion.
if (a > 1)
p = p + multiply(a >> 1, b << 1);
return p;
}

---

0 pour la réponse № 6

public static int multiply(int x, int y) {
if (y == 0 || x == 0) {
return 0;
}
if (x == 1) {
return y;
} else {
return multiply(x >> 1, y << 1);
}
}

---