我在考虑写一个代码来创建一个PASCAL三角形。我已经做过了，但后来我想做得更好。我想到了一个主意，但我找不到合适的答案。有可能创建一个像这样的数组吗?[1]|[1][1]|[1][2][1]|[1][3][3][1]|[1][4][6][4][1]|等等?所以我的[1]是(0,0)[1][2][1]是单元格(2,0)(2,1)(2,2)的元素。如有任何建议，我将不胜感激。
可以通过单维数组实现三角形数组。固定大小的数组可能像这样:
template<typename T, size_t N>
struct TriangleArray {
T& element(size_t i, size_t j)
{
if (i >= N || j >= N || i < j)
throw std::out_of_range("incorrect index");
return container[(i + 1) * i / 2 + j];
}
private:
T container[(N + 1) * N / 2];
};
不可能。在数组中，所有元素必须具有相同的类型。二维数组是数组的数组。这意味着对于多维数组，所有的行必须具有相同的长度。你应该使用
std::vector<std::vector<int> >
。或者一个一维数组，以及从2个dim索引中计算1个dim位置的逻辑:
index = row*(row+1)/2 + column.
如果需要反向索引，请参见无嵌套循环的迭代矩阵。
编辑:修正了我的公式，这是一个。下面是Python中的检查:
下面的索引函数接受row, col，并使用我的公式计算一维数组中的相应索引:
>>> index = lambda row, col: row*(row+1)/2 + col
这是坐标对
>>> [[(i,j) for j in range(i+1)] for i in range(5)]
[[(0, 0)],
[(1, 0), (1, 1)],
[(2, 0), (2, 1), (2, 2)],
[(3, 0), (3, 1), (3, 2), (3, 3)],
[(4, 0), (4, 1), (4, 2), (4, 3), (4, 4)]]
我现在检查相应的索引是从0开始的整数序列(打印缩进是我的):
>>> [[index(i,j) for j in range(i+1)] for i in range(5)]
[[0],
[1, 2],
[3, 4, 5],
[6, 7, 8, 9],
[10, 11, 12, 13, 14]]
最好的方法是将整个东西包装在一个名为PascalTriangle的类中，并按照以下行实现它:
class PascalTriangle
{
private:
std::vector<std::vector<int> > m_data;
std::vector<int> CalculateRow(int row_index) const
{
// left as an exercise :)
}
public:
PascalTriangle(int num_rows) :
m_data()
{
assert(num_rows >= 0);
for (int row_index = 0; row_index < num_rows; ++row_index)
{
m_data.push_back(CalculateRow(row_index));
}
}
int operator()(int row_index, int column_index) const
{
assert(row_index >= 0 && row_index < m_data.size());
assert(column_index >= 0 && column_index < row_index);
return m_data[row_index][column_index];
}
};
现在问题来了:这种方法允许执行延迟求值。考虑以下情况:您可能并不总是需要每个值。例如，您可能只对第5行感兴趣。那么为什么要存储其他未使用的值呢?
基于这个思想，这里是上一个类的高级版本:
class PascalTriangle
{
private:
int m_num_rows;
std::vector<int> CalculateRow(int row_index) const
{
// left as an exercise :)
}
public:
PascalTriangle(int num_rows) :
m_num_rows(num_rows)
{
assert(num_rows >= 0);
// nothing is done here!
}
int operator()(int row_index, int column_index) const
{
assert(row_index >= 0 && row_index < m_num_rows);
assert(column_index >= 0 && column_index < row_index);
return CalculateRow(row_index)[column_index];
}
};
请注意，类的公共接口保持完全相同，但其内部结构完全不同。这就是适当封装的优点。您可以有效地集中错误处理和优化点。
我希望这些想法能激励你更多地思考操作，因为它们将决定最合适的数据结构。
编辑:根据请求，这里有一些更多的解释:
在第一个版本中，m_data是向量的向量。每个包含的std::vector<int>代表三角形中的一行。
operator()函数是一个语法助手，允许您像这样访问PascalTriangle对象:
PascalTriangle my_triangle(10);
int i = my_triangle(3, 2);
assert确保您的代码不会操作非法值，例如负行计数或行索引大于三角形。但这只是一种可能的错误报告机制。您还可以使用异常、错误返回值或易出错的习惯用法(std::optional)。请参阅过去的Stackoverflow问题，了解何时使用哪种错误报告机制。这是一个纯粹的软件工程方面，与数学无关，但你可以想象，它在软件中非常重要:)
CalculateRow返回代表row_index指定的行的std::vector<int>。要正确地实现它，你需要一些数学知识。这是我刚刚在谷歌上发现的:http://www.mathsisfun.com/pascals-triangle.html
为了应用数学，你要知道如何计算n!在c++中。过去有很多关于这方面的Stackoverflow问题，例如:在c++中计算大阶乘
注意，使用类方法，以后可以很容易地切换到另一个实现。(您甚至可以将其发挥到极致，切换到基于三角形高度的特定计算算法，而类的用户却不会注意到任何事情!看看正确的封装有多强大吧?)
在类的第二个版本中，不再有永久的数据存储。CalculateRow只在需要时被调用，但是类的客户端并不知道这一点。作为一个额外的(可能是)性能改进措施，您可以记住已经计算过的行，例如，通过添加一个私有std::map<int, std::vector<int> >成员变量，其int键表示行索引，其值表示行。每个CalculateRow调用将首先查看结果是否已经存在，并在最后添加计算的结果:
private mutable std::map<int, std::vector<int> > m_cache;
std::vector<int> CalculateRow(int row_index) const
{
// find the element at row_index:
std::map<int, std::vector<int> >::const_iterator cache_iter =
m_cache.find(row_index);
// is it there?
if (cache_iter != m_cache.end())
{
// return its value, no need to calculate it again:
return cache_iter->second;
}
// actual calculation of result left as an exercise :)
m_cache[row_index] = result;
return result;
}
auto关键字的一个很好的应用。例如，您只需写入auto cache_iter = m_cache.find(row_index);
这里是另一个编辑:我使m_cache 可变，因为否则事情不会编译，因为CalculateRow是const成员函数(即不应该从客户端的角度改变类的对象)。