亲宝软件园·资讯

展开

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

36°熨斗的学习日记 人气:0

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

前言

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

一、杨辉三角是什么

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

具体实现:

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

二、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;
}

加载全部内容

相关教程
猜你喜欢
用户评论