子集和 TI 基本编程

Question

我正在尝试对 TI-83 进行编程以进行子集和搜索。因此，给定一个长度为 N 的列表，我想找到给定长度为 L 的所有列表，其总和为给定值 V。

这与常规子集总和问题有点不同，因为我只搜索给定长度的子集，不是所有长度，并且递归不一定是首选，因为我无法调用我正在使用的程序。

我可以使用嵌套循环轻松完成任务，但是对于大于 L 的值来说，这变得很麻烦5. 我正在尝试动态解决方案，但一无所获。

实际上，此时，我只是想让列表引用正确，所以这就是我正在查看的内容。让我们举个例子：

L1={p,q,r,s,t,u}

让

N=6

我们寻找长度为 3 的所有子集以使其相对较短，因此 L = 3（6c3 = 20 个总输出）。

理想情况下，要搜索的列表引用是：

{1,2,3}
{1,2,4}
{1,2,5}
{1,2,6}
{1,3,4}
{1,3,5}
{1,3,6}
{1,4,5}
{1,4,6}
{1,5,6}
{2,3,4}
{2,3,5}
{2,3,6}
{2,4,5}
{2,4,6}
{2,5,6}
{3,4,5}
{3,4,6}
{3,5,6}
{4,5,6}

显然是通过以下方式完成的：

FOR A,1,N-2
    FOR B,A+1,N-1
        FOR C,B+1,N
            display {A,B,C}
        END
    END
END

我最初对 N 的数据进行降序排序，这使我能够搜索缩短搜索的条件，并且当我增加循环内 A、B 和 C 的值。

我也在寻找更好的动态解决方案。我在网上做了一些研究，但我似乎无法根据我的具体情况调整那里的内容。

任何帮助将不胜感激。我尽量保持简短，以免写小说，而是解释我想要表达的意思。我可以根据需要提供更多详细信息。

Answer 1

为了优化，您只需跳过搜索的那些子树，它们现在已经超过值 V。递归是可行的方法，但是，由于您已经排除了这种情况，因此您将最好对允许的深度设置上限。

我会选择这样的东西（深度为 3）：

N is the total number of array elements.
L is the desired length (3).
V is the desired sum
Y[] is the array
Z is the total

Z = 0
IF Z <= V
  FOR A,1,N-L
    Z = Z + Y[A]
    IF Z <= V
      FOR B,A+1,N-L+1
        Z = Z + Y[B]
        IF Z <= V
          FOR C,B+1,N-L+2
            Z = Z + Y[C]
            IF Z = V
              DISPLAY {A,B,C}
            END
            Z = Z - Y[C]
          END
        END
        Z = Z - Y[B]
      END
    END
    Z = Z - Y[A]
  END
END

现在这相当复杂，但它基本上在每个阶段都会检查您是否已经超过了所需的值，并且拒绝检查较低的子树作为效率衡量标准。它还保留当前级别的运行总计，以便在检查较低级别时不必进行大量添加。这是针对 Z 的数组值的加法和减法。

当您修改它以处理更多深度时（通过使用从 D 到 的变量，它会变得更加复杂。 >K 11 个级别（如果您愿意将 N 和 L 向下移动到 W 和 X，则可以更多 或者如果 TI BASIC 允许变量名中包含多个字符），

我能想到的唯一另一种非递归方法是使用一组值组来模拟迭代递归，这看起来很简单。只是稍微少了一些麻烦（尽管代码应该更少嵌套）。