10.29 Поиск с возвратом

Сложная рекурсия, организация поиска с возвратом.

Разбор задачи UberPalindrome (в переложении на строку, так быстрее)

• Условие можно упростить: строка — это u-p, если она сама p, или если её начало — p, а конец — u-p.
• Алгоритм: цикл по всем возможным началам
  • если в начале стоит палиндром, а потом (рекурсивно!) — u-p, ответ готов
  • иначе — следующая итерация цикла

Задача о ферзях

Будем пользоваться не шахматной, а Сишной нотацией: вместо a…h / 1…8 используем индексы 0…7 / 0…7, т .е e2 — это 1:4 (но в целом это не важно)

• Два ферзя стоят на клетках y₀:x₀ и y₁:x₁ доски 8×8. Привести формулу из 4-x сравнений, которая проверяет, что они бьют друг друга (т. е. не находятся на одной вертикали, горизонтали или диагонали) x==x || y==y || x-y==x-y || x+y == x+y

• (предварительная) написать функцию check(x0, y0, x1, y1), которая принимает x₀, y₀, x₁, y₁, и возвращает, находятся ли два ферзя по этим координатам под боем друг друга. Написать программу для проверки, которая вводит x0, y0, x1, y1 и выводит check(x0, y0, x1, y1)

• Пусть в массиве int queens[H] индекс ячейки обозначает горизонталь, на которой стоит ферзь, а её содержимое — вертикаль, т. е. queens[2]=5 — это указание поставить ферзя на f3. Написать функцию checkto(k, queens), которая проверяет, что ферзь на горизонтали k / вертикали queens[k] не находится под боем предыдущих k ферзей. Написать программу для проверки, которая вводит несколько пар целых чисел — координат ферзей, заполняя queens, и затем — результат checkto(n, queens) (где n — количество введённых пар).

• Написать функцию putqueens(k, H, queens), в которой queens[0…k-1] считаются заданными, а queens[k…H-1] следует заполнить так, чтобы ферзи не били друг друга. Функция возвращает true, если сумел это сделать, и false в противоположном случае.

  • Очевидно, что putqueens(0, 8, queens) решит классическую задачу о ферзях

  • Алгоритм:
    • Основание рекурсии — k==H, все ферзи расставлены, вернуть true!
    • в цикле по всем столбцам проверить, можно ли
      1. Поставить ферзя в i-й столбец k-й строки
      2. После этого решить задачу для k+1
    • Если где-то было можно, вернуть true
    • Если нигде нельзя, вернуть false

• Бонусом: написать функцию вывода массива queens в виде шахматного поля. Пустая клетка — «[]», клетка с ферзём — «++»

Поиск шаблона

Примитивный шаблон может состоять из любых символов. Если в нём нет "*", строка называется сопоставимой шаблону, если она в точности ему равна. Спецсимвол "*" сопоставляется любому количеству любых символов, например, строка "a1234b" сопоставима шаблону "a*b".

• TODO примеры сопоставимых и несопоставимых пар для опроса аудитории

• Сопоставление

  1. Если шаблон начинается на символ и слово начинается на этот символ
     • Сопоставление удачно, если ли остаток шаблона сопоставим с остатком строки, неудачно в противном случае
  2. Если шаблон начинается на символ, а слово — на другой, сопоставление неудачно

  3. Если шаблон начинается на cпецсимвол "*"

     1. Цикл по максимально возможной длине строки, сопоставимой с "*" (от конца строки до 0)

        • Сопоставление удачно, если ли остаток шаблона сопоставим с остатком строки
     2. Сопоставление неудачно, если цикл не дал удачного сопоставления (завершился))

• Чуть-чуть поправить неуместную рекурсию (она всё равно останется неуместной, но это хорошее исправление):

  1. (замена п. 1) Если шаблон и слово имеют непустой общий префикс… (далее всё то же самое)

• Организовать поиск вместо сопоставления (шаблон может начинаться не с начала строки и заканчиваться не в концее)

Д/З (пока не готово)

TODO

1. Скорее всего. последнее задание (поиск вместо сопоставления)

2. TODO ещё что-то.