javascript - 在 JS 中将纸张切割成最小数量的正方形

Question

我正在尝试从 https://www.geeksforgeeks.org/paper-cut-minimum-number-squares-set-2/ 转换算法 在 JavaScript 中。

我能够轻松地在 js ( https://www.geeksforgeeks.org/paper-cut-minimum-number-squares/ ) 中翻译第一个算法，但是贪婪的方法不够精确。

我在 js 和递归编程方面遇到了一些问题，在我第一次尝试时，我遇到了“超出最大调用堆栈大小”错误，因此我尝试使用 node --stack-size=10000 <app> 来引发它, 但在这种情况下，脚本不会输出任何内容。

这就是我现在拥有的:

// JS program to find minimum  
// number of squares  
// to cut a paper using Dynamic Programming  

const MAX = 300


let dp = new Array(MAX);

for (let i = 0; i < dp.length; i++) {
  dp[i] = new Array(MAX).fill(0);
}

// Returns min number of squares needed  
function minimumSquare(m, n) {

    // Initializing max values to  
    // vertical_min  
    // and horizontal_min 
    let vertical_min = 10000000000
    let horizontal_min = 10000000000


    // If the given rectangle is  
    // already a square  
    if (m === n) {
        return 1
    }

    // If the answer for the given rectangle is  
    // previously calculated return that answer  
    if (dp[m][n] !== 0) {
        return dp[m][n]
    }

    // The rectangle is cut horizontally and  
    // vertically into two parts and the cut  
    // with minimum value is found for every  
    // recursive call.  
    for (let i=1; i<m/2+1; i++) {
        // Calculating the minimum answer for the  
        // rectangles with width equal to n and length  
        // less than m for finding the cut point for  
        // the minimum answer 
        horizontal_min = Math.min(minimumSquare(i, n) + minimumSquare(m-i, n), horizontal_min)

    }

    for (let j=1; j<n/2+1; j++) {

        // Calculating the minimum answer for the  
        // rectangles with width equal to n and length  
        // less than m for finding the cut point for  
        // the minimum answer 
        vertical_min = Math.min(minimumSquare(m, j) + minimumSquare(m, n-j), vertical_min)

    }

    // Minimum of the vertical cut or horizontal 
    // cut to form a square is the answer 
    dp[m][n] = Math.min(vertical_min, horizontal_min) 
    return dp[m][n]

}

// Driver code 
    let m = 30
    let n = 35
    console.log(minimumSquare(m, n))

//This code is contributed by sahilshelangia 

预期结果是 m、n 维矩形中可能的最小正方形数。

例如，对于 30x15 的矩形，脚本将输出 2。

Answer 1

我添加了 2 个新条件来解决这个问题。那些是

• 如果 m 能被 n 整除则返回值 m/n
• 如果 n 能被 m 整除则返回值 n/m

const MAX = 300


let dp = new Array(MAX);

for (let i = 0; i < dp.length; i++) {
  dp[i] = new Array(MAX).fill(0);
}

// Returns min number of squares needed  
function minimumSquare(m, n) {
    // Initializing max values to  
    // vertical_min  
    // and horizontal_min 
    let vertical_min = 10000000000
    let horizontal_min = 10000000000


    // If the given rectangle is  
    // already a square  
    if (m === n) {
        return 1
    }

    // If the answer for the given rectangle is  
    // previously calculated return that answer  
    if (dp[m][n] !== 0) {
        return dp[m][n]
    }
    
    if(m%n==0){//if m is exactly divisible by n
      dp[m][n] = m/n
      return m/n;
    }
    
    if(n%m==0){//if n is exactly divisible by m
      dp[m][n] = n/m
      return n/m;
    }

    // The rectangle is cut horizontally and  
    // vertically into two parts and the cut  
    // with minimum value is found for every  
    // recursive call.  
    for (let i=1; i<m/2+1; i++) {
        // Calculating the minimum answer for the  
        // rectangles with width equal to n and length  
        // less than m for finding the cut point for  
        // the minimum answer 
        horizontal_min = Math.min(minimumSquare(i, n) + minimumSquare(m-i, n), horizontal_min)

    }

    for (let j=1; j<n/2+1; j++) {

        // Calculating the minimum answer for the  
        // rectangles with width equal to n and length  
        // less than m for finding the cut point for  
        // the minimum answer 
        vertical_min = Math.min(minimumSquare(m, j) + minimumSquare(m, n-j), vertical_min)

    }

    // Minimum of the vertical cut or horizontal 
    // cut to form a square is the answer 
    dp[m][n] = Math.min(vertical_min, horizontal_min) 
    return dp[m][n]

}

// Driver code 
    let m = 30
    let n = 35
    console.log(minimumSquare(m, n))