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; }
加载全部内容