把纸切成最少的正方形-yiteyi-C++库

给定一张纸的大小，x B。任务是将纸切成任意大小的正方形。找出可以从纸上剪下的最小方块数。 例如：

null

Input  : 13 x 29Output : 9Explanation : 2 (squares of size 13x13) + 4 (squares of size 3x3) + 3 (squares of size 1x1)=9Input  : 4 x 5Output : 5Explanation : 1 (squares of size 4x4) + 4 (squares of size 1x1)

建议：请在“上解决” 实践 “首先，在讨论解决方案之前。

我们知道，如果我们想从纸上切下最少数量的正方形，那么我们必须先从纸上切下尽可能大的正方形，最大的正方形将与较小的正方形有相同的一面。例如，如果纸张尺寸为13 x 29，则最大正方形为13面。所以我们可以切割2个大小为13×13的正方形（29/13=2）。现在剩下的纸张尺寸为3 x 13。同样，我们可以使用4个3×3的正方形和3个1×1的正方形来切割剩余的纸张。因此，从尺寸为13 x 29的纸张上至少可以切割9个正方形。

dig1

以下是上述方法的实施情况。

C++

                         // C++ program to find minimum number of squares                       
                         // to cut a paper.                       
                         #include<bits/stdc++.h>                       
                         using                                     namespace                                     std;                       
           
                         // Returns min number of squares needed                       
                         int                                     minimumSquare(                                     int                                     a,                                     int                                     b)                       
                         {                       
                                                 long                                     long                                     result = 0, rem = 0;                       
           
                                                 // swap if a is small size side .                       
                                                 if                                     (a < b)                       
                                                 swap(a, b);                       
           
                                                 // Iterate until small size side is                       
                                                 // greater then 0                       
                                                 while                                     (b > 0)                       
                                                 {                       
                                                 // Update result                       
                                                 result += a/b;                       
           
                                                 long                                     long                                     rem = a % b;                       
                                                 a = b;                       
                                                 b = rem;                       
                                                 }                       
           
                                                 return                                     result;                       
                         }                       
           
                         // Driver code                       
                         int                                     main()                       
                         {                       
                                                 int                                     n = 13, m = 29;                       
                                                 cout << minimumSquare(n, m);                       
                                                 return                                     0;                       
                         }                       

JAVA

                         // Java program to find minimum                       
                         // number of squares to cut a paper.                       
                         class                                     GFG{                       
                                   
                         // To swap two numbers                       
                         static                                     void                                     swap(                                     int                                     a,                                     int                                     b)                       
                         {                       
                                                 int                                     temp = a;                       
                                                 a = b;                       
                                                 b = temp;                       
                         }                       
           
                         // Returns min number of squares needed                       
                         static                                     int                                     minimumSquare(                                     int                                     a,                                     int                                     b)                       
                         {                       
                                                 int                                     result =                                     0                                     , rem =                                     0                                     ;                       
           
                                                 // swap if a is small size side .                       
                                                 if                                     (a < b)                       
                                                 swap(a, b);                       
           
                                                 // Iterate until small size side is                       
                                                 // greater then 0                       
                                                 while                                     (b >                                     0                                     )                       
                                                 {                       
                                                 // Update result                       
                                                 result += a/b;                       
                                                 rem = a % b;                       
                                                 a = b;                       
                                                 b = rem;                       
                                                 }                       
           
                                                 return                                     result;                       
                         }                       
           
                         // Driver code                       
                         public                                     static                                     void                                     main(String[] args)                       
                         {                       
                                                 int                                     n =                                     13                                     , m =                                     29                                     ;                       
                                                 System.out.println(minimumSquare(n, m));                       
                         }                       
                         }                       
           
                         //This code is contributed by Smitha Dinesh Semwal.                       

