幫助修改遞歸函數

給定一個畫布，讓我們說10x10，並給出3個矩形/方塊。幫助修改遞歸函數

帆布= 10×10

矩形1 = 2×2矩形 2 = 3×3矩形 3 = 2x4的

我已經創建了循環在畫布上的每個矩形的每一個位置的遞歸函數，和它的工作原理精細。（我已經包括下面的功能，任何人都想看到它，但我不認爲這是必要的）。

我們可以看到矩形1和2是不可旋轉的IE，如果你將它們中的任何一個旋轉90度，它們本質上是相同的形狀。但矩形3是可旋轉的。

我該如何改變/構造循環/ recurisve函數，以便循環每個矩形的每個位置以及每個可能的旋轉？

目標是循環遍歷畫布上所有可能的形狀。

感謝您的幫助！

Sub recurse(ByVal startPoint As Integer) 

    Dim x As Integer 
    Dim y As Integer 
    Dim validSolution As Boolean = isSolutionValid() 
    Dim loopXTo As Integer 
    Dim loopYTo As Integer 
    Dim solutionRating As Integer 

    'If parent nodes create invalid solution, we can skip (375 iterations from 1,600 iterations saving) 
    If validSolution = True Then 

     If (startPoint = 0) Then 
      loopXTo = Math.Floor((canvasCols - squareObjects(startPoint).sqRows())/2) '576 iterations from 1,680 iterations 
      loopYTo = Math.Floor((canvasRows - squareObjects(startPoint).sqCols)/2)  '31,104 iterations from 90,720 iterations 
     Else 
      loopXTo = canvasCols - squareObjects(startPoint).sqRows 
      loopYTo = canvasRows - squareObjects(startPoint).sqCols 

     End If 

     'Loop all positions on canvas 
     For x = 0 To loopXTo 
      For y = 0 To loopYTo 

       'Set coords of square 
       squareObjects(startPoint).setSquareCords(x, y) 

       'Phyiscally place it in canvas 
       placeSquareOnCanvas(x, y, squareObjects(startPoint).sqRows, squareObjects(startPoint).sqCols) 

       'Recursive, get next square 
       If (startPoint + 1 < totalSquares) Then 
        recurse(startPoint + 1) 
       Else 
        validSolution = isSolutionValid() 

        'Is solution valud 
        If (validSolution = True) Then 
         solutions = solutions + 1 
        End If 

        iterations = iterations + 1 

        'Response.Write("<br /><b>Iteration " & iterations & "</b>") 
        If (validSolution) Then 

         'Rate solution, record if best 
         solutionRating = rateSolution() 
         If solutionRating > bestCellSaving Then 
          bestCellSaving = solutionRating 
          copySolution() 
         End If 
         'Response.Write(" <span style='color:green'> <B>VALID SOLUTION</B></span> (" & rateSolution() & ")") 
        End If 
        'printCanvas(canvas) 

       End If 

       squareObjects(startPoint).removeSquare(canvas) 

      Next 
     Next 
    End If 

End Sub

來源

2010-06-24 Tom Gullen

我添加了賞金，因爲我還沒有找到解決方案。爲了清楚起見，我試圖循環畫布上每個形狀的每一個位置（已經完成），但是我需要修改它，以便它在每次旋轉時循環每個形狀的每個位置。基本上，每個位置的組合！ – 2010-07-01 09:54:37

如果您在提取一個單獨的例程的環路中比較容易出現。

我已經改變了有效解決方案的邏輯，使代碼更短 - 現在如果解決方案無效，並且我們不需要在recurse（）的開頭檢查isSolutionValid（），現在我們不調用遞歸。這些更改使迭代難度更大，因此我刪除了該代碼，但應該可以稍後添加它。

沒有最後一個「If」語句的recurse（）例程的行爲應該與您的代碼完全相同。最後一個「If」語句基本上爲循環矩形執行循環。

我不確定removeSquare（）是如何實現的，但它可能需要知道方向才能正常工作。

Sub recurse(ByVal startPoint As Integer) 
    Dim loopXTo As Integer 
    Dim loopYTo As Integer 
    If (startPoint = 0) Then 
     loopXTo = Math.Floor((canvasCols - squareObjects(startPoint).sqRows)/2) 
     loopYTo = Math.Floor((canvasRows - squareObjects(startPoint).sqCols)/2) 
    Else 
     loopXTo = canvasCols - squareObjects(startPoint).sqRows 
     loopYTo = canvasRows - squareObjects(startPoint).sqCols 
    End If 
    fitSqare(loopXTo, loopYTo, False) 
    If (squareObjects(startPoint).sqCols <> squareObjects(startPoint).sqRows) Then 
     fitSqare(loopYTo, loopXTo, True) 
    End If 
