Ich kann dann ja auch mal meine Rekursion mit Backtracking anbringen
Der Vorteil ist, wenn eine kurze Ziffernfolge sich als falsch erweist, wird sie verworfen und die Untersuchung der Folge-Ziffern, die man damit auch noch bilden könnten, wird übersprungen (Backtracking)
VB.NET-Quellcode
- Public Sub Main(ParamArray args() As String)
- Dim sw = Diagnostics.Stopwatch.StartNew
- Dim nmbs = GetNumbsEDR()
- Console.WriteLine($"GetNumbsEDR: { nmbs.Count} Lösungen gefunden in {sw.ElapsedMilliseconds} ms")
- nmbs.ForEach(AddressOf Console.WriteLine)
- Console.ReadKey()
- End Function
- Private Function ComposeNumb(digits As Integer(), count As Integer) As Integer
- Dim result = 0
- For i = 0 To count - 1
- result = result * 10 + digits(i)
- Next
- Return result
- End Function
- Private Function GetNumbsEDR() As List(Of Integer)
- Dim result = New List(Of Integer)
- Dim digits = Enumerable.Range(1, 9).ToArray
- Dim recurse As Action(Of Integer) _
- = Sub(index)
- Dim divisor = index + 1
- For i = index To 8
- digits.Swap(index, i) ' ziffer am Index mit einer der Folge-Zahlen tauschen
- Dim testNumb = ComposeNumb(digits, divisor)
- If testNumb Mod divisor = 0 Then ' Regel wird eingehalten
- If divisor = 9 Then
- result.Add(testNumb) ' EndErgebnis
- Else
- recurse(divisor) ' ZwischenErgebnis, geeignet für rekursive Vertiefung
- End If
- End If
- digits.Swap(index, i) 'ziffern zurücktauschen, für den nächsten Versuch
- Next
- End Sub
- recurse(0)
- Return result
- End Function
- <Runtime.CompilerServices.Extension(), DebuggerStepThrough()>
- Public Sub Swap(items As IList, i1 As Integer, i2 As Integer)
- If i1 = i2 Then Return
- Dim Tmp = items(i1)
- items(i1) = items(i2)
- items(i2) = Tmp
- End Sub
Dieser Beitrag wurde bereits 3 mal editiert, zuletzt von „ErfinderDesRades“ ()