மறுநிகழ்வு மற்றும் மறுநிகழ்வு சூத்திரத்தைப் புரிந்துகொள்வது

மறுப்பு

மறு செய்கை என்பது ஒரு செயல்முறையின் மறுபடியும் ஆகும். பள்ளிக்குச் செல்லும் ஒரு மாணவர் பட்டப்படிப்பு வரை தினமும் பள்ளிக்குச் செல்லும் செயல்முறையை மீண்டும் செய்கிறார். பொருட்கள் வாங்க மாதத்திற்கு ஒரு முறையாவது அல்லது இரண்டு முறையாவது மளிகை கடைக்குச் செல்கிறோம். ஒவ்வொரு மாதமும் இந்த செயல்முறையை நாங்கள் மீண்டும் செய்கிறோம். கணிதத்தில், ஒரு பைபோனச்சி வரிசை பணி மீண்டும் நிகழும் பண்புகளையும் பின்பற்றுகிறது. முதல் இரண்டு எண்கள் 0 மற்றும் 1 ஆக இருக்கும் ஃபைபோனச்சி வரிசையை கருத்தில் கொள்வோம், மற்ற எல்லா எண்களும் முந்தைய இரண்டு எண்களின் கூட்டுத்தொகையாகும்.

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89

மறுசீரமைப்பு படிகள்

ஃபைபோனச்சி சூத்திரத்தை இவ்வாறு எழுதலாம்,

F (n) = F (n - 1) + F (n - 2)
fibonacci (0) = 0
fibonacci (1) = 1
ஃபைபோனச்சி (2) = ஃபைபோனச்சி (1) + ஃபைபோனச்சி (0) = 1 + 0 = 1
fibonacci (3) = fibonacci (2) + fibonacci (1) = 1 + 1 = 2
fibonacci (4) = fibonacci (3) + fibonacci (2) = 2 + 1 = 3
fibonacci (5) = fibonacci (4) + fibonacci (3) = 3 + 2 = 5
fibonacci (6) = fibonacci (5) + fibonacci (4) = 5 + 3 = 8

கீழே கொடுக்கப்பட்டுள்ள வழிமுறை n வது ஃபைபோனச்சி எண்ணை வழங்குகிறது.

மறுநிகழ்வு

ஒவ்வொரு முறையும் ஒரு புதிய ஃபைபோனச்சி எண்ணை (n வது எண்) பெறும்போது, ​​அந்த n வது எண் உண்மையில் (n - 1) வது எண் (n + 1) வது Fibonacci ஐ நமது அடுத்த n வது Fibonacci எனக் கண்டறியும்போது. மேலே குறிப்பிட்டுள்ள மறு செய்கை படிகளைப் பார்க்கும்போது: n = 2 என்றால்
ஃபைபோனச்சி (2) = ஃபைபோனச்சி (2 - 1) + ஃபைபோனாக்கி (2 - 2) = ஃபைபோனச்சி (1) + ஃபைபோனச்சி (0) = 1 + 0 = 1

இப்போது, ​​நாம் ஃபைபோனாக்கி (3) ஐ உருவாக்க விரும்புகிறோம், அதாவது n = 3.

ஃபைபோனச்சி (3) = ஃபைபோனச்சி (3 - 1) + ஃபைபோனாக்கி (3 - 2) = ஃபைபோனச்சி (2) + ஃபைபோனச்சி (1) = 1 + 1 = 2
அதாவது, ஒவ்வொரு முறையும் n மின்னோட்டத்தின் மதிப்பை அதிகரிக்கிறது (n - 1) வது மற்றும் (n - 2) வது ஃபைபோனாக்கியும் அதிகரிக்கிறது. ஆனால் ஒவ்வொரு n க்கும் (n - 1) வது மற்றும் (n - 2) வது ஃபைபோனாக்கியைக் கண்காணிப்பது சோர்வாக இருக்கிறது. மறு செய்கையின் பணியைத் தானே மீண்டும் செய்ய தன்னை அழைக்கும் ஒரு முறையை எழுதுவது எப்படி?

தன்னை அழைக்கும் ஒரு முறை சுழல்நிலை முறை என்று பெயரிடப்பட்டது. ஒரு சுழல்நிலை முறைக்கு ஒரு அடிப்படை வழக்கு இருக்க வேண்டும், அங்கு நிரல் தன்னை அழைப்பதை நிறுத்துகிறது. ஃபைபோனாக்கி தொடருக்கான எங்கள் அடிப்படை வழக்கு ஃபைபோனச்சி (0) = 0 மற்றும் ஃபைபோனச்சி (1) = 1. இல்லையெனில், ஃபைபோனச்சி முறை தன்னை இரண்டு முறை அழைக்கிறது - ஃபைபோனச்சி (என் - 1) மற்றும் ஃபைபோனச்சி (என் - 2). பின்னர் அது ஃபைபோனச்சி (என்) பெற அவற்றைச் சேர்க்கிறது. N வது ஃபைபோனாக்கியைக் கண்டுபிடிப்பதற்கான ஒரு சுழல்நிலை முறையை இவ்வாறு எழுதலாம் -

