Создание фрактальной модели с использованием рекурсии

Question

Я пытаюсь создать этот фрактальный узор, используя рекурсию.

* 
* * 
    * 
* * * * 
    * 
    * * 
     * 
* * * * * * * * 
     * 
     * * 
      * 
     * * * * 
      * 
      * * 
       * 

Функция, которую мне нужно реализовать это:

void pattern(ostream& outs, unsigned int n, unsigned int i); 
// Precondition: n is a power of 2 greater than zero. 
// Postcondition: A pattern based on the above example has been 
// printed to the ostream outs. The longest line of the pattern has 
// n stars beginning in column i of the output. For example, 
// The above pattern is produced by the call pattern(cout, 8, 0). 

До сих пор, это то, что у меня есть:

void pattern(ostream& outs, unsigned int n, unsigned int i){ 

    if (n == 1){ 
     outs << "*"<<endl; 
    } 

    else{ 
     pattern(outs, n/2, i + 1); 
     for (int k = 0; k < n; k++){ 
      outs << "* "; 

     } 
     outs<<endl; 


     for (int k = 0; k < i; k++){ 
      outs << ' '; 
     } 

     pattern(outs, n/2, i + 1); 

    } 

}

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

Answer 1

Шаблон содержит 2*N-1 линий. Мой подход состоит в том, чтобы разделить шаблон на две половины. Верхняя половина имеет N линии и нижняя половина, имеющие N-1 линии. Нижняя половина представляет собой только реплику верхней половины, имеющую один меньший ряд и несколько дополнительных мест (то есть ^N/ дополнительные помещения). Итак, теперь вам нужно найти шаблон только для верхней половины.

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

я нашел для N=8

LineNumber Stars Spaces 
    1   1  0 
    2   2  0 
    3   1  1 
    4   4  0 
    5   1  2 
    6   2  2 
    7   1  3 
    8   8  0 
    9   1  4 
    10  2  4 
    11  1  5 
    12  4  4 
    13  1  6 
    14  2  6 
    15  1  7 

Надеется, что вы найдете шаблон теперь, глядя на приведенном выше примере. Если нет, то вы можете обратиться к spaces функции в коде, указанном ниже.

#include <iostream> 
#include <cmath> 
using namespace std; 
bool PowerOfTwo(int n) 
{ 
    if ((n&(n-1)) == 0 && n!=1) 
     return true; 
    return false; 
} 
int star(int n) 
{ 
    int i=n,ans=0; 
    while(i%2==0) 
    { 
     i/=2; 
     ans++; 
    } 
    return pow(2,ans); 
} 
int spaces(int n) 
{ 
    if(PowerOfTwo(n)==true) 
     return 0; 
    return (n-1)/2; 
} 
void printpattern(int n) 
{ 
    int i,sp,st; 
    sp = spaces(n); 
    for(i=1;i<=sp;i++) 
     cout<<" "; 
    st = star(n); 
    for(i=1;i<=st;i++) 
     cout<<"* "; 
} 
void pattern(int n) 
{ 
    int i,j,sp; 
    for(i=1;i<=n;i++)    //Upper Half  
    { 
     printpattern(i); 
     cout<<endl; 
    } 
    sp = n/2; 
    for(i=1;i<=n-1;i++)    //Lower Half 
    { 
     for(j=1;j<=sp;j++) 
      cout<<" "; 
     printpattern(i); 
     cout<<endl; 
    } 
} 
int main() 
{ 
    int n=8; 
    pattern(n); 
    return 0; 
}