Создание GreyCode рекурсивно - PullRequest
Новая
       37

Создание GreyCode рекурсивно

0 голосов
/ 14 февраля 2020

поэтому я пытаюсь найти рекурсивное решение для гиперкуба, где метод обхода позволяет вам пройти к каждой точке гиперкуба. например, если вы поставите walk (3), консоль должна вывести: 

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

Я сделал итеративное решение этой проблемы, используя greycode, так как я придерживался того мнения, что каждая точка находится на расстоянии всего 1 бита с другой стороны, так что мне просто нужно сдвигать бит один раз каждые l oop. Затем я попытался сделать то же самое, но рекурсивным способом. Мне не разрешено использовать массивы, списки, стеки и т. Д. c любого типа квеста, и вот что я выбрал в качестве моего рекурсивного решения:

Рекурсивное решение: 

   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) в основную часть, код выводится следующим образом: 

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();
      }
   }
...