Número máximo de cuadrados que pueden caber en un triángulo isósceles de ángulo recto

Te dan un triángulo isósceles (un triángulo con al menos dos lados iguales) de ángulo recto con base b, necesitamos encontrar el número máximo de cuadrados de lado m, que se pueden ajustar en el triángulo dado.
Ejemplos: 
 

Input : b = 6, m = 2
Output : 3

Input : b = 4, m = 1
Output : 6

Consideremos un triángulo rectángulo XYZ, donde YZ es la base del triángulo. Suponga que la longitud de la base es b. Si consideramos la posición del primer cuadrado con el vértice Y, tendremos (b/m-1) cuadrados en la base, y nos quedará otro triángulo rectángulo isósceles con longitud de base (b – m).
Ilustración : 
 

Sea f(b, m) = Número de cuadrados que se pueden encajar en un triángulo con base de longitud b. 
entonces f(b, m) = (b / m – 1) + f(b – m, m) 
Podemos calcular f(b) usando la recursividad anterior, y con el uso de memorización. Más tarde podemos responder cada consulta en tiempo O(1). Podemos hacerlo para números pares e impares por separado con el caso base si (b < 2 * m) f(b, m) = 0.
La recursividad dada se puede resolver como:
f(b, m) = b / m – 1 + f(b – m, m) = b / m – 1 + (b – m) / m – 1 + f(b – 2m, m) 
f(b, m) = b / m – 1 + b / m – 2 + f(b – 3m, m) +…+ f(b – (b / m)m, m) 
f(b) = b / m – 1 + b / m – 2 + b / m – 3 +…..+ 1 + 0 
Con condiciones, si (b < 2 * m) f(b, m) = 0 
f(b) = suma de los primeros (b/m – 1) números naturales 
= (b/m – 1) * (b/m)/2 
Esta fórmula se puede utilizar para reducir la complejidad del tiempo hasta O(1).
 

// CPP program for finding maximum squares
// that can fit in right angle isosceles
// triangle
#include<bits/stdc++.h>
using namespace std;
 
// function for finding max squares
int maxSquare(int b, int m)
{
    // return in O(1) with derived
    // formula
    return (b / m - 1) * (b / m) / 2;
}
 
// driver program
int main()
{
    int b = 10, m = 2;
    cout << maxSquare (b,m);
    return 0;
}

// Java program for finding maximum squares
// that can fit in right angle isosceles
// triangle
public class GFG
{    
    // function for finding max squares
    static int maxSquare(int b, int m)
    {
        // return in O(1) with derived
        // formula
        return (b / m - 1) * (b / m) / 2;
    }
      
    // driver program
    public static void main(String args[])
    {
        int b = 10, m = 2;
        System.out.println(maxSquare (b,m));
    }
}
 
// This code is contribute by Sumit Ghosh

# Python3 program for
# finding maximum squares
# that can fit in
# right angle isosceles
# triangle
 
# function for finding max squares
def maxSquare(b, m):
  
    # return in O(1) with derived
    # formula
    return (b / m - 1) * (b / m) / 2
  
 
# driver program
b = 10
m = 2
print(int(maxSquare (b,m)))
 
# This code is contributed by
# Smitha Dinesh Semwal

// C# program for finding maximum squares
// that can fit in right angle isosceles
// triangle
using System;
 
public class GFG
{
    // function for finding max squares
    static int maxSquare(int b, int m)
    {
        // return in O(1) with derived
        // formula
        return (b / m - 1) * (b / m) / 2;
    }
     
    // driver program
    public static void Main()
    {
        int b = 10, m = 2;
        Console.WriteLine(maxSquare (b, m));
    }
}
 
// This code is contribute by vt_m

<?php
// PHP program for finding
// maximum squares that can
// fit in right angle isosceles
// triangle
 
// function for finding
// max squares
function maxSquare($b, $m)
{
     
    // return in O(1) with 
    // derived formula
    return ($b / $m - 1) *
           ($b / $m) / 2;
}
 
    // Driver Code
    $b = 10; $m = 2;
    echo maxSquare($b,$m);
// This code is contribute by vt_m
?>

<script>
 
// Javascript program for finding maximum squares
// that can fit in right angle isosceles
// triangle
 
// function for finding max squares
function maxSquare(b, m)
{
 
    // return in O(1) with derived
    // formula
    return (b / m - 1) * (b / m) / 2; a
}
 
// Driver program
  
    let b = 10, m = 2;
    document.write(maxSquare (b,m));
     
// This code is contributed by Mayank Tyagi
</script>

Producción: 
 

10

Complejidad del tiempo: O(1)

Espacio auxiliar: O(1)
Este artículo es una contribución de Shivam Pradhan (anuj_charm) . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.