Главная страница
Навигация по странице:

  • ..001010...

  • Примеры. ScSmall[3,l]=2: ((), ()(.

  • — закрывающую. А это уже реаль- ный путь подсчета числа последовательностей. Ответом задачи будет 0 12 345

  • Ограничимся при вычислениях диапазоном типа

  • Дополним ее функцией определения количества частично правильных последовательностей из массива SCSmall. •

  • 2. Комбинаторные алгоритмы 73

  • 3. Перебор и методы его сокращения

  • Пример 1

  • 86 3. Перебор и методы его сокращения

  • Окулов.Программирование.в.алгоритмах. По вопросам приобретения обращаться


    Скачать 5.46 Mb.
    НазваниеПо вопросам приобретения обращаться
    АнкорОкулов.Программирование.в.алгоритмах.pdf
    Дата26.04.2017
    Размер5.46 Mb.
    Формат файлаpdf
    Имя файлаОкулов.Программирование.в.алгоритмах.pdf
    ТипДокументы
    #5718
    страница5 из 26
    1   2   3   4   5   6   7   8   9   ...   26

    Четвертая задача. По разбиению (Now) получить его но- мер. Принцип прост. Брать текущее число из разбиения, начи- ная с первого, и смотреть на его «вклад» в количество номеров.
    Например, разбиение «22211». Определяем, сколько номеров приходится на первую 2, затем на вторую и т. д.
    Function GetNumByWh:LongInt;
    Var
    Begin
    {*Формируем номер разбиения.*}
    {*Номер строки в массиве
    For i : = 1
    Do Begin {*Просматриваем
    For
    To
    Do
    числа из разбиения определяет
    число столбцов в массиве
    {*Изменяем номер строки.*}
    End;

    58 2. Комбинаторные алгоритмы
    End;
    Трассировка логики (N=8, Now
    1 2
    3 4
    4 8
    6 4
    2 1
    i
    1 2
    3 4
    5
    Р
    0 1
    0 1
    0 1
    0 0
    SCновое
    2 3
    4 4
    4
    jkновое
    6 4
    2 1
    0
    Итак, номер определен, он равен 4.
    2.2.5. Последовательности из нулей и единиц длины N
    без двух единиц подряд
    Первая задача. Подсчет числа таких последовательностей.
    Приведем пример при N=4. Таких последовательностей 8.
    0000 0001 0010 0100 0101 1000 1001 1010
    Как подсчитать количество таких последовательностей (обо- значим через P(N))? Пусть есть последовательность длины N. На первом месте в последовательностях записан ноль. Число таких последовательностей P(N—1). Рассмотрим случай, когда на пер-
    вом месте записана единица. Тогда на втором месте обязате-
    льно должен быть записан 0. Число таких последовательно-
    P(N-2). Итак, получили формулу: P(N)=P(N-1)+P(N-2), a это не что иное, как формула вычисления чисел Фибоначчи. Та- ким образом, число последовательностей длины N, в которых нет двух идущих подряд 1, равно числу Фибоначчи. Огра- ничимся диапазоном чисел типа LongInt (N=<44). Для вычисле- ния количества последовательностей при больших значениях N
    требуется использовать «длинную» арифметику, в частности процедуры сложения и вывода длинных чисел. А при наших ограничениях можно ввести результаты в массив констант.
    Of

    2. Комбинаторные алгоритмы
    59
    1597, 2584, 4181, 6765, 10946, 17711, 28657,
    46368, 75025, 121393, 196418, 317811, 514229,
    832040, 1346269, 2178309, 3524578, 5702887,
    9227465, 14930352, 24157817, 39088169,
    63245986, 102334155, 165580141, 267914296,
    433494437, 701408733, 1134903170, 1836311903);
    И процедура вычисления количества последовательностей.
    Function
    (N: Integer) :
    Begin
    If
    Then
    Else
    ;
    End;
    Вторая задача. Генерация последовательностей. Рассмот- рим пример для
    (номер последовательности, последовате- льность).
    0 1
    2 3
    4 5
    6 000000 000001 000010 000100 000101 001000 001001 7
    8 9
    10 11 12 13 001010 010000 010001 010010 010100 010101 100000 14 15 16 17 18 20 100001 100010 100100 100101 101000 101001 101010
    Принцип перехода к следующей последовательности: начи- наем с конца последовательности, подпоследовательности типа
    ..0010... переходят в тип ...0100... и типа ..001010... в тип
    010000.... Формализация этого принципа приведена в следую- щей процедуре. Для хранения последовательности использует- ся массив Now.
    Procedure GetNext;
    Var i: Integer;
    Begin
    i :
    While
    Or ( (i>l) And
    =1) )
    Do Begin
    Now[i] :=0;Dec(i) ;
    End;
    End;

    60
    Комбинаторные алгоритмы
    Третья задача. Необходимо по номеру получить последова- тельность. Зададим себе простой вопрос. Если значение L боль- ше, чем число последовательностей длины N—1, то что находится на первом месте (слева) в последовательности — 0
    или 1? Ответ очевиден: 1. Вычтем из значения!- число последо- вательностей длины N—1 и продолжим сравнение с новым зна- чением L. В этом суть решения.
    Пример N=6,
    15 2
    2 2
    2 0
    /
    1 3
    4 5
    6
    Р
    13 8
    5 3
    2
    Now
    * * * * *
    10****
    100***
    1000**
    10001*
    100010
    Procedure
    Longlnt);
    Var i: Integer;
    Begin
    For
    To N Do
    If
    (N-i) Then Begin
    Else
    End;
    Четвертая задача. По последовательности необходимо по- лучить ее номер в соответствии с введенным отношением по- рядка. Если в последовательности на месте i находится 1, то в номере есть вклад от числа всех последовательностей длины
    N-i. Итак, следует просмотреть последовательность и по значе- нию 1 подсчитать сумму количества последовательностей соот- ветствующих
    Function
    Longlnt;
    Var i: Integer;
    sc: Longlnt;
    Begin
    For i:=l To N Do If Now[i]=l Then
    (sc,
    (N-i));
    :=s
    End;

    2. Комбинаторные алгоритмы 61 2.2.6. Подмножества
    Проблема. Научиться работать с подмножествами iV-элемен- тного множества натуральных чисел от 1 до N такими, что каждое следующее подмножество отличалось бы от предыдуще- го только на один элемент.
    традиционные четыре зада- чи: подсчет количества подмножеств; генерация подмножеств;
    определение подмножества по номеру и определение номера по подмножеству.
    Первая задача. Количество подмножеств множества из N
    элементов равно 2N. Эта задача проста, если значение N не очень большое. Однако уже при N=15 количество подмножеств
    32768, поэтому тип данных требуется использовать осторожно. Пусть N меньше или равно 100. При таких значе- ниях N необходимо использовать элементы «длинной» арифме- тики, а именно: умножение «длинного» числа на короткое (пя- тая задача 1-й главы, процедура Mul) и вывод «длинного»
    числа (вторая задача 1-й главы, процедура SayTLong).
    Процедура вычисления количества подмножеств множества из N элементов. Есть небольшой «нюанс». Возводить двойку в степень N — утомительное занятие, сократим его по возможно- сти.
    Procedure
    Var i: Integer;
    Tmp: TLong;
    Begin
    i :=N; {
    для
    Основанием
    системы счисления в нашей задаче является
    10000, а два в степени 13 равно 8192.*}
    в степени 0 равно
    While i>0 Do Begin
    If i>13 Then Begin
    1
    13, Tmp);
    i:=i-13; End
    что команда shl -
    сдвиг влево, итак 1 сдвигается на 13
    разрядов влево, т.е. мы умножаем на
    А почему нельзя умножать на 2
    14
    ?*}
    Else Begin Mul (Res, 1 shl i, Tmp); i:=0; End;
    End;
    End;
    Вторая задача. Подмножества iV-элементного множества натуральных чисел от 1 до N будем представлять двоичными последовательностями длины N

    62 2. Комбинаторные алгоритмы
    (массив Now). Элемент равный единице, говорит о том,
    что принадлежит подмножеству.
    Число
    0 1
    2 3
    4 5
    6 7
    8 9
    10 11 12 13 14 15
    Двоичное представление числа
    (В)
    0000 0001 0010 0011 0100 0101 0110 0111 1000 1001 1010 1011 1100 1101 1110 1111
    Двоичная последовательность
    (Now)
    0000 0001 0010 0110 0111 0101 0100 1100 1101 1111 1110 1010 1011 1001 1000
    Подмножество
    []
    [1]
    [1,2]
    [2]
    [2,3]
    [1,2,3]
    [1,3]
    [3]
    [3,4]
    [1,3,4]
    [1,2,3,4]
    [2,3,4]
    [2,4]
    [1,2,4]
    [1,4]
    [4]
    Во втором столбце таблицы записаны двоичные представле- ния чисел от 0 до
    Каждое из чисел мы подвергли преобра- зованию (кодирование по Грею), заменив каждую двоичную цифру, кроме первой, на ее сумму с предыдущей цифрой по мо- дулю 2, таким образом, получив элементы массива Now. Т. е.,
    и для всех i от 2 до N. В
    четвертом столбце таблицы записаны подмножества, построен- ные по единичным элементам массива Now. Обратите внимание на то, что каждое следующее отличается от предыдущего толь- ко на один элемент. Запишем формирование массива Now в виде процедуры.
    Procedure
    Var i: Integer;
    Begin
    FillChar (Now,
    (Now) , 0) ;
    Now[l]:=B[1];
    For i:=2 To N Do Now[i] :=B[i] Xor B[i-1] ;
    End;

    2. Комбинаторные алгоритмы 63
    Обратное преобразование:
    для i от 2 до N.
    Procedure
    Var i ,
    Integer;
    Begin
    FillChar(B,
    0);
    B[l]
    ;
    For
    To N Do B[i]
    Xor B[i-1] ;
    End;
    Воспринимая данное преобразование как факт, осмысление которого лежит за пределами данного материала, генерацию подмножеств можно осуществлять с использованием массива
    В. В качестве материала для самостоятельного осмысления предлагается следующая изящная процедура генерации оче- редного разбиения.
    Procedure GetNext;
    Var i: Integer;
    Begin
    Repeat
    Dec (i) ;
    B[i] :=B[i] Xor 1;
    Until
    Xor 1;
    End; {*Будет ли работать данная процедура для
    последовательности 1111 (N=4) ?*}
    Можно решать задачу по-другому. Вспомним зрительный образ «лесенки» со стрелками, который мы использовали при генерации перестановок, таких, что каждая следующая отли- чалась от предыдущей только одной транспозицией соседних элементов. В данной задаче следует использовать не лесенку, а прямоугольное поле 2*N. Шашки в начальный момент нахо- дятся в первой строке (она соответствует нулевым значениям в двоичной последовательности) и двигаются в направлении стрелок. Определяется первая справа шашка, которую можно сдвинуть в направлении стрелки. Сдвигаем ее, а у шашек, на- ходящихся справа от нее, меняем направление движения. По- следовательности 0000 при N=4 соответствует следующая
    «картинка».

    64
    2. Комбинаторные алгоритмы
    А последовательности 0100:
    Следующее состояние поля будет иметь вид (последователь- ность 1100):
    и процесс генерации окончится при состоянии (последователь- ность
    Третья задача. Получение последовательности В по номеру разбиения на подмножества L соответствует записи числа L в двоичной системе счисления с использованием массива В. Дво- ичный разряд числа L — это значение соответствующего эле- мента массива В.
    Procedure
    Var i: Integer;
    Begin
    For i:=l To N Do Begin
    B[N-i+l] :=L And
    младший разряд
    числа L. *} •
    shr
    L в два раза (деление
    на 2) . *}
    End;
    End;
    Четвертая задача. Логика получения номера разбиения на подмножества по последовательности соответствует в нашем случае переводу числа из двоичной системы счисления в деся- тичную.
    Function
    Longlnt;
    Var sc: Longlnt;
    i: Integer;
    Begin
    For
    To N Do
    + B[i] ;
    End;

    2. Комбинаторные алгоритмы
    65 2.2.7. Скобочные последовательности
    Последовательность из 2*N скобок правильная, если для любого значения i (l число открывающих скобок, на- пример «(», больше или равно числу закрывающих скобок «)»
    и общее число открывающих скобок в последовательности рав- но числу закрывающих.
    Пример. Последовательность (())()() — правильная последовательность (()))(() — не является правильной.
    Мы по-прежнему решаем наши четыре задачи. Однако изме- ним порядок их рассмотрения. Начнем с генерации последова- тельностей.
    Пусть N равно 4. В нечетных столбцах таблицы приведены номера последовательностей, а в соседних — соответствующие последовательности.
    0
    1
    2
    3
    4
    5
    6
    0000 00(0)
    0(0)0 0(00)
    ()((()))
    (0)00
    (())(())
    7
    8
    9
    10
    11
    12
    13
    (00)0
    (000)
    (()(()))
    ((()))()
    ((())())
    ((()()))
    (((О)))
    Что же мы делаем? Какое отношение порядка введено на множестве последовательностей? Сколько существует таких по- следовательностей для заданного значения N? Вопросов много,
    ответов пока нет.
    Пусть наша последовательность хранится в переменной строкового типа Now. Мы просматриваем строку справа налево до первой комбинации скобок типа «)(». Она обязательно дол- жна встретиться, ибо, считаем, что текущая последователь- ность не является последней. Заменяем эту комбинацию скобок на
    Подсчитываем с начала строки (последовательности),
    на сколько число открывающих скобок больше числа закрыва- ющих, дописываем это количество закрывающих скобок, и если строка не длины 2*N, то дополняем ее комбинациями ско- бок «()».
    Procedure
    Var i, j, sc: Integer;
    Begin
    While (i>l) And
    +
    (')
    Do
    комбинации
    3500

    66
    Комбинаторные алгоритмы
    Now[i-1]: = ' (';
    = ') ';{"Замена. *}
    разности числа открывающих и
    числа закрывающих скобок. *}
    For j:=l
    i Do If Now[j ] = ' (' Then Inc(sc) Else
    Dec (sc) ;
    While sc<>0 Do
    подпоследовательности закрывающими скобками. *}
    ;
    End;
    While Length (Now) <2*N Do
    () ' ;
    строку, максимально "ухудшая"
    ее, т.е. из остатка строки делаем ее
    начальное
    End;
    Даны две последовательности и
    например ()()(()) и
    ()(()())• Какая из них имеет больший номер? Просматриваем по- следовательности слева направо, сравнивая соответствующие символы. Найдем первое значение i, при котором
    Если окажется, что a
    то имеет мень- ший номер, чем
    Можно записать сей факт и в математиче- ских обозначениях, но суть не изменится, поэтому воздержим- ся. Перейдем к первой задаче. Введем понятие частично правильной скобочной последовательности. Последователь- ность частично правильная, если для любой позиции в последо- вательности число открывающих скобок больше или равно чис- лу закрывающих, естественно, что количество тех и других считается от начала последовательности. Так, последователь- ность «(((((» является частично правильной, а последователь- ность «(()))((» — нет, для позиции 5 число закрывающих боль- ше числа открывающих скобок. Оформим наши дальнейшие рассуждения в виде таблицы. Номер строки указывает на чис- ло скобок в последовательности, номер столбца — на разность между числом открывающих и закрывающих скобок, имя таб- лицы элемент таблицы ScSmall[i,j] равен количеству частично правильных последовательностей из i скобок, причем разность между числом открывающих и закрывающих равна
    Это ключевой момент для понимания: «разность — номер столбца». На диагонали таблицы записаны 1, число последова- тельностей, состоящих из одних открывающих скобок, а они попадают под определение частично правильной последовате- льности. Элементы таблицы ScSmall[i,j] равны 0, если и j
    числа разной четности.

    2. Комбинаторные алгоритмы
    67
    Примеры. ScSmall[3,l]=2: ((), ()(.
    (((),
    (()(, ()((.
    ()(), (()).
    ()()(,
    (())(,
    (()(). ()(()•
    «крохотный факт»:
    Дописываем в ко-
    нец последовательностей из ScSmall[4,0] открывающую скоб-
    ку, а в конец ScSmall[4,2] — закрывающую. А это уже реаль-
    ный путь подсчета числа последовательностей. Ответом задачи
    будет
    0 1
    2 3
    4
    5
    6 7
    8
    -1 0
    0 0
    0 0
    0 0
    0 0
    0 1
    0 1
    0 2
    0
    5
    0 14 1
    0 1
    0 2
    0
    5
    0 14 0
    2 0
    0 1
    0 3
    0 9
    0 28 3
    0 0
    0
    1
    0 4
    0 14 0
    4 0
    0 0
    0 1
    0
    5
    0
    20
    5 0
    0 0
    0 0
    1 0
    6 0
    0 0
    0 0
    0 0
    1 0
    7 7
    0 0
    0 0
    0 0
    0 1
    0 8
    0 0
    0 0
    0 0
    0 0
    1
    Ограничимся при вычислениях диапазоном типа
    Const SmallN=37;
    Var
    +
    -1.
    + 1]
    Of Longlnt;
    Процедура формирования таблицы вряд ли нуждается в по-
    яснениях.
    Procedure
    Var i , : Integer;
    Begin
    (ScSmall,
    0) ;
    0]:=l;
    For
    To
    Do
    For j:=0 To SmallN Do
    End;
    Дополним ее функцией определения количества частично
    правильных последовательностей из массива SCSmall. •'
    Function
    Up: Longlnt): Longlnt;
    Begin
    If (N<0) Or (Up<0) Then
    Else

    68 2. Комбинаторные алгоритмы
    If
    Or (Up>SmallN) Then
    Else
    Up];
    End;
    Вычисление последовательности номеру и обратное пре- образование можно вынести на самостоятельную часть работы.
    Ниже приведены соответствующие процедура и функция. В пе- ременной Up, как и выше, формируется текущая разность меж- ду числом открывающих и закрывающих скобок.
    Procedure
    Var i, Up: Integer;
    P: Longlnt;
    Begin
    Up:=0;
    For i:=l To N*2 Do Begin
    If (L>=P) Then Begin
    (Up);
    End
    Else Begin Dec (Up);
    End;
    End;
    End;
    Function
    Longlnt;
    sc: Longlnt;
    Up: Integer;
    Begin
    sc:=l; Up:=0;
    For i:=l To N*2 Do
    If
    Then Begin
    (N*2-i,Up-l) ;Inc (Up) ;End
    Else
    End;
    2.3. Задачи
    1. Разработать программу генерации всех последовательно- стей длины k из чисел 1, 2, ... N. Первой последовательностью является 1,
    ...,1, последней — N, N, ..., N.
    2. Разработать программу генерации всех последовательно- стей длины k, у которых i-й элемент не превосходит значения
    i. Первой последовательностью является 1, 1,
    послед- ней — 1, 2, ..., k.

    Комбинаторные алгоритмы 69 3. Перечислить все разбиения натурального числа N на на- туральные слагаемые (разбиения, отличающиеся лишь поряд- ком слагаемых, считаются за одно) в следующих порядках
    (пример, при N=4):
    4, 3+1, 2+2, 2+1+1, 1+1+1+1;
    2+2, 1+3, 1+1+2, 1+1+1+1;
    1+1+1+1, 1+1+2, 1+3, 2+2, 4.
    4. Разработать программу генерации всех последовательно- стей длины 2*N, составленных из N единиц и N минус единиц,
    у которых сумма любого начального отрезка неотрицательна,
    т. е. количество минус единиц в нем не превосходит количества единиц.
    5. Определить, что делает следующая процедура. Первое об- ращение — R(N,1).
    Procedure
    Var
    Begin
    If
    Then Begin
    к элементов
    массива A>;End
    Else Begin
    к элементов массива А>;
    For
    Do Begin
    End;
    End;
    6. На множестве перестановок задается антилексикографи- ческий порядок. Решить задачи 2-5 из п. 2.2.1.
    7. Решить задачи 1-5 из п. 2.2.1 для перестановок с повторе- ниями.
    8. Решить задачи 1-5 из п. 2.2.2 для размещений с повторе- ниями.
    9. Решить задачи 1-5 из п. 2.2.3 для сочетаний с повторени- ями.
    10. Путем трассировки приведенной программы [18] опреде- лите её назначение и логику работы.
    Const п-4 ;
    Var A:Array[l..n] Of Integer;
    Function Place (i
    Integer) -.Integer;
    Begin
    If
    Mod 2=0) And (m>2) Then
    If i

    70 2. Комбинаторные алгоритмы
    Else
    Else
    End;
    Procedure Perm
    Var
    If m=l Then Begin For i:=l To n Do Write (A[i]
    ;
    Else
    For i : = J
    Do Begin
    Perm
    ;
    If Km Then Begin
    (i ,m) ] ;
    End;
    End;
    Begin
    For i:=l
    n Do
    Perm (n);
    End.
    Путем трассировки приведенной программы [18] опреде- лите её назначение и логику работы.
    Const
    Var
    Of Integer;
    Begin
    For i:=l
    n Do
    Repeat
    For
    To n Do Write (A[l] : 3)
    ;
    i : =i +1
    =1 ;j : =i ;
    While j Mod 2=0 Do Begin
    j:=j Div 2;p:=p+l;
    End;
    If
    Then
    ;
    Until p>n;
    End.
    12. Путем трассировки приведенной программы [18] опреде- лите её назначение и логику работы.
    Const
    Var
    Of Integer;

    2. Комбинаторные алгоритмы
    71
    Begin
    For
    к Do A[i] :=i;
    p:=k;
    While p>=l Do Begin
    For i:=l
    к Do Write (A [i] : 3) ;
    If A[k]=n Then
    Else
    If p>=l Then
    For i:=k DownTo p Do A[i] :=A[p] +i-p+l ;
    End;
    End.
    13.
    На одном из секретных заводов осу- ществляется обработка радиоактивных материалов, в результа- те которой образуются радиоактивные отходы двух типов: А
    (особо опасные) и Б (неопасные). Все отходы упаковываются в специальные прямоугольные контейнеры одинаковых разме- ров, после чего эти контейнеры укладываются в стопку один над другим для сохранения. Стопка является взрывоопасной,
    если в ней соседствуют два ящика с отходами типа А.
    Требуется написать программу, которая подсчитывает коли- чество возможных вариантов формирования не- взрывоопасной стопки из заданного общего числа контейнеров N
    Входные данные. Во входном файле
    put.txt) содержится единственное число N.
    Выходные данные. В выходной файл (out-
    put.txt) необходимо вывести искомое число ва- риантов.
    Указание. Обозначим опасный контейнер 1, а неопасный —
    0. Моделью стопки является последовательность из 0 и 1.
    Взрывоопасная стопка есть последовательность из 0 и 1, в кото- рой соседствуют хотя бы две 1 подряд. Задача сводится к под- счету числа последовательностей длины N без двух соседних 1.
    Приведем пример при N=4. Таких последовательностей 8.
    0000 0001 0010 0100 0101 1000 1001 1010
    Как подсчитать количество таких последовательностей (обо- значим через
    Пусть есть последовательность длины N.
    На первом месте в последовательности записан 0. Число таких последовательностей P(N—1). Рассмотрим случай, когда на первом месте записана 1. Тогда на втором месте обязательно должен быть записан 0. Число таких последовательностей

    72
    Комбинаторные алгоритмы
    P(N-2). Итак, получили формулу:
    a это не что иное, как формула вычисления чисел Фибоначчи.
    Таким образом, число последовательностей длины N, в кото- рых нет двух идущих подряд 1, равно iV-му числу Фибоначчи.
    Типа данных достаточно только для вычислений при
    N<44. Для вычисления количества последовательностей при больших значениях N требуется использовать «длинную»
    арифметику, а именно процедуры сложения и вывода «длин- ных» чисел. Если задачу чуть-чуть изменить — вычислять ко- личество взрывоопасных стопок, то потребуется процедура вы- читания «длинных» чисел. Из необходимо вычесть число невзрывоопасных стопок.
    14. Натуральные числа от 1 до N
    поступают на об- работку в определенной последовательности. Например, 3, 4, 6,
    2, 5, 1. Числа размещаются в таблице следующим образом: по- следовательно просматриваются числа из первой строки и срав- ниваются с поступившим числом k. Если число больше всех чисел строки, то оно размещается в конце строки. Если же най- дено (первое) число t, такое, что то число k записывается на это место, а число t «выдавливается» из строки и размещается во второй строке по этому же принци- пу, затем в третьей (если потребуется) и т. д., пока для числа или «выдавливаемого») не будет най- дено место. Для приведенной последователь- ности вид размещения дан в таблице.*
    Требуется по конечному результату восста- новить все возможные входные последовате- льности чисел, обработка которых по данной логике приводит к этому размещению. Так,
    для примера из формулировки задачи, отве- том являются 16 последовательностей.
    Указание. Простейший способ решения за- ключается в генерации всех перестановок и про- верке — удовлетворяет ли очередная переста- новка «правилам игры». Однако если ввести ограничение на время решения, то этот способ не выдерживает элементарной критики. Обра- тим внимание на следующие моменты. На обра- ботку поступила последовательность (N=6) 1, 2,
    3, 4, 5, 6. Её размещение имеет вид:
    3 4 5 6.
    Обратный порядок поступления дает размеще-
    Задача с международной олимпиады школьников 2001 г. (формулировка со- кращена).

    2. Комбинаторные алгоритмы 73
    ние по одному элементу в строке: в первой — 1, во второй — 2 и т. д. Зададим себе вопрос: а возмож- ны ли размещения, при которых элементы в столб- цах (не в строках!) идут не в порядке возрастания,
    как, например, приведенное на следующем рисун- ке. Оказывается, нет.** Мы всегда получаем раз- мещения, элементы в столбцах и строках которых записаны в порядке возрастания. Если так, то первое решение получается простым выписыванием элементов по столбцам в обратном по- рядке. Для примера из формулировки задачи это будет 3 2 4
    5. Второй вариант решения может заключаться в том, что из полученной (первой) последовательности путем перестановки соседних элементов мы получаем какую-то последовательность.
    Проверяем ее на «пригодность» и если она удовлетворяет
    «условиям игры», то запоминаем ее в очереди. Итак, выполня- ем все перестановки соседних элементов в исходной последова- тельности, а затем переходим к очередному необработанному элементу очереди, если он есть. Недостаток алгоритма очеви- ден. Мы можем получать одну и ту же последовательность не- сколькими способами. Поэтому приходится их хранить и перед записью в очередь проверять, нет ли дублирования. А это уже потеря времени и, естественно, данное решение (приведем его
    «костяк») является только очередным приближением, хотя и работающим, к окончательному варианту.
    Const
    Type
    Of Word;
    Var
    Function Check (Const
    проверки - удовлетворяет ли очередная
    последовательность условиям задачи?*}
    Begin
    End;
    Procedure
    Type
    элемент очереди.
    Очередь размещаем
    куче". Обычный список.
    Записываем в конец - указатель
    считываем первый элемент - указатель
    *}
    В этом заключается неточность в формулировки задачи на международной олимпиаде. Если проверять по несуществующим размещениям, то часть ре- шений, включая опубликованные в газете «Информатика», будут генериро- вать неизвестные входные последовательности.

    Комбинаторные алгоритмы
    End;
    Var
    p:pnt;
    i -.Word;
    Function
    проверки -
    есть ли данная
    в очереди?*}
    Begin
    End;
    Begin
    New
    первый элемент в очередь. *}
    While ykrOnil Do Begin {*Пока очередь не пуста. *}
    элемент из очереди. *}
    For i:=l
    Do Begin
    все
    возможные последовательности путем
    перестановок соседних
    *}
    ;
    If Check (Qj And NotQue Then Begin {*Если
    последовательность удовлетворяет условиям
    задачи и её нет в очереди, то записываем
    в
    *}
    New
    Print
    вывода элементов
    одномерного массива в файл не
    *}
    End;
    End;
    к следующему
    элементу очереди. *}
    End;
    End;
    Begin {*Основная программа. Ввод данных.
    Формирование первой последовательности
    массив А) . *}
    Solve;
    End.

    2. Комбинаторные алгоритмы
    75 15. На клетчатой полоске бумаги высотой в одну клеточку и длиной клеток некоторые клетки раскрашены в зеленый и белый цвета.
    По этой полоске строится ее код, которым явля- ется последовательность чисел — количества по- дряд идущих зеленых клеток слева направо. На- пример, для такой полоски кодом будет последовательность 2 3 2 8 1. При этом количество белых клеток, которыми разделяются группы зеленых клеток,
    нигде не учитывается (главное, что две группы разделяются, по крайней мере, одной белой клеткой). Одному и тому же коду могут соответствовать несколько полосок. Например, указанно- му коду соответствует и такая полоса:
    Задача состоит в том, чтобы найти количество полосок дли- ны N, соответствующих заданному коду.
    Входные данные. В единственной строке входного файла in-
    put.txt записано число N — длина полоски (l — количество чисел в коде и далее чисел, определяющих код.
    Выходные данные. В выходной файл output.txt записывает- ся количество полосок длины N, соответствующих заданному коду.
    Указание. Добавляем к каждому числу кода по единице (со- ответствует пробелу), получаем значение s. Остается решить за- дачу о подсчете числа размещений N-s пробелов по известному количеству мест — количеству чисел в коде плюс единица. Ес- тественно, что ограничения требуют применения многоразряд- ной арифметики.
    16. Между числами нужно вставить знаки арифме- тических операций +, —, * так, чтобы результат вычисления полученного арифметического выражения был равен заданно- му целому числу В.
    Входные данные. Во входном файле input.txt записано сна- чала требуемое число В
    затем число
    — коли-

    76
    2. Комбинаторные алгоритмы чество чисел в арифметическом выражении а затем целые числа
    Выходные данные. В выходной файл out-
    put.txt вывести искомое арифметическое вы- ражение или число 0, если его построить не удается. Если решений несколько, вывести любое из них.
    Указание. Количество мест для расста- новки знаков —
    Требуется сгенериро-
    вать все строки этой длины, состоящие из
    символов +, —, *, их
    Для каждой строки вычислить арифметическое выражение и, в зависимости от результата, продолжить про- цесс генерации или закончить работу.
    Представляет определенный интерес логика вычисления вы- ражения. Приведем её. В строке (глобальная переменная от- носительно приведенных функций) записана очередная после- довательность из символов +, —, *, а в массиве А
    последовательность чисел.
    Function
    Comp;
    Var tm: Comp;
    Begin

    While (p
    (p) ;
    Case B[p-1] Of
    ' + ' :
    (p);
    End;
    End;
    GetRes:=tm;
    End;
    И функция, вычисляющая произведение очередных сомно- жителей.
    Function
    p: Integer): Comp;
    Var tm: Comp;
    Begin
    ;
    While (p
    Do Begin

    2. Комбинаторные алгоритмы 77
    ;
    (p) ;
    End;
    End;
    Обратной задачей является поиск количества «счастливых билетов» (например, троллейбусных, т. е. шестизначных). Об- щая формулировка задачи. Последовательность из 2N цифр,
    каждая цифра от 0 до 9, называется счастливым билетом, если сумма первых N цифр равна сумме последних цифр. Опера- ции даны, требуется найти числа. Так, пусть нам необходимо подсчитать количество счастливых чисел в диапазоне [А,В],
    где А, В — заданные натуральные числа, имеющие в десяти- чной записи не более 20 цифр. Пусть
    Ответ задачи — 55251. Следующая функция является наброс- ком решения. Она правильная, но работает достаточно мед- ленно.
    Function Rec
    рекурсии являются k

    номер позиции в числе и
    Sum - сумма цифр в числе до позиции к.*}
    Var
    Begin
    If k=2*N+l Then If
    Then Rec:=l Else Rec:=0
    Else Begin
    Ans:=0;
    For
    To 9 Do
    If k<=N Then
    Else If
    Then
    End;
    End;
    Работа логики ускоряется за счет следующего приема. Схе- ма рекурсивного подсчета замедляется из-за многократного подсчета одного и того же значения, например Rec(3,8)
    iV=2. Следует ввести структуру данных для хранения подсчи- танных значений сумм типа
    Of Сотр.
    Пусть начальное значение элементов массива равно
    1. После того, как вычислено какое-то значение, оно запоминается в массиве и используется при дальнейшей работе. Проведите со- ответствующее изменение логики.

    78 2. Комбинаторные алгоритмы
    На плоскости заданы N точек с целочисленными коорди- натами. Требуется выделить те точки этого множества, кото- рые образуют выпуклую оболочку (вырожденные случаи — все точки на одной прямой и т. д. не рассматриваются).
    Указание. Специальные методы построения выпуклой обо- лочки будут рассмотрены в главе 5. В данном случае можно воспользоваться следующим фактом. Точка (х, у) принадлежит выпуклой оболочке, если она не лежит внутри любого треуго- льника, образованного остальными точками исходного множе- ства. Всего треугольников, которые можно построить из N то- чек, —
    общая временная сложность задачи

    3. Перебор
    и методы его сокращения
    Обучение программированию, алгоритмизации — сверх- сложное дело*. Знание конструкций языка программирования,
    способов описания алгоритмов не решает проблемы. Требуется проделать огромную работу для того, чтобы сформировать стиль мышления, присущий специалисту по информатике.
    Этот стиль характеризуется, на наш: взгляд, двумя основопола- гающими моментами: язык информатики (он не зависит от конкретного языка программирования) должен стать естест- венным языком выражения своих мыслей (рассуждений); мето- дология решения задач, присущая информатике, должна быть освоена не на фактографическом уровне. Тема «перебор и мето- ды его сокращения» является одной из ключевых в этой систе- ме обучения. Весь процесс обучения построен через решение за- дач, естественно, с использованием компьютера.
    3.1. Перебор с возвратом (общая схема)
    Даны N уопрядоченных множеств
    ...,
    — изве- стно), и требуется построить вектор
    ...,
    где удовлетворяющий заданному множе- ству условий и ограничений.
    Может быть, это явилось одной из причин, по которой, после появления мощных персональных компьютеров, образовательная информатика с таким энтузиазмом «бросилась» в изучение так называемых информационных тех- нологий.

    80 3. Перебор и методы его сокращения
    В алгоритме перебора вектор А строится покомпонентно сле- ва направо. Предположим, что уже найдены значения первых
    к-1
    ...,
    ?, ..., ?), тогда заданное мно- жество условий ограничивает выбор следующей компоненты некоторым множеством Если
    ] (не пустое), мы вправе выбрать в качестве наименьший элемент и перейти к выбору компоненты и так далее. Однако если условия та- ковы, что оказалось пустым, то мы возвращаемся к выбору
    к-1 компоненты, отбрасываем и выбираем в качестве ново- го тот элемент который непосредственно следует за только что отброшенным. Может оказаться, что для нового условия задачи допускают непустое и тогда мы пытаемся снова выбрать элемент
    Если невозможно выбрать мы возвращаемся еще на шаг назад и выбираем новый элемент и так далее.
    Графическое изображение — дерево поиска. Корень дерева
    (О уровень) есть пустой вектор. Его сыновья суть множество кандидатов для выбора и, в общем случае, узлы fc-ro уровня являются кандидатами на выбор при условии, что выбраны так, как указывают предки этих узлов. Вопрос о том, имеет ли задача решение, равносилен вопросу, являются ли какие-нибудь узлы дерева решениями. Разыскивая все ре- шения, мы хотим получить все такие узлы.
    Рекурсивная схема реализации алгоритма.
    Procedure Backtrack
    Begin
    <вектор является
    Then
    его>
    Else Begin
    <вычислить
    For
    Backtrack
    ;
    {*\\ - добавление к вектору компоненты. *}
    End;
    End;
    Оценим временную сложность алгоритма. Данная схема реа- лизации перебора приводит к экспоненциальным алгоритмам.
    Действительно, пусть все решения имеют длину 2V, тогда иссле- довать требуется порядка
    *|
    узлов дерева. Если значение ограничено некоторой константой С, то получаем порядка узлов.

    3. Перебор и методы его сокращения 81 3.2. Примеры задач для разбора общей схемы перебора
    Пример 1 «Задача о расстановке ферзей». Для разбора
    общей схемы одной из лучших задач является задача о расста- новке ферзей. На шахматной доске N*N требуется расставить
    N ферзей таким образом, чтобы ни один ферзь не атаковал дру- гого.
    Отметим следующее. Все возможные способы расстановки ферзей —
    (около для N=8). Каждый столбец содер- жит самое большее одного ферзя, что дает только расстано- вок для iV=8). Никакие два ферзя нельзя поставить в одну строку, а поэтому, для того чтобы вектор
    ...,
    был решением, он должен быть перестановкой элементов (1,2,
    ..., N), что дает только
    (4,0*10 4
    для N==8) возможностей. Ни- какие два ферзя не могут находиться на одной диагонали, это сокращает число возможностей еще больше (для в дереве остается 2056 узлов). Итак, с помощью ряда наблюдений мы исключили из рассмотрения большое число возможных расста- новок N ферзей на доске размером N*N. Использование подоб- ного анализа для сокращения процесса перебора называется поиском с ограничениями или отсечением ветвей в связи с тем,
    что при этом удаляются поддеревья из дерева. Второе. Другим усовершенствованием является слияние, или склеивание, вет- вей. Идея состоит в том, чтобы избежать выполнения дважды одной и той же работы: если два или больше поддеревьев дан- ного дерева изоморфны, мы хотим исследовать только одно из них. В задаче о ферзях мы можем использовать склеивание, за- метив, что если то найденное решение можно отра- зить и получить решение, для которого
    Следователь- но, деревья, соответствующие, например, случаям и
    изоморфны.
    Следующие рисунки иллюстрируют сказанное и поясняют ввод используемых структур данных.
    Структуры данных.
    Up: Array
    .16] Of Boolean ;•{
    занятости
    диагоналей первого
    *}
    7] Of
    занятости
    диагоналей второго типа.
    Of Boolean;{*Признак занятости
    вертикали. *}
    X: Array
    .8] Of
    вертикали,
    на которой стоит ферзь на каждой горизонтали. *}

    82 3. Перебор и методы его сокращения
    Далее идет объяснение «кирпичиков», из которых «склады- вается» решение (технология «снизу вверх»).
    Procedure
    {*Сделать ход.*}
    Begin
    :=j;Vr[j] :
    :=False;
    End;
    Procedure
    ход.*}
    Begin
    Vr
    End;
    Function
    допустимости хода в позицию (i,j). *}
    Begin
    D_hod:=Vr[j] And Up[i+j] And Down [i-j] ;
    End;
    Основная процедура поиска одного варианта расстановки ферзей имеет вид:
    Procedure
    Var

    Перебор и методы его сокращения 83
    Begin
    Repeat
    Inc
    вертикали. *}
    If
    Then Begin
    If i<8 Then Begin
    Solve
    ,q) ;
    If Not q Then
    ;
    End
    Else
    найдено.*}
    End;
    Until q Or (j=8) ;
    End;
    Изменим формулировку задачи. Пусть требуется найти все способы расстановки ферзей на шахматной доске N*N. Для до- ски 8*8 ответ 92. Возможный вариант реализации приведен ниже по тексту.
    Procedure
    Var
    Begin
    If
    Then Begin
    For j : =1 To N Do
    If D_hod(i,j) Then Begin
    Hod(i,j) ;
    Solve (i+1) ;
    ;
    End;
    End
    Else Begin
    Inc (S);{*Счетчик числа решений, глобальная
    *}
    Print;{*Вывод решения. *}
    End;
    End;
    Продолжим изучение задачи. Нас интересуют только несим- метричные решения. Для доски 8*8 ответ 12. Это задание тре- бует предварительных разъяснений. Из каждого решения зада- чи о ферзях можно получить ряд других при помощи вращений доски на 90°, 180° и 270° и зеркальных отражений относитель- но линий, разделяющих доску пополам (система координат

    84
    Перебор я методы его сокращения фиксирована). Доказано, что в общем случае для любой допус- тимой расстановки N ферзей возможны три ситуации:
    • при одном отражении доски возникает новая расстановка ферзей, а при поворотах и других отражениях новых ре- шений не получается;
    • поворот на 90° и его отражение дают еще две расстановки ферзей;
    • три поворота и четыре отражения дают новые расстанов- ки. ,
    Для отсечения симметричных решений на всем множестве решений требуется определить некоторое отношение порядка.
    Представим решение в виде вектора длиной N, координатами которого являются числа от 1 до N. Для ферзя, стоящего в строке, координатой его столбца является координата век- тора. Для того, чтобы не учитывать симметричные решения,
    будем определять минимальный вектор среди всех векторов,
    получаемых в результате
    Процедуры
    Sim2,
    Sim3 выполняют зеркальные отображения вектора решения от- носительно горизонтальной, вертикальной и одной из диагона- льных осей. Известно (из геометрии), что композиция этих дает все определенные выше симметрии шахматной доски, причем не принципиально, в какой последовательности выполняются эти процедуры для каждой конкретной компози- ции. Проверка «на минимальность» решения производится функцией которая возвращает значение True в том слу- чае, когда одно из симметричных решений строго меньше теку- щего решения. Возможный вариант реализации (отсечение на выводе решений) приведен ниже по тексту.
    Type
    Of 'Integer;
    Procedure
    Var
    Begin
    For
    To N Do
    :
    ;
    End;
    Procedure Sim2 (Var
    ;
    Var i ,
    Begin
    For i:=l To N Div 2 Do Begin
    End;
    End;
    Procedure

    Перебор и методы его сокращения 85
    Var
    Begin
    For i:=l To N Do
    End;
    Function
    -.Boolean;
    Var
    Begin
    i : =1 ;
    While
    And (Y[i]=X[i]) Do Inc(i);
    If i>N Then Cmp:=False
    Else If Y[i]
    End;
    Procedure
    Var j
    Y:
    Begin
    If i<=N Then Begin
    For
    To N Do
    If
    Then Begin
    ;
    Solve
    ;
    ;
    End;
    End
    Else Begin
    For
    To 7 Do Begin
    Y:=X;
    If j And 1 =0 Then
    (Y) ;
    If j And 2 =0 Then
    (Y) ;
    If j And 4 =0 Then
    (Y) ;
    If
    Then
    End;
    If f Then Begin
    Inc(S);{*Счетчик числа решений, глобальная
    переменная. *}
    Print-; {*Вывод решения. *}
    End;
    End;
    End;

    86 3. Перебор и методы его сокращения
    Примечание
    Программу решения задачи о шахматных ферзях можно написать по-разному. Ниже по тексту приведено одно из возможных реше- ний . Решение очень компактное, по-своему изящное, но не будем комментировать его. Попробуйте разобраться с ним и ответить на вопрос: в чем заключается отличие в стилях при написании про- грамм в этом примере и в целом в данном учебнике.
    Program Ferz;
    Uses Crt;
    Const N=8;
    Var
    Of
    Procedure Rf
    ;
    Var
    Begin
    For j:=l To N Do Begin
    While (k
    Do Begin
    If
    Or
    (k-i)=Abs(B[k]-B[i] ) )
    Then
    Inc(k) ;
    End;
    If p=0 Then
    If i
    Else Begin
    For t:=l To N Do Write (B [t] : 3) ;
    End;
    End;
    End;
    Begin
    ClrScr;
    End.
    Пример 2 «Задача о шахматном коне». Существуют спо- собы обойти шахматным конем доску, побывав на каждом поле по одному разу. Составить программу подсчета числа способов обхода.
    Разбор задачи начинается с оценки числа 64! — таково об- щее число способов разметки доски 8*8. Каждую разметку сле- дует оценивать на предмет того, является ли она способом обхо- программы из учебника по информатике для студентов педагогиче- ских вузов.

    3. Перебор и методы его сокращения
    87
    да конем доски (решение в
    Затем оцениваем порядок сокращения перебора исходя из условия — логика выбора оче- редного хода коня. Будем считать, что поля для хода выбира- ются по часовой стрелке. Объяснение иллюстрируется следую- щими рисунками.
    Структуры данных.
    Const N= ;
    ;
    Of
    .8] Of
    Var
    Of Integer;
    Основной фрагмент реализации — процедура Solve.
    Procedure
    Var
    Begin
    If q=N*M Then
    (t)
    Else For z:=l To 8 Do Begin
    If
    Then Solve (i , j ,q+l)
    End;
    End;
    1   2   3   4   5   6   7   8   9   ...   26


    написать администратору сайта