लेख में, पहले हमें एक रंगीन त्रिभुज बनाना है। हमें एक बिना रंग का त्रिभुज लेना है और उसे चार छोटे समभुज त्रिभुजों में विभाजित करना है। समान क्षेत्रफल वाले त्रिभुज और इसे nवें चरण तक करते रहना है और आकृति में मौजूद समभुज त्रिभुजों की संख्या निकालनी है।
समाधान खोजने का दृष्टिकोण
इस समाधान के दो दृष्टिकोण हैं -
ब्रूट फोर्स दृष्टिकोण
हम देख सकते हैं कि प्रत्येक चरण के बाद त्रिभुजों की संख्या कुछ संख्या से बढ़ती रहती है (3*पिछली_संख्या + 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*पिछला + 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 की गई चालों की संख्या है।
उपरोक्त कोड की व्याख्या
दिए गए प्रोग्राम में, हम बस अपनी दी गई प्रक्रिया को हल करने के लिए एक सूत्र बना रहे हैं और सूत्र में आवश्यक मान डालकर परिणाम प्रिंट कर रहे हैं।