首页 > 试题广场 >

杨辉三角代码编写

[编程题]杨辉三角代码编写

热度指数：341 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

杨辉三角，是二项式系数在三角形中的一种几何排列，中国南宋数学家杨辉1261年所著的《详解九章算法》一书中出现。

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
观察这个排列，发现其中的规律，编写代码，实现打印其中任意一行

输入描述:

输入想要打印的行号n,例如:5

输出描述:

只要打印该行的内容即可，不用打印头尾的空格例如：1 4 6 4 1

示例1

输入

输出

示例2

输入

输出

1 4 6 4 1

算法知识视频讲解

tuiheishu

#!/usr/bin/bash

b=( 0 1 )

read -p "请输入要输出的行数：" number

for ((i=1;i<=$number;i++))

for ((j=1;j<=$i;j++))

if [ $j -eq 1 ] || [ $j -eq $i ];then

a[$j]=1

else

a[$j]=$((${b[$j-1]}+${b[$j]}))

done

for n in ${!a[*]}

b[$n]=${a[$n]}

done

for m in ${!b[*]}

if [ $m -gt 0 ];then

echo -n "${b[$m]}"

echo -n " "

done

发表于 2021-09-24 21:12:34 回复(0)

pein531

prev为前一层，cur为后一层，第m层有m个数，其中第一个数和最后一个数都是1。除了第一个数和最后一个数，其余位置的数满足

cur[i] = prev[i] + prev[i - 1]

于是写出如下的迭代做法：

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.ArrayList;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        if(n == 1){
            System.out.println(1);
        }else if(n == 2){
            System.out.println(1 + " " + 1);
        }else{
            int[] prev = new int[]{1, 1};
            int[] cur = new int[3];
            for(int layerNum = 3; layerNum <= n; layerNum++){
                cur = new int[layerNum];
                cur[0] = 1;
                cur[cur.length - 1] = 1;
                for(int j = 1; j < layerNum - 1; j++)
                    cur[j] = prev[j] + prev[j - 1];
                prev = cur;
            }
            for(int i = 0; i < n; i++)
                System.out.print(cur[i] + " ");
        }
    }
}

发表于 2021-09-19 20:51:46 回复(0)

黄某人1997

n = int(input())
ans_list = []
ans_list.append(1)
fenzi = 1
fenmu = 1
for index in range(1,n):
    fenzi = fenzi * (n-index)
    fenmu = fenmu * index
    ans_list.append(int(fenzi/fenmu))
for i in ans_list:
    print(i,end=' ')

发表于 2021-09-19 17:30:57 回复(0)

C/C++

猫猫猫1

#include<bits/stdc++.h>
using namespace std;

int main(){
    int n;
    while(cin>>n){
        int a[n][n];
        for(int i=0;i<n;i++){
            for(int j=0;j<=i;j++){
                a[i][j]=1;
            }
        }
        for(int i=1;i<n;i++){
            for(int j=1;j<i;j++){
                a[i][j]=a[i-1][j-1]+a[i-1][j];
            }
        }
        for(int i=0;i<n;i++){
cout<<a[n-1][i]<<" ";
}
    }
    return 0;
}

发表于 2022-10-08 17:33:10 回复(1)

C/C++

Monkiii

递归思想，C++实现：

#include <iostream>
#include <cstdio>
using namespace std;

int Solve(int n,int p){
    if(n==0||n==1||p==0||p==n-1) return 1;
    else{
        return Solve(n-1,p-1)+Solve(n-1,p);
    }
}

int main() {
    int n;
    while(scanf("%d",&n)!=EOF){
        int arr[n];
        for(int p=0;p<n;p++){
            arr[p] = Solve(n,p);
        }
        for(int p=0;p<n;p++){
            printf("%d ",arr[p]);
        }
        printf("\n");
    }
}

发表于 2023-05-27 16:19:41 回复(0)

牛客694617193号

#include<bits/stdc++.h>
using namespace std;

class Solution{
public:
	vector<int> func(int n){
		vector<int> res(n, 1);
		for(int i = 1; i <= n-1; i++){          //n行一共要n-1次递推；
			for(int j = i; j >= 1; j--){    //从后往前计算，避免被覆盖。
				res[j] = res[j] + res[j-1];
			}
		}
		
		return res;
	}
};

int main(){
    int n;
    cin>>n;
	Solution s;
	vector<int> nums = s.func(n);
	for(int num: nums){
		cout<<num<<" ";
	}
}

编辑于 2022-03-18 16:02:56 回复(0)

Python

9527号程序猿

杨辉三角还有另外一个规律：

第二行开始，由上一行前面加一个0组成的列表，去缝合（zip）上一行后面加一个0组成的列表，然后相加，得到答案，如第二行为：

第一行前面加0，为： 0 1
第一行后面加0, 为： 1 0
上下同位相加得到： 1 1
即为第二行数据

Python2代码：

def get_function(n):
    a1 = [1]
    x = []
    i = 1
    while i < n:
        for t in zip([0] + a1, a1+[0]):
            x.append(sum(t))
        a1 = x
        x = []
        i += 1
    return a1

