使用 C++ 计算 N 次移动后的三角形数

在文章中，首先，我们要画一个彩色三角形。我们需要取一个未着色的三角形，将三角形分成四个小等边形。面积相同的三角形，一直做到第n步，求出图中等边三角形的个数。

寻找解决方案的方法

此解决方案有两种方法，它们是-

蛮力方法

我们可以观察到三角形的数量在每一步之后都会增加一些（增加3*previous_number+2）。所以我们可以运行一个循环直到n并计算三角形的数量。

示例

#include <iostream> using namespace std; int main() { int n = 2; //我们进行的操作数 int count = 1; //一开始我们只有一个三角形 for(int i = 0; i < n; i++) { //循环直到n count = 3 * count + 2; //随着三角形计数增加3*prev+2 } cout <<count << "\n"; }输出结果17

上述程序的时间复杂度为O(N)，其中N是执行的操作数。现在我们可以进一步提高它的时间复杂度，这在我们处理更高的约束时会非常有帮助。

有效的方法

在这种方法中，我们将制定一个公式来计算我们的答案。

示例

#include <bits/stdc++.h> using namespace std; int main() { int n = 2; //我们进行的操作数 int count; count = 2 * (pow(3, n)) - 1; //第n次移动后的三角形总数 cout << count << "\n"; }输出结果17

上述代码的时间复杂度为O(·log(N))，其中N是我们执行的移动次数。

上面代码的解释

在给定的程序中，我们只是简单地编写一个公式来解决给定的过程，并将所需的值放入公式中，然后打印结果。

结论

本文通过应用一些观察和一些数学计算得出N次移动后三角形的数量。我们还学习了针对此问题的C++程序以及解决此问题的完整方法（正常和高效）。

我们可以用其他语言编写相同的程序，例如C、java、python和其他语言。我们希望这篇文章对您有所帮助。