66 lines
1.9 KiB
Text
66 lines
1.9 KiB
Text
Dim Shared As Integer minPasos 'minimal number of steps to get to 1
|
|
Dim Shared As Integer Subtractor '1 or 2
|
|
Dim Shared As Integer Ns(20000), Ops(20000), MinNs(20000), MinOps(20000)
|
|
|
|
Sub Reduce(N As Integer, Paso As Integer) 'Reduce N to 1, recording minimum steps
|
|
If N = 1 Then
|
|
If Paso < minPasos Then
|
|
For i As Integer = 0 To Paso-1
|
|
MinOps(i) = Ops(i)
|
|
MinNs(i) = Ns(i)
|
|
Next i
|
|
minPasos = Paso
|
|
End If
|
|
End If
|
|
If Paso >= minPasos Then Exit Sub 'don't search further
|
|
If N Mod 3 = 0 Then Ops(Paso) = 3 : Ns(Paso) = N/3 : Reduce(N/3, Paso+1)
|
|
If N Mod 2 = 0 Then Ops(Paso) = 2 : Ns(Paso) = N/2 : Reduce(N/2, Paso+1)
|
|
Ops(Paso) = -Subtractor
|
|
Ns(Paso) = N-Subtractor
|
|
Reduce(N-Subtractor, Paso+1)
|
|
End Sub
|
|
|
|
Sub ShowSteps(N As Integer) 'Show minimal steps and how N steps to 1
|
|
minPasos = 50000
|
|
Reduce(N, 0)
|
|
Print "N = " & N & " takes " & minPasos & " steps: N";
|
|
For i As Integer = 0 To minPasos-1
|
|
Print Iif(Sgn(MinOps(i)) < 0, " -", " /");
|
|
Print Abs(MinOps(i)) & "=>" & MinNs(i); '" "
|
|
Next i
|
|
Print
|
|
End Sub
|
|
|
|
Sub ShowCount(Range As Integer) 'Show count of maximum minimal steps and their Ns
|
|
Dim As Integer N, MaxSteps
|
|
MaxSteps = 0 'find maximum number of minimum steps
|
|
For N = 1 To Range
|
|
minPasos = 50000
|
|
Reduce(N, 0)
|
|
If minPasos > MaxSteps Then MaxSteps = minPasos
|
|
Next N
|
|
Print "Maximum steps:"; MaxSteps; " for N =";
|
|
For N = 1 To Range 'show numbers (Ns) for Maximum steps
|
|
minPasos = 50000
|
|
Reduce(N, 0)
|
|
If minPasos = MaxSteps Then Print N; '" ";
|
|
Next N
|
|
Print
|
|
End Sub
|
|
|
|
Dim As Integer N
|
|
Subtractor = 1 '1.
|
|
For N = 1 To 10
|
|
ShowSteps(N)
|
|
Next N
|
|
ShowCount(2000) '2.
|
|
ShowCount(20000) '2a.
|
|
|
|
Print
|
|
Subtractor = 2 '3.
|
|
For N = 1 To 10
|
|
ShowSteps(N)
|
|
Next N
|
|
ShowCount(2000) '4.
|
|
ShowCount(20000) '4a.
|
|
Sleep
|