Напечатайте либо True, либо False - PullRequest
Новая
       27

Напечатайте либо True, либо False

0 голосов
/ 19 февраля 2019

Учитывая массив целых чисел, m = количество ходов.Начиная с индекса 0. С каждым ходом вы можете сделать arr [i] шагов вперед или назад.если m становится 0. и вы находитесь на последней позиции, то выведите true, иначе выведите false.

Например: arr содержит элементы 2,3,1.м = 1;ответ: верно;Объяснение: значение при i = 0 равно 2, поэтому при m = 1 сделайте 2 шага вперед, и вы достигнете конечной позиции.Итак, true.

Я попробовал приведенный ниже код, но он не печатает правильный ответ: num_ele - общее количество элементов в массиве. 

bool fun(int arr[],int m,int i,int num_ele)
{
    if(m==0)
    {
        if(i==(num_ele)
            return true;
        else
            return false;
    }
    fun(arr,m-1,i+arr[i],num_ele);
    fun(arr,m-1,i-arr[i],num_ele);
}

Ответы [ 2 ]

0 голосов
/ 19 февраля 2019

Реализация может быть выполнена следующим образом с использованием синтаксиса C #. 

bool fun(int[] arr, int m, int i)
{
    if (0 == m)            // base case - if no moves are left, decide
    {                      // whether the end of the array is reached
        return i == arr.Length-1 ;
    }
    else
    {
        int LeftPos = i+arr[i];
        int RightPos = i-arr[i];
        bool ResultLeft = 0 <= LeftPos
                       && LeftPos =< arr.Length-1
                       && fun(arr, m-1, LeftPos);
        bool ResultRight = 0 <= RightPos
                        && RightPos =< arr.Length-1
                        && fun(arr, m-1, RightPos);
        return ResultLeft || ResultRight;
    }
}

Реализация выполняет некоторую проверку границ, чтобы проверить, будет ли полученная позиция по-прежнему находиться внутри массива.Обратите внимание, что можно сократить оценку;если один из рекурсивных вызовов возвратит true, оценка другого вызова не будет необходимой.При этом проверка индекса может быть сделана первой в вызове;следовательно, реализация выиграет от кратковременного поведения оператора || следующим образом. 

bool fun(int[] arr, int m, int i)
{
    if (i < 0 || i > arr.Length-1) // index checking
    {
        return false;
    }
    else
    {
      if (0 == m)            // base case - if no moves are left, decide
      {                      // whether the end of the array is reached
          return i == arr.Length-1 ;
      }
      else                   // compund case - decide whether moving left
      {                      // or right yields the end position
          return fun(arr, m-1, i+arr[i]) || fun(arr, m-1, i-arr[i]);
      }
    }
}
0 голосов
/ 19 февраля 2019

Эта задача эквивалентна задаче определения того, принимает ли детерминированный конечный автомат над двоичным алфавитом строку длины m.Чтобы построить автомат, добавьте столько состояний, сколько элементов массива, и два перехода, чтобы представить перемещение влево или вправо на соответствующее количество позиций.Сделайте состояние, соответствующее последнему принимаемому элементу массива, и сделайте состояние, соответствующее первому элементу массива, начальным состоянием.

Затем создайте детерминированный конечный автомат, который принимает все двоичные строки длины ровно n.Этот DFA будет иметь n + 1 состояний, одно начальное состояние и одно принимающее состояние.

Затем создайте DFA для пересечения языков этих DFA, используя конструкцию Cartesian Product Machine.Этот DFA будет иметь одно состояние для каждой пары состояний из двух вышеупомянутых DFA, начнется в состоянии, соответствующем паре начальных состояний, и завершится в состоянии, соответствующем паре принимающих состояний.

Наконец, определите, является ли язык этого DFA пустым языком или нет.Достаточно поиска в ширину или глубину или минимизацию с последующим сравнением с DFA для пустого языка.

Вы начинаете с двух DFA, имеющих состояния n и n + 1;построить DFA с n (n + 1) состояниями;а затем посмотреть, принимает ли он строки.Сложность должна быть O (n ^ 2).

...