使用 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和其他语言。我们希望这篇文章对您有所帮助。