C++ หาจำนวนสามเหลี่ยมหลังจากการเคลื่อนที่ N ครั้ง

ในบทความนี้ เราต้องวาดสามเหลี่ยมที่มีสี เริ่มจากสามเหลี่ยมที่ไม่มีสี แบ่งสามเหลี่ยมออกเป็น 4 สามเหลี่ยมด้านเท่าเล็กๆ ที่มีพื้นที่เท่ากัน และทำซ้ำจนถึงขั้นตอนที่ n แล้วหาจำนวนสามเหลี่ยมด้านเท่าที่ปรากฏในรูป

วิธีการแก้ปัญหา

มีสองวิธีแก้ปัญหานี้ คือ

วิธี Brute Force

สังเกตว่าจำนวนสามเหลี่ยมเพิ่มขึ้นตามรูปแบบ (เพิ่มขึ้น 3*ค่าก่อนหน้า + 2) หลังจากแต่ละขั้นตอน เราสามารถรันลูปจนถึง n และคำนวณจำนวนสามเหลี่ยม

ตัวอย่าง

#include <iostream> 
using namespace std; 

int main() { 
    int n = 2; // จำนวนการดำเนินการ 
    int count = 1; // เริ่มต้นมีแค่ 1 สามเหลี่ยม 
    for(int i = 0; i < n; i++) { 
        count = 3 * count + 2; 
    } 
    cout << count << "\n"; 
}

ผลลัพธ์

17

ความซับซ้อนด้านเวลาของโปรแกรมข้างต้นคือ O(N) โดย N คือจำนวนการดำเนินการ เราสามารถปรับปรุงความซับซ้อนด้านเวลาให้ดีขึ้นสำหรับข้อจำกัดที่สูงกว่า

วิธีมีประสิทธิภาพ (Efficient Approach)

ในวิธีนี้ เราจะสร้างสูตรเพื่อคำนวณคำตอบโดยตรง

ตัวอย่าง

#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 ได้ หวังว่าจะเป็นประโยชน์