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

  • Третья задача.

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


    Скачать 5.46 Mb.
    НазваниеПо вопросам приобретения обращаться
    АнкорОкулов.Программирование.в.алгоритмах.pdf
    Дата26.04.2017
    Размер5.46 Mb.
    Формат файлаpdf
    Имя файлаОкулов.Программирование.в.алгоритмах.pdf
    ТипДокументы
    #5718
    страница4 из 26
    1   2   3   4   5   6   7   8   9   ...   26
    Пятая задача. По размещению определить его номер (раз- мещения упорядочены в лексикографическом порядке).
    Поясним идею решения на примере. Дано размещение 345.
    Количество свободных элементов, меньших 3, равно 2
    (12*2=24). Количество свободных номеров, меньших 4, также
    2 — 24+3*2=30. И наконец, меньших пяти, также 2. Ответ:
    12*2+3*2+1*2=32.
    Function
    {*Используется
    процедура
    вычисления количества
    Var
    LongInt;
    Of
    {*Множество элементов
    Begin
    = [] ;
    =0 ;
    For i : = 1 To
    Do
    {*i - номер позиции
    {*Счетчик числа незанятых элементов.*}
    For
    A [ i ] - 1 Do
    If Not (j In ws) Then
    (num); {*Если элемента
    j нет в ws, то увеличиваем значение
    счетчика числа незанятых
    которые встречаются до значения A[i].*}

    46 2. Комбинаторные алгоритмы
    A[i] задействован
    в размещении.*}
    счетчика
    умножаем на количество
    приходящихся на одно значение
    в позиции с номером i.*}
    End;
    End;
    2.2.3. Сочетания
    Между k-элементными подмножествами мно- жества и возрастающими последовательностями длины k с эле- ментами из множества целых чисел от 1 до N (сочетаниями) су- ществует взаимно однозначное соответствие. Так, например,
    подмножеству [2, 6, 1, 3] соответствует последовательность чи- сел 1, 2, 3,
    Таким образом, решая задачи подсчета и генера- ции всех сочетаний, мы решаем аналогичные задачи для k-эле- ментных подмножеств. Лексикографический порядок на множестве последовательностей определяется так же, как и для перестановок.
    Пример,
    1234 1235 1236 1245 1246 1256 1345 1346 1356 1456 2345 2346 2356 2456 3456
    Первая задача. Попробуем подсчитать количество сочета- ний для данных значений N и k. Использование формулы явно не продуктивно. Факториал представля- ет собой быстровозрастающую функцию, поэтому при вычисле- нии числителя и знаменателя дроби может возникнуть пере- полнение, хотя результат — число сочетаний — не превышает,
    например, значения
    Воспользуемся для подсчета чис- ла сочетаний формулой
    Получаем знаменитый треугольник Паскаля (см. с. 47). Про- сматривается явная схема вычислений. Очевидно, что если в за- даче не требуется постоянно использовать значения для раз- личных значений N и k, а требуется только подсчитать одно значение , то хранить двумерный массив в памяти компьюте- ра нет необходимости.

    Приведем процедуры вычисления для того и другого слу- чая. Подсчет всех значений C
    kN
    .
    Const
    Var
    Of LongInt;
    {*Нулевой столбец и нулевая строка необходимы,
    это позволяет обойтись без анализа на выход
    за пределы массива.*}
    Procedure FillSmallSc;
    Var i,j
    Begin
    FillChar
    For
    To N Do SmallSc
    For
    To N Do
    For
    To k Do
    If
    Then
    Else
    {*Умножение на 1.0 переводит
    целое число в
    поэтому
    переполнения при сложении не
    Стандартный прием, обязательный при "игре"
    на границах диапазона целых чисел.*}
    End;
    Второй вариант реализации процедуры.
    Type
    Of LongInt;
    Function
    LongInt;
    Var A,B:SmallSc;

    48
    2. Комбинаторные алгоритмы
    Begin
    (A),0) ;
    ;
    For
    To N Do Begin
    B[0]
    B[1] :=1;
    For
    k Do В [j]:=A[j]+A[j-1]; {*Если число
    больше максимального значения типа LongInt,
    то необходимо работать с
    арифметикой. Данная операция должна быть
    изменена - вызов процедуры сложения двух
    "длинных" чисел.*}
    А:=В;
    End;
    End;
    Вторая задача. Перейдем к алгоритму генерирования всех сочетаний в лексикографическом порядке, но прежде пример при и k=5. Число сочетаний равно 21.
    0 1
    2 3
    4 5
    6 12345 12346 12347 12357 12367 12456 7
    8 9
    10 11 12 13 12467 12567 13456 13457 13467 13567 14 15 16 17 18 19 20 14567 23456 23457 23467 23567 24567 34567
    Начальное сочетание равно 1, 2, ..., k, последнее —
    ..., N. Переход от текущего сочетания к другому осуще- ствляется по следующему алгоритму. Просматриваем сочета- ние справа налево и находим первый элемент, который можно увеличить. Увеличиваем этот элемент на единицу, а часть соче- тания (от этого элемента до конца) формируем из чисел натура- льного ряда, следующих за ним.
    Procedure
    что текущее
    сочетание (хранится в массиве С) не является
    последним.*}
    Var i,j:Integer;
    Begin

    2. Комбинаторные алгоритмы 49
    While (C[i]+k-i+1>N)
    элемент, который можно
    {*Увеличиваем на единицу.*}
    For
    k Do
    {*Изменяем
    стоящие справа элементы.*}
    End;
    Третья задача. По номеру L определяем соответствующее сочетание. Для решения этой задачи необходимо иметь (вычис- лить) массив SmallSc, т. е. использовать первую схему вычис- ления числа сочетаний (первая задача) для данных значений N
    и k. Порядок на множестве сочетаний лексикографический. В
    таблице, приведенной выше, номера с 0 по 14 имеют сочета- ния, в которых на первом месте записана единица. Число та- ких сочетаний — («израсходован» один элемент из N и один элемент из
    Сравниваем число L со значением Если зна- чение L больше , то на первом месте в сочетании записана не единица, а большее число. Вычтем из L значение и продол- жим сравнение.
    Procedure
    (L:LongInt);
    Var
    Begin
    sc:=n;
    For i:=1
    k Do
    {*i - номер элемента
    в сочетании; k-i - число элементов
    в сочетании.*}
    j:=1; {*sc-j - число элементов (п), из которых
    формируется сочетание.*}
    While
    Do Веgiп {*Для
    данной позиции в сочетании и числа
    элементов в сочетании находим тот элемент
    массива SmallSc, который превышает
    текущее значение L.*}
    Dec
    ;
    Inc
    {*Невыполнение условия цикла While
    говорит о том, что мы нашли строку
    таблицы
    т.е. то количество
    из которых формируется
    очередное сочетание, или тот интервал
    номеров сочетаний (относительно
    предыдущей цифры), в котором находится
    текущее значение номера

    50 2. Комбинаторные алгоритмы
    End;
    цифра плюс приращение.*}
    Inc(ls,j); {*Изменяем зна чение текущей цифры
    Dec
    {*Изменяем количество элементов,
    из которых формируется остаток
    End;
    End;
    Пример (N=7,
    Для полного понимания логики выполните ручную трасси- ровку при N=9,
    Ответ — 23479. Однако достаточно,
    пора и честь знать.

    2. Комбинаторные алгоритмы
    51
    Четвертая задача. Требуется по сочетанию получить его номер. Как и в предыдущей задаче, необходимо иметь массив
    Эта задача проще предыдущей. Требуется аккуратно просмотреть часть массива
    Эта часть массива опреде- ляется сочетанием, для которого ищется номер. Например, на первом месте в сочетании стоит цифра 3
    k=4). Ищется сумма — количество сочетаний, в которых на пер- вом месте записана цифра 1, цифра 2 и цифра 3. Аналогично для следующих цифр сочетания. Предполагаем, что С[0] равно
    0 — технический прием, позволяющий избежать лишних про- верок условий.
    Function
    Var sc:LongInt;
    j; Integer;
    Begin
    sc:=1;
    For
    к Do
    For j:=C[i-1]+1 To C[i]-1 Do Inc(sc,
    ;
    ;
    End;
    Пример (N=9, k=5,
    i
    1 2
    3 4
    5
    j
    1
    от З до 2, цикл j не работает от 4 до 3, цикл по j не работает
    5 6
    8
    SC
    старое
    1 71 71 71 75 78
    SmallSc[N-j,k-i]
    70
    -
    4 3
    1
    SC
    новое
    71
    -
    -
    75 78 79
    Пример (N=7,
    i
    1 3
    4 5
    j
    1
    от 3 до 2, цикл по j не работает от 4 до 3, цикл по j не работает
    5
    от 7 до 6, цикл по j не работает
    SC
    старое
    1 16 16 16 18 15
    -
    -
    2
    -
    SC
    новое
    16
    -
    -
    18
    -
    Обратите внимание на то, что нумерация сочетаний в зада- чах 3 и 4 различна. В задаче 3 сочетания нумеруются с 0, а в задаче 4 — с 1.

    52 2. Комбинаторные алгоритмы
    Пятая задача. Выберем для представления сочетания дру- гой вид — последовательность из 0 и 1. Последовательность храним в массиве (С) из N элементов со значениями 0 или 1,
    при этом С[i]=1 говорит о том, что элемент есть в соче- тании (подмножестве). Пусть N=7,
    В таблице представле- ны последовательности в той очередности, в которой они гене- рируются, и соответствующие им сочетания.
    0 1
    2 3
    4 5
    6 0011111 0101111 0110111 0111011 0111101 0111110 1001111 12346 12356 12456 13456 23456 12347 7
    9 10 11 12 13 1010111 1011011 1011101 1011110 1100111 1101011 1101101 12357 12457 13457 23457 12367 12467 13467 14 15 16 17 18 19 20 1101110 1110011 1110101 1110110 1111001 1111010 1111100 23467 12567 13567 23567 14567 24567 34567
    Принцип генерации последовательностей. Начинаем с конца последовательности. Находим пару C[i]=0 и C[i+1]=1. Если та- кой пары нет, то получена последняя последовательность. Если есть, то заменяем на месте i нуль на единицу и корректируем последовательность справа от i. Последовательность должна быть минимальна с точки зрения введенного порядка, поэтому вначале записываются 0, а затем 1, при этом количество 1 в по- следовательности должно быть сохранено. Опишем основные фрагменты реализации этой логики.
    Const
    Type
    Of 0. .1;
    Var Curr,
    MyArray;
    и последняя
    k:
    Begin ...
    For i : = 1 To N Do Begin
    For i:=1 To k Do Begin
    End; {*Формируем начальную
    и последнюю
    While Not
    Do Begin
    While (i>0) And Not ((Curr [i]=0) And
    (Curr [i + 1] =1) ) Do Dec (i);
    пару
    она
    так как последовательность
    не
    Num:=0;

    2. Комбинаторные алгоритмы
    53
    For
    n Do
    (Num,Curr
    );
    количество единиц.*}
    For j : = i + 1
    Do
    {*Записываем
    нули.*}
    For
    To n Do
    {*3аписываем
    End;
    End;
    2.2.4. Разбиение числа на слагаемые
    Дано натуральное число N. Его можно записать в виде сум- мы натуральных слагаемых:
    где
    a
    1
    ...,
    бо- льше нуля. Будем считать суммы эквивалентными, если они отличаются только порядком слагаемых. Класс эквивалентных сумм приведенного вида однозначно представляется последова- тельностями b
    1
    ...,
    упорядоченными по невозрастанию.
    Каждую такую последовательность b
    1
    ...,
    назовем разбиени- ем числа N на слагаемых.
    Как обычно, решаем четыре задачи: подсчет количества раз- личных разбиений числа; генерация разбиений относительно определенного отношения порядка, введенного на множестве разбиений; получение разбиения по его номеру и задача, обрат- ная третьей.
    Первая задача.
    пример для N=8, а затем рассуж- дения, позволяющие написать программный код.
    1 2
    3 4
    5 6
    7 8
    11111111 2222 311111 3221 9
    10 11 12 13 14 15 16 3311 332 41111 4211 422 431 44 5111 17 19 20 21 22 521 53 611 62 71 8
    Число разбиений числа N на слагаемых обозначим через
    P(N,k), общее число разбиений — P(N). Очевидно, что значение равно сумме P(N,k) по значению
    Считаем, что
    Известен следующий факт.

    54 2. Комбинаторные алгоритмы
    Теорема. Число разбиений числа N на слагаемых равно числу разбиений числа N с наибольшим слагаемым, равным
    Теорема доказывается простыми рассуждениями на основе диаграмм Феррерса. Пример такой диаграммы приведен ниже.
    Главное, что следует из этого факта, — реальный путь под- счета числа разбиений. Число разбиений P(i,j) равно сумме по значению k, где k изменяется от 0 до j. Другими сло- вами, j «выбрасывается» из i и подсчитывается число способов разбиения числа i-j на k слагаемых. Проверьте эту логику с помощью следующей таблицы.
    1
    2
    3
    4
    5
    6
    7
    8
    0
    0
    0
    0
    0
    0
    0
    0
    0
    1
    1
    1
    1
    1
    1
    1
    1
    1
    2
    0
    1
    1
    2
    2
    3
    3
    4
    3
    0
    0
    1
    1
    2
    .3
    4
    5
    4
    0
    0
    0
    1
    1
    2
    3
    5
    5
    0
    0
    0
    0
    1
    1
    2
    3
    6
    0
    0
    0
    0
    0
    1
    1
    2
    7
    0
    0
    0
    0
    0
    0
    1
    1
    8
    0
    0
    0
    0
    0
    0
    0
    1
    2
    3
    5
    7
    11
    15
    22
    Например, Р(8,3)=Р(5,0)+Р(5,1)+Р(5,2)+Р(5,3).
    Определим данные.
    Const
    Var N:LongInt;
    SmallSc:Array[0..MaxN,
    Of LongInt;
    Procedure FillSmallSc;
    Var
    Begin
    For i:=1 To N Do
    For
    To i Do

    2. Комбинаторные алгоритмы 55
    For k:=0
    j Do
    j ] ,
    End;
    Таблица значений сформирована, она нам потребуется для решения других задач. Для подсчета же числа разбиений оста- лось написать простую процедуру.
    Procedure
    Var
    Begin
    For i:=2 To N Do
    [N , i ] ;
    End;
    Вторая задача. Генерация разбиений. Во-первых, необхо- дима структура данных для хранения разбиения. По традиции используем массив.
    Var
    Of Integer;
    В
    будем хранить длину разбиения, т. е. число задей- ствованных элементов массива Now. Возьмем из первой табли- цы одно из разбиений числа 8, например «41111», следующее
    «4211». В каком случае можно увеличить
    Видим, что
    Now[1] должно быть больше Now[2], т. е. в текущем разбиении находится «скачок» - Now[i-1]>Now[i],
    увеличивается на единицу, а все следующие элементы разбиения берутся ми- нимально возможными. Всегда ли возможна данная схема из- менения разбиения? Например, разбиение «44», следующее —
    «5111». Таким образом, или «скачок», или i равно 1. Кроме того, изменяемый элемент не может быть последним, ибо уве- личение без уменьшения невозможно.
    Procedure GetNext;
    Var
    Begin
    элемент
    {*B sc накапливаем
    сумму, это число представляется затем
    минимально возможными
    While (i>1) And
    Do Begin

    56 2. Комбинаторные алгоритмы
    End;
    Inc
    {*Увеличиваем найденный элемент
    на единицу.*}
    {*Изменяем длину
    For j :=1
    sc Do
    :=1;
    минимально возможные элементы,
    End;
    А будет ли работать данная логика для последнего разбие- ния (в нашем примере для «8»)? Оказывается, что нет. Прове- рьте.
    Считаем, что в Now хранится первое разбиение, а в массиве
    Last — последнее. Они формируются, например, в процедуре типа In.it. И схема генерации....
    While
    ) Do
    {*Фунция Eq дает
    если текущее распределение
    совпадает с последним, и
    в противном случае, можно сделать проще -
    While Now[0]<>1 Do ...*}
    GetNext;
    Print; {*Вывод
    End;
    Третья задача. По номеру разбиения получить само раз- биение (Now). Нумерация разбиений осуществляется относите- льно введенного отношения порядка. Пусть L равно 0. Сделаем
    «набросок» логики.
    {*sc - число, которое представлено
    разбиением, i - номер позиции в
    While scOO Do Begin {*Пока число не исчерпано.*}
    которое должно записываться
    на место i в разбиении.*}
    ???????????
    j определяется по
    L, пока не знаем как.*}
    {*Формируем текущую
    позицию разбиения и готовимся к переходу для
    формирование новой.*}
    End;
    Как это ни странно, но если вместо знаков «???» оставить пустое место («заглушку»), то при L, равном 0, данный набро-

    2. Комбинаторные алгоритмы 57
    сок будет работать — на выходе логики мы получим начальное разбиение, состоящее из единиц. Пусть L равно 1. Обратимся ко второй таблице данного материала. Проверяем
    SmallSc[8,1]. Если L больше или равно этому значению, то мы уменьшим значение L на SmallSc[8,1], увеличим значение j на единицу и, в конечном итоге, получим разбиение 2111111.
    Итак, что нам необходимо сделать? Да просто просмотреть строку массива SmallSc с номером sc и определить последний элемент строки, его номер в j, который меньше текущего значе- ния L. Мы последовательно отсекаем разбиения числа sc, начи- нающиеся с чисел j. Ниже приведен полный текст процедуры.
    Procedure
    Var
    Begin
    sc:=N;
    While sc<>0 Do Begin j:=1;
    Do Begin
    Inc(j);
    End;
    (i);
    End;
    :=i-1; {*Корректируем длину
    End;
    1   2   3   4   5   6   7   8   9   ...   26


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