Крючкова Е.Н. Основы математической логики и теории алгоритмов

Подождите немного. Документ загружается.

Найдем производящую последовательность для чисел Фибоначчи. Построим произ-

водящую функцию

F (x) =

∞

∑

i=0

. (6.6)

Подставим в (6.6) рекурсивную формулу (6.5) вычисления f

F (x) =

∑

∞

i=0

= f

+ f

x +

∑

∞

i=2

= f

+ f

x +

∑

∞

i=2

i−1

+ f

i−2

= f

+ f

x +

∑

∞

i=2

i−1

∑

∞

i=2

i−2

= f

+ f

x + x

∑

∞

i=1

+ x

∑

∞

i=0

= f

+ f

x + x(F (x) − f

) + x

F (x).

Из полученного уравнения

F (x) = f

+ f

x + x(F (x) − f

) + x

F (x)

или

F (x) = 1 + x + x(F (x) − 1) + x

F (x)

определяем F (x) :

F (x) =

1 − x − x

. (6.7)

Для того, чтобы найти аналитическое выражение для f

достаточно разложить (6.7)

в степенной ряд и сопоставить коэффициенты при равных степенях переменной x.

Сначала преобразуем выражение 1 − x − x

по теореме Виета:

1 − x − x

= (1 − αx)(1 − βx),

где

α =

1 −

√

, β =

1 +

√

Используя метод неопределенных коэффициентов, получим

F (x) =

1 − x − x

1 − α x

1 − βx

и тогда

A =

α − β

, B =

α − β

Разложим в ряд Маклорена функцию f(x), представляющую собой общий вид каж-

дого из двух слагаемых в полученном выражении функции F(x):

f(x) =

1 − α x

∞

∑

k=0

(k)

(0),

где

′

(x) = α(1 − αx)

−2

′′

(x) = 2α

(1 − αx)

−3

...

(x) = k! · α

(1 − αx)

−k−1

...

171

Тогда в точке x = 0 получаем

′

(0) = α,

′′

(x) = 2α

...

(x) = k! · α

...

При подстановке в ряд Маклорена полученных значений производных получаем

f(x) =

1 − α x

∞

∑

k=0

Окончательно имеем

F (x) =

1 − x − x

1 − α x

1 − βx

∞

∑

k=0

− β

α − β

Отсюда получаем общее выpажение для f

− β

α − β

[

√

((

1 +

√

)

k+1

− (

1 −

√

)

k+1

)

]

. (6.8)

Значения функций, вычисляемых по формулам (6.8) и (6.5), совпадают. Этот теоре-

тически доказанный факт иллюстрирует следующая программа.

// Пример производящей последовательности для чисел Фибoначчи

#include <stdio.h>

#include <math.h>

#include <STDLIB.H>

int main(void)

{

long int a=1, b=1, d, r, i;

double d1, d2, s1, s2, p=5.0, frac;

frac=1.0/sqrt(p);

d1=(1+sqrt(p))/2; d2=(1-sqrt(p))/2;

s1=d1*d1; s2=d2*d2;

for(i=3; i<25; i++)

{

s1*=d1; s2*=s2;

d=a+b; r=(long int)(frac*(s1-s2)+0.500001);

printf("%ld %ld\n",d,r);

a=b; b=d;

}

return 0;

}

Приведенная программа преследует только демонстрационные цели, показывая

на практике совпадение значений функций (6.8) и (6.5). Реальное использование

172

этой формулы для вычисления значений чисел Фибоначчи на числах обычной длины

неэффективно по следующим причинам. Вычисление степени либо все равно потре-

бует цикла (как это сделано в приведенной выше программе ), либо выполняется

через функции логарифма и экспоненты (а это фактически приводит к вычислению

рядов ), либо использует стандартную функцию возведения в степень, которая так-

же вычисляет степенную функциию через экспоненту и логарифм. Все это означает,

что ускорения вычислений на числах обычной длины не получится. Только при ре-

ализации длинной арифметики формула (6.8) окажется эффективной, т.к. в этом

случае существенно уменьшится число выполняемых операций сложения. При этом

надо аккуратно работать с точностью вычисления рядов, чтобы полученное значение

функции было точным на множестве целых чисел.

Приведенный пример показывает сам метод использования производящих функ-

ций, которые в более сложных случаях дают хороший инструмент сокращения вы-

числений. Здесь следует сделать одно очень важное замечание. Далеко не всегда

требуется вывести явную формулу вычисления коэффициента, как мы это сделали

для чисел Фибоначчи. В большинстве случаев достаточно получить рекуррентное

соотношение между коэффициентами. В качестве упражнения предлагается решить

следующую задачу.

Задача. Найти число способов заплатить N рублей монетками достоинством по

1, 5, 10, 50 копеек, а также рублевыми монетками — по 1 и 5 рублей.

Указание к решению: запишите бесконечные суммы, представляющие все возмож-

ные способы размена. Начать проще всего со случая, когда имеется меньше разно-

видностей монет, поэтому положите для начала, что у Вас нет никаких монет, кроме

однокопеечных. Запишите производящую последовательность. Затем допустите, что

кроме монет по одной копейке допускается использовать еще и пятикопеечные. За-

пишите производящую последовательность. Аналогично продолжайте действия при

увеличении достоинства добавляющихся к разменной кассе монет.

В результате решения задачи у Вас должны получиться следующие рекурсивные

зависимости между коэффициентами:

= K

n−1

+ 1 способ выплаты монетками не старше 1 копейки

= P

n−5

+ K

способ выплаты монетками не старше 5 копеек

= D

n−10

+ P

способ выплаты монетками не старше 10 копеек

= Q

n−50

+ D

способ выплаты монетками не старше 50 копеек

= R

n−100

+ Q

способ выплаты монетками не старше 1 рубля

= M

n−500

+ R

способ выплаты монетками не старше 5 рублей

При решении задач с использованием производящих функций можно использо-

вать таблицу 6.1 аналитических выражений для этих функций.

173

Таблица 6.1

Таблица простых последовательностей и их

производящийх функций

последовательность производящая формула

функция

⟨1, 1, 1, 1, 1, 1, ...⟩

∑

∞

i=0

1−x

⟨1, −1, 1, −1, 1, −1, ...⟩

∑

∞

i=0

(−1)

1+x

⟨1, 0, 1, 0, 1, 0, ...⟩

∑

∞

i=0

[

]

1−x

⟨1, 0, ..., 0, 1, 0, ..., 0, 1, ...⟩

∑

∞

i=0

[

]

1−x

⟨1, 2, 3, 4, 5, ...⟩

∑

∞

i=0

(i + 1)x

(1−x)

⟨1, 2, 4, 8, 16, ...⟩

∑

∞

i=0

1−2x

⟨1, k, C

, C

, ...⟩

∑

∞

i=0

(1 + x)

⟨1, k, k

, k

, ...⟩

∑

∞

i=0

1−kx

⟨0, 1,

, ...⟩

∑

∞

i=1

1+x

⟨0, 1, −

, −

, ...⟩

∑

∞

i=1

(−1)

i+1

l n (1 + x)

174

6.8 Контрольные вопросы к разделу

1. В каких случаях целесообразно применение рекурсивных алгоритмов?

2. Перечислите типы данных, имеющих рекурсивную природу. Предложите на

языке Си или Паскаль описание соответствующих типов.

3. Что представляет собой метод "разделяй и властвуй"?

4. Что означает принцип балансировки при использовании метода "разделяй и

властвуй"?

5. Как устранить рекурсию в случае, когда имеется схема примитивной рекурсии?

6. Как устранить рекурсию в общем случае?

7. Что означает термин "полный перебор"?

8. Какие цели преследует отсечение вариантов?

9. Зачем используется функция цели в методе отсечения?

10. Приведите пример использования функции цели для отсечения вариантов.

11. Напишите программу игры в "крестики-нолики" с отсечением вариантов пе-

ребора.

12. Зачем используется динамическое программирование?

13. Поясните принцип динамического программирования.

14. Приведите пример программы, в которой используется принцип динамическо-

го программирования.

15. Что такое виртуальный граф и зачем он используется?

16. Приведите пример программы, в которой используется виртуальный граф.

17. Вычислите временную сложность алгоритмы Дейкстры поиска в графе мини-

мального пути от заданной вершины.

18. Какие данные хранятся в стеке при рекурсивном вызове функции?

19. Напишите нерекурсивную программу вычисления функции Аккермана.

20. Приведите пример рекурсивной функции, схема рекурсии которой не является

примитивно–рекурсивной.

6.9 Упражнения к разделу

Задание.

Написать программу решения поставленной задачи. При выполнении задания

проанализируйте постановку задачи. Не все приведенные в заданиях задачи явля-

ются NP –полными и не все — P – задачами. Если в постановке задачи сразу указана

размерность, ее величина может дать некоторую подсказку для поиска алгоритма

решения. Небольшая величина размерности, как правило, позволяет решить задачу

полным перебором, возможно, с некоторым отсечением вариантов. Большие порядки

размерности означают, что задачу можно решить только с помощью полиномиаль-

ных алгоритмов. В разработке таких алгоритмов хорошую помощь должны оказать

рассмотренные в главе методы проектирования эффективных алгоритмов.

Часть заданий сформулирована без указания порядков размеров задачи. В этом

случае Вам необходимо рассмотреть максимально эффективные с Вашей точки зре-

ния алгоритмы и сформировать требования к размерности задачи с тем, чтобы за-

дача могла быть решена на реальной памяти компьютера за разумное время.

175

6.9.1 Задача

Рассмотpим следующую задачу.

Для срочной покупки квартиры мистер Смит получил в банке заем, эквивалент-

ный Q долларам. Он должен выплатить свой долг в течении K лет, выплачивая

каждый год еще и проценты P . Это значит, что к концу каждого года долг мистера

Смита вырастает на P ∗Q

/100 ( Q

– долг на начало года ) и его текущие выплаты

вычитаются из общей суммы с учетом процентов.

В первый год мистер Смит хочет заплатить такую минимальную сумму, которая

позволит ему выплатить весь долг точно за K лет. В каждый последующий год он

хочет выплачивать или точно такую же сумму, как в предшествующий год, либо на

один цент меньше. Кроме того, он хочет закончить выплачивать долг без переплаты

даже одного цента к концу K-го года.

Банк выполняет начисление процентов с точностью в один цент и производит

начисление процентов в конце каждого года. При вычислении процентов результат

немедленно округляется до ближайшего цента, причем 0.5 центов округлается до 1

цента.

Ограничения на данные. 10 ≤ Q ≤ 1000000, 0 ≤ P ≤ 100, 1 ≤ K ≤ 100.

Входные данные. Входной файл содержит три числа Q, P и K.

Результаты. Выходной файл содержит выплаты. Если решение невозможно, вы-

ходной файл должен содержать единственную строку с текстом "Impossible". В про-

тивном случае требуется вывести выплачиваемую сумму и число лет, в течение ко-

торых эта сумма выплачивается, в виде строки: "$X for Y year(s)"

Решение.

Рассмотрим рекурсивную схему решения задачи. Пусть функция Solve(Q, M, i)

решает задачу распределения выплат и выполняет следующие действия:

а) возвращает значение 1, если при условии выплаты в текущем году M центов

на последующих шагах задача успешно решается ( здесь i - число лет до окончания

срока всех выплат, Q - общая сумма к выплате );

б) возвращает 0, если решение невозможно.

Если известно, что за i-ый год выплатили M центов, то по условию задачи в новом

(i − 1)-ом году можно выплатить M или M − 1 центов. Таким образом, достаточно

вычислить новое значение общей суммы к выплате и проверить два варианта выплат

M и M − 1 центов. Сначала надо вычислить значение нового долга по формуле

percent = 1 + P/100;

NewQ = percent ∗ Q − M + 0.5001.

Сразу следует отметить, что эта формула является абсолютно неправильным с

точки зрения языка С++ оператором, т.к. в ней не учтено представление разных ти-

пов данных в памяти ЭВМ и операции приведения типов (смотрите текст программы,

где указаны соответствующий операторы ). После того, как начислили проценты и

заплатили в данном году, делаем попытку дальнейшего решения:

if (Solve(NewQ, M-1, year-1) || Solve(NewQ, M, year-1)) return 1;

Обратите особое внимание на порядок вызова функции

Solve(...M − 1...) и Solve(...M...)

1997-1998 ACM Northeastern EuropeanRegionalProgramming Contest

176

для получения минимальной выплаты в каждом году, а не только в первом году.

Решение будет достигнуто при одновременном выполнении условий (Q == 0) и

(i == 0), т.е.

if ( Q == 0 ) return ( i == 0 );

if ( i == 0 ) return ( Q == 0 );

Анализ временной сложности указанного алгоритма приводит к определению по-

рядка сложности O(2

100

), что говорит о необходимости реализации отсечения. Чтобы

отсечь на ранних шагах решения неверные варианты выплат, необходимо на каждом

шаге контролировать возможность получения решения на последующих шагах. Для

этой цели рассмотрим минимально возможное значение выплаты в текущем (первом

от начала выплат ) году, если все выплаты совершаются за K лет. Минимальное зна-

чение выплат в текущем году получается при условии, что на последующих годах нет

снижения выплат. Введем обозначения: Q — общая сумма к выплате на начало года,

p — коэффициент роста 1 + P/100. Тогда условию задачи соответствует следующее

уравнение для вычисления минимальной суммы выплат a:

(...(((Q ∗ p − a) ∗ p − a) ∗ p − a) ∗ ...) ∗ p − a

| {z }

= 0

или

Q ∗ p

− a ∗ (p

K−1

+ p

K−2

+ ... + p

+ p + 1) = 0.

Отсюда

K−1

+ p

K−2

+ ... + p

+ p + 1

Q ∗ p

Или

· (

+ ... +

Получаем

a = Q/(

+ ··· +

Аналогично надо найти условие максимальной выплаты. В первый год придется вы-

платить максимальное значение b, если выплаты будут снижаться на всех последу-

ющих годах. Тогда получаем следующее уравнение

(...(((Q · p − b) · p − b + 1) · p − b + 2) · ...) · p − b + (k − 1) = 0

или

−b·(p

K−1

K−2

+...+p

+p+1)+1·p

k−2

+2·p

k−3

+3·p

k−4

+···+(k−2)·p

+(k−1)·p

= 0.

Получаем максимальное значение первой выплаты

b = a +

(1 ∗ p

k−2

+ 2 ∗ p

k−3

+ 3 ∗ p

k−4

+ ··· + (k − 2) ∗ p

+ (k − 1) ∗ p

)

K−1

+ p

K−2

+ ··· + p

+ p + 1)

Замечание. Значения сумм приходится вычислять на каждом шаге рекурсии, поэто-

му можно сформировать вспомогательные массивы числителей и знаменателей перед

началом вычислений. При данных по условию ограничениях такие массивы можно

не использовать, т.к. задача решается за достаточно разумное время.

Приводим текст программы решения поставленной задачи.

177

#include <STDLIB.H>

#define MAXK 100

long int Q;

int P, K; // данные: начальная сумма, проценты и число лет

double percent; // 1+P/100 - рост долга

FILE *in = fopen("loan.in","r");

FILE *out= fopen("loan.out","w");

long int payment[MAXK+1]; // выплаты по годам

void GetInterval(long int Q,int year, long int * Min, long int *Max)

// расчет границ возможных выплат [Min,Max] в текущем году

// Q - исходная сумма, year - число лет

{

int i;

double a,b,c,d;

if (year==0) { *Min=*Max=Q; return; }

if (P==0) { (*Max)=(*Min)=Q/year;

if ((*Min)*year<Q) *Max=(*Min)+1; return;

}

a=0; b=1; c=0; d=0;

for (i=0; i<year; i++)

{

c+=(year-i-1)*b; d+=b;

b=b/percent;

a+=b;

}

*Min= Q/a+0.0001;

if ( (*Min)==0 ) *Min=1;

// вычисляем максимальное значение выплаты в первый год

*Max=(*Min) + c/d + 0.5001 +1;// +1 на всякий случай из-за округления 0.5

}

int Solve(long int Q, long int M, int year) // в данном году платим M

{

if ( Q == 0) return ( year==0 );

if (year == 0) return (Q == 0); // все время истекло

if ( (Q < 0) || (M <= 0) ) return 0;

long int MaxNew=M, MNew=M, NewQ;

NewQ=(double)(percent * (double)(Q) + 0.5001) ; //начислили проценты

NewQ= NewQ - M ; // заплатили в данном году

if (NewQ!=0) GetInterval(NewQ, year-1, &MNew, &MaxNew);

if ((M < MNew) || (M-1 > MaxNew)) return 0;

if (Solve(NewQ, M-1, year-1) || Solve(NewQ, M, year-1))

{ payment[year] = M; return 1; }

return 0;

}

int main(void)

{

178

double QFloat; // float - эквивалент переменной Q

fscanf(in,"%lf %d %d",&QFloat, &P, &K);

Q= QFloat * 100 + 0.0001; // в центах исходная сумма

percent=1+((double)P)/100;

long int Min, Max; // минимальная граница выплат и максимальная на K лет

GetInterval(Q, K, &Min, &Max);

int years, num;

long int i; // текущее значение минимальной выплаты в первый год

for (i= Min; i<=Max; i++) // попытка выплатить за первый год не более i:

if (Solve( Q, i, K))

{

years= 0; // число лет одинаковых выплат

payment[0]= -1; // для организации сравнения на последнем шаге

for (num=K; num > 0; num--) //num - общее число лет для выплат

{

years++;

if (payment[num-1] != payment[num])

{

fprintf(out,"$%.2lf for %d year(s)\n",

(double)(payment[num])/100, years);

years = 0;

}

fclose(in);fclose(out);

return 0;

}

fprintf(out,"Impossible\n");

fclose(in);fclose(out);

return 0;

}

6.9.2 Варианты заданий

1. "Цепь". Дано множество слов одинаковой длины, первые два слова из них выде-

лены. Построить цепь минимальной длины от первого выделенного слова ко второму

так, чтобы все слова этой цепи были только из заданного множества. Соседние сло-

ва построенной цепи должны отличаться только одной буквой. Число слов не более

1000, длина каждого слова не превышает 10 символов.

Например, если дано множество

вол, сыр, воз, сор, вор, тор, рот, сон,

то можно построить цепь

вол → вор → сор → сыр.

2. "Кроссворд". Дано множество слов. Построить из них кроссворд заданной кон-

фигурации (число слов может быть больше требуемого количества для заполнения

кроссворда). Конфигурация кроссворда задается полем M ×N, где M – число строк

179

и N – число столбцов поля кроссворда. Знак "." на этом поле означает клетку, пред-

назначенную для записи буквы, знак "*" означает неиспользуемую для записи букв

клетку. Ограничения: M ≤ 5, N ≤ 7, число заданных слов не превышает 100.

3. "Муха на кубике". Муха ползет по кубику размерами N ×N ×N сантиметров.

Грани кубика разбиты на клетки со стороной в один сантиметр. Каждая такая клетка

выкрашена в черный или белый цвет. Переход мухи из клетки в клетку допускается

только через общую сторону при условии совпадения цветов этих клеток. Найти

кратчайший маршрут мухи из одной заданной клетки в другую заданную клетку

этого же цвета. Если существует несколько таких маршрутов, вывести любой из

них. Если решение невозможно, вывести соответствующее сообщение.

Заданы начальное и конечное положение мухи, число N(N ≤ 10) и раскраска

граней кубика. Кубик задается разверткой. На развертке черная клетка задается

буквой "B белая – буквой "W". Клетка, на которой находится муха, а также целевая

клетка также нанесены на развертку. Если муха находится на белой клетке, то она

обозначается символом "0 если на черной – символом "1". Целевая клетка всегда

того же цвета, что и занятая мухой клетка, и обозначается символом "*".

Развертка содержится в исходном файле, каждая строка и каждая позиция стро-

ки которого соответствует 1 сантиметру (или одной клетке на поверхности кубика).

Пример задания развертки в файле исходных данных для N = 2:

. . . . . . . . . . . . . . .

. . . . . B W . . . . . . . .

. . . . . W B . . . . . . . .

. . . W B W B W B W B . . . .

. . . 1 B W B B * B B . . . .

. . . . . W B . . . . . . . .

. . . . . B B . . . . . . . .

. . . . . . . . . . . . . . .

4. "Цифровая пирамида". Дана последовательность целых чисел

a = (a

, a

, . . . , a

), n < 100,

являющаяся основанием целочисленной пирамиды. Пирамида строится снизу вверх.

Каждый новый ряд получается как разность или частное соседних элементов преды-

дущего ряда, т.е. все элементы нового ряда равны

= a

i+1

− a

или все элементы этого ряда равны

i+1

Равенство всех чисел на некотором уровне пирамиды — признак конца построения

этой пирамиды. Найти очередной элемент a

n+1

, продолжающий заданную последо-

вательность a = (a

, a

, . . . , a

) так, чтобы пирамида кончалась на том же уровне.

Одновременно с вычислением a

n+1

напечатать формулу его вычисления.

Пример.

1 1 1 → 1 операция вычитания

2 3 4 5 → 6 операция деления

1 2 6 24 120 → 720

180