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

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

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

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

• Два ферзя стоят на клетках 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 ферзей. Написать программу для проверки, которая вводит несколько целых чисел — вертикальные координаты ферзей, горизонтальные координаты которых равны соответственно 0, 1, 2.. , заполняя queens, и затем — результат checkto(n-1, queens) (где n — количество введённых чисел).

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

• Написать функцию 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

Минутка отдыха

• Что такое argc/argv? Кто знает — не говорите!

     1 #include <stdio.h>
     2 
     3 int main(int argc, char *argv[]) {
     4         for(int i=0; i< argc; i++)
     5                 puts(argv[i]);
     6         return 0;
     7 }
  

• (если будет время) Переписать программу расстановки N ферзей с вводом N из командной строки с помощью atoi()

FIXME Остановились здесь

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

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

• вопрос к аудитории: каким шаблонам соответствует строка "abcdef" ?

  • "a*c*f"

  • "ab*df"

  • "a*"

  • "*f"

  • "*cd*"

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

  int pattmatch(char *str, char *patt) { if (*str == 0 && *patt==0) return 1; if (*str == *patt) return pattmatch(str+1, patt+1); if (*patt != '*') return 0; if (*str == 0) return pattmatch(str, patt+1); for (int i=strlen(str); i>=0; i--) if (pattmatch(str+i, patt+1)) return 1; return 0; }

  Рекурсивная функция с параметрами «строка», «шаблон» Если шаблон и строка пусты, сопоставление успешно Если шаблон начинается на символ, и слово начинается на этот же символ, осталось сопоставить остаток шаблона с остатком строки Итак, символы не равны. Если в шаблоне не '*' сопоставление неуспешно Значит, в шаблоне "*". Если строка уже пуста, осталось сопоставить её с остатком шаблона Цикл по максимально возможной длине подстроки (включая нулевую длину), Если ли остаток шаблона сопоставим с остатком строки сопоставление успешно Цикл не дал успешного сопоставления (завершился), сопоставление неуспешно …

  • Да, это неуместная рекурсия как она есть.

TODO перенести сюда Д/З с модификацией

Если успеем (не успели)

envp

Вместо i<argc напишем argv[i] (т. е. до пустой строки)

• Хоба!

• Это main(int argc, char *argv[], char *envp[])

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

TODO

1. Ввести целые положительные N, K. Написать неуместно рекурсивную функцию , которая вычисляет количество натуральных N-значных чисел в системе счисления с основанием K, таких что их запись не содержит двух подряд идущих нулей. Лидирующие нули не допускаются. Для EJudge N⩽33. Вывести это количество.

• Подсказка: довольно легко вывести рекуррентное соотношение, которое в виде трёх функций, вызывающих друг друга, занимает 6 строк. Однако алгоритм из трёх функций неэффективен настолько, что не пройдёт тесты. Лучше объединить их в одну, тогда она вообще в 4 строчки будет.

• TODO: здесь будут спойлеры и трейлеры. Главное - решать задачу надо рекурсией, а не через школьные формулы комбинаторики.

6 3

→

328

2. Ввести целое положительное N. Вывести в лексикографическом порядке все правильные скобочные последовательности, состоящие из N открывающих круглых скобок и N закрывающих скобок. Для EJudge N⩽11.

3

→

((()))
(()())
(())()
()(())
()()()

3. Сортировка слиянием. Написать функцию join(int low, int middle, int high, int array[high]), которая считает, что в массиве array есть два последовательно идущих упорядоченных фрагмента: array[low] … array[middle-1] и array[middle] … array[high-1]. Функция создаёт временный массив на high-low элементов, формирует там упорядоченную последовательность и записывает её обратно в array[low] … array[high-1].

• Алгоритм слияния: циклически выбирать меньшее между array[low] и array[middle] и добавлять его во временный массив, увеличивая low или middle соответственно. Когда один фрагмент закончится, числа во втором будут точно больше остальных, они дописываются в конец.

• Написать функцию joinsort(int n, int array[n]), которая сортирует массив array методом простого слияния.

• Алгоритм простого слияния:
  • попарно слить соседние элементы в упорядоченные пары
  • попарно слить соседние пары в упорядоченные четвёрки
  • …

  • попарно слить соседние 2^k-1-ки в упорядоченные 2^k-ки

  • …
  • PROFIT!

• Потренируйтесь на массивах размера 2ⁿ, но затем адаптируйте алгоритм для массивов любого размера (high иногда будет меньше, чем middle+2^k-1, вот и всё).

4. Поиск шаблона в строке на основе доработанной функции pattmatch(), базовая версия которой приведена выше. Ввести строку s и строку-шаблон p, и то и другое без пробелов. Вывести FOUND, если в строке s есть подстрока, соответствующая p; в противном случае вывести FAIL. Доработки pattmatch():

• Поправить неуместную рекурсию в сопоставлении шаблона: на шаге 2 вместо «Если шаблон начинается на символ, и слово начинается на этот же символ» реализовать «Если шаблон и слово имеют непустой общий префикс», далее как обычно