关于杨辉三角的一点问题

Question

public class YangHuiTriangle {
private int n;// 表示行 public YangHuiTriangle(int n) {
this.n = n;
} public void printYangHuiTriangle() {
System.out.println("杨辉三角(" + n + ")层:");
System.out.println(1);
for (int i = 1; i <= n - 1; i++) {
for (int j = 0; j <= i; j++) {
if (j == 0)
System.out.print(1 + "\t");
else {
System.out.print(calc(i, j) + "\t");
}
}
System.out.println();
}
}

//计算i行j列上的值,i,j从0开始
public long calc(int i, int j) {
double a = 1.0;//i行j列上的值
for (int k = 1; k <= j; k++) {
a *= (double)i / k;
i--;
}
return (long)a;
} public static void main(String[] args) {
YangHuiTriangle y = new YangHuiTriangle(20);
y.printYangHuiTriangle();
}}
写个杨辉三角玩玩,但发现结果中第12行和16行有点问题.如下:
12行:1 11 55 165 330 461 461 329 164 54 10 0
16行:1 15 105 454 1364 3002 5004 6434 6434 5004 3002 1364 454 104 14 0
望高人指点.谢谢.

Answer 1

public class YangHuiTriangle {
    private int n;// 表示行
    long[] mat;          //*********
    public YangHuiTriangle(int n) {
        this.n = n;
        mat=new long[(1+n)*n/2+1];   //*************
        mat[0]=1;
        for(int i=1;i<n;i++){
         for(int j=0;j<=i;j++){
         System.out.println("i:"+i+"  j=:"+j+"  k="+(i*(i+1)/2+j+1));
         if(i*(i-1)/2+j<i*(i-1)/2+1||i*(i-1)/2+j>=i*(i-1)/2+i){
         mat[(1+i)*i/2+j+1]=1;
         }else{
         mat[(1+i)*i/2+j+1]=mat[i*(i-1)/2+j]+mat[i*(i-1)/2+j+1];
         }
         }
        }
    }    public void printYangHuiTriangle() {
        System.out.println("杨辉三角(" + n + ")层:");
        String space="                                                                   ";
        System.out.println(space.substring(0,(n-1)*4+7)+1);
        long temp;
        for (int i = 1; i <= n - 1; i++) {
         System.out.print(space.substring(0,(n-i-1)*4));
            for (int j = 0; j <= i; j++) {
             temp=mat[(1+i)*i/2+j+1];
                System.out.print(space.substring(0,8-(Long.toString(temp)).length())+temp);
            }
            System.out.println();
        }
    }
    
    //计算i行j列上的值,i,j从0开始
    public long calc(int i, int j) {
        double a = 1.0;//i行j列上的值
        for (int k = 1; k <= j; k++) {
            a *= (double)i / k;
            i--;
        }
        return (long)a;
    }    public static void main(String[] args) {
        YangHuiTriangle y = new YangHuiTriangle(10);
        y.printYangHuiTriangle();
    }}运行结果如下:F:\java>javac YangHuiTriangle.javaF:\java>java YangHuiTriangle
杨辉三角(15)层:
                                                               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
           1      13      78     286     715    1287    1716    1716    1287     715     286      78      13       1
       1      14      91     364    1001    2002    3003    3432    3003    2002    1001     364      91      14       1F:\java>

Answer 2

F:\java>javac YangHuiTriangle.javaF:\java>java YangHuiTriangle
杨辉三角(20)层:
                                                                                   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
                               1      13      78     286     715    1287    1716    1716    1287     715     286      78      13       1
                           1      14      91     364    1001    2002    3003    3432    3003    2002    1001     364      91      14       1
                       1      15     105     455    1365    3003    5005    6435    6435    5005    3003    1365     455     105      15       1
                   1      16     120     560    1820    4368    8008   11440   12870   11440    8008    4368    1820     560     120      16       1
               1      17     136     680    2380    6188   12376   19448   24310   24310   19448   12376    6188    2380     680     136      17       1
           1      18     153     816    3060    8568   18564   31824   43758   48620   43758   31824   18564    8568    3060     816     153      18       1
       1      19     171     969    3876   11628   27132   50388   75582   92378   92378   75582   50388   27132   11628    3876     969     171      19       1F:\java>

Answer 3

找到问题了.
a *= (double)i / k;改成 a = a * i / k;
就没问题了.怪怪 

Answer 4

虽然改成 a = a * i / k;但是在第56行还是出现这种问题.
先说明下,表达式中a = a * i / k;是可以除尽的.
但为什么会在第56行倒数最后个值变为0.9999999999999993?

Answer 5

double在运算的时候会出现损失精度的情况

Answer 6

但你在循环中的a*i/k，i,k的值在变化过程中，是可能除不尽的，列出来的式子是可以除尽的。计算过程有可能除不尽。所以才把a设为double.

Answer 7

用浮点数来运算，自然存在误差，精度问题
杨辉三角完全没必要用浮点数啊public class YangHuiTriangle {
    private int n;// 表示行    public YangHuiTriangle(int n) {
        this.n = n;
    }    public void printYangHuiTriangle() {
        System.out.println("杨辉三角(" + n + ")层:");
        for (int i = 0; i < n ; i++) {
            for (int j = 0; j <= i; j++) {
             System.out.print(calc(i, j) + "\t");
            }
            System.out.println();
        }
    }
    //递归计算C(i,j) = 1 (k=0或者j=i);C(i,j) = C(i-1,j-1) + C(i-1,j)
    public long calc(int i, int j) {
        if (( j == 0 ) || (j == i)) return 1;
        return calc(i-1, j-1) + calc(i-1, j);
    }    public static void main(String[] args) {
        YangHuiTriangle y = new YangHuiTriangle(20);
        y.printYangHuiTriangle();
    }}这个方法不知道你满意不

Answer 8

杨辉三角的算法实在可以有很多种实现
再来一个public class YangHuiTriangle {
    private int n;// 表示行    public YangHuiTriangle(int n) {
        this.n = n;
    }    public void print()
    {
long[] result = new long[n]; //存储输出行 result[0] = 1; //初始化
for (int index = 1; index < n; index++)
{
result[index] = 0;
} long left =0;
long right = 0; for (int line = 1; line < n; line++)
{
left = 0;
//生成第line行数据
for (int column = 0; column<line; column++)
{
right = result[column];
result[column] = left + right; //left =a[i-1] right = a[i];
left = right;
} //输出第line行
for ( int index = 0; index < line; index ++)
System.out.print(result[index] + "\t");
System.out.println();
}
}
    public static void main(String[] args) {
        YangHuiTriangle y = new YangHuiTriangle(20);
        y.print();
    }}

Answer 9

a = a * i / k ;虽然 i,k在变,但是是可以除尽的.

Answer 10

哦。这样的话，你就可以把a变为long了，浮点数机内表示是损失精度的。

Answer 11

public class YangHuiTriangle {
    private int n;// 表示行    public YangHuiTriangle(int n) {
        this.n = n;
    }    public void print()
    {
        long[] result = new long[n]; //存储输出行        result[0] = 1;                //初始化
        for (int index = 1; index < n; index++)
        {
            result[index] = 0;
        }        long left =0;
        long right = 0;        for (int line = 1; line < n; line++)
        {
            left = 0;
            //生成第line行数据
            for (int column = 0; column<line; column++)
            {
                right = result[column];
                result[column] = left + right; //left =a[i-1] right = a[i];
                left = right;
            }            //输出第line行
            for ( int index = 0; index < line; index ++)
                System.out.print(result[index] + "\t");
            System.out.println();
        }
    }
    public static void main(String[] args) {
        YangHuiTriangle y = new YangHuiTriangle(20);
        y.print();
    }}

Answer 12

实际上double损失的精度也没有什么，关键是一强制类型转换就所小数部分都截去了，这个受不了，可能截去的是0.99999啊。

Answer 13

把
    public long calc(int i, int j) {
        double a = 1.0;//i行j列上的值
        for (int k = 1; k <= j; k++) {
            a *= (double)i / k;
            i--;
        }
        return (long)a;
    }的return (long)a 改成 return (long）(a+0.5)结果就对了，嘿嘿

Answer 14

一看到那些i,j,k,a,b,c之类的变量就没兴趣看下去了，玩具程序...

Answer 15

呵呵，你还是没转过来啊
首先你说的应该是这个等式吧56÷1×55÷2×54÷3×53÷4×52÷5×······×3÷54×2÷55×1÷56
不错，理论上56÷1×55÷2×54÷3×53÷4×52÷5×······×3÷54×2÷55×1÷56是应该 = 1但是你想过没有，double的精度是有限的，你的中间结果存在小数，可能是无理数（如2/55 = 0.036363636363636363636363636363636...）,对于这样的数double也无法精确表示啊
由于这种不精确，导致最后累积起来的结果也不够精确
如果每次中间运算也是精确地自然就不存在这种问题你把calc函数改成这样，double运算也不会有问题
        public long calc(int i, int j) {
        double a = 1.0;//i行j列上的值
        double b = 1.0;
        for (int k = 1; k <= j; k++) {
            a *= i;
            b *=  k;
            i--;
        }
        return (long)(a/b);
    }
不过这样就要注意溢出的问题了实际上杨辉三角用整型完全就可以解决了的问题，就不涉及精度问题了

Answer 16

数字太大了，用BigInteger即可。
import java.math.BigInteger;public class YangHuiTriangle {
    private int n;// 表示行    public YangHuiTriangle(int n) {
        this.n = n;
    }    public void printYangHuiTriangle() {
        System.out.println("杨辉三角(" + n + ")层:");
        System.out.println(1);
        for (int i = 1; i <= n - 1; i++) {
            for (int j = 0; j <= i; j++) {
                if (j == 0)
                    System.out.print(1 + "\t");
                else {
                    System.out.print(calc(i, j) + "\t");
                }
            }
            System.out.println();
        }
    }    //计算i行j列上的值,i,j从0开始
    public BigInteger calc(int i, int j) {
        BigInteger a = new BigInteger("1") ;//i行j列上的值
        for (int k = 1; k <= j; k++) {
            a = a.multiply(new BigInteger(String.valueOf(i))).divide(new BigInteger(String.valueOf(k)));
            i--;
        }
        return a;
    }    public static void main(String[] args) {
        YangHuiTriangle y = new YangHuiTriangle(20);
        y.printYangHuiTriangle();
    }}输出如下：
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
1 13 78 286 715 1287 1716 1716 1287 715 286 78 13 1
1 14 91 364 1001 2002 3003 3432 3003 2002 1001 364 91 14 1
1 15 105 455 1365 3003 5005 6435 6435 5005 3003 1365 455 105 15 1
1 16 120 560 1820 4368 8008 11440 12870 11440 8008 4368 1820 560 120 16 1
1 17 136 680 2380 6188 12376 19448 24310 24310 19448 12376 6188 2380 680 136 17 1
1 18 153 816 3060 8568 18564 31824 43758 48620 43758 31824 18564 8568 3060 816 153 18 1
1 19 171 969 3876 11628 27132 50388 75582 92378 92378 75582 50388 27132 11628 3876 969 171 19 1

Answer 17

import java.util.Scanner;
public class 杨辉三角 { /**
 * @param args
 */
public static void main(String[] args) {
// TODO Auto-generated method stub
Scanner s =new Scanner(System.in);
int [][]yanghui =new int[50][50];
System.out.println("请输入(a+b)的几次方");
int a=s.nextInt();
for (int i = 0; i <a+1; i++) {
yanghui[i][0]=1;
yanghui[i][i]=1;
}
for (int i = 2; i < a+1; i++) {
for (int j = 1; j < i; j++) {
yanghui[i][j]=yanghui[i-1][j]+yanghui[i-1][j-1];
}
}
for (int i = 0; i < a+1; i++) {
for (int j = 0; j < 10-i; j++) {
System.out.print(" ");
}
for (int j = 0; j < i+1; j++) {
System.out.print(" "+yanghui[i][j]);
}
System.out.println();
} }}

Answer 18

D:\javafile>java  YangHuiTriangle
杨辉三角(20)层:
                                                                                   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
                               1      13      78     286     715    1287    1716    1716    1287     715     286      78      13       1
                           1      14      91     364    1001    2002    3003    3432    3003    2002    1001     364      91      14       1
                       1      15     105     455    1365    3003    5005    6435    6435    5005    3003    1365     455     105      15       1
                   1      16     120     560    1820    4368    8008   11440   12870   11440    8008    4368    1820     560     120      16       1
               1      17     136     680    2380    6188   12376   19448   24310   24310   19448   12376    6188    2380     680     136      17       1
           1      18     153     816    3060    8568   18564   31824   43758   48620   43758   31824   18564    8568    3060     816     153      18       1
       1      19     171     969    3876   11628   27132   50388   75582   92378   92378   75582   50388   27132   11628    3876     969     171      19       1D:\javafile>

Answer 19

实际上double损失的精度也没有什么，关键是一强制类型转换就所小数部分都截去了，这个受不了，可能截去的是0.99999啊。