首页 >编程 >正文

C/C++经典杨辉三角问题解决方案

杨辉三角形,又称帕斯卡三角形、贾宪三角形、海亚姆三角形,它的排列形如三角形。本文将为大家介绍通过C++/C语言实现打印杨辉三角形的示例代码,需要的可以参考一下

按理来说,杨辉三角是一个非常经典的问题,以至于随手一搜遍地的代码,但是今天在使用c++实现时遇到了问题,百度出来的没有一个是我想要的答案,所以有了此文。

前言

本文主要讲述了杨辉三角c和c++的具体实现,均为动态。

一、杨辉三角是什么

杨辉三角是二项式系数的集合排列。

具体实现:

是第i行j列的数据是由上一列第j个和j-1个数据相加得到的。

C/C++经典杨辉三角问题解决方案

二、C语言版实现步骤

1.开辟动态二维数组

首先开辟一个存储指针的地址的数组,即二级指针用来存放数据。

下一步便是给每一个二级指针的每个元素开辟空间。

代码如下(示例):

int** Creat(int m)
{
	// 杨辉三角每行数据与行数相同
    //先开二级指针
	int** triAngle = (int**)malloc(sizeof(int*) * m);
	assert(triAngle);
    // 再开二级指针中每个元素存储数据的数组
	for (size_t i = 0; i < m; i++)
	{
		triAngle[i] = (int*)malloc(sizeof(int) * (i + 1));
	}
	return triAngle;
}

2.初始化

杨辉三角的两个等腰边的数字是1,数学规律也比较好找,即每行第0个和最后一个是1,接下来就是开头提到的内部的规律:

是第i行j列的数据是由上一列第j个和j-1个数据相加得到的。

代码如下(示例):

void Init(int** triAngle, int m)
{
	// 先将两腰上的数据初始化为1
	for (size_t i = 0; i < m; i++)
	{
		if (i == 0)
		{
			triAngle[i][0] = 1;
		}
		else
		{
			triAngle[i][0] = triAngle[i][i - 1] = 1;
		}
	}
	// 构建杨辉三角
	for (size_t i = 0; i < m; i++)
	{
		for (size_t j = 0; j < i; j++)
		{
			if (triAngle[i][j] != 1)
			{
				triAngle[i][j] = triAngle[i - 1][j] + triAngle[i - 1][j - 1];
			}
		}
	}
}

3.打印

两层for循环遍历二维数组进行访问然后打印。

代码如下(示例):

void Print(int** triAngle, int m)
{
	for (size_t i = 0; i < m; i++)
	{
		for (size_t j = 0; j < i; j++)
		{
			printf("%d ", triAngle[i][j]);
		}
		printf("\n");
	}
}

4.销毁

首先释放一级指针,再释放存放它们的二级指针。

代码如下(示例):

void Destory(int** triAngle, int m)
{
	for (size_t i = 0; i < m; i++)
	{
		free(triAngle[i]);
	}
	free(triAngle);
}

二、C++版实现步骤

1.实现类的成员变量

杨辉三角只需要一个成员变量:二维数组(两个int的vector嵌套)

存放二维数组的行和列可以用_vv.size()和_vv[i].size()来表示。

代码如下(示例):

class Yanghui
{
private:
	vector<vector<int>> _vv;
	size_t _n;
};

2.实现成员函数

与c语言版相同,也需要创建、初始化、销毁。

创建&初始化

我将创建函数实现为了构造函数,目的是为了不用调用,创建的时候就是开辟好的且已经初始化好的vector<vector<int>>。

代码如下(示例):

// 构建实现为构造函数就不用调用了
	Yanghui(int n = 5)
	{
		_vv.resize(n);
		for (size_t i = 0; i < _vv.size(); i++)
		{
			_vv[i].resize(i + 1);
		}
		// 先初始化两腰数据为1
		for (size_t i = 0; i < _vv.size(); i++)
		{
			_vv[i][0] = _vv[i][_vv[i].size() - 1] = 1;
		}
		// 构建杨辉三角
		for (size_t i = 0; i < _vv.size(); i++)
		{
			for (size_t j = 0; j < _vv[i].size(); j++)
			{
				if (_vv[i][j] != 1)
				{
					_vv[i][j] = _vv[i - 1][j] + _vv[i - 1][j - 1];
				}
			}
		}
	}

打印

代码如下(示例):

void Print(int n)
	{
		for (size_t i = 0; i < n+1; i++)
		{
			for (size_t j = 0; j < i; j++)
			{
				cout << _vv[i][j] << " ";
			}
			cout << endl;
		}
	}

3.类的总体

代码如下(示例):

#include <vector>
using namespace std;
class Yanghui
{
public:
	// 构建实现为构造函数就不用调用了
	Yanghui(int n = 5)
	{
		_vv.resize(n);
		for (size_t i = 0; i < _vv.size(); i++)
		{
			_vv[i].resize(i + 1);
		}
		// 先初始化两腰数据为1
		for (size_t i = 0; i < _vv.size(); i++)
		{
			_vv[i][0] = _vv[i][_vv[i].size() - 1] = 1;
		}
		// 构建杨辉三角
		for (size_t i = 0; i < _vv.size(); i++)
		{
			for (size_t j = 0; j < _vv[i].size(); j++)
			{
				if (_vv[i][j] != 1)
				{
					_vv[i][j] = _vv[i - 1][j] + _vv[i - 1][j - 1];
				}
			}
		}
	}
	void Print()
	{
		for (size_t i = 0; i < _vv.size(); i++)
		{
			for (size_t j = 0; j < _vv[i].size(); j++)
			{
				cout << _vv[i][j] << " ";
			}
			cout << endl;
		}
	}
	~Yanghui()
	{
		cout << "~Yanghui()" << endl;
	}
private:
	vector<vector<int>> _vv;
};
int main()
{
	Yanghui triAngle(5);
	triAngle.Print();
	return 0;
}

到此这篇关于C/C++经典杨辉三角问题解决方案的文章就介绍到这了,更多相关C++杨辉三角内容请搜索脚本之家以前的文章或继续浏览下面的相关文章希望大家以后多多支持脚本之家!

网友评论

验证码 换一张
取 消
暂无评论...
三日内热门评论文章
关键词
为您推荐
  • 相关阅读
  • 业界资讯
  • 手机通讯
  • 电脑办公
  • 新奇数码
  • 软件游戏
  • 科学探索