SashaMercuryчто касается самостоятельного вывода, то это вероятно затруднительный и долгий процесс. Большие умы трудились над этой задачей не один год
Как вариант не одну суперформулу, а какой-то упрощенный алгоритм.
Посчитал табличку, расчеты где n <= k пропустил, т.к. их неккоректно считает sums()
k= 2 3 4 5 6 7 8 9n=02n=03 3n=04 5 7n=05 8 13 15n=06 13 24 29 31n=07 21 44 56 61 63n=08 34 81 108 120 125 127n=09 55 149 208 236 248 253 255n=10 89 274 401 464 492 504 509 511n=11 144 504 773 912 976 1004 1016 1021n=12 233 927 1490 1793 1936 2000 2028 2040n=13 377 1705 2872 3525 3840 3984 4048 4076n=14 610 3136 5536 6930 7617 7936 8080 8144
Просматривается формула:
при изменении n каждый результат равен сумме k предыдущих . Т.е. для k=2 каждый последующий равен сумме двух предыдущих. Для к=3 сумма трех предыдущих. И т.д.
Т.е. достаточно посчитать значения от sums(k+1, k) до sums(k+k, k) а дальше простым циклом для любого n.
Может еще как-то можно улучшить, сходу не соображу.
Исходник на С генератора таблички
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.
33.
#include <stdio.h>
int sums(int n, int k) {
if (n < 2) {
return 1;
}
k = k > n ? n : k;
int s = 0;
for (int i = 1; i <= k; ++i) {
s += sums(n - i, k);
}
return s;
}
#define MAX_K 9
#define MAX_N 14
int main()
{
printf(" k=");
for(int k = 2; k <= MAX_K; k++) {
printf(",%5d", k);
}
for(int n = 2; n <= MAX_N; n++) {
printf("\nn=%02d", n);
for(int k = 2; k <= (n > MAX_K ? MAX_K : n - 1); k++) {
printf(",%5d", sums(n, k));
}
}
printf("\n");
system("pause");
return 0;
}
