混合等差/等比序列检测与分解算法问询及代码调试

问题背景 #

纯等差数列（如1,3,5,7,9...）或纯等比序列（如3,9,27,81...）的检测难度较低，但针对等差/等比混合序列，需要实现检测并分解出其中所有长度大于2的子序列。

示例 #

• 序列2 3 5 6 7 9 10 14，包含3个等差数列：(3 6 9)、(3 5 7 9)、(2 6 10 14)
• 序列2 3 4 8 9 16 27 32 81，包含2个等比数列：(2 4 8 16 32)、(3 9 27 81)
• 序列2 3 4 5 8 9 16 32，包含1个等比数列(2 4 8 16 32)和2个等差数列(2 3 4 5)、(3 5 7 9)

要求 #

原序列元素数量≤20个，需列出所有符合条件的子序列。

AutoIt代码调试问题 #

基于Abhinav Mathur算法编写的AutoIt代码目前所有输出结果均为-1，需排查并修复问题。原代码如下：

#include <Array.au3>

Func GetSequences(ByRef $arr)
    Local $arithmetic_seq[1], $geometric_seq[1]
    Local $n = UBound($arr)

    For $i = 0 To $n - 3
        For $j = $i + 1 To $n - 2
            Local $arithmetic = $arr[$i] & "|" & $arr[$j]
            Local $geometric = $arr[$i] & "|" & $arr[$j]
            Local $d = $arr[$j] - $arr[$i]
            Local $r = $arr[$j] / $arr[$i]

            $ArithTmp=$arr[$j]
            $GeoTmp=$arr[$j]
            For $k = $j + 1 To $n - 1
                If ($arr[$k] - $ArithTmp) = $d Then
                    $arithmetic &= "|" & $arr[$k]
                    $ArithTmp=$arr[$k]
                EndIf

                If $arr[$k] / $GeoTmp = $r Then
                    $geometric &= "|" & $arr[$k]
                    $GeoTmp=$arr[$k]
                EndIf
            Next

            If StringReplace($arithmetic, "|", "") <> $arr[$i] & $arr[$j] And StringLen($arithmetic) > 2 Then
                _ArrayAdd($arithmetic_seq, StringSplit($arithmetic, "|", 2))
            EndIf

            If StringReplace($geometric, "|", "") <> $arr[$i] & $arr[$j] And StringLen($geometric) > 2 Then
                _ArrayAdd($geometric_seq, StringSplit($geometric, "|", 2))
            EndIf
        Next
    Next

    ConsoleWrite("Sequences for " & _ArrayToString($arr) & @CRLF)
    ConsoleWrite("Arithmetic: " & @CRLF)
    _ArrayDisplay($arithmetic_seq)

    ; Clear the arithmetic sequence for the next iteration
    _ArrayDelete($arithmetic_seq, 1)

    ConsoleWrite("Geometric: " & @CRLF)
    _ArrayDisplay($geometric_seq)

    ; Clear the geometric sequence for the next iteration
    _ArrayDelete($geometric_seq, 1)
EndFunc

Local $sequence1[9] = [2, 3, 5, 6, 7, 8, 9, 10, 14]
Local $sequence2[9] = [2, 3, 4, 8, 9, 16, 27, 32, 81]
Local $sequence3[9] = [2, 3, 4, 5, 7, 8, 9, 16, 32]

Local $sequences[3] = [$sequence1, $sequence2, $sequence3]

For $i = 0 To UBound($sequences) - 1
    GetSequences($sequences[$i])
Next

代码问题分析 #

1. 数组初始化与分割参数错误
   • 初始数组$arithmetic_seq[1]和$geometric_seq[1]自带空元素，导致后续输出异常；StringSplit的第三个参数2会限制分割为2部分，无法得到完整子序列数组。
2. 等比序列浮点数精度问题
   • 使用除法判断公比时，浮点数误差会导致判断失效（如非整数公比的场景）。
3. 遍历范围过严
   • 外层循环$i = 0 To $n - 3限制过窄，会遗漏部分可能的子序列起始组合。
4. 无重复过滤逻辑
   • 不同起始对可能生成相同子序列，导致重复输出。

修复后的代码 #

