Как я мог найти повторение этого алгоритма?

Question

Рассмотрим следующий рекурсивный алгоритм, где n - положительное целое число. Найти повторение, как функцию от n, которая представляет, сколько звездочек будет напечатано при вызове Asterisk(n).

Asterisk (n): 
   if n > 0: 
      for ( i=0; i<n; i=i+2):
         print (*)
         Asterisk (n-2)

Answer 1

Пусть A(n) - количество звездочек, напечатанных для n

. Из for l oop видно, что для каждой n вы печатаете ceil(n/2) звездочек, потому что oop увеличивается на 2. А также для каждой напечатанной звездочки есть дополнительные A(n-2) звездочек.

Таким образом, повторение будет

A(n) = 0 if n <= 0
     = (ceil(n/2))( 1 + A(n-2) ) if n > 0

Answer 2

Последовательность *:

1, 4, 15, 64, 325, ...

Формула повторения для этого равна

f(1) = 1
f(n) = n * f(n-1) + n

В вашем случае Asterisk сгенерирует эту последовательность, но в другой шаблон:

1, 1, 4, 4, 15, 15, 64, 64, 325, 325, ...

По сути, каждое значение появляется дважды, поэтому 2 * i-е значение соответствует i-му исходному значению.

Asterisk(n) = 0                                    if n < 1
Asterisk(n) = Asterisk(n + 1)                      if n is odd
Asterisk(n) = (n/2) * Asterisk(n-2) + (n/2)        if n is even

Программно:

int Asterisk(int n){
    if(n < 1) return 0;
    if(n % 2 == 1) return mAst(n + 1);
    return (n/2) * mAst(n-2) + (n/2);
}