재귀 함수 수정에 대한 도움말

Question

캔버스를 생각하면 10x10이라고 가정하고 3 개의 직사각형/사각형이 제공됩니다.

캔버스 =

10 × 10 사각형 1 = 2 × 2 사각형 2 = 3 × 3 사각형 3 = 나는 캔버스에 모든 사각형의 모든 위치를 루프 재귀 함수를 만들었습니다,하고 작동

× 4 벌금. (나는 누군가가 그것을보고 싶어하는 다음 함수를 포함 시켰지만 그것이 필요하다고 생각하지는 않는다).

직사각형 1과 2는 회전 할 수없는 IE라는 것을 알 수 있습니다.이 중 하나를 90도 회전 시키면 본질적으로 같은 모양입니다. 그러나 직사각형 3은 회전 가능합니다.

모든 순환 게재와 함께 모든 직사각형의 모든 위치를 반복하도록 순환/순환 기능을 변경/구성하는 방법은 무엇입니까?

가능한 목표는 캔버스의 모든 모양을 피팅하는 것입니다.

도움 주셔서 감사합니다.

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 

Answer 1

같은 일을하고.

코드를 더 짧게 만들기 위해 validSolution 논리를 약간 변경했습니다. 이제 솔루션이 유효하지 않으며 recurse()가 시작될 때 isSolutionValid()를 확인할 필요가없는 경우 recurse를 호출하지 않습니다. 이러한 변경으로 인해 반복 횟수가 세게 계산되므로 코드를 제거했지만 나중에 추가 할 수 있어야합니다.

마지막 "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 

Answer 2

캔버스가 항상 정사각형 인 경우 많이 변경할 필요가 없습니다. 회전 된 사각형 3에 대한 결과는 캔버스의 원점이 다른 점을 제외하고는 회전되지 않은 것과 동일합니다. 직사각형 3을 회전하지 않고 캔버스를 다른 방향으로 90도 회전시키는 것을 상상해보십시오. 즉, 동일한 결과에 대한 몇 가지 수학을 사용하여 답을 얻을 수 있어야합니다.

Answer 3

(x, y) 좌표 루프를 자체 기능에 배치하십시오. 그런 다음 WxH 직사각형에 (x, y) 좌표 루프를 호출 한 다음 회전 된 사각형 HxW에서 다시 호출합니다.

또는 두 좌표를 모두 선택한 후 재귀 호출을 만들기 전에 직사각형의 두 회전에 (x, y) 루프를 분기 할 수 있습니다.

두 경우 모두 회전으로 인해 사각형이 테두리 상자의 높이 또는 너비를 초과하는지 조심해야합니다.

Answer 4

간단히 도형 목록을 스캔 할 수없고 사각형 인 경우 (SizeX != SizeY) { SizeX = source.SizeY, SizeY = source.SizeX } (예 : 회전 된 사각형)의 복제 된 사각형을 추가 할 수 있습니까?

물론 이것은 루프를 두 번 수행하는 것을 의미합니다 (회전되지 않은 모양 목록과 회전 된 목록에 대해 하나씩).

=> 당신이 솔루션은 비교적 쉽게 나온다 별도의 루틴에서 루프를 추출 할 경우

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

Answer 5

은 솔직히 나는 당신의 구현이되는 최선이지만 별도의 루틴을 큰 변화를 만들 수 있도록하지 않으려면 그냥 같은 기능 - 반복 두 번 사각형의 코드를 넣을 수 있다고 생각하지 않습니다 .

그래서 후 : 사각형이 사각형 (폭 <> 높이) 다음 (다음 코드에서) 다시 같은 코드를 복사 변경 sqRows 인 경우

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

[......] 

End If

  squareObjects(startPoint).removeSquare(canvas) 

당신은

을 체크 할 수 있습니다 placeSquareOnCanvas()에 sqCols가 있습니다.

재귀는 더 이상 직선이 아니며 각 직사각형에 대해 2 개의 재귀 분기를 만듭니다. 어쩌면 똑같은 코드를 2 번 복사하는 것이 좋지 않을 수도 있지만 그 결과는 맞을 것입니다. 코드를 변경하는 것이 최소한이며 코드를 기반으로하는이 똑 바른 해결책은 다른 조작을 시도하는 것보다 더 많은 성능을 제공합니다.