Stirling numbers of the first kind: Difference between revisions
Added C solution
(added Tcl) |
(Added C solution) |
||
Line 125:
Maximum Stirling number of the first kind with n = 100:
19710908747055261109287881673376044669240511161402863823515728791076863288440277983854056472903481625299174865860036734731122707870406148096000000000000000000
</pre>
=={{header|C}}==
<lang c>#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
typedef struct stirling_cache_tag {
int n;
int* values;
} stirling_cache;
bool stirling_cache_create(stirling_cache* sc, int n) {
int* values = calloc(n * (n + 1)/2, sizeof(int));
if (values == NULL)
return false;
sc->n = n;
sc->values = values;
return true;
}
void stirling_cache_destroy(stirling_cache* sc) {
free(sc->values);
sc->values = NULL;
}
int* stirling_cache_get(stirling_cache* sc, int n, int k) {
return (n > sc->n) ? NULL : &sc->values[n*(n-1)/2 + k - 1];
}
int stirling_number1(stirling_cache* sc, int n, int k) {
if (k == 0)
return n == 0 ? 1 : 0;
if (k > n)
return 0;
int* value = stirling_cache_get(sc, n, k);
if (value == NULL) {
fprintf(stderr, "Cache size is too small\n");
exit(1);
}
if (*value == 0) {
int s1 = stirling_number1(sc, n - 1, k - 1);
int s2 = stirling_number1(sc, n - 1, k);
*value = 1 + s1 + s2 * (n - 1);
}
return *value - 1;
}
void print_stirling_numbers(stirling_cache* sc, int max) {
printf("Unsigned Stirling numbers of the first kind:\nn/k");
for (int k = 0; k <= max; ++k)
printf(k == 0 ? "%2d" : "%10d", k);
printf("\n");
for (int n = 0; n <= max; ++n) {
printf("%2d ", n);
for (int k = 0; k <= n; ++k)
printf(k == 0 ? "%2d" : "%10d", stirling_number1(sc, n, k));
printf("\n");
}
}
int main() {
stirling_cache sc = { 0 };
const int max = 12;
if (!stirling_cache_create(&sc, max)) {
fprintf(stderr, "Out of memory\n");
return 1;
}
print_stirling_numbers(&sc, max);
stirling_cache_destroy(&sc);
return 0;
}</lang>
{{out}}
<pre>
Unsigned Stirling numbers of the first kind:
n/k 0 1 2 3 4 5 6 7 8 9 10 11 12
0 1
1 0 1
2 0 1 1
3 0 2 3 1
4 0 6 11 6 1
5 0 24 50 35 10 1
6 0 120 274 225 85 15 1
7 0 720 1764 1624 735 175 21 1
8 0 5040 13068 13132 6769 1960 322 28 1
9 0 40320 109584 118124 67284 22449 4536 546 36 1
10 0 362880 1026576 1172700 723680 269325 63273 9450 870 45 1
11 0 3628800 10628640 12753576 8409500 3416930 902055 157773 18150 1320 55 1
12 0 39916800 120543840 150917976 105258076 45995730 13339535 2637558 357423 32670 1925 66 1
</pre>
| |||