黑马程序员技术交流社区

标题: 重金悬赏杨辉三角，要详细注释的~~~~ [打印本页]
作者: 尘埃落定    时间: 2014-9-9 17:24
标题: 重金悬赏杨辉三角，要详细注释的~~~~
如题~~
作者: hanchun776    时间: 2014-9-9 17:24
package interview;


//题目：输出杨辉三角的前10行。
/*思路分析：
*                         1
*                         1        1
*                         1        2        1
*                         1        3        3        1
*                         1        4        6        4        1
*                         1        5        10        10        5        1
* 杨辉三角的计算规则是：
* 第一行有1个元素，值为1，以后每行中的元素都增加一个，每个元素值的增加规则是：
* 它上方元素的值（如果存在的话）加上它上方元素左边的那个元素的值（如果存在的话）。
* 比如第2行的第一个元素，它上面的元素是1，上面的左边没有元素，所以，他的值就是1.
* 对于第三行元素的第二个元素，它上面是2,2的左边是1，所以，它是3.
* 依次类推。
* */
public class YangHui {

        /**
         * @param args
         */
        public static void main(String[] args) {
                // TODO Auto-generated method stub
               
                int level = 10;//程序生成的杨辉三角的层数。
               
                int[][] yangHui = new int[level][0];//创建一个二维数组，用来存储杨辉三角中的数值。第二维定义为0，是因为每一层中的元素的个数都不一样，先定义为0
               
                for(int x = 0;x < level;x++){//使用for循环，为杨辉三角的每一层创建一个int数组。
                        yangHui[x] = new int[x+1];//此层杨辉三角包含的个数是x+1。
                       
                        for(int y = 0;y <= x; y++){//每次循环计算杨辉三角中一层中的一个数据
                                if(x == 0)//如果是第一行，就直接赋值为1.
                                        yangHui[x][y]=1;
                                else{//如果不是第一行，则根据上一行的值计算当前元素的值。
                                        int value = 0;//用来保存当前元素的值。
                                        if(y >= 1){//根据杨辉三角的计算规则，判断此上方是否有元素
                                                value += yangHui[x-1][y-1];//如果有，则将当前元素上方的值加入到value变量中
                                        }
                                        if(y < x){//根据杨辉三角的计算规则，判断次上方的左边是否有元素
                                                value += yangHui[x-1][y];//有，则将上方左边的值加入到value变量中
                                        }
                                        yangHui[x][y] = value;
                                }
                               
                        }
                }
               
                for(int x = 0;x < 10;x++){//遍历数组，输出数组中的元素。
                        for(int y = 0;y <= x;y++){
                                System.out.print(yangHui[x][y]+"\t");
                        }
                        System.out.println();
                }
               
        }

}
作者: hanchun776    时间: 2014-9-9 17:43
本帖最后由 hanchun776 于 2014-9-9 17:48 编辑

谢谢楼主,楼主好人
作者: daoqin    时间: 2014-9-9 22:28
本帖最后由 daoqin 于 2014-9-9 22:31 编辑

我给出递归的解法。
1.第一种递归
f(x,y)=1  (x==1或者x==y)
f(x,y)=f(x-1, y-1)+f(x, y-1)   (其他）
x表示列数，y表示层数。

  1. /**
  2. * 递归打印杨辉三角
  3. * @author Administrator
  4. *
  5. */
  6. public class YanHui {
  7.         
  8.         int f(int x,int y){
  9.                 if(x == 1 || x == y){//递归的出口
  10.                         return 1;
  11.                 }else {
  12.                         return f(x-1, y-1)+f(x, y-1);//杨辉三角的规律
  13.                 }
  14.         }
  15.         void printYanhui(int n){
  16.                 int i,j;
  17.                 for(i = 1;i<=n;i++){
  18.                         for (j = 1; j <=i; j++) {
  19.                                 System.out.printf("%5d",f(j, i));//打印第i行第j个元素
  20.                         }
  21.                         System.out.print("\n");
  22.                 }
  23.         }
  24.         public static void main(String[] args) {
  25.                 int x = 6;
  26.                 new YanHui().printYanhui(x);//设定阶数
  27.         }
  28. }
复制代码
2.利用阶乘实现
1
1        1
1        2        1
1        3        3        1
1        4        6        4        1
1        5        10        10        5        1
规律如下：
第4行第一个数为3：3！/（2！*（3-2）！） =3
第4行第0个数为3： 3！/(0！*（3-0）！）=1
杨辉三角满足一个组合公式：n！/(!m*!(n-m)) 利用此公式就可求出每一个数
公式如下：
某个位置杨辉三角数= 当前行数的阶乘(从0开始)/( 列的位置数组成的阶乘从0开始) *(行数-列组成数的阶乘) ）
  1. /**
  2. * 递归打印杨辉三角
  3. * @author Administrator
  4. *
  5. */
  6. public class YanHui {
  7.         
  8.         int f(int n){
  9.                 if(n==0){
  10.                         return 1;
  11.                 }
  12.                 return n*f(n-1);
  13.         }
  14.         void printYanhui(int n){
  15.                 int i,j;//i表示行数,j表示层数，均从0开始
  16.                 for(i = 0;i<=n;i++){
  17.                         for (j = 0; j<=i; j++) {
  18.                                 System.out.printf("%5d",f(i)/(f(i-j)*f(j)));//打印第i行第j个元素
  19.                         }
  20.                         System.out.print("\n");
  21.                 }
  22.         }
  23.         public static void main(String[] args) {
  24.                 int x = 5;
  25.                 new YanHui().printYanhui(x);//设定阶数
  26.         }
  27. }
复制代码







作者: however_    时间: 2014-9-11 10:30
public class PrintYangHui {


  public static void main(String[] args){
   /**
    * 比较两个print方法会有新的发现
    */
   print1(5);
   print2(5);

  }
  
  /**
   * 按照书本上面描述的三角图计算的
   * 给第一行和第二行赋值
   * 按照规则第二行的“2”不知道是怎么计算的，所以手动赋初始值
   * @param line
   */
  public static void print1(int line){
   /**
    * 用int二维数组存储，第一维表示行数，第二维表示列数
    */
   int[][]  aa = new int[line][2*line+1];
   for(int i = 0; i<line ;i++){
    for(int j = 0;j< 2*line+1;j++){
     if(i == 0){
      if(j == line ){
       aa[i][j] = 1;
      }else{
       aa[i][j] = 0;
      }
     }else if(i == 1){
      if(j == line ){
       aa[i][j] = 2;
      }else if(j == line -2 || j == line +2 ){
       aa[i][j] = 1;
      }else{
       aa[i][j] = 0;
      }
     }else{
      if(j == 0){
       aa[i][j] = aa[i-1][j+1];
      }else if(j == 2*line){
       aa[i][j] = aa[i-1][j-1];
      }else{
       aa[i][j] = aa[i-1][j-1] +aa[i-1][j+1];
      }
     }
     /**
      * 输出时把所有的“0”都替换成空格
      */
     if(aa[i][j] == 0){
      System.out.print(" ");
     }else{
      System.out.print(aa[i][j]);
     }
    }
    System.out.println("\n");
   }
  }
  
  /**
   * 按照杨辉三角的规则计算
   * 只给予第一行赋值
   * @param line
   */
  public static void print2(int line){
   int[][]  aa = new int[line][2*line+1];
   for(int i = 0; i<line ;i++){
    for(int j = 0;j< 2*line+1;j++){
     if(i == 0){
      if(j == line ){
       aa[i][j] = 1;
      }else{
       aa[i][j] = 0;
      }
     }else{
      if(j == 0){
       aa[i][j] = aa[i-1][j+1];
      }else if(j == 2*line){
       aa[i][j] = aa[i-1][j-1];
      }else{
       aa[i][j] = aa[i-1][j-1] +aa[i-1][j+1];
      }
     }
     if(aa[i][j] == 0){
      System.out.print(" ");
     }else{
      System.out.print(aa[i][j]);
     }
    }
    System.out.println("\n");
   }
  }
}
作者: 2100    时间: 2014-9-15 06:50
public class PascalTriangle{
/**Pascal三角形的计算深度为5*/
private static final int PASCAL_DEPTH = 5;

/**数组的行*/
private int row;

/**数组的列*/
private int column;

/**存储不同长度数组的数组，是一个二维数组*/
private int[][] pascalArray = {new int[1],new int[2],new int[3],new int[4],new int[5]};

/**产生Pascal三角形*/
public void producePascal(){
  for(row = 0; row < PASCAL_DEPTH; row++){
   for(column = 0; column <= row; column++){
    //第一列数全为1
    if(column == 0){
     pascalArray[row][column] = 1;
    }
    else{
     pascalArray[row][column] = (row - column + 1) * pascalArray[row][column - 1] / column;
    }//end if-else
   }//end for(column...)
  }//end for(row...)
}

/**按照每个数组的长度length打印Pascal三角形*/
public void printWithLength(){
  for(int i = 0; i < PASCAL_DEPTH; i++){
   for(int j = 0, n = pascalArray[i].length; j < n; j++){
    System.out.print(pascalArray[i][j] + " ");
   }
   System.out.println();
  }
}

public static void main(String[] args){
  PascalTriangle pascal = new PascalTriangle();
  
  pascal.producePascal();
  pascal.printWithLength();
}
}
希望对你有用
作者: 徐家大少爷    时间: 2014-9-17 22:51
楼上太麻烦了，来个简单点的
#include <stdio.h>
#define N 10
void yanghui (int a[][N],int n)
{
   
    int i,j;
//    控制第一个数和最后个数都为1
    for (i = 0; i< n; i++) {
        a[i][0] = 1;
        a[i][i]=1;
    }
//    除了和第一数和最后一个数意外其他数都等上面两个顶数值和
    for (i = 2; i< n; i++) {
        for (j = 1; j< i; j++) {
            a[i][j] = a[i-1][j-1]+a[i-1][j];
        }
    }
}


int main(int argc, const char * argv[])
{
    int i,j,n,a[N][N];
    printf("输入一个正整数n:\n");
    scanf("%d",&n);
    yanghui(a,n);
    for (i = 0; i<n; i++) {
        for (int k = 0; k < n-i; k++) {
            printf("***");
        }
        //j<=i的原因是不输出其它的数，只输出我们想要的数
        for (j = 0; j<=i; j++) {
            printf("%6d",a[i][j]);
            

        }printf("\n");
    }
    return 0;
}
作者: yueyazhishang    时间: 2014-9-22 14:17
来晚了，还有没黑马币？
作者: Lizzie    时间: 2014-9-27 20:31
既然有最佳答案了就要设置为已解决 要不然会被扣分的
作者: 没劲睡觉    时间: 2014-10-22 10:58
福利贴啊  







欢迎光临 黑马程序员技术交流社区 (http://bbs.itheima.com/) 黑马程序员IT技术论坛 X3.2