ในบทความ ขั้นแรก เราต้องวาดรูปสามเหลี่ยมสี เราต้องใช้สามเหลี่ยมที่ไม่มีสีแล้วแบ่งสามเหลี่ยมออกเป็นสี่ด้านเล็กๆ สามเหลี่ยมที่มีพื้นที่เท่ากันและทำต่อไปจนถึงขั้นที่ n แล้วหาจำนวนสามเหลี่ยมด้านเท่าที่มีอยู่ในรูป
แนวทางในการหาทางออก
แนวทางแก้ไขปัญหานี้มีอยู่สองแนวทางด้วยกันคือ -
แนวทางกำลังเดรัจฉาน
เราสามารถสังเกตได้ว่าจำนวนสามเหลี่ยมเพิ่มขึ้นเรื่อยๆ ตามจำนวนบางส่วน (เพิ่มขึ้น 3*previous_number + 2) หลังจากทุกขั้นตอน ดังนั้นเราจึงสามารถวนซ้ำจนถึง n และคำนวณจำนวนสามเหลี่ยมได้
ตัวอย่าง
#include <iostream>
using namespace std;
int main() {
int n = 2; // number of operations we made
int count = 1; // at first we have only one triangle
for(int i = 0; i < n; i++) { // looping till n
count = 3 * count + 2; // as the triangle count is increasing by 3*prev + 2
}
cout <<count << "\n";
} ผลลัพธ์
17
ความซับซ้อนของเวลาของโปรแกรมด้านบนคือ O(N) โดยที่ N คือจำนวนการดำเนินการที่ดำเนินการ ตอนนี้ เราสามารถปรับปรุงความซับซ้อนของเวลาได้ ซึ่งจะมีประโยชน์มากเมื่อเราจัดการกับข้อจำกัดที่สูงขึ้น
แนวทางที่มีประสิทธิภาพ
ในแนวทางนี้ เราจะสร้างสูตรที่จะคำนวณคำตอบให้เรา
ตัวอย่าง
#include <bits/stdc++.h>
using namespace std;
int main() {
int n = 2; // number of operations we made
int count;
count = 2 * (pow(3, n)) - 1; // the total number of triangles after nth move
cout << count << "\n";
} ผลลัพธ์
17
รหัสด้านบนมีความซับซ้อนของเวลาของ O(log(N)) โดยที่ N คือจำนวนการเคลื่อนไหวที่เราดำเนินการ
คำอธิบายของโค้ดด้านบน
ในโปรแกรมที่กำหนด เรากำลังสร้างสูตรเพื่อแก้ปัญหาขั้นตอนที่กำหนดและใส่ค่าที่ต้องการลงในสูตร แล้วพิมพ์ผลลัพธ์
บทสรุป
บทความนี้จะค้นหาจำนวนสามเหลี่ยมหลังจากที่ N เคลื่อนที่โดยใช้การสังเกตและคณิตศาสตร์บางส่วน เรายังได้เรียนรู้โปรแกรม C++ สำหรับปัญหานี้และแนวทางที่สมบูรณ์ (Normal and excellent ) ซึ่งเราแก้ปัญหานี้ได้
เราสามารถเขียนโปรแกรมเดียวกันในภาษาอื่นๆ เช่น C, java, python และภาษาอื่นๆ เราหวังว่าคุณจะพบว่าบทความนี้มีประโยชน์