Python3

                         # Python 3 program to find minimum                       
                         # number of squares to cut a paper.                       
           
                         # Returns min number of squares needed                       
                         def                                     minimumSquare(a, b):                       
           
                                                 result                                     =                                     0                       
                                                 rem                                     =                                     0                       
           
                                                 # swap if a is small size side .                       
                                                 if                                     (a < b):                       
                                                 a, b                                     =                                     b, a                       
           
                                                 # Iterate until small size side is                       
                                                 # greater then 0                       
                                                 while                                     (b >                                     0                                     ):                       
                                   
                                                 # Update result                       
                                                 result                                     +                                     =                                     int                                     (a                                     /                                     b)                       
           
                                                 rem                                     =                                     int                                     (a                                     %                                     b)                       
                                                 a                                     =                                     b                       
                                                 b                                     =                                     rem                       
           
                                                 return                                     result                       
           
                         # Driver code                       
                         n                                     =                                     13                       
                         m                                     =                                     29                       
           
                         print                                     (minimumSquare(n, m))                       
           
                         # This code is contributed by                       
                         # Smitha Dinesh Semwal                       

C#

                         // C# program to find minimum                       
                         // number of squares to cut a paper.                       
                         using                                     System;                       
                                   
                         class                                     GFG                       
                         {                       
                                   
                         // To swap two numbers                       
                         static                                     void                                     swap(                                     int                                     a,                                     int                                     b)                       
                         {                       
                                                 int                                     temp = a;                       
                                                 a = b;                       
                                                 b = temp;                       
                         }                       
           
                         // Returns min number of squares needed                       
                         static                                     int                                     minimumSquare(                                     int                                     a,                                     int                                     b)                       
                         {                       
                                                 int                                     result = 0, rem = 0;                       
           
                                                 // swap if a is small size side .                       
                                                 if                                     (a < b)                       
                                                 swap(a, b);                       
           
                                                 // Iterate until small size side is                       
                                                 // greater then 0                       
                                                 while                                     (b > 0)                       
                                                 {                       
                                                 // Update result                       
                                                 result += a / b;                       
                                                 rem = a % b;                       
                                                 a = b;                       
                                                 b = rem;                       
                                                 }                       
                                                 return                                     result;                       
                         }                       
           
                         // Driver code                       
                         public                                     static                                     void                                     Main(String[] args)                       
                         {                       
                                                 int                                     n = 13, m = 29;                       
                                                 Console.WriteLine(minimumSquare(n, m));                       
                         }                       
                         }                       
           
                         // This code is contributed by 29AjayKumar                       

Javascript

                         <script>                       
           
                         // Javascript program to find                       
                         // minimum number of squares                       
                         // to cut a paper.                       
           
                         // Returns min number of squares needed                       
                         function                                     minimumSquare(a, b)                       
                         {                       
                                                 let result = 0, rem = 0;                       
           
                                                 // swap if a is small size side .                       
                                                 if                                     (a < b) {                       
                                                 let temp = a;                       
                                                 a = b;                       
                                                 b = temp;                       
                                                 }                       
           
                                                 // Iterate until small size side is                       
                                                 // greater then 0                       
                                                 while                                     (b > 0)                       
                                                 {                       
                                                 // Update result                       
                                                 result += parseInt(a/b);                       
           
                                                 let rem = a % b;                       
                                                 a = b;                       
                                                 b = rem;                       
                                                 }                       
           
                                                 return                                     result;                       
                         }                       
           
                         // Driver code                       
                                                 let n = 13, m = 29;                       
                                                 document.write(minimumSquare(n, m));                       
           
                         </script>                       

输出：

请注意，上述贪婪的解决方案并不总是产生最佳结果 例如，如果输入为36 x 30，上述算法将产生输出6，但我们可以将纸张切成5个正方形 1）三个大小为12 x 12的正方形 2）两个大小为18×18的正方形。感谢Sergey V.Pereslavtsev指出上述情况。本文由 库尔德普·辛格（库利·杜·编码员） .如果你喜欢GeekSforgek，并想贡献自己的力量，你也可以使用写极客。组织或者把你的文章寄去评论-team@geeksforgeeks.org.看到你的文章出现在Geeksforgeks主页上，并帮助其他极客。如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请写下评论。

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

THE END

技术文章