0

我正在解决大约 2 年前在我的课程中给出的一个测试，它得到了以下方法

public static void what(int n,int k,String s){
          if(k==0)
              System.out.println(s);
          else if(n>0){
              what(n-1,k,s);
              what(n-1,k-1,n+s);
          }
      }

现在，我在我的 IDE 上运行它，发现它打印了所有可能的 k 单元格和 n 个数字的组合。我也花时间用调试器来跟踪它，但我就是不明白它背后的逻辑是什么

我的意思是，作为开发人员，我该如何创建这样的递归。这个回溯背后的逻辑是什么

4

1 回答 1

0

描述

n = range of elements
k = population of each cell
s = solution so far

if the remaining population is 0
    print the solution
else
    if there are still elements available, search two cases:
        (1) Don't use **n** in the solution; recur.
        (2) Do use **n** in the solution; 
            decrease the population by 1 and recur.

调试

调试器非常适合查找逻辑流问题。对于全局，您有时需要收集更多数据以进行整体调查。坚持几个打印语句来跟踪逻辑，让它向你喷出几行输出。

对于函数，我建议第一个语句是打印以显示“ENTER”、函数名称（在这种情况下是冗余的）和参数。同时在决策点打印：跟踪递归步骤。

跟踪此例程

这是我跟踪问题时的输出，每个递归级别缩进 2 个空格：

   ENTER 4 3 
   RECUR without n
     ENTER 3 3 
     RECUR without n
       ENTER 2 3 
       RECUR without n
         ENTER 1 3 
         RECUR without n
           ENTER 0 3 
         RECUR using n
           ENTER 0 2 1
       RECUR using n
         ENTER 1 2 2
         RECUR without n
           ENTER 0 2 2
         RECUR using n
           ENTER 0 1 12
     RECUR using n
       ENTER 2 2 3
       RECUR without n
         ENTER 1 2 3
         RECUR without n
           ENTER 0 2 3
         RECUR using n
           ENTER 0 1 13
       RECUR using n
         ENTER 1 1 23
         RECUR without n
           ENTER 0 1 23
         RECUR using n
           ENTER 0 0 123
123
   RECUR using n
     ENTER 3 2 4
     RECUR without n
       ENTER 2 2 4
       RECUR without n
         ENTER 1 2 4
         RECUR without n
           ENTER 0 2 4
         RECUR using n
           ENTER 0 1 14
       RECUR using n
         ENTER 1 1 24
         RECUR without n
           ENTER 0 1 24
         RECUR using n
           ENTER 0 0 124
124
     RECUR using n
       ENTER 2 1 34
       RECUR without n
         ENTER 1 1 34
         RECUR without n
           ENTER 0 1 34
         RECUR using n
           ENTER 0 0 134
134
       RECUR using n
         ENTER 1 0 234
234
于 2017-02-28T17:45:19.040 回答