Haciendo uso de la recursividad, podemos multiplicar dos enteros con las restricciones dadas.
Para multiplicar x e y, suma recursivamente xy veces.
Acercarse:
Como no podemos usar ninguno de los símbolos dados, la única forma que queda es usar la recursividad, con el hecho de que x debe sumarse a xy veces.
Caso base: cuando el número de veces que se tiene que sumar x se convierte en 0.
Llamada recursiva: si no se cumple el caso base, agregue x al valor resultante actual y páselo a la siguiente iteración.
C++
// C++ program to Multiply two integers without
// using multiplication, division and bitwise
// operators, and no loops
#include<iostream>
using namespace std;
class GFG
{
/* function to multiply two numbers x and y*/
public : int multiply(int x, int y)
{
/* 0 multiplied with anything gives 0 */
if(y == 0)
return 0;
/* Add x one by one */
if(y > 0 )
return (x + multiply(x, y-1));
/* the case where y is negative */
if(y < 0 )
return -multiply(x, -y);
}
};
// Driver code
int main()
{
GFG g;
cout << endl << g.multiply(5, -11);
getchar();
return 0;
}
// This code is contributed by SoM15242
C
#include<stdio.h>
/* function to multiply two numbers x and y*/
int multiply(int x, int y)
{
/* 0 multiplied with anything gives 0 */
if(y == 0)
return 0;
/* Add x one by one */
if(y > 0 )
return (x + multiply(x, y-1));
/* the case where y is negative */
if(y < 0 )
return -multiply(x, -y);
}
int main()
{
printf("\n %d", multiply(5, -11));
getchar();
return 0;
}
Java
class GFG {
/* function to multiply two numbers x and y*/
static int multiply(int x, int y) {
/* 0 multiplied with anything gives 0 */
if (y == 0)
return 0;
/* Add x one by one */
if (y > 0)
return (x + multiply(x, y - 1));
/* the case where y is negative */
if (y < 0)
return -multiply(x, -y);
return -1;
}
// Driver code
public static void main(String[] args) {
System.out.print("\n" + multiply(5, -11));
}
}
// This code is contributed by Anant Agarwal.
Python3
# Function to multiply two numbers # x and y def multiply(x,y): # 0 multiplied with anything # gives 0 if(y == 0): return 0 # Add x one by one if(y > 0 ): return (x + multiply(x, y - 1)) # The case where y is negative if(y < 0 ): return -multiply(x, -y) # Driver code print(multiply(5, -11)) # This code is contributed by Anant Agarwal.
C#
// Multiply two integers without
// using multiplication, division
// and bitwise operators, and no
// loops
using System;
class GFG {
// function to multiply two numbers
// x and y
static int multiply(int x, int y) {
// 0 multiplied with anything gives 0
if (y == 0)
return 0;
// Add x one by one
if (y > 0)
return (x + multiply(x, y - 1));
// the case where y is negative
if (y < 0)
return -multiply(x, -y);
return -1;
}
// Driver code
public static void Main() {
Console.WriteLine(multiply(5, -11));
}
}
// This code is contributed by vt_m.
PHP
<?php
// function to multiply
// two numbers x and y
function multiply($x, $y)
{
/* 0 multiplied with
anything gives 0 */
if($y == 0)
return 0;
/* Add x one by one */
if($y > 0 )
return ($x + multiply($x,
$y - 1));
/* the case where
y is negative */
if($y < 0 )
return -multiply($x, -$y);
}
// Driver Code
echo multiply(5, -11);
// This code is contributed by mits.
?>
Javascript
<script>
// javascript program to Multiply two integers without
// using multiplication, division and bitwise
// operators, and no loops
/* function to multiply two numbers x and y*/
function multiply( x, y)
{
/* 0 multiplied with anything gives 0 */
if(y == 0)
return 0;
/* Add x one by one */
if(y > 0 )
return (x + multiply(x, y-1));
/* the case where y is negative */
if(y < 0 )
return -multiply(x, -y);
}
// Driver code
document.write( multiply(5, -11));
// This code is contributed by todaysgaurav
</script>
Producción
-55
Complejidad de tiempo: O(y) donde y es el segundo argumento de la función multiplicar().
Espacio auxiliar: O(y) para la pila de recursión
Otro enfoque: el problema también se puede resolver usando la propiedad matemática básica
(a+b) 2 = un 2 + b 2 + 2a*b
⇒ a*b = ((a+b) 2 – a 2 – b 2 ) / 2
Para calcular el cuadrado de números, podemos usar la función de potencia en C++ y para dividir por 2 en la expresión anterior podemos escribir una función recursiva.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to Multiply two integers without
// using multiplication, division and bitwise
// operators, and no loops
#include<bits/stdc++.h>
using namespace std;
// divide a number by 2 recursively
int divideby2(int num)
{
if(num<2)
return 0;
return 1 + divideby2(num-2);
}
int multiply(int a,int b)
{
int whole_square=pow(a+b,2);
int a_square=pow(a,2);
int b_square=pow(b,2);
int val= whole_square- a_square - b_square;
int product;
// for positive value of variable val
if(val>=0)
product = divideby2(val);
// for negative value of variable val
// we first compute the division by 2 for
// positive val and by subtracting from
// 0 we can make it negative
else
product = 0 - divideby2(abs(val));
return product;
}
// Driver code
int main()
{
int a=5;
int b=-11;
cout << multiply(a,b);
return 0;
}
// This code is contributed by Pushpesh raj.
Java
// Java program to Multiply two integers without
// using multiplication, division and bitwise
// operators, and no loops
import java.util.*;
class GFG {
// divide a number by 2 recursively
static int divideby2(int num)
{
if (num < 2)
return 0;
return 1 + divideby2(num - 2);
}
static int multiply(int a, int b)
{
int whole_square = (int)Math.pow(a + b, 2);
int a_square = (int)Math.pow(a, 2);
int b_square = (int)Math.pow(b, 2);
int val = whole_square - a_square - b_square;
int product;
// for positive value of variable val
if (val >= 0)
product = divideby2(val);
// for negative value of variable val
// we first compute the division by 2 for
// positive val and by subtracting from
// 0 we can make it negative
else
product = 0 - divideby2(Math.abs(val));
return product;
}
// Driver code
public static void main(String[] args)
{
int a = 5;
int b = -11;
System.out.println(multiply(a, b));
}
}
// This code is contributed by phasing17
Python3
# Python3 program to Multiply two integers without # using multiplication, division and bitwise # operators, and no loops # divide a number by 2 recursively def divideby2(num): if(num < 2): return 0 return 1 + divideby2(num-2) def multiply(a, b): whole_square = (a + b) ** 2 a_square = pow(a, 2) b_square = pow(b, 2) val = whole_square - a_square - b_square # for positive value of variable val if(val >= 0): product = divideby2(val) # for negative value of variable val # we first compute the division by 2 for # positive val and by subtracting from # 0 we can make it negative else: product = 0 - divideby2(abs(val)) return product # Driver code a = 5 b = -11 print(multiply(a, b)) # This code is contributed by phasing17
C#
// C# program to Multiply two integers without
// using multiplication, division and bitwise
// operators, and no loops
using System;
class GFG {
// divide a number by 2 recursively
static int divideby2(int num)
{
if (num < 2)
return 0;
return 1 + divideby2(num - 2);
}
static int multiply(int a, int b)
{
int whole_square = (int)Math.Pow(a + b, 2);
int a_square = (int)Math.Pow(a, 2);
int b_square = (int)Math.Pow(b, 2);
int val = whole_square - a_square - b_square;
int product;
// for positive value of variable val
if (val >= 0)
product = divideby2(val);
// for negative value of variable val
// we first compute the division by 2 for
// positive val and by subtracting from
// 0 we can make it negative
else
product = 0 - divideby2(Math.Abs(val));
return product;
}
// Driver code
public static void Main(string[] args)
{
int a = 5;
int b = -11;
Console.WriteLine(multiply(a, b));
}
}
// This code is contributed by phasing17
Javascript
// JavaScript program to Multiply two integers without
// using multiplication, division and bitwise
// operators, and no loops
// divide a number by 2 recursively
function divideby2(num)
{
if(num<2)
return 0;
return 1 + divideby2(num-2);
}
function multiply(a, b)
{
let whole_square = Math.pow(a+b,2);
let a_square = Math.pow(a,2);
let b_square = Math.pow(b,2);
let val = whole_square- a_square - b_square;
let product;
// for positive value of variable val
if(val>=0)
product = divideby2(val);
// for negative value of variable val
// we first compute the division by 2 for
// positive val and by subtracting from
// 0 we can make it negative
else
product = 0 - divideby2(Math.abs(val));
return product;
}
// Driver code
let a = 5;
let b = -11;
console.log(multiply(a,b));
// This code is contributed by phasing17
Producción
-55
Campesino ruso (Multiplique dos números usando operadores bit a bit)
Escriba comentarios si encuentra que alguno de los códigos/algoritmos anteriores es incorrecto, o encuentre mejores formas de resolver el mismo problema.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA