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

Форма для сдачи

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

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

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

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

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

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

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

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

envp

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

Д/З

  1. EJudge: Without2ZerosC 'Без двух нулей'

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

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

    • Решать задачу надо рекурсией, а не через школьные формулы комбинаторики.
    Input:

    6 3
    Output:

    328
  2. EJudge: BracketSequence 'Cкобочные поcледовательности'

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

    Input:

    3
    Output:

    ((()))
    (()())
    (())()
    ()(())
    ()()()
  3. EJudge: JoinSort 'Сортировка слиянием'

    Сортировка слиянием. Написать функцию 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 методом простого слияния.

    • Алгоритм простого слияния (да, не рекурсивный, и что?):
      • попарно слить соседние элементы в упорядоченные пары
      • попарно слить соседние пары в упорядоченные четвёрки
      • …
      • попарно слить соседние 2k-1-ки в упорядоченные 2k-ки

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

    • Напишите программу, которая вводит N ⩽ 300000, затем массив из N целых, а затем выводит его в отсортированном виде.
    Input:

    15
    3 1 4 1 5 3 1 4 1 5 3 1 4 1 5
    Output:

    1 1 1 1 1 1 3 3 3 4 4 4 5 5 5 
  4. EJudge: PattMatch 'Поиск шаблона'

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

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

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

    xxabcdefyy
    a*
    Output:

    FOUND

LecturesCMC/AL/Prac/17_Backtracking (последним исправлял пользователь FrBrGeorge 2026-11-06 00:28:46)