சுழற்சியும், தற்சுழற்சியும் | கணினி அறிவியல் - பின்வரும் கேள்விகளுக்கு பதில் அளிக்கவும் | 11th Computer Science : Chapter 8 : Iteration and recursion
கணினி அறிவியல்: நெறிமுறைசார் சிக்கல் தீர்வு
சுழற்சியும், தற்சுழற்சியும்
மதிப்பாய்வு
பகுதி – ஆ
குறு வினாக்கள்
1. மாற்றமிலி என்றால் என்ன?
விடை : மாறிகள் சம்பந்தப்பட்ட ஒரு கோவையிலுள்ள ஒரு மாறிக்கு ஒன்றை மதிப்பிருத்திய
பிறகும், அந்தக் கோவை மாறாமல் அப்படியே இருந்தால் அது மதிப்பிருத்தலின் மாற்றமிலி
என்று அழைக்கப்படுகிறது.
2. மடக்கு மாற்றுமிலியை வரையறுக்கவும்.
விடை : மடக்கின் உடற்பகுதியிலுள்ள மாற்றமிலி மடக்கு மாற்றமிலி என்றழைக்கப்படுகிறது.
3. மாற்றமிலியின் நிலைமையைச் சோதிப்பது
மடக்கு மாற்றமிலியைப் பாதிக்குமா? ஏன்?
விடை : ஆம். பாதிக்கும். ஏனெனில் ஒரு மடக்கு முடியும்போது, மடக்கு மாற்றமிலி உண்மையாக இருக்கும். மேலும், முடிவுறும் நிலைமையும் உண்மையாக
இருக்கும்.
4. மடக்கு மாற்றமிலிக்கும்,
மடக்கு நிலைமைக்கும்,
உள்ளீட்டு வெளீயீட்டு தொடர்புக்கும் என்ன உறவு?
விடை :
(i) மடக்கு முடியும்
போது அதின் முடிவு நிபந்தனையும், மடக்கு மாற்றமிலியும் சேர்ந்து உள்ளீட்டு - வெளியீட்டு உறவை மெய்யாக்க வேண்டும்.
(ii) தற்சுழற்சிப் படியில், தற்சுழற்சி அழைப்புக்கான உள்ளீட்டின் அளவு கொடுக்கப்பட்ட உள்ளீட்டின்
அளவைவிட கண்டிப்பாகச் சிறியதாக இருக்க வேண்டும்.
5. தற்சுழற்சி முறையில் சிக்கலைத் தீர்ப்பது
என்றால் என்ன?
விடை : ஒவ்வொரு தீர்ப்பானும் தான் பெறும் உள்ளீட்டின் அளவை சோதித்தறிய வேண்டும். அந்த உள்ளீட்டின் அளவு போதுமான
அளவுக்குச் சிறியதாக இருந்தால், தீர்ப்பான் சிக்கலுக்கான தீர்வை நேரடியாக வெளியிட வேண்டும். உள்ளீட்டின் அளவு போதுமான அளவுக்குச்
சிறியதாக இல்லையென்றால், தீர்ப்பான் உள்ளீட்டின் அளவைக் குறைத்து, குறைக்கப்பட்ட உள்ளீட்டைவைத்து
சிக்கலைத் தீர்க்குமாறு ஒரு துணைத்தீர்ப்பானை அழைக்க வேண்டும்.
6. இயல் எண்ணின் தொடர் பெருக்கத்தை
தற்சுழற்ச்சி முறையில் வரையறுக்கவும்.
விடை :
factorial(n)
----உள்ளீடு : n
----வெளியீடு : factorial of n
if n = 0 - அடிப்படை நிலை
1
else
n* factorial (n-1) - தற்சுழற்சி நிலை.
பகுதி - இ
சிறு வினாக்கள்
1. ஒரு மேஜையில்
7 குவளைகள் தலைகீழாக இருக்கின்றன.
எந்த இரண்டு குவளைகளையும் நீங்கள் ஒரே நேரத்தில் திருப்புவதற்கு
உங்களுக்கு அனுமதி உண்டு. எல்லாக்
குவளைகளும் நேராக இருக்கக்கூடிய நிலையை எட்டுவது சாத்தியமா?
(குறிப்பு: தலைகீழாக
இருக்கும் குவளைகளுடைய எண்ணிக்கையின் சமநிலை மாறாது)
விடை :
u என்பது தலைகீழாக
இருக்கும் குவளைகளுடைய எண்ணிக்கையை குறிப்பது என்க.
மாதிரி :
(i) இரண்டு குவளைகள்
நேராக இருக்கலாம். திருப்பிய பிறகு u இரண்டு அதிகரிக்கிறது
(ii) இரண்டு குவளைகள் தலைகீழாக இருக்கலாம் திருப்பிய பிறகு u இரண்டு குறைகிறது.
(iii) ஒரு குவளை நேராகவும் மற்றது தலைகீழாகவும் இருந்தால் u மாற்றுவதில்லை.
ஆகையால் ஒவ்வொரு சுற்றிலும் u இரண்டு அதிகரிக்கிறது அல்லது இரண்டு
குறைகிறது அல்லது மாறுவதில்லை.
மாறுவதில்லை என்ற நிலையை தவிர்த்து விடலாம்
இப்பொழுது
u: = u + 2
அல்லது
u: = u - 2
ஒவ்வொரு நிலையிலும் u வின் சமநிலை மாறாது. தொடக்கத்தில் u ஒற்றைப் படையாக இருப்பின், கடைசி வரை ஒற்றைப் படையாகவே இருக்கும். இரட்டைப்படையாக இருப்பின், கடைசி வரை இரட்டைப் படையாகவே இருக்கும்
இந்த மாற்றமிலியை நாம் தொடக்க நிலையில் வரையறுக்க வேண்டும். u பூச்சியமாக வேண்டும் என்பதே இறுதி
தேவையாகும். u-வின் சமநிலை இரட்டைப் படையாக இருந்தால் மட்டுமே இது சாத்தியம்.
எனவே தொடக்கத்தில் தலைகீழாக இருக்கும் குவளைகளின்
எண்ணிக்கை இரட்டைப் படையாக இருந்தால் மட்டுமே எல்லா குவளைகளும் நேராக இருக்கக் கூடிய
நிலையை எட்டுவது சாத்தியமாகும்.
2. தோற்றால் வெளியேறிவிட வேண்டும் என்ற
நிபந்தனையுள்ள ஒரு விளையாட்டு போட்டியில் வரிசையாக போட்டிகள் நடக்கின்றன.
ஒவ்வொரு போட்டியிலும் இரண்டு விளையாட்டு வீரர்கள்
போட்டியிடுகிறார்கள் தோற்றவர் வெளியேறிவிட வேண்டும்
(அதாவது, அதற்குப்பின்
அவர் எந்தப் போட்டியிலும் பங்கெடுக்கமாட்டார்). வெற்றிபெற்றவர்
தெடர்ந்து போட்டியில் பங்கெடுப்பார். எல்லா
விளையாட்டு வீர்ர்களும் இவ்வாறு வெளியேற்றப்பட்டபின்,
கடைசியில் எஞ்சியிருக்கும் வீரரே போட்டியில் வெற்றிபெற்றவர்.
ஒரு விளையாட்டுப் போட்டியில்
1234 வீரர்கள் இருக்கிறார்கள் என்று வைத்துக்கொள்வோம்.
வெற்றிவீரரைத் தீர்மானிப்பதற்கு எத்தனை போட்டிகள்
நடத்தப்பட வேண்டும்?
விடை : Knockout tournament
1 2 3 4 விளையாட்டு வீரர்கள்
ஒவ்வொரு சுற்றின் முடிவில் ஒருவர் வெளியேற வேண்டும்
n = மிதமுள்ள விளையாட்டு
வீரர்கள்
r = மொத்தம் உள்ள
சுற்று
k = நடந்த சுற்றுகள் n இரட்டை என்க
n, r: = n-k, r+k
n+r மாற்றமலி
வெற்றியாளர் தேர்ந்தெடுத்தால் n = 1
முதலில் n + 1 = 1234 nr - 1233! (make sens=1233)
1233 போட்டிகள் நடத்தப்பட வேண்டும்.
3. மன்னன் விக்கிரமாதித்தனிடம் இரண்டு
மந்திர வாள்கள்
இருக்கின்றன. ஒரு வாளை
வைத்து அவனால் வேதாளத்தின் 19 தலைகளை
வெட்டியெறிய முடியும். ஆனால்,
அதன்பின் வேதாளத்துக்கு
13 தலைகள் முளைக்கின்றன.
இன்னொரு வாளை வைத்து
7 தலைகளை வெட்டியெறிய முடியும்.
ஆனால், அதற்குப்பின்
22 புதிய தலைகள் முளைக்கின்றன.
எல்லாத் தலைகளையும் வெட்டிவிட்டால்,
வேதாளம் செத்துவிடும்.
வேதாளத்துக்கு ஆரம்பத்தில்
1000 தலைகள் இருந்தால், அது
சாகிற வாய்ப்பு உண்டா ? (சகுறிப்பு:
தலை mod 3
-ன் எண்ணிக்கை மாறாது).
விடை :
u என்பது வேதாளத்தின்
தலைகளின் எண்ணிக்கையை குறிப்பது என்க.
மாதிரி :
முதல் வாளை பயன்படுத்தினால்
u: = u – 19 + 13 = u - 6
(ii) இரண்டாவது வாளை பயன்படுத்தினால்
u: = u -7 + 22 = u + 15
ஆனால் ஒவ்வொரு சுற்றிலும் u வை 3ஆல் வகுத்தால் கிடைக்கும் மீதி
சமமாகும். எந்த எண்ணையும் 3 ஆல் வகுத்தால் கிடைக்கும் மீதி 0 அல்லது 1 அல்லது 2 ஆகும். u பூச்சியமாகவேண்டும் என்பது இறுதி
தேவையாகும் ஆகையால் தொடக்கத்தில் u மூன்றால் வகுபடும். எண்ணாக இருந்தால் மட்டுமே இது சாத்தியமாகும் (ஏனெனில் பூச்சியம் 3ஆல் வகுபடும் எண்).
பகுதி - ஈ
நெடுவினாக்கள்
1. வழக்கமான நிறமுடைய
8 × 8 அளவிலான ஒரு சதுரங்கப்பலகையை எடுத்துக் கொள்ளுங்கள்.
குறுக்குவரிசை மற்றும் நேர்வரிசையின் எல்லாக் கட்டங்களுக்கும்
வேறு நிறமிட்டு அவைகளின் நிறத்தை மாற்றிவிடுவோம். திரும்பத்திரும்ப
வேறு நிறமிடலாம். இப்படிச்
செய்வதால், கடைசியில்
ஒரேவொரு கருப்புக் கட்டம் மட்டுமே வர வேண்டும் என்பதே இலக்கு.
இந்த இலக்கை அடைய முடியாது என்று நிருப்பிக்கவும்
[குறிப்பு:
ஒரு குறுக்கு வரிசையில் அல்லது நேர்வரிசையில் என்ற
கருப்புக் கட்டங்கள் இருந்தால். அது
|(8 - b) - b| என்று மாறுகிறது.
விடை :
கருப்பு சதுரங்களின் எண்ணிக்கை B மற்றும் வெள்ளை சதுரங்கள் W ஆக இருக்கும்.
கருப்பு சதுரங்கள் மற்றும் வெள்ளை சதுரங்களுடனான
மாதிரி வரிசை/நெடுவரிசை என எடுத்துக் கொள்வோம்.
இந்த கட்டுப்பாடுகளால் B,W மற்றும் (bw) சாத்தியமான மதிப்புகளாகும்.
bw(b-w)
0 8 -8
1 7 -6
2 6 -4
3 5 -2
4 4 0
5 3 2
6 2 4
7 1 6
8 0 8
(bw) ன் மதிப்பு இந்த அட்டவணையில் இருந்து தெளிவாக தெரிகிறது.
BW என்பது ஒற்றைப்படை
மற்றும் (bw) = 2 K -1 என்பது ஒரு முழு எண்.
தீர்வு காணல் :
b + w = 8
b – w = 2K - 1
(1) மற்றும் (2) னை கூட்ட
(1) + (2) => 2b = 8 + 2 K - 1
b = (4 + K - 0.5) => ஒரு முழு எண் அல்ல, இது உண்மை அல்ல.
எனவே வேறுபாடு = (bw) என இருக்கும்.
சதுரங்க இருப்பு B மற்றும் கருப்பு வெள்ளை சதுரங்களைக்
கொண்டிருக்கும்.
W வெள்ளை சதுரம்
கருப்பு மற்றும் கருப்பு சதுரம் வெள்ளை மாறும்.
B – W + b எனில்
W + வேறுபாடு
எனவே B என அதிகரிக்கும் அல்லது குறைந்துவிடும் பலகை.
எனவே இலக்கை அடைய முடியாது.
2. Power தற்சுழற்சியை பின்வருமாறு வரையறுக்கலாம்.
இந்த வரையறையைப் பயன்படுத்தி தற்சுழற்சி நெறிமுறையை உருவாக்கவும்.
a10 யைக் கணக்கிட எத்தனை முறை பெருக்க
வேண்டும்?
விடை :
Power (a,n)
-- inputs n is an integer, n ≥ 0
-- outputs : an
if n = 0 -- base case
1
else
if (n%2! = 0) -- recursion step in case of
odd
a × power (a, n -1)
else
a × power (a, n/2) --- recursion step in case
of even.
3. 2n × 2n சதுர
அளவைக் கொண்ட ஒரு சதுர மூலை மூடப்பட்ட அட்டையில், ஒரு
மூளைச் சதுரம் ஒரு தனிச் சதுர ஒட்டினால் மூடப்பட்டிருக்கிறது. ஒன்றின்மேல் ஒன்று இல்லாமல்
முக்கோண ஒட்டு அட்டையை மூட முடியும் என்பதை காண்பிக்க.
விடை : சிக்கலின் அளவு n (அளவு 2n × 2n) ஆகும். மறுநிகழ்வு மூலம் சிக்கலை தீர்க்க முடியும். அடிப்படை வழக்கு n = 1. இது 2 × 2 மூலையால் மூடப்பட்ட பலகை. நாம் அதை ஒரு ட்ரையோமினோ மூலம் மூடி, சிக்கலை தீர்க்கலாம். மறுநிகழ்வு படியில், 2n × 2n அளவுள்ள மூலையால் மூடப்பட்ட பலகையை 4 துணைப் பலகைகளாகப் பிரிக்கவும், ஒவ்வொன்றும் 2n −l × 2n−l அளவு, பலகையின் மையத்தின் வழியாக கிடைமட்ட மற்றும் செங்குத்து கோடுகளை வரையவும். இடதுபுறம் உள்ள பலகையில் காட்டப்பட்டுள்ளபடி, முழு பலகையின் மையத்தில் ஒரு ட்ரையோமினோவை வைக்கவும். இப்போது, எங்களிடம் நான்கு மூலைகளால் மூடப்பட்ட பலகைகள் உள்ளன, ஒவ்வொன்றும் 2n −l × 2n−l அளவு.
எங்களிடம் 4 துணைச் சிக்கல்கள் உள்ளன,
அவற்றின் அளவு கொடுக்கப்பட்ட சிக்கலின் அளவை விட கண்டிப்பாக
சிறியது. ஒவ்வொரு துணைப் பிரச்சனைகளையும் நாம் மீண்டும் மீண்டும் தீர்க்க முடியும்.
ஓடு மூலை_மூடப்பட்ட பலகை அளவு n
n = 1 என்றால் -- அடிப்படை வழக்கு 3 சதுரங்களை ஒரு ட்ரையோமினோ
கொண்டு மூடும்
வேறு --- மறுநிகழ்வுப் படி பலகையை n-1 அளவுள்ள 4 துணைப் பலகைகளாகப் பிரித்து,
பலகையின் மையத்தில் ஒரு ட்ரையோமினோவை வைக்கவும்,
n-1 அளவுள்ள ஒவ்வொரு துணைப் பலகையின் மூலையில்_மூடப்பட்ட சப்-போர்டு டைலையும் விட்டுவிடவும்.
23 × 23 மூலை-மூடப்பட்ட பலகையை மறைப்பதற்கான விளைவாக ஏற்படும் சுழல்நிலை
செயல்முறை விளக்கப்பட்டுள்ளது.