Bonjour chère communauté,
J'y réfléchis depuis un certain temps maintenant mais je n'arrive pas à trouver une solution.
J'ai mon int [] [] bino = new int [15] [] dans lequel je calcule les 15 premières lignes de la pyramide pascals et je ne suis pas autorisé à changer le type (pas de double, long, etc.).
Nous savons que la faculté de 12 est 479001600
La valeur maximale de int est 2147483647 donc fac (12) y tient toujours .
Maintenant, pour les 3 dernières lignes, c'est là que ça se complique.
Fac (13) est 6227020800, ce qui est trop grand pour int.
Donc, ce qui se passe, c'est que pour les lignes 13, 14 et 15, il n'affichera pas les bons numéros (car 6227020800 mod 2147483647 = 1932053506 ce qui signifie que fac (13) = 1932053506 dans mon exemple).
La question est de savoir s'il existe un moyen d'afficher toujours les bons nombres, sans changer le type de champ dans int [] [] bino = new int [15] [] code >). Tout le reste peut être modifié.
public static void main(String args[])
{
int[][] bino = new int[15][]; //Create 2d array for pascal pyramid
for(int i = 0; i < bino.length;i++)
for(int j = 0; j < bino[i].length;j++)
{
binos[i][j] = nOverk(i,j)
}
}
public int nOverk(int n, int k)
{
return(fac(n) / (fac(k) * fac((n-k))));
}
public int fac(int z) //Calculats the faculty of a number
{
int res = 1;
if(z == 0 || z == 1)
return 1;
for(int i = 2; i <= z; i++)
res *= i;
return res;
}
3 Réponses :
La solution simple consiste à utiliser long , mais vous pouvez utiliser int pour des nombres plus grands (et enregistrer le travail) en calculant à la place fac (a) / fac (b) qui est plus efficace.
public static void main(String... args) {
int[][] bino = new int[15][]; //Create 2d array for pascal pyramid
for (int i = 0; i < bino.length; i++) {
bino[i] = new int[i + 1];
for (int j = 0; j < i + 1; j++) {
bino[i][j] = nOverk(i, j);
}
}
}
static int nOverk(int n, int k) {
int min = Math.min(k, n - k);
int max = Math.max(k, n - k);
return fac(n, max) / fac(min, 1);
}
static int fac(int hi, int lo) {
if (hi == 0 || hi == 1)
return 1;
int res = 1;
for (int i = lo + 1; i <= hi; i++)
res *= i;
return res;
}
AFAICT vous n'utilisez que resp. besoin de fac () pour nOverk () . Dans le terme fac (n) / (fac (k) * fac ((nk)))) , vous pouvez annuler certains des facteurs, en gardant les valeurs temporaires dans la plage autorisée.
Par exemple, au lieu de nOverk (4,2) = 4 * 3 * 2 * 1 / ((2 * 1) * (2 * 1)) , vous calculez simplement (4 * 3) / (2 * 1) . Il peut y avoir des cas secondaires où cela n'aide pas, mais je pense que la tâche est définie de cette façon pour qu'elle aide.
public int nOverk(int n, int k)
{
return (lim_fac(n, k) / lim_fac(k, k));
}
private int lim_fac(int z, int n) //Calculats the "limited" faculty of a number, by multiplying n factors.
{
int res = 1;
if (n == 0) {
return 1;
}
if (n == 1) {
return z;
}
for (int i = z - n + 1; i <= z; i++) {
res *= i;
}
return res;
}
Remarque: je ne suis pas sûr à 100% si J'ai bien compris lim_fac () , mais vous devriez avoir l'idée.
Dans le triangle de Pascal, chaque nombre est la somme des deux nombres directement au-dessus. Si la tâche consiste simplement à imprimer les 15 premières lignes, vous n'avez pas vraiment besoin d'utiliser factorielle.
public static void main(String[] args) {
int n = 15;
int[][] pascal = new int[n+1][];
// initialize first row
pascal[1] = new int[1+2];
pascal[1][1] = 1;
// fill in Pascal's triangle
for (int i = 2; i <= n; i++) {
pascal[i] = new int[i+2];
for (int j = 1; j < pascal[i].length - 1; j++)
pascal[i][j] = pascal[i-1][j-1] + pascal[i-1][j];
}
// print results
for (int i = 1; i <= n; i++) {
for (int j = 1; j < pascal[i].length - 1; j++) {
System.out.print(pascal[i][j] + " ");
}
System.out.println();
}
}
C'est probablement de loin la meilleure réponse et devrait être celle acceptée.
en
long, il est possible de stocker des valeurs plus grandes que dans int, ou BigInteger J'ai trouvé qu'il était recommandé d'utiliser le type de donnéeslong, si possible, sinon, alors biginteger - voir stackoverflow.com/a/17416986/4892907