直角等腰三角形中可容纳的最大正方形数-yiteyi-C++库

给你一个等腰三角形（一个至少有两条等边的三角形）一个以b为底的直角三角形，我们需要求出m边的最大平方数，它可以拟合到给定的三角形中。例如：

null

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

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

推荐：请尝试你的方法 {IDE} 首先，在进入解决方案之前。

让我们考虑一个直角三角形XYZ，其中YZ是三角形的基础。假设基的长度是B。如果我们考虑第一个正方形与顶点Y的位置，我们将有（B/M-1）方块在基部，我们将剩下另一个等腰直角三角形，具有基长度（B-M）。 插图：

Maximum number of squares that can fit in a right angle isosceles triangle

设f（b，m）=可以拟合成基长为b的三角形的正方形数。然后 f（b，m）=（b/m-1）+f（b-m，m） 我们可以使用上面的递归和记忆来计算f（b）。之后，我们可以在O（1）时间内回答每个问题。如果（b<2*m）f（b，m）=0，我们可以分别对偶数和奇数进行计算。给定的递归可通过以下方式解决： 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 有条件时，如果（b<2*m）f（b，m）=0 f（b）=第一（b/m–1）个自然数之和 =（b/m–1）*（b/m）/2 该公式可用于将时间复杂度降低到O（1）。

C++

                         // 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

                         // 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

                         # 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#

                         // 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                       
                         // 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                       
                         ?>                       

Javascript

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

输出：

本文由 希瓦姆·普拉丹（anuj_charm） .如果你喜欢GeekSforgek，并想贡献自己的力量，你也可以使用写极客。组织或者把你的文章寄去评论-team@geeksforgeeks.org.看到你的文章出现在Geeksforgeks主页上，并帮助其他极客。如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请写下评论。

文章版权归作者所有，未经允许请勿转载。

THE END

技术文章