А. шень Издание шестое, дополненное Москва
 Скачать 1.62 Mb.
|
|
1.2.37. Как решить предыдущую задачу, если сумма по квадрату заменена на максимум? [Указание. Сравните задачи 1.2.34 и 1.2.35 .] 38 1. Переменные, выражения, присваивания 1.2.38. В массиве a[1] . . . a[n] встречаются по одному разу все це- лые числа от 0 до n, кроме одного. Найдите пропущенное число за время порядка n и с конечной дополнительной памятью. [Указание. Сложите все числа в массиве.] 1.3. Индуктивные функции (по А. Г. Кушниренко) Пусть M | некоторое множество. Функция f, аргументами которой являются последовательности элементов множества M, а значениями | элементы некоторого множества N, называется индуктивной, если её значение на последовательности x[1] . . . x[n] можно восстановить по её значению на последовательности x[1] . . . x[n-1] и по x[n], то есть если существует функция F: N × M → N, для которой f(⟨x[1], . . . , x[n]⟩) = F( f(⟨x[1], . . . , x[n-1]⟩), x[n]). Например, функция sum (сумма всех членов последовательности) ин- дуктивна, поскольку очередной член последовательности прибавляется к её сумме: sum(⟨x[1], . . . , x[n]⟩) = sum(⟨x[1], . . . , x[n-1]⟩) + x[n]. Другой пример индуктивной функции | длина последовательности. В этом случае F(n, m) = n + 1. Напротив, среднее арифметическое не является индуктивной функ- цией: если мы знаем среднее арифметическое некоторой последователь- ности, но не знаем её длины, то не можем предсказать, каким ста- нет среднее арифметическое после дописывания некоторого (известно- го нам) числа. Схема алгоритма вычисления индуктивной функции: k := 0; f := f0; {инвариант: f - значение функции на while k<>n do begin k := k + 1; f := F (f, x[k]); end; Здесь f0 | значение функции на пустой последовательности (по- следовательности длины 0). Если функция f определена только на не- 1.3. Индуктивные функции (по А. Г. Кушниренко) 39 пустых последовательностях, то первая строка заменяется на k:=1; f:=f( Если функция f не является индуктивной, полезно искать её индук- тивное расширение | такую индуктивную функцию g, значения кото- рой определяют значения f (это значит, что существует такая функ- ция t, что f(⟨x[1] . . . x[n]⟩) = t(g(⟨x[1] . . . x[n]⟩)) при всех ⟨x[1] . . . x[n]⟩). Можно доказать, что среди всех индуктив- ных расширений существует минимальное расширение F (минималь- ность означает, что для любого индуктивного расширения g значения F определяются значениями g). 1.3.1. Укажите индуктивные расширения для следующих функций: (а) среднее арифметическое последовательности чисел; (б) число элементов последовательности целых чисел, равных её мак- симальному элементу; (в) второй по величине элемент последовательности целых чисел (тот, который будет вторым, если переставить члены в неубывающем порядке); (г) максимальное число идущих подряд одинаковых элементов; (д) максимальная длина монотонного (неубывающего или невозра- стающего) участка из идущих подряд элементов в последовательности целых чисел; (е) число групп из единиц, разделённых нулями (в последовательно- сти нулей и единиц). Решение. (а) ⟨сумма всех членов последовательности; длина⟩; (б) ⟨число элементов, равных максимальному; значение максималь- ного⟩; (в) ⟨наибольший элемент последовательности; второй по величине элемент⟩; (г) ⟨максимальное число идущих подряд одинаковых элементов; чи- сло идущих подряд одинаковых элементов в конце последовательности; последний элемент последовательности⟩; (д) ⟨максимальная длина монотонного участка; максимальная дли- на неубывающего участка в конце последовательности; максимальная длина невозрастающего участка в конце последовательности; послед- ний член последовательности⟩; (е) ⟨число групп из единиц, последний член⟩. 40 1. Переменные, выражения, присваивания 1.3.2. (Сообщил Д. В. Варсанофьев) Даны две последовательности целых чисел x[1] . . . x[n] и y[1] . . . y[k]. Выясните, является ли вторая последовательность подпоследовательностью первой, то есть можно ли из первой вычеркнуть некоторые члены так, чтобы осталась вторая. Число действий порядка n + k. Решение. Вариант 1. Будем сводить задачу к задаче меньшего раз- мера. n1:=n; k1:=k; {инвариант: искомый ответ <=> возможность из x[1]..x[n1] получить y[1]..y[k1] } while (n1 > 0) and (k1 > 0) do begin if x[n1] = y[k1] then begin n1 := n1 - 1; k1 := k1 - 1; end else begin n1 := n1 - 1; end; end; {n1 = 0 или k1 = 0; если k1 = 0, то ответ - да, если k1<>0 (и n1 = 0), то ответ - нет} answer := (k1 = 0); Мы использовали то, что если x[n1] = y[k1] и y[1] . . . y[k1] | под- последовательность x[1] . . . x[n1], то y[1] . . . y[k1-1] | подпоследова- тельность x[1] . . . x[n1-1]. Вариант 2. Функция ⟨x[1] . . . x[n1]⟩ ↦→ [максимальное k1, для кото- рого y[1] . . . y[k1] есть подпоследовательность x[1] . . . x[n1]] индук- тивна. 1.3.3. Даны две последовательности x[1] . . . x[n] и y[1] . . . y[k] це- лых чисел. Найдите максимальную длину последовательности, явля- ющейся подпоследовательностью обеих последовательностей. Количе- ство операций порядка n · k. Решение (сообщено М. Н. Вайнцвайгом, А. М. Диментманом). Обо- значим через f(p, q) максимальную длину общей подпоследовательно- сти последовательностей x[1] . . . x[p] и y[1] . . . y[q]. Тогда x[p] ̸= y[q] ⇒ f(p, q) = max (f(p, q−1), f(p−1, q)); x[p] = y[q] ⇒ f(p, q) = max (f(p, q−1), f(p−1, q), f(p−1, q−1)+1). 1.3. Индуктивные функции (по А. Г. Кушниренко) 41 (Поскольку f(p − 1, q − 1) + 1 > f(p, q − 1), f(p − 1, q), во втором слу- чае максимум трёх чисел можно заменить на третье из них.) Поэтому можно заполнять таблицу значений функции f, имеющую размер n · k. Можно обойтись и памятью порядка k (или n), если индуктивно (по p) вычислять ⟨f(p,0), . . . , f(p,k)⟩ (как функция от p этот набор индук- тивен). 1.3.4. (Из книги Д. Гриса) Дана последовательность целых чисел x[1], . . . , x[n]. Найдите максимальную длину её возрастающей подпо- следовательности (число действий порядка n log n). Решение. Искомая функция не индуктивна, но имеет следующее индуктивное расширение: в него входят помимо максимальной длины возрастающей подпоследовательности (обозначим её k) также и числа u[1], . . . , u[k], где u[i] | минимальный из последних членов возраста- ющих подпоследовательностей длины i. Очевидно, u[1] 6 . . . 6 u[k]. При добавлении нового члена в x значения u и k корректируются. n1 := 1; k := 1; u[1] := x[1]; {инвариант: k и u соответствуют данному выше описанию} while n1 <> n do begin n1 := n1 + 1; {i - наибольшее из тех чисел отрезка 1..k, для которых u[i] < x[n1]; если таких нет, то i=0 } if i = k then begin k := k + 1; u[k+1] := x[n1]; end else begin {i < k, u[i] < x[n1] <= u[i+1] } u[i+1] := x[n1]; end; end; Фрагмент ... использует идею двоичного поиска; в инварианте услов- но полагаем u[0] равным минус бесконечности, а u[k+1] | плюс бес- конечности. Наша цель: u[i] < x[n1] 6 u[i+1]. i:=0; j:=k+1; {u[i] < x[n1] <= u[j], j > i} while (j - i) <> 1 do begin s := i + (j-i) div 2; {i < s < j} if x[n1] <= u[s] then begin j := s; end else begin {u[s] < x[n1]} 42 1. Переменные, выражения, присваивания i := s; end; end; {u[i] < x[n1] <= u[j], j-i = 1} Замечание. Более простое (но не минимальное) индуктивное рас- ширение получится, если для каждого i хранить максимальную длину возрастающей подпоследовательности, оканчивающейся на x[i]. Это расширение приводит к алгоритму с числом действий порядка n 2 . Есть и другой изящный алгоритм с квадратичным временем работы (со- общил М. В. Вьюгин): найти максимальную общую подпоследователь- ность исходной последовательности и отсортированной последователь- ности с помощью предыдущей задачи. 1.3.5. Какие изменения нужно внести в решение предыдущей за- дачи, если надо искать максимальную неубывающую последователь- ность? 2. ПОРОЖДЕНИЕ КОМБИНАТОРНЫХ ОБЪЕКТОВ Здесь собраны задачи, в которых требуется получить один за дру- гим все элементы некоторого множества. 2.1. Размещения с повторениями 2.1.1. Напечатайте все последовательности длины k из чисел 1..n. Решение. Будем печатать их в лексикографическом порядке (после- довательность a предшествует последовательности b, если для некото- рого s их начальные отрезки длины s равны, а (s+1)-й член последова- тельности a меньше). Первой будет последовательность <1,1,...,1>, последней | последовательность ...x[1]..x[k] положить равными 1 ...напечатать x ...last[1]..last[k] положить равным n {напечатаны все до x включительно} while x <> last do begin ...x := следующая за x последовательность ...напечатать x end; Опишем, как можно перейти от x к следующей последовательности. Согласно определению, у следующей последовательности первые s чле- нов должны быть такими же, а (s+1)-й | больше. Это возможно, если x[s+1] меньше n. Среди таких s нужно выбрать наибольшее (иначе полученная последовательность не будет непосредственно следующей). 44 2. Порождение комбинаторных объектов Соответствующее x[s+1] нужно увеличить на 1. Итак, надо, двигаясь с конца последовательности, найти самый правый член, меньший n (он найдётся, т. к. по предположению x<>last), увеличить его на 1, а иду- щие за ним члены положить равными 1. p:=k; while not (x[p] < n) do begin p := p-1; end; {x[p] < n, x[p+1] = ... = x[k] = n} x[p] := x[p] + 1; for i := p+1 to k do begin x[i]:=1; end; Замечание. Если членами последовательности считать числа не от 1 до n, а от 0 до n-1, то переход к следующему соответствует прибавле- нию единицы в n-ичной системе счисления. 2.1.2. В предложенном алгоритме используется сравнение двух мас- сивов (x <> last). Устраните его, добавив булевскую переменную l и включив в инвариант соотношение l ⇔ последовательность x | последняя. 2.1.3. Напечатайте все подмножества множества {1..k}. Решение. Подмножества находятся во взаимно однозначном соот- ветствии с последовательностями нулей и единиц длины k. 2.1.4. Напечатайте все последовательности положительных целых чисел длины k, у которых i-й член не превосходит i. 2.2. Перестановки 2.2.1. Напечатайте все перестановки чисел 1..n (то есть последова- тельности длины n, в которые каждое из этих чисел входит по одному разу). Решение. Перестановки будем хранить в массиве x[1]..x[n] и пе- чатать в лексикографическом порядке. (Первой при этом будет пере- становка ⟨1 2 . . . n⟩, последней | ⟨n . . . 2 1⟩. Для составления алгоритма перехода к следующей перестановке зададимся вопросом: в каком слу- чае k-й член перестановки можно увеличить, не меняя предыдущих? 2.3. Подмножества 45 Ответ: если он меньше какого-либо из следующих членов (т. е. членов с номерами больше k). Мы должны найти наибольшее k, при котором это так, т. е. такое k, что x[k] < x[k+1] > . . . > x[n] После этого значение x[k] нужно увеличить минимальным возмож- ным способом, т. е. найти среди x[k+1]..x[n] наименьшее число, боль- шее его. Поменяв x[k] с ним, остаётся расположить числа с номерами k+1..n так, чтобы перестановка была наименьшей, т. е. в возрастаю- щем порядке. Это облегчается тем, что они уже расположены в убыва- ющем порядке. Алгоритм перехода к следующей перестановке: { k:=n-1; {последовательность справа от k убывающая: x[k+1]>...>x[n]} while x[k] > x[k+1] do begin k:=k-1; end; {x[k] < x[k+1] > ... > x[n]} t:=k+1; {t <=n, все члены отрезка x[k+1] > ... > x[t] больше x[k]} while (t < n) and (x[t+1] > x[k]) do begin t:=t+1; end; {x[k+1] > ... > x[t] > x[k] > x[t+1] > ... > x[n]} ...обменять x[k] и x[t] {x[k+1] > ... > x[n]} ...переставить участок x[k+1]..x[n] в обратном порядке Замечание. Программа имеет знакомый дефект: если t=n, то x[t+1] не определено. 2.3. Подмножества 2.3.1. Для заданных n и k (k 6 n) перечислите все k-элементные под- множества множества {1..n}. Решение. Будем представлять каждое подмножество последователь- ностью x[1]..x[n] нулей и единиц длины n, в которой ровно k еди- ниц. (Другой способ представления разберём позже.) Такие последова- тельности упорядочим лексикографически (см. выше). Очевидный спо- соб решения задачи | перебирать все последовательности как раньше, 46 2. Порождение комбинаторных объектов а затем отбирать среди них те, у которых k единиц | мы отбросим, считая его неэкономичным (число последовательностей с k единицами может быть много меньше числа всех последовательностей). Будем ис- кать такой алгоритм, чтобы получение очередной последовательности требовало не более C·n действий. В каком случае s-й член последовательности можно увеличить, не меняя предыдущие? Если x[s] меняется с 0 на 1, то для сохранения общего числа единиц нужно справа от х[s] заменить 1 на 0. Для это- го надо, чтобы справа от x[s] единицы были. Если мы хотим перейти к непосредственно следующему, то x[s] должен быть первым справа нулём, за которым стоят единицы. Легко видеть, что х[s+1]=1 (иначе х[s] не первый). Таким образом надо искать наибольшее s, для кото- рого х[s]=0, x[s+1]=1: x 0 ↑ s 1..1 0..0 За х[s+1] могут идти ещё несколько единиц, а после них несколько ну- лей. Заменив х[s] на 1, надо выбрать идущие за ним члены так, чтобы последовательность была бы минимальна с точки зрения нашего поряд- ка, т. е. чтобы сначала шли нули, а потом единицы. Вот что получается: первая последовательность: 0..01..1 (n-k нулей, k единиц); последняя последовательность: 1..10..0 (k единиц, n-k нулей); алгоритм перехода к следующей за х[1]..x[n] последовательности (предполагаем, что она есть): s := n - 1; while not ((x[s]=0) and (x[s+1]=1)) do begin s := s - 1; end; {s - член, подлежащий изменению с 0 на 1} num:=0; for k := s to n do begin num := num + x[k]; end; {num - число единиц на участке x[s]..x[n], число нулей равно (длина - число единиц), т.е. (n-s+1) - num} x[s]:=1; for k := s+1 to n-num+1 do begin x[k] := 0; end; 2.3. Подмножества 47 {осталось поместить num-1 единиц в конце} for k := n-num+2 to n do begin x[k]:=1; end; Другой способ представления подмножеств | это перечисление их элементов. Чтобы каждое подмножество имело ровно одно представле- ние, договоримся перечислять элементы в возрастающем порядке. При- ходим к такой задаче. 2.3.2. Перечислите все возрастающие последовательности длины k из чисел 1..n в лексикографическом порядке. (Пример: при n=5, k=2 получаем: 12 13 14 15 23 24 25 34 35 45.) Решение. Минимальной будет последовательность ⟨1 2 . . . k⟩; макси- мальной | ⟨(n-k+1) . . . (n-1) n⟩. В каком случае s-й член последова- тельности можно увеличить? Ответ: если он меньше n-k+s. После уве- личения s-го элемента все следующие должны возрастать с шагом 1. Получаем такой алгоритм перехода к следующему: s:=n; while not (x[s] < n-k+s) do begin s:=s-1; end; {s - номер элемента, подлежащего увеличению}; x[s] := x[s]+1; for i := s+1 to n do begin x[i] := x[i-1]+1; end; 2.3.3. Пусть мы решили представлять k-элементные подмножества множества {1..n} убывающими последовательностями длины k, упо- рядоченными по-прежнему лексикографически. (Пример: 21 31 32 41 42 43 51 52 53 54.) Как выглядит тогда алгоритм перехода к следу- ющей? Ответ. Ищем наибольшее s, для которого х[s+1]+1 < x[s]. (Если такого s нет, полагаем s=0.) Увеличив x[s+1] на 1, кладём остальные минимально возможными (x[t]=k+1-t для t>s). 2.3.4. Решите две предыдущие задачи, заменив лексикографиче- ский порядок на обратный (раньше идут те, которые больше в лек- сикографическом порядке). 2.3.5. Перечислите все вложения (функции, переводящие разные элементы в разные) множества {1..k} в {1..n} (предполагается, что 48 2. Порождение комбинаторных объектов k 6 n). Порождение очередного элемента должно требовать не более C · k действий. [Указание. Эта задача может быть сведена к перечислению подмно- жеств и перестановок элементов каждого подмножества.] 2.4. Разбиения 2.4.1. Перечислите все разбиения целого положительного числа n на целые положительные слагаемые (разбиения, отличающиеся лишь порядком слагаемых, считаются за одно). (Пример: n=4, разбиения 1+1+1+1, 2+1+1, 2+2, 3+1, 4.) Решение. Договоримся, что (1) в разбиениях слагаемые идут в не- возрастающем порядке, (2) сами разбиения мы перечисляем в лексико- графическом порядке. Разбиение храним в начале массива x[1]..x[n], при этом количество входящих в него чисел обозначим k. В начале x[1]=...=x[n]=1, k=n, в конце x[1]=n, k=1. В каком случае x[s] можно увеличить, не меняя предыдущих? Во-первых, должно быть x[s-1]>x[s] или s=1. Во-вторых, s долж- но быть не последним элементом (увеличение s надо компенсировать уменьшением следующих). Увеличив s, все следующие элементы надо взять минимально возможными. s := k - 1; while not ((s=1) or (x[s-1] > x[s])) do begin s := s-1; end; {s - подлежащее увеличению слагаемое} x [s] := x[s] + 1; sum := 0; for i := s+1 to k do begin sum := sum + x[i]; end; {sum - сумма членов, стоявших после x[s]} for i := 1 to sum-1 do begin x [s+i] := 1; end; k := s+sum-1; 2.4.2. Представляя по-прежнему разбиения как невозрастающие по- следовательности, перечислите их в порядке, обратном лексикографи- ческому (для n=4, например, должно быть 4, 3+1, 2+2, 2+1+1, 1+1+1+1). 2.5. Коды Грея и аналогичные задачи 49 [Указание. Уменьшать можно первый справа член, не равный 1; най- дя его, уменьшим на 1, а следующие возьмём максимально возможны- ми (равными ему, пока хватает суммы, а последний | сколько оста- нется).] 2.4.3. Представляя разбиения как неубывающие последовательно- сти, перечислите их в лексикографическом порядке. Пример для n=4: 1+1+1+1, 1+1+2, 1+3, 2+2, 4. [Указание. Последний член увеличить нельзя, а предпоследний | можно; если после увеличения на 1 предпоследнего члена за счёт по- следнего нарушится возрастание, то из двух членов надо сделать один, |