Создание игры классиков, чтобы увидеть, является ли она разрешимой или не разрешимой в

Question

Предположим, вам даны следующие цифры:
4 4 1 5 2 6 3 4 2 0

Число с квадратом вокруг него указывает, где вы сейчас находитесь.Вы можете двигаться влево или вправо по линии, перепрыгивая через количество пробелов, обозначенных числом, на котором вы стоите.Поэтому, если вы стоите на 4, вы можете прыгнуть либо влево на 4 пробела, либо вправо на 4 пробела.Вы не можете перепрыгнуть через любой конец линии.

Например, первое число (4) позволяет вам прыгать только вправо, поскольку слева нет цифр, к которым вы можете перейти.

Цель: вы хотите добраться до 0 в дальнем конце (справа) линии.Вам также гарантировано, что будет только один ноль, который, опять же, будет в крайней правой части.

Вы должны написать рекурсивную функцию, которая возвращает целое число 1 (для разрешимого) или 0 (для неразрешимого), указывающее, можете ли вы добраться до самого правого 0 или нет.

Answer 1

Вы должны написать рекурсивную функцию, которая возвращает целое число 1 (для разрешимого) или 0 (для неразрешимого),…

Рекурсия (информатика) - Википедия - хорошее начало:

Определение рекурсивной функции имеет один или несколько базовых случаев , что означает ввод (ы), для которых функция выдает результат тривиально (без повторения)) и один или несколько рекурсивных случаев , что означает ввод (ы), для которых программа повторяется (вызывает себя).

Базовые случаи:

• выпрыгнуть за пределы заданной линии квадратов → возврат 0
• прибыл на квадрат с номером 0 → возврат 1

Рекурсивный случай:

• return (решаемо для прыжка вправо ИЛИ решаемо для прыжка влево)

Краткий код C для этого:

int hops[] = { 4, 4, 1, 5, 2, 6, 3, 4, 2, 0 };
#define DIM(a)  sizeof a / sizeof *a

int solvable(int square)
{
    if (square < 0 || DIM(hops) <= square) return 0;    // past an end
    if (hops[square] == 0) return 1;                    // got to the 0
    return solvable(square+hops[square]) || solvable(square-hops[square]);
}

Первоначальный вызов начинается сквадрат с индексом 0: solvable(0).