Quando si prova a stampare il triangolo di pascal, 13a ripetizione stampa una risposta errata - c, pascals-triangle

Sto scrivendo una sceneggiatura in C per stampare i pascaltriangolo, quindi ho scritto una funzione per fattoriale, poi ho fatto la variabile c = all'equazione di espansione binomiale, questa funziona fino alla riga n = 13 dove produce l'output:

1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
1 5 10 10 5 1
1 6 15 20 15 6 1
1 7 21 35 35 21 7 1
1 8 28 56 70 56 28 8 1
1 9 36 84 126 126 84 36 9 1
1 10 45 120 210 252 210 120 45 10 1
1 11 55 165 330 462 462 330 165 55 11 1
1 12 66 220 495 792 924 792 495 220 66 12 1
0 4 24 88 221 399 532 532 399 221 88 24 4 0

Con l'ultima riga n = 13. Originariamente pensavo che si stesse rompendo perché i fattoriali sarebbero troppo grandi per interi a 32 bit ma l'errore è ancora presente con interi a 64 bit ...

#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
#include <inttypes.h>


int64_t factorial(int k);

int main(int argc, char **argv)
{
int c, n, r, i;

if (argc < 2) {
printf("[function]:  %s [number of lines to print]", argv[0]);
return -1;
}

n = atoi(argv[1]);

for (i = 0; i <= n; i++) {
for (r = 0; r <= i; r++) {
c = (int) factorial(i) / (factorial(r) * factorial((i - r)));
printf("%d ", c);
}
printf("n");
}
return 1;


}

int64_t factorial(int k)
{
int64_t j;

if (k == 0 || k == 1)
return 1;

int n = k;

for (j = k; n > 1;)
j = j * --n;
return j;
}

Apprezzerei molto l'aiuto con questo ...

risposte:

8 per risposta № 1

Il tuo calcolo fallisce anche a 64 bit perché ti colpisci al piede con un cast (fa male):

c = (int) factorial(i) / (factorial(r) * factorial((i - r)));

viene analizzato come

c = ((int)factorial(i)) / (factorial(r) * factorial((i - r)));

Basta rimuovere il cast o posizionarlo sul risultato:

c = (int)(factorial(i) / (factorial(r) * factorial(i - r)));

Nota che il tuo factorial la funzione è troppo complicata, ecco una versione più semplice:

int64_t factorial(int n) {
int64_t x;
for (x = 1; n > 1; n--) {
x *= n;
}
return x;
}

Si noti inoltre che non è necessario calcolare il fattoriale completo, questa versione va a 29 e può essere ulteriormente migliorata con alcuni lavori:

#include <stdio.h>
#include <stdlib.h>

long long binomial(int n, int p) {
int q;
long long x;

if (p < n - p)
p = n - p;
q = n - p;
for (x = 1; n > p; n--)
x *= n;
for (; q > 1; q--)
x /= q;
return x;
}

int main(int argc, char **argv)
{
int n, r, i;

if (argc < 2) {
printf("[function]:  %s [number of lines to print]", argv[0]);
return -1;
}

n = atoi(argv[1]);

for (i = 0; i <= n; i++) {
for (r = 0; r <= i; r++) {
printf("%lld ", binomial(i, r));
}
printf("n");
}
return 0;
}

Infine, se ti è permesso usare gli array, il calcolo del triangolo Pascal può essere ulteriormente semplificato in quanto ogni coefficiente è la somma di quello sopra e quello a sinistra di quello:

#include <stdio.h>
#include <stdlib.h>

int main(int argc, char **argv) {
int n, r, i;

if (argc < 2) {
printf("[function]:  %s [number of lines to print]", argv[0]);
return -1;
}

n = atoi(argv[1]);
long long coeff[n + 1];

coeff[0] = 1;
for (r = 1; r <= n; r++) {
coeff[r] = 0;
}
for (i = 0; i <= n; i++) {
for (r = i; r > 0; r--) {
coeff[r] += coeff[r - 1];
}
for (r = 0; r <= i; r++) {
printf("%lld ", coeff[r]);
}
printf("n");
}
return 0;
}

---

4 per risposta № 2

        c = (int) factorial(i) / (factorial(r) * factorial((i - r)));

Questo non fa quello che pensi che faccia

        c = (int) (factorial(i) / (factorial(r) * factorial((i - r))));

---