நாம் கவனமாகப் பார்த்தால், மறுநிகழ்வு அடுக்கின் சொத்தைப் பின்பற்றுகிறது. இது ஒரு சிக்கலின் தீர்வைப் பெற சிறிய துணை சிக்கல்களை தீர்க்கிறது. N> 1 க்கு, இது கடைசி வரியை இயக்குகிறது. எனவே, n = 6 எனில், செயல்பாடு ஃபைபோனச்சி (6 - 1) மற்றும் ஃபைபோனச்சி (6 - 2) ஆகியவற்றைச் சேர்க்கிறது. ஃபைபோனச்சி (6 - 1) அல்லது ஃபைபோனச்சி (5) ஃபைபோனச்சி (5 - 1) மற்றும் ஃபைபோனச்சி (5 - 2) ஆகியவற்றைச் சேர்க்கிறது. ஃபைபொனாச்சி (0) = 0 அல்லது ஃபைபோனச்சி (1) = 1. அதன் அடிப்படை வழக்கு மதிப்பை 6 அடையும் வரை இந்த மறுநிகழ்வு தொடர்கிறது. இது அடிப்படை வழக்கைத் தாக்கியவுடன் அது இரண்டு அடிப்படை மதிப்புகளைச் சேர்த்து, ஃபைபோனாக்கியின் மதிப்பைப் பெறும் வரை மேலே செல்கிறது ( 6). மறுநிகழ்வின் மர பிரதிநிதித்துவம் கீழே.

மறுநிகழ்வு மரம்

நாம் பார்க்க முடியும் என, ஒரு மறுநிகழ்வு எவ்வளவு சக்திவாய்ந்ததாக இருக்கும். குறியீட்டின் ஒரு வரி மட்டுமே மேலே உள்ள மரத்தை உருவாக்குகிறது (மேலே உள்ள குறியீட்டின் கடைசி வரி அடிப்படை வழக்குகள் உட்பட). மறுநிகழ்வு ஒரு அடுக்கை பராமரிக்கிறது மற்றும் அது அடிப்படை வழக்கை அடையும் வரை ஆழமாக செல்லும். டைனமிக் புரோகிராமிங் (டிபி): மறுநிகழ்வு புரிந்துகொள்வது மற்றும் குறியீடு செய்வது எளிது, ஆனால் நேரம் மற்றும் நினைவகத்தின் அடிப்படையில் விலை உயர்ந்ததாக இருக்கலாம். கீழே உள்ள மறுநிகழ்வு மரத்தைப் பாருங்கள். ஃபைப் (4) உடன் தொடங்கும் இடது சப்டிரீ மற்றும் ஃபைப் (4) உடன் தொடங்கும் வலது சப்டிரீ ஆகியவை ஒரே மாதிரியானவை. அவை 3 என்ற அதே முடிவை உருவாக்குகின்றன, ஆனால் ஒரே பணியை இரண்டு முறை செய்கின்றன. N என்பது ஒரு பெரிய எண்ணாக இருந்தால் (எடுத்துக்காட்டு: 500000), மறுநிகழ்வு ஒரு நிரலை மிக மெதுவாகச் செய்யலாம், ஏனெனில் அது ஒரே துணைப் பணியை பல முறை அழைக்கும்.

மறுநிகழ்வு மரம் வட்டமானது

இந்த சிக்கலைத் தவிர்க்க டைனமிக் நிரலாக்கத்தைப் பயன்படுத்தலாம். டைனமிக் புரோகிராமிங்கில், அதே வகையான எதிர்கால பணியைத் தீர்க்க முன்னர் தீர்க்கப்பட்ட துணைப் பணியைப் பயன்படுத்தலாம். அசல் சிக்கலைத் தீர்ப்பதற்கான பணியைக் குறைப்பதற்கான ஒரு வழி இது. முன்னர் தீர்க்கப்பட்ட துணை பணி தீர்வுகளை நாங்கள் சேமித்து வைக்கும் ஒரு வரிசை ஃபைப் [] இருக்கட்டும். ஃபைப் [0] = 0 மற்றும் ஃபைப் [1] = 1. இந்த இரண்டு மதிப்புகளையும் சேமிப்போம். இப்போது, ​​ஃபைப் [2] இன் மதிப்பு என்ன? ஃபைப் [0] = 0 மற்றும் ஃபைப் [1] = 1 ஏற்கனவே சேமிக்கப்பட்டுள்ளதால், நாம் ஃபைப் [2] = ஃபைப் [1] + ஃபைப் [0] என்று சொல்ல வேண்டும். நாம் இழை [3], இழை [4], இழை [5], ……, இழை [n] ஆகியவற்றை ஒரே வழியில் உருவாக்கலாம். அசல் பணி தீர்க்கப்படாத வரை அடுத்த துணைப் பணிகளைப் பெறுவதற்கு முன்னர் தீர்க்கப்பட்ட துணை பணிகள் அழைக்கப்படுகின்றன, இதனால் தேவையற்ற கணக்கீட்டைக் குறைக்கிறது.