End Sub 

Sub fitSquare(ByVal loopXTo As Integer, ByVal loopYTo As Integer, ByVal rotate As Boolean) 
    Dim x As Integer 
    Dim y As Integer 
    Dim solutionRating As Integer 
    Dim validSolution As Boolean 

    'Loop all positions on canvas 
    For x = 0 To loopXTo 
     For y = 0 To loopYTo 
      'Set coords of square 
      squareObjects(startPoint).setSquareCords(x, y) 

      'Phyiscally place it in canvas 
      If (rotate) Then 
       placeSquareOnCanvas(x, y, squareObjects(startPoint).sqCols, squareObjects(startPoint).sqRows) 
      Else 
       placeSquareOnCanvas(x, y, squareObjects(startPoint).sqRows, squareObjects(startPoint).sqCols) 
      End If 

      validSolution = isSolutionValid() 
      'Is solution valud 
      If (validSolution) Then 
       'Recursive, get next square 
       If (startPoint + 1 < totalSquares) Then 
        recurse(startPoint + 1) 
       Else 
        solutions = solutions + 1 
        'Rate solution, record if best 
        solutionRating = rateSolution() 
        If solutionRating > bestCellSaving Then 
         bestCellSaving = solutionRating 
         copySolution() 
        End If 
       End If 
      End If 
      squareObjects(startPoint).removeSquare(canvas) 'removeSquare may require additional work to handle rotated state 
     Next 
    Next 
End Sub

來源

2010-07-06 15:14:45 Kcats

如果畫布總是正方形，那麼您不需要改變太多。旋轉的矩形3的結果與未旋轉的相同，但Canvas的原點不同。想象一下，讓矩形3不旋轉並將畫布向另一個方向旋轉90度。這意味着你應該能夠使用相同結果的一些數學來得到你的答案。

來源

2010-06-24 08:57:53

謝謝，我意識到這類問題的鏡像屬性，並且已經爲此節約了成本，當現實存在多個矩形時，我將它作爲簡化問題呈現。我在尋找一個通用的解決方案。 – 2010-06-24 09:00:59

將你的（x，y）座標循環放在它自己的函數中。然後調用WxH矩形上的（x，y）座標循環，然後在旋轉的矩形HxW上再次調用它。

或者，您可以在兩個座標被選中之後，但在進行遞歸調用之前，在（x，y）循環內的矩形的兩個旋轉上放置分支。

在這兩種情況下，您都需要注意您的旋轉是否會導致矩形超出邊界框的高度或寬度。

來源

2010-06-24 22:47:11 Eric

難道你不能簡單地掃描形狀的列表和那些矩形（SizeX != SizeY）添加與{ SizeX = source.SizeY, SizeY = source.SizeX }（例如：旋轉矩形）的克隆矩形嗎？

這當然意味着要循環兩次（一個用於未旋轉的形狀列表，另一個用於旋轉的形狀）。

=>做這樣的事情

squareObjects(startPoint) = squareObjects(startPoint).Rotate(); 
recurse(startPoint);

來源

2010-07-05 15:26:32

坦白說，我不認爲你的實現是最有名，但如果你不想讓大的變化，使例程分開你可以把爲矩形的代碼兩次在同一個函數迭代。

所以經過：

'Phyiscally place it in canvas placeSquareOnCanvas(x, y, squareObjects(startPoint).sqRows, squareObjects(startPoint).sqCols)

 [......] 
 End If
   squareObjects(startPoint).removeSquare(canvas)

你可以做一個檢查

如果正方形是矩形（寬度<>高度）然後重新複製相同的代碼（在隨後的代碼）改變sqRows sqCols in placeSquareOnCanvas（）。

遞歸將不再是線性的，因爲這將爲每個矩形創建2個遞歸分支。也許這不是很好，寫了2次相同的代碼，但結果是正確的，代碼更改是最小的，基於代碼的這個直接的解決方案將比嘗試其他調整有更多的性能。

來源

2010-07-08 02:25:40 cripox

一定要第二次去除方塊 – cripox 2010-07-08 02:27:05

幫助修改遞歸函數

回答

相關問題