अपने आप में नंबर

मेरा शौक स्कूली बच्चों को गणित और कंप्यूटर विज्ञान सिखाना है। इस प्रक्रिया में, प्रेरणा का मुद्दा बहुत महत्वपूर्ण है, इसलिए आपको सामग्री की गुणवत्ता को ध्यान से देखना होगा। सामग्री को पढ़ने के विभिन्न तरीकों की गणना करने के बाद, "वन टास्क" परियोजना का विचार पैदा हुआ, जिसमें, केवल एक समस्या को हल करने के एक उदाहरण के रूप में, विभिन्न सामग्रियों के साथ एक व्याख्यान दिया जाता है। इसलिए, मैं इस परियोजना की पहली सामग्री प्रदर्शित करता हूं।

कार्य: वहाँ टाइलें 1x1 और 1x2 मीटर आकार की हैं। इन टाइलों के साथ 1x15 मीटर आयत को टाइल करने के कितने तरीके हैं?

इस समस्या के समाधान का प्रस्ताव करने के लिए इस तरह की जुझारू समस्याओं को सुलझाने में अनुभव के बिना आमतौर पर किसी व्यक्ति के लिए यह आसान नहीं है। इसलिए, काम की परिकल्पना प्राप्त करने के लिए इसे सरल बनाने के लिए इसे कम करने के लायक है। आइए छोटे आयतों को टाइल करने के तरीकों से छंटनी शुरू करें।
1x1 आयत को केवल एक तरह से टाइल किया जा सकता है। आयत 1x2 - दो। आइए सरल आयतों के लिए एक तालिका बनाएं:

आकार	विकल्पों की संख्या
1x1	1
1X2	2
1x3	3
1x4	5
1h5	8

बस मामले में, हम एक 1x5 आयत के लिए सभी विकल्पों को सूचीबद्ध करते हैं, जहां नंबर 1 एक 1x1 टाइल है, नंबर 2 एक 1x2 टाइल है:

1. 1
२.११ २
3. 111 12 21
4.1111 112 121 211 22
5.11111 1112 1121 1211 2111 122 212 221

यह देखना आसान है कि दूसरे कॉलम में तालिका में फाइबोनैचि संख्याएं हैं। उनकी उपस्थिति स्पष्ट रूप से आकस्मिक नहीं है। चलो सोचते हैं कि वे कहां से आ सकते हैं।
कल्पना करें कि हम एक आयत को बाएं से दाएं बाँध रहे हैं। तब आप 1x आयत (N-1) में 1x1 टाइल या 1x आयत (N-2) के लिए 1x2 टाइल जोड़कर 1xN आयत प्राप्त कर सकते हैं। तो, प्रत्येक टाइलिंग 1x (N-1) और 1x (N-2) एक टाइलिंग 1x (N) से मेल खाती है। यदि हम P (N) के लिए 1xN आयत को टाइल करने के लिए विकल्पों की संख्या को निरूपित करते हैं, तो हम सूत्र P (N) = P (N-1) + P (N-2) प्राप्त करते हैं, जो कि फाइबोनैचि संख्याओं का सूत्र है।

आइए अब एक प्रोग्राम लिखने की कोशिश करें जो फाइबोनैचि संख्याओं की गणना करता है। जाहिर है, इन संख्याओं का सूत्र पुनरावर्ती है, इसलिए हम समस्या को दो तरीकों से हल करेंगे: एक चक्र के माध्यम से और पुनरावृत्ति के माध्यम से।

 कार्यक्रम प्रोजेक्ट 2;
 {$ APPTYPE CONSOLE}
 का उपयोग करता है
   SysUtils;
 var a: array [1..15] पूर्णांक का;
 i: पूर्णांक;
 function p (n: पूर्णांक): पूर्णांक;
 शुरू करना
   अगर n <3 तो p: = n अन्यथा p: = p (n-1) + p (n-2);
 अंत;
 शुरू करना
   एक [१]: = १;
   एक [२]: = २;
   i: = 3 से 15 एक [i]: = एक [i-1] + एक [i-2];
   writeln (एक [15]);
   रिटेलन (पी (15));
   readln;
 अंत।

अब गणना करते हैं कि इस एल्गोरिथ्म में कितनी बार प्रत्येक तर्क के लिए एक पुनरावर्ती कार्य कहा जाता है। पी (n) द्वारा निरूपित करें तर्क n के साथ p पर कॉल की संख्या। जाहिर है, पी (15) = 1 और पी (14) = 1। लेकिन p (n) = p (n + 1) + (n + 2)। यही है, हम फिर से एक ही फाइबोनैचि अनुक्रम प्राप्त करते हैं। अपवाद केवल p (1) = p (3) है। इस प्रकार, हमने एक अद्भुत तथ्य सिद्ध किया है: फाइबोनैचि संख्याओं की गणना के लिए पुनरावर्ती एल्गोरिथ्म की जटिलता को फाइबोनैचि संख्याओं के योग द्वारा मापा जाता है।