Вопрос или проблема
Следующие две функции не дают правильный ответ для поиска последовательности из более чем 500 элементов. Функции должны генерировать последовательность чисел и количество в последовательности. Программа не требует этого, но предназначена для отладки с помощью вывода номеров последовательностей. Пример вывода представлен в сеансе ниже.
Цель этой программы — найти самую длинную цепочку чисел, генерируемую функциями.
Dim maxCollatz, i, curColl, maxI As Long
maxCollatz = 0
'Open "collatz.txt" For Output As #1
For i = 1 To 1000000
curColl = Collatz(i, 0)
'Print #1, i, " содержит цепочку с ", curColl, " последовательностью(ями). "
If (curColl > maxCollatz) Then
maxCollatz = curColl
maxI = i
End If
Next i
'Close #1
Print "Максимальная последовательность чисел Коллатца меньше 1000000 равна "; maxI; " с "; maxCollatz; "'й."
'Print Collatz(12345, 1); " количество найденных последовательностей Коллатца."
Function nextCollatz (num As Long)
If ((num& And 1) = 1) Then
nextCollatz = 3 * num& + 1
Else
nextCollatz = num& \ 2
End If
End Function
Function Collatz (num As Long, debug As Integer)
Rem $dynamic
Const BUF_SIZ = 512
Dim nxNum As Long
Dim nums(BUF_SIZ) As Long
Dim idx, i As Integer
idx = 0
nxNum = num
nums(idx) = nxNum
While (nxNum > 1)
nxNum = nextCollatz(nxNum)
idx = idx + 1
If (idx > BUF_SIZ) Then
Print "Длина цепочки превышает буфер"; num
ReDim _Preserve nums(idx)
End If
nums(idx) = nxNum
Wend
If (debug = 1) Then
Print "[";
For i = 0 To idx
Print nums(i); ", ";
Next i
Locate CsrLin, Pos(0) - 2
Print "]"
End If
Erase nums
Collatz = idx + 1
End Function
Вывод:
837797 содержит цепочку с 132 последовательностью(ями).
837798 содержит цепочку с 132 последовательностью(ями).
837799 содержит цепочку с 238 последовательностью(ями).
837800 содержит цепочку с 145 последовательностью(ями).
837801 содержит цепочку с 344 последовательностью(ями).
837802 содержит цепочку с 145 последовательностью(ями).
837803 содержит цепочку с 114 последовательностью(ями).
....
992280 содержит цепочку с 60 последовательностью(ями).
992281 содержит цепочку с 140 последовательностью(ями).
992282 содержит цепочку с 60 последовательностью(ями).
**992283 содержит цепочку с 502 последовательностью(ями)**.
992284 содержит цепочку с 122 последовательностью(ями).
992285 содержит цепочку с 122 последовательностью(ями).
Программа, использующая вышеприведенные функции, не может получить корректную самую длинную последовательность.
Ответ или решение
Для решения задачи поиска самой длинной последовательности чисел, сгенерированной функцией Коллатца, необходимо внести несколько изменений в изначальный код, чтобы он корректно обрабатывал большие последовательности чисел.
Основные проблемы:
- Переполнение буфера: Исходная реализация функции
Collatzиспользует статический массив фиксированного размера для хранения последовательности, что может вызвать ошибки при работе с большими числами. - Неэффективное использование памяти: Память для массива выделяется только единожды, что приводит к ошибкам при превышении заданного размера массива.
- Некорректный подсчет последовательностей: Требуется альтернативный подход для учета уже вычисленных значений последовательности.
Решение:
- Увеличим размер буфера или лучше используем динамический подход.
- Внедрим мемоизацию для хранения уже вычисленных длин последовательностей, что позволит избежать избыточных вычислений.
Обновленный код на Visual Basic:
Dim maxCollatz As Long, i As Long, curColl As Long, maxI As Long
maxCollatz = 0
For i = 1 To 1000000
curColl = Collatz(i)
If curColl > maxCollatz Then
maxCollatz = curColl
maxI = i
End If
Next i
Print "Максимальная последовательность чисел Коллатца для значений меньше 1000000: "; maxI; " с шириной "; maxCollatz; " элементов."
Function Collatz(num As Long) As Long
Dim count As Long
count = 0
Dim originalNum As Long
originalNum = num
' Используем словарь для хранения уже вычисленных последовательностей
Static memo As Object
If memo Is Nothing Then Set memo = CreateObject("Scripting.Dictionary")
Do While num > 1
' Проверяем, если уже встретили это число
If memo.Exists(num) Then
count = count + memo(num)
Exit Do
End If
count = count + 1
If (num Mod 2) = 0 Then
num = num \ 2
Else
num = 3 * num + 1
End If
Loop
' Сохраняем длину последовательности для начального числа
memo(originalNum) = count + 1
Collatz = memo(originalNum)
End FunctionОбъяснение кода:
- Мемоизация: Используем объект
Dictionaryдля хранения длины последовательности. Это значительно ускоряет вычисления для уже известных значений. - Цикл для вычисления Коллатца: Переписываем логику так, чтобы она учитывала результаты мемоизации.
- Ввод и вывод данных: Убрал ненужные переменные и связи, чтобы сделать код более чистым и понятным.
Заключение
С помощью предложенного кода, программа теперь сможет находить самые длинные последовательности Коллатца для чисел до 1 миллиона, исправляя ошибки исходной реализации. Она также более эффективно использует память благодаря мемоизации, что предотвращает повторные вычисления уже известных последовательностей.