在写代码之前,比贾宪迟600年

作者: 编程  发布:2019-11-20

9159.com 19159.com 2
 杨辉三角有以下几个特点 :

用java实现杨辉三角的示例代码,

之前有学弟问过我一道java的面试题,题目不算难。用java实现杨辉三角。我花了点时间整理了一下,发现挺有意思的,于是想写下来分享一下。在写代码之前,我们先理清下面两个问题。

什么是杨辉三角

杨辉三角,是二项式系数在三角形中的一种几何排列。在我国南宋数学家杨辉1261年所著的《详解九章算法》有提到过。在欧洲叫做帕斯卡三角形,如图。

9159.com 3

杨辉三角

杨辉三角的规律即原理

1.每个数等于它上方两数之和。

2.每行数字左右对称,由1开始逐渐变大。

3.第n行的数字有n项。

4.第n行数字和为2n-1。

5.第n行的m个数可表示为 C(n-1,m-1),即为从n-1个不同元素中取m-1个元素的组合数。

6.第n行的第m个数和第n-m+1个数相等 ,为组合数性质之一。

7.每个数字等于上一行的左右两个数字之和。可用此性质写出整个杨辉三角。即第n+1行的第i个数等于第n行的第i-1个数和第i个数之和,这也是组合数的性质之一。即 C(n+1,i)=C(n,i)+C(n,i-1)。

8.(a+b)n的展开式中的各项系数依次对应杨辉三角的第(n+1)行中的每一项。

9.将第2n+1行第1个数,跟第2n+2行第3个数、第2n+3行第5个数……连成一线,这些数的和是第4n+1个斐波那契数;将第2n行第2个数(n>1),跟第2n-1行第4个数、第2n-2行第6个数……这些数之和是第4n-2个斐波那契数。

10.将各行数字相排列,可得11的n-1(n为行数)次方:1=11^0; 11=11^1; 121=11^2……当n>5时会不符合这一条性质,此时应把第n行的最右面的数字"1"放在个位,然后把左面的一个数字的个位对齐到十位... ...,以此类推,把空位用“0”补齐,然后把所有的数加起来,得到的数正好是11的n-1次方。以n=11为例,第十一行的数为:1,10,45,120,210,252,210,120,45,10,1,结果为 25937424601=1110。

清楚了这两点之后,我们的思路就十分的清晰了。实现的方法有很多种,这里我打算用二维数组加双重for循环来实现。

demo代码:

public class Yanghui {
  public static void main(String[] args) {
    // 创建二维数组
    int t[][]=new int[10][];
    // 遍历二维数组的第一层
    for (int i = 0; i < t.length; i++) {
      // 初始化第二层数组的大小
      t[i]=new int[i+1];
      // 遍历第二层数组
      for(int j=0;j<=i;j++){
        // 将两侧的数组元素赋值为1
        if(i==0||j==0||j==i){
          t[i][j]=1;
        }else{
          // 其他数值通过公式计算
          t[i][j]=t[i-1][j]+t[i-1][j-1];
        }
        // 输出数组元素
        System.out.print(t[i][j]+"t");     
      }
      //换行
      System.out.println();        
    }
  }
}

输出在控制台的结果如下:

9159.com 4

这里只输出了十行的杨辉三角。优化一下,可以改成动态的获取行数。也可以变成正三角,只需在加一个循环用来计算空格。有兴趣的同学可以尝试一下。 ———来自java十八线程序猿

以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持帮客之家。

之前有学弟问过我一道java的面试题,题目不算难。用java实现杨辉三角。我花了点时间整理了一下,发现挺...

组合算法

杨辉三角,是二项式系数在三角形中的一种几何排列。在欧洲,这个表叫做帕斯卡三角形。帕斯卡(1623----1662)是在1654年发现这一规律的,比杨辉要迟393年,比贾宪迟600年

  1. 每个数等于它上方两数之和。

  2. 每行数字左右对称,由1开始逐渐变大。

  3. 第n行的数字有n项。

  4. 第n行数字和为2n-1

  5. 第n行的m个数可表示为 C(n-1,m-1),即为从n-1个不同元素中取m-1个元素的组合数。

  6. 第n行的第m个数和第n-m+1个数相等 ,为组合数性质之一。

            1
          1   1
        1   2   1
      1   3   3   1
    1   4   6   4   1
    

    1 5 10 10 5 1

非递归算法

组合算法的思路是开一个数组,其下标表示1到m个数,数组元素的值为1表示其下标代表的数被选中,为0则没选中。

初始化,将数组前n个元素置1,表示第一个组合为前n个数。

从左到右扫描数组元素值的“10”组合,找到第一个“10”组合后将其变为“01”组合,同时将其左边的所有“1”全部移动到数组的最左端。

当第一个“1”移动到数组的m-n的位置,即n个“1”全部移动到最右端时,就得到了最后一个组合。

例如求5中选3的组合:

1   1   1   0   0   //1,2,3     
1   1   0   1   0   //1,2,4     
1   0   1   1   0   //1,3,4     
0   1   1   1   0   //2,3,4     
1   1   0   0   1   //1,2,5     
1   0   1   0   1   //1,3,5     
0   1   1   0   1   //2,3,5     
1   0   0   1   1   //1,4,5     
0   1   0   1   1   //2,4,5     
0   0   1   1   1   //3,4,5

c++代码如下:

class Combination {
public:
    void combination(int n, int m) {
        int *a = new int[n];
        for (int i = 0; i < m; i++)
            a[i] = 1;
        for (int i = m; i < n; i++)
            a[i] = 0;
        bool tag = true;
        while (tag) {
            displayArray(a, n);
            for (int i = 0; i < n - 1; i++)
                if (a[i] == 1 && a[i + 1] == 0) {
                    tag = true;
                    a[i] = 0;
                    a[i + 1] = 1;
                    moveZeros(a, i);
                    break; 
                }
                else
                    tag = false;
        }
    }
private:
    void displayArray(int *a, int n) {
        for (int i = 0; i < n; i++)
            cout << a[i] << " ";
        cout << endl;
    }
    // 0到n-1,把1移到最左边
    void moveZeros(int *a, int n) {
        int left = 0, right = 0;
        while (right < n) {
            if (a[left] == 1)
                left++;
            else if (a[left] == 0 && a[right] == 1) {
                int t = a[left];
                a[left] = a[right];
                a[right] = t;
                left++;
            }
            right++;
        }
    }
};

概述

前提:每行端点与结尾的数为1.

  1. 每个数等于它上方两数之和。

  2. 每行数字左右对称,由1开始逐渐变大。

  3. 第n行的数字有n项。

  4. 第n行数字和为2n-1。

  5. 第n行的m个数可表示为 C(n-1,m-1),即为从n-1个不同元素中取m-1个元素的组合数。

  6. 第n行的第m个数和第n-m+1个数相等 ,为组合数性质之一。

  7. 每个数字等于上一行的左右两个数字之和。可用此性质写出整个杨辉三角。即第n+1行的第i个数等于第n行的第i-1个数和第i个数之和,这也是组合数的性质之一。即 C(n+1,i)=C(n,i)+C(n,i-1)

  8. (a+b)n的展开式中的各项系数依次对应杨辉三角的第(n+1)行中的每一项。

  9. 将第2n+1行第1个数,跟第2n+2行第3个数、第2n+3行第5个数……连成一线,这些数的和是第4n+1个斐波那契数;将第2n行第2个数(n>1),跟第2n-1行第4个数、第2n-2行第6个数……这些数之和是第4n-2个斐波那契数。

  10. 将各行数字相排列,可得11的n-1(n为行数)次方:1=11^0; 11=11^1; 121=11^2……当n>5时会不符合这一条性质,此时应把第n行的最右面的数字"1"放在个位,然后把左面的一个数字的个位对齐到十位... ...,以此类推,把空位用“0”补齐,然后把所有的数加起来,得到的数正好是11的n-1次方。以n=11为例,第十一行的数为:1,10,45,120,210,252,210,120,45,10,1,结果为 25937424601=1110。

 

  

#!/usr/local/sbin/python3
# -*- coding: utf-8 -*-

from functools import reduce


def row(x):
    return ' '.join(list(map(str,reduce(lambda x,y:list(map(sum,zip([0]+x,x+[0]))),range(x),[1]))))



def pascal(x):
    return 'n'.join(row(i).center(len(row(x-1))) for i in range(x))


print(pascal(10))

 

 

  实现效果如下:

  9159.com 5

    我的思路是由于第一行只有一个元素1,所以第二行也一定是1。所以重点在计算后面几行输出的数字,先把它输进列表。

递归算法

从n个数中选取编号最大的数,然后在剩下的n-1个数里面选取m-1个数,直到从n-(m-1)个数中选取1个数为止。

从n个数中选取编号次小的一个数,继续执行1步,直到当前可选编号最大的数为m。

c++代码如下:

class Combination {
public:
    void combination(int n, int m) {
        int *a = new int[n];
        for (int i = 0; i < n; i++)
            a[i] = 0;
        func(a, n, m, n);
    }
private:
    void displayArray(int *a, int n) {
        for (int i = 0; i < n; i++)
            cout << a[i] << " ";
        cout << endl;
    }
    void func(int *a, int n, int m, const int N) {
        if (m == 0) {
            displayArray(a, N);
            return;
        }
        for (int i = n - 1; i >= m - 1; i--) {
            a[i] = 1;
            func(a, i, m - 1, N);
            a[i] = 0;
        }
    }
};

由上图可以知道第三行 列表第一个元素[2 ] 是第2行列表第0个元素和第一个元素的和,因为第0个元素一直是1不用管它,所以有l[a]=l[a]+l[a+1],由上一行输出下一行,现在第三行

排列算法

是[1,2],然后尾部加上一个[1],就可以得到第三行,列表长度也加了一个,依次类推第四行为[1,3,3],而后再加[1],输出第四行,代码实现如下

递归算法

如果集合是{a,b,c},那么这个集合中元素的所有排列是{(a,b,c),(a,c,b),(b,a,c),(b,c,a),(c,a,b),(c,b,a)},显然,给定n个元素共有n!种不同的排列.

如果给定集合是{a,b,c,d},可以用下面给出的简单算法产生其所有排列,即集合(a,b,c,d)的所有排列有下面的排列组成:
(1)以a开头后面跟着(b,c,d)的排列
(2)以b开头后面跟着(a,c,d)的排列
(3)以c开头后面跟着(a,b,d)的排列
(4)以d开头后面跟着(a,b,c)的排列

这显然是一种递归的思路,于是我们得到了以下的c++代码实现:

class Permutation {
public:
    void permutation(int n) {
        int *a = new int[n];
        for (int i = 0; i < n; i++)
            a[i] = 0;
        func(a, 1, n);
    }
private:
    void displayArray(int *a, int n) {
        for (int i = 0; i < n; i++)
            cout << a[i] << " ";
        cout << endl;
    }
    void func(int *a, int m, const int n) {
        if (m == n + 1) {
            displayArray(a, n);
            return;
        }
        for (int i = 0; i < n; i++) {
            if (a[i] == 0) {
                a[i] = m;
                func(a, m + 1, n);
                a[i] = 0;
            }
        }
    }
};
1 def yanghui(n):
2     l=[1,1]
3     for x in range(1,n):
4         for a in range(x):
5             l[a]=l[a]+l[a+1]
6         l.insert(0,1)
7     return l

非递归算法

<div class="div-border left-purple"> 全排列生成算法的一个重要思路,就是将集合A中的元素的排列,与某种顺序建立一一映射的关系,按照这种顺序,将集合的所有排列全部输出。这种顺序需要保证,既可以输出全部的排列,又不能重复输出某种排列,或者循环输出一部分排列。
字典序就是用此种思想输出全排列的一种方式。这里以A{1,2,3,4}来说明用字典序输出全排列的方法。
首先,对于集合A的某种排列所形成的序列,字典序是比较序列大小的一种方式。
以A{1,2,3,4}为例,其所形成的排列1234 < 1243,比较的方法是从前到后依次比较两个序列的对应元素,如果当前位置对应元素相同,则继续比较下一个位置,直到第一个元素不同的位置为止,元素值大的元素在字典序中就大于元素值小的元素。
上面的a1[1…4]=1234和a2[1…4]=1243,对于i=1,i=2,两序列的对应元素相等,但是当i=2时,有a1[2]=3 < a2[2]=4,所以1234 < 1243。
使用字典序输出全排列的思路是,首先输出字典序最小的排列,然后输出字典序次小的排列,……,最后输出字典序最大的排列。
这里就涉及到一个问题,对于一个已知排列,如何求出其字典序中的下一个排列。这里给出算法。
对于排列a[1…n],找到所有满足a[k] < a[k+1] (0 < k < n-1)的k的最大值,如果这样的k不存在,则说明当前排列已经是a的所有排列中字典序最大者,所有排列输出完毕。
在a[k+1…n]中,寻找满足这样条件的元素l,使得在所有a[l]>a[k]的元素中,a[l]取得最小值。也就是说a[l]>a[k],但是小于所有其他大于a[k]的元素。
交换a[l]与a[k].
对于a[k+1…n],反转该区间内元素的顺序。也就是说a[k+1]与a[n]交换,a[k+2]与a[n-1]交换,……,这样就得到了a[1…n]在字典序中的下一个排列。
这里我们以排列a[1…8]=13876542为例,来解释一下上述算法。首先我们发现,1(38)76542,括号位置是第一处满足a[k] < a[k+1]的位置,此时k=2。
所以我们在a[3…8]的区间内寻找比a[2]=3大的最小元素,找到a[7]=4满足条件,交换a[2]和a[7]得到新排列14876532,对于此排列的3~8区间,反转该区间的元素,将a[3]-a[8],a[4]-a[7],a[5]-a[6]9159.com ,分别交换,就得到了13876542字典序的下一个元素14235678。</div>

下面是该算法的实现代码:

class Permutation {
public:
    void permutation(int n) {
        int *a = new int[n];
        for (int i = 0; i < n; i++)
            a[i] = i + 1;
        while (true) {
            displayArray(a, n);
            //找到k
            int k = n - 2;
            while (k != -1 && a[k] > a[k + 1])
                k--;
            if (k == -1)
                return;
            // 交换比k稍大的数
            int l = k + 1;
            for (int i = k + 1; i < n; i++)
                if (a[i] > a[k] && a[i] < a[l])
                    l = i;
            int t = a[k];
            a[k] = a[l];
            a[l] = t;
            //反转
            for (int i = 1; 2 * i < n - k; i++) {
                int t = a[k + i];
                a[k + i] = a[n - i];
                a[n - i] = t;
            }
        }
    }
private:
    void displayArray(int *a, int n) {
        for (int i = 0; i < n; i++)
            cout << a[i] << " ";
        cout << endl;
    }
};

    后面将每一行按照格式输出即可,

再统一打印

1 x=int(input())
2 a=1
3 b=0
4 print((x-a+1)*' ',[1])
5 while a<x:
6     b=yanghui(a)
7     print((x-a)*' ',b)
8     a+=1

比起需要用到生成器的算法更好理解,也有些取巧了,可以作为一种思路

本文由9159.com发布于编程,转载请注明出处:在写代码之前,比贾宪迟600年

关键词:

上一篇:例如下面我要根据9159.com
下一篇:没有了