#include <Array.au3>

Func GetSequences(ByRef $arr)
    Local $arithmetic_seq[0], $geometric_seq[0]
    Local $n = UBound($arr)

    For $i = 0 To $n - 2
        For $j = $i + 1 To $n - 1
            ; 处理等差数列
            Local $d = $arr[$j] - $arr[$i]
            Local $current_arith = [$arr[$i], $arr[$j]]
            Local $last = $arr[$j]
            For $k = $j + 1 To $n - 1
                If $arr[$k] - $last == $d Then
                    _ArrayAdd($current_arith, $arr[$k])
                    $last = $arr[$k]
                EndIf
            Next
            ; 长度>2且去重后添加
            If UBound($current_arith) > 2 Then
                Local $seq_str = _ArrayToString($current_arith, "|")
                Local $exists = False
                For $m = 0 To UBound($arithmetic_seq) - 1
                    If _ArrayToString($arithmetic_seq[$m], "|") == $seq_str Then
                        $exists = True
                        ExitLoop
                    EndIf
                Next
                If Not $exists Then
                    _ArrayAdd($arithmetic_seq, $current_arith)
                EndIf
            EndIf

            ; 处理等比数列，跳过0避免除零错误
            If $arr[$i] == 0 Or $arr[$j] == 0 Then ContinueLoop
            Local $r = $arr[$j] / $arr[$i]
            Local $current_geo = [$arr[$i], $arr[$j]]
            $last = $arr[$j]
            For $k = $j + 1 To $n - 1
                ; 用乘法+精度容差避免浮点数误差
                If Abs($arr[$k] - $last * $r) < 0.0001 Then
                    _ArrayAdd($current_geo, $arr[$k])
                    $last = $arr[$k]
                EndIf
            Next
            ; 长度>2且去重后添加
            If UBound($current_geo) > 2 Then
                Local $seq_str = _ArrayToString($current_geo, "|")
                Local $exists = False
                For $m = 0 To UBound($geometric_seq) - 1
                    If _ArrayToString($geometric_seq[$m], "|") == $seq_str Then
                        $exists = True
                        ExitLoop
                    EndIf
                Next
                If Not $exists Then
                    _ArrayAdd($geometric_seq, $current_geo)
                EndIf
            EndIf
        Next
    Next

    ConsoleWrite("序列: " & _ArrayToString($arr) & @CRLF)
    ConsoleWrite("等差数列:" & @CRLF)
    If UBound($arithmetic_seq) > 0 Then
        For $m = 0 To UBound($arithmetic_seq) - 1
            ConsoleWrite("(" & _ArrayToString($arithmetic_seq[$m], " ") & ")" & @CRLF)
        Next
    Else
        ConsoleWrite("无符合条件的等差数列" & @CRLF)
    EndIf
    ConsoleWrite("等比数列:" & @CRLF)
    If UBound($geometric_seq) > 0 Then
        For $m = 0 To UBound($geometric_seq) - 1
            ConsoleWrite("(" & _ArrayToString($geometric_seq[$m], " ") & ")" & @CRLF)
        Next
    Else
        ConsoleWrite("无符合条件的等比数列" & @CRLF)
    EndIf
    ConsoleWrite("------------------------" & @CRLF)
EndFunc

Local $sequence1[8] = [2, 3, 5, 6, 7, 9, 10, 14]
Local $sequence2[9] = [2, 3, 4, 8, 9, 16, 27, 32, 81]
Local $sequence3[8] = [2, 3, 4, 5, 8, 9, 16, 32]

Local $sequences[3] = [$sequence1, $sequence2, $sequence3]

For $i = 0 To UBound($sequences) - 1
    GetSequences($sequences[$i])
Next

修复说明 #

• 初始化空数组避免无效元素干扰输出
• 等差/等比序列逻辑拆分，可读性提升
• 等比序列改用乘法+精度容差解决浮点数精度问题
• 添加子序列去重逻辑，避免重复输出
• 调整遍历范围，覆盖所有可能的起始组合
• 优化控制台输出格式，直接打印结果而非依赖_ArrayDisplay

内容的提问来源于stack exchange，提问作者Chi-fung LAM