Треугольник Стирлинга

Question

Помогите дописать программу для задачки треугольник Стирлинга, есть наметки, но пока не доходит что надо исправить. При вводе числа 6 программа должна выдавать:

1
0 1
0 1 1
0 1 3 1
0 1 7 6 1
0 1 15 25 10 1

а выдает:

0
0 0
1 0 0
3 1 0 0
6 7 1 0 0
0 0 1 15 25 10

Код:

#include <iostream>

using namespace std;

int main()
{
   long n, i, j;
   cin>>n;
   long a[n+1];
   for(i=1; i<=n; i++){
    a[i]=1;
   }
   a[0]=0;
   for(j=1; j<n; j++){
    for(i=j; i>0; i--){
        cout<<a[i-1]<<" ";
        a[i]=a[i]*(i-1)+a[i-1];
    }
     cout<<endl;
   }
  for(i=0; i<n; i++)
  cout<<a[i]<<" ";
}

Answer 1

Для таких небольших чисел можно просто с помощью рекурсивной функции:

unsigned int Stirl(unsigned int n, unsigned int k)
{
    if (k == n) return 1;
    if (k > n) return 0;
    if (k == 0 || n == 0) return 0;
    return Stirl(n-1,k)*k + Stirl(n-1,k-1);
}

int main(int argc, char * argv[])
{
    unsigned int N;
    cin >> N;
    for(unsigned int n = 0; n <= N; ++n)
    {
        for(unsigned int k = 0; k <= n; ++k)
            cout << setw(5) << Stirl(n,k) << " ";
        cout << endl;
    }
}

Для тех, кто не в состоянии переписать это через массивы...

int main(int argc, char * argv[])
{
    unsigned int N;
    cin >> N;
    unsigned int ** s = new unsigned int*[N+1];
    for(unsigned int i = 0; i <= N; ++i)
        s[i] = new unsigned int[N+1]{0};
    for(unsigned int n = 0; n <= N; ++n)
    {
        for(unsigned int k = 0; k <= n; ++k)
        {
            if (k == n) s[n][k] = 1;
            else if (k == 0 || n == 0) s[n][k] = 0;
            else s[n][k] = k*s[n-1][k] + s[n-1][k-1];
            cout << setw(5) << s[n][k] << " ";
        }
        cout << endl;
    }
}

Для тех, кто совсем не привык думать и работать самостоятельно:

int main(int argc, char * argv[])
{
    unsigned int N;
    cin >> N;
    unsigned int *s = new unsigned int[N+1]{0};
    for(unsigned int n = 0; n <= N; ++n)
    {
        for(unsigned int k = n; k > 0; --k)
        {
            if (k == 0) s[k] = 0;
            else if (k == n) s[k] = 1;
            else s[k] = k*s[k] + s[k-1];
        }
        for(unsigned int k = 0; k <= n; ++k)
            cout << setw(5) << s[k] << " ";

        cout << endl;
    }
}

БЛОГ НА HUSL

Треугольник Стирлинга

Ответы (1 шт):