Без двух нулей подряд

ЗАДАЧА №114

Без двух нулей подряд

(Время: 1 сек. Память: 16 Мб Сложность: 37%)

Требуется вычислить количество N-значных чисел в системе счисления с основанием K, таких что их запись не содержит двух подряд идущих нулей.

Входные данные

Во входном файле INPUT.TXT записаны два натуральных числа N и K в десятичной системе счисления (2 ≤ K ≤ 10; 2 ≤ N; 4 ≤ N+K ≤ 18).

Выходные данные

В выходной файл OUTPUT.TXT необходимо вывести целое число в десятичной записи – ответ на задачу.

Примеры

INPUT.TXT      OUTPUT.TXT

2   10                              90

4   2                                   5

6   3                                 328

Идея решения

Хотя сложность задачи, указанная на сайте, невысокая, но, по моему мнению, это идейно наиболее сложная задача. Конечно, несложно написать переборный вариант, но это неэффективный алгоритм, рассматривать который не будем.

Рассмотрим идеи, лежащие в основе эффективного алгоритма.

Сама по себе идея проста. Множество чисел, не содержащих двух нулей подряд, следует разбить на два подмножества. Первое содержит числа, заканчивающиеся нулем, второе содержит числа, нулем не заканчивающиеся.

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

Как мне кажется, понятнее всего описать алгоритм решения в виде трех взаимно рекурсивных  функций.

Пусть функция

long Without_2Zero(int n, int p)

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

Используя идею о разложении этого множества на два подмножества, нетрудно дать описание  этой функции:

{

return Zero_tail(n,p) + No_Zero_tail(n,p);

}

Функция

long Zero_tail(n,p)

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

if (n == 1) return 0;

return No_Zero_tail(n -1, p);

По определению мы рассматриваем только такие числа, которые начинаются цифрой, отличной от нуля. Поэтому нерекурсивная ветвь алгоритма очевидна. Понятна и рекурсивная ветвь. Если известно число (n-1)-разрядных чисел, не заканчивающихся нулем, то столько же будет n-разрядных чисел, заканчивающихся нулем. Действительно к каждому числу из подмножества чисел, нулем не заканчивающимся, можно приписать ноль в качестве следующей цифры. Эти и только эти числа не будут иметь двух нулей подряд, и будут составлять подмножество n-разрядных чисел, заканчивающихся нулем.

Осталось показать, что нетрудно дать описание функции

long No_Zero_tail(n -1, p)

рекурсивно связывающее все три функции:

if (n == 1) return p — 1;

return Without_2Zero(n — 1, p) * (p — 1);

Нерекурсивная ветвь этой функции очевидна. Достаточно понятна и рекурсивная ветвь. Если определено множество (n – 1)-разрядных чисел, не содержащих двух нулей подряд, то к каждому такому числу можно приписать цифру, не являющуюся нулем. Таких цифр в системе счисления с основанием p ровно p -1. Эти и только эти числа будут составлять множество чисел разрядности n, не будут содержать двух нулей подряд, и будут заканчиваться цифрой, отличной от нуля.

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

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

using System;

using System.Collections.Generic;

using System.Linq;

using System.Text;

using System.Threading.Tasks;

 

namespace TwoZero

{

class Program

{

static void Main(string[] args)

{

int n, p;

Console.WriteLine(«Введите разрядность числа»);

n = int.Parse(Console.ReadLine());

Console.WriteLine(«Введите основание системы счисления»);

p = int.Parse(Console.ReadLine());

long result = 0 ;

result = Without_2Zero(n, p);

Console.WriteLine(«В системе счисления {0} {1}-разрядных чисел » +

«без двух нулей — {2}», p, n, result);

result = Simple(n, p);

Console.WriteLine(«В системе счисления {0} {1}-разрядных чисел » +

«без двух нулей — {2}», p, n, result);

}

/// <summary>

/// Число n-разрядных чисел

/// в системе с основанием p,

/// не содержащих двух нулей подряд

/// </summary>

/// <param name=»n»>разрядность</param>

/// <param name=»p»>основание системы счисления</param>

/// <returns>количество чисел с заданными свойствами</returns>

static long Without_2Zero(int n, int p)

{

return Zero_tail(n,p) + No_Zero_tail(n,p);

}

 

/// <summary>

/// Число n-разрядных чисел

/// в системе с основанием p,

/// не содержащих двух нулей подряд

/// и заканчивающихся нулем

/// </summary>

/// <param name=»n»>разрядность</param>

/// <param name=»p»>основание системы счисления</param>

/// <returns>количество чисел с заданными свойствами</returns>

static long Zero_tail(int n, int p)

{

if (n == 1) return 0;

return No_Zero_tail(n -1, p);

}

 

/// <summary>

/// Число n-разрядных чисел

/// в системе с основанием p,

/// не содержащих двух нулей подряд

/// и заканчивающихся цифрой, отличной от нуля

/// </summary>

/// <param name=»n»>разрядность</param>

/// <param name=»p»>основание системы счисления</param>

/// <returns>количество чисел с заданными свойствами</returns>

static long No_Zero_tail(int n, int p)

{

if (n == 1) return p — 1;

if (n == 2) return (p — 1) * (p — 1);

return Without_2Zero(n — 1, p) * (p — 1);

}

 

/// <summary>

/// Число n-разрядных чисел

/// в системе с основанием p,

/// не содержащих двух нулей подряд

/// Не рекурсивный вариант

/// </summary>

/// <param name=»n»>разрядность</param>

/// <param name=»p»>основание системы счисления</param>

/// <returns>количество чисел с заданными свойствами</returns>

static long Simple(int n, int p)

{

long P0 = 0, P1 = p — 1, P = p-1;

for(int i = 2; i <=n; i++)

{

P0 = P1;

P1 = P * (p — 1);

P = P0 + P1;

}

return P;

 

}

}

}