0

所以我试图对超立方体提出递归解决方案，其中步行方法允许您步行到超立方体中的每个点。例如，如果你放 walk(3) 控制台应该输出：

000, 001, 011, 010, 110, 111, 101, 100

我已经使用灰码为这个问题制定了一个迭代解决方案，因为我的心态是每个点距离另一个点只有 1 位，所以我只需要在每个循环中移位一次。然后我尝试以递归的方式做同样的事情。我不允许使用数组、列表、堆栈等任何类型的问题，这是我提出的递归解决方案：

递归解决方案：

   public static void recursiveWalk(int n)
   {
      if (n < 1)
      {
         System.out.print("no");
      }
      else
      {
         String ass = "";
         recursiveWalkHelper(n, 0, ass);
         System.out.print(ass);
      }
   }

   public static void recursiveWalkHelper(int n, int i, String str)
   {
      int N = 1 << n;

      if (i < N)
      {
         int x = i ^ (i >> 1);
         getGrayCode(x, n, str, 0, 0, 0);
         System.out.println();
         i++;
         recursiveWalkHelper(n, i, str);
      }
      return;
   }

   public static void getGrayCode(int x, int n, String str, int i, int j, int k)
   {

      if (x > 0)
      {
         str = str + x % 2;
         x = x / 2;
         i++;
         getGrayCode(x, n, str, i, j, k);
      }

      if (j < n - i)
      {
         System.out.print('0');
         j++;
         getGrayCode(x, n, str, i, j, i - 1);
         return;
      }

      if (k >= 0)
      {
         System.out.print(str.charAt(k));
         i--;
         getGrayCode(x, n, str, i, j, k);
         return;
      }

      return;
   }

但是，当我将 recursiveWalk(3) 放入 main 时，代码的输出如下：

000
00100010
0101001010010101010
0100001000000000000
0010000010000110001100000000000000000000000
1010101010100110101101001101011010110101010
1000101000100000100001001101011010110101010
0000000000000000000000000000000000000000000

这不是我所期待的。我想强调一下，我并不打算使用任何形式的问题，所以我只使用了字符串和简单的打印输出

这是我提出的可行的迭代解决方案：

   static void iterativehelper(int x, int n)
   {
      String ass = "";
      int i = 0;

      for (i = 0; x > 0; i++)
      {
         ass = ass + x % 2;
         x = x / 2;
      }

      // leftmost digits are
      // filled with 0
      for (int j = 0; j < n - i; j++)
      {
         System.out.print('0');
      }

      for (int j = i - 1; j >= 0; j--)
      {
         System.out.print(ass.charAt(j));
      }
   }

   // Function to generate
   // gray code
   static void iterative(int n)
   {
      int N = 1 << n;
      for (int i = 0; i < N; i++)
      {
         // generate gray code of
         // corresponding binary
         // number of integer i.
         int x = i ^ (i >> 1);

         // printing gray code
         iterativehelper(x, n);
         System.out.println();
      }
   }
4

0 回答 0