n = int(input())
res = get_function(n)
print ' '.join(list(map(str, res)))

发表于 2022-02-25 01:33:04 回复(0)

牛客728027687号

递归：

package main
import (
    "fmt"
    "strings"
)
func yhTriangle(n int) []int {
    if n < 1 {
        return nil
    }
    if n == 1 {
        return []int{1}
    }
    if n == 2 {
        return []int{1, 1}
    }
    ls := make([]int, n)
    for i:=1;i<n-1;i++ {
        ls[i] = yhTriangle(n-1)[i-1] + yhTriangle(n-1)[i]
    }
    ls[0] = 1
    ls[n-1] = 1
    return ls
}

func main() {
    var n int
    _, _ = fmt.Scanln(&n)
    r := strings.Trim(fmt.Sprint(yhTriangle(n)), "[]")
    fmt.Printf("%s", r)
}

发表于 2021-12-21 00:01:35 回复(0)

牛客488074532号

public class Main {

    public static int[] f(int n) {
        int[] a = new int[n];
        if (n == 1) {
            a[0]=1;
            return a;
        }
        if (n == 2) {
            a[0]=1;
            a[1]=1;
            return a;
        }
        a[0]=1;
        a[n-1]=1;
        for(int i=1;i<n-1;i++) {
            a[i]=f(n-1)[i-1]+f(n-1)[i];
        }
        return a;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n=sc.nextInt();
        int[] a=f(n);
        for (int i = 0; i < a.length; i++) {
            System.out.print(a[i] + " ");
        }

    }

}

发表于 2021-11-18 10:16:57 回复(0)

在洛杉矶冲浪的卷心菜

逆天编译器。。。

发表于 2021-10-09 17:31:03 回复(0)

FreeRay

使用二维数组求出杨辉三角

import java.util.Scanner;
public class Main {
 public static void main(String[] args){
     Scanner sc=new Scanner(System.in);
     int input=sc.nextInt(); 
     Main t=new Main();
     for(int i=0;i<input;i++){
         System.out.print(t.yanghui(input,i)+" ");
     }
 }
   public int yanghui(int m,int n){
       int result;
       int[][] yanghui=new int[100][100];
       for (int i = 1; i < m+1; i++) {
            for (int j = 0; j < i; j++) {
                if(i==1||j==0||j==(i-1))
                yanghui[i][j]=1;
                else{
                    yanghui[i][j] = yanghui[i-1][j-1] + yanghui[i-1][j];
                }
            }
       }
           result=yanghui[m][n];
       return result;

 }
}

发表于 2021-09-27 22:40:48 回复(0)

Java

MCTBL

import java.util.Scanner;

public class Pascal_Triangle {

	public static int[] Line(int line) {
		if(line==1) {
			int a[]= {1};
			return a;
		}
		int temp[]=Line(line-1);
		int a[]=new int[line];a[0]=1;a[line-1]=1;
		for(int i=0;i<temp.length-1;i++) {
			a[i+1]=temp[i]+temp[i+1];
		}
		return a;
	}
	
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner inPut=new Scanner(System.in);
		int line=inPut.nextInt();
		for(int a:Line(line)) {
			System.out.print(a+" ");
		}
	}

}

差不多很简单易懂，递归一下，每次调用递归返回上一层数组，数组两边直接赋予1，中间由上一行两个数决定，两两之和赋予下一行下标较大的位置即可。

编辑于 2021-09-16 23:49:57 回复(0)

Moria_Moriarity

构建一个二维数组，第一列赋值为1，其余赋值为0；

然后根据题意，发现第i行j列的值是i-1行的j列和j-1列之和；

用公式表示即为dp[i][j]=dp[i-1][j-1]+dp[i-1][j];

第i行会有i列，逐层递归计算。

最后输出第i行的结果。完。

#include <iostream>
#include <vector>
usingnamespacestd;
 
intmain()
{
    intN;
    cin >> N;
    vector<vector<int>> dp(N, vector<int>(N));
    for(inti = 0; i < N; i++)
        dp[i][0] = 1;
    for(inti = 0; i < N; i++)
        for(intj = 1; j < N; j++)
            dp[i][j] = 0;
    for(inti = 1; i < N; i++)
        for(intj = 1; j <= i; j++)
            dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j];
    for(inti = 0; i < N - 1; i++)
        cout << dp[N - 1][i] << ' ';
    cout << dp[N - 1][N - 1] << endl;
    return0;
}

有很多可以优化的空间，比如通过剪枝降低空间占用，只构建vector<int> dp(N)大小的数组储存变量。

等待后续大佬们的完善和优化。

发表于 2021-09-14 15:49:11 回复(0)

提交观点

问题信息

运维工程师游卡

上传者：小小

难度：

13条回答 12收藏 1806浏览

通过挑战的用户

大牛来了_

2023-03-13 09:15:32
Augenst...

2023-03-05 18:15:16
牛客49234...

2023-02-15 15:28:42
牛客80892...

2023-02-13 09:39:10
Huster水仙

2023-01-26 13:57:06

杨辉三角代码编写

输入描述:

输出描述:

输入

输出

输入

输出

问题信息

热门推荐

通过挑战的用户

相关试题