പൈത്തണ്‍ : പാഠം ഏഴ്

ആമുഖം

എണ്ണല്‍സംഖ്യകളുടെ ഘടകങ്ങള്‍ എന്ന ആശയത്തെ കഴിഞ്ഞ പാഠത്തില്‍ പരിചയപ്പെട്ടിരുന്നല്ലോ. രണ്ടേരണ്ട് ഘടകങ്ങള്‍ മാത്രമുള്ള അഭാജ്യസംഖ്യകളെ പൈത്തണ്‍ ഉപയോഗിച്ച് തിരിച്ചറിയുന്നത് എങ്ങനെയെന്നും, ഇവയുടെ ഒരു പട്ടിക എങ്ങനെ ഉണ്ടാക്കാമെന്നതും കഴിഞ്ഞ പാഠത്തില്‍ നാം കണ്ടു. ഈ പാഠത്തില്‍ ഘടകങ്ങളെപ്പറ്റി കൂടുതല്‍ ചില കാര്യങ്ങള്‍ നമുക്ക് കാണാം. ഇതോടൊപ്പം പൈത്തണിലെ ബലവത്തായ ഒരു ഉപാധിയെ പരിചയപ്പെടുകയും ചെയ്യാം.

ഘടകങ്ങളും പൊതുഘടകങ്ങളും

കഴിഞ്ഞ പാഠത്തില്‍ ഘടകങ്ങളെ പരിചയപ്പെട്ടത് മറന്നുപോയെങ്കില്‍: 16-നെ 16 = 1 x 16 = 2 x 8 = 4 x 4 എന്നിങ്ങനെ ഗുണിതങ്ങളായി എഴുതാമല്ലോ. 1, 2, 4, 8, 16 എന്നിവയെ 16-ന്റെ ഘടകങ്ങള്‍ (factors) എന്ന് വിളിക്കുന്നു. ഇതുപോലെ 21-നെ 21 = 1 x 21 = 3 x 7 എന്നിങ്ങനെ എഴുതാം; 1, 3, 7, 21 എന്നിവയാണ് 21-ന്റെ ഘടകങ്ങള്‍. ഏത് എണ്ണല്‍സംഖ്യയുടെയും ഘടകമായി 1-ഉം ആ സംഖ്യതന്നെയും ഉണ്ടാവും എന്ന് കുറച്ചൊന്നാലോചിച്ചാല്‍ മനസ്സിലാകും — 1-നെ അതിനോടുതന്നെ പല പ്രാവശ്യം കൂട്ടി ഏത് എണ്ണല്‍സംഖ്യയിലും എത്തിക്കാം; ഏത് എണ്ണല്‍സംഖ്യയും "ഒരു പ്രാവശ്യം കൂട്ടിയാല്‍" ആ സംഖ്യതന്നെയാണുതാനും.

രണ്ട് സംഖ്യകള്‍ക്ക് പൊതുവായുള്ള ഘടകങ്ങളെ അവയുടെ പൊതുഘടകങ്ങള്‍ (common factors) എന്ന് വിളിക്കുന്നു. ഏതു രണ്ട് എണ്ണല്‍സംഖ്യകളെടുത്താലും അവയ്ക്ക് പൊതുവായി ഒരു ഘടകമെങ്കിലും ഉണ്ടാവും (എന്തുകൊണ്ട്?). ചില സംഖ്യാജോടികള്‍ക്ക് ഏറെ പൊതുഘടകങ്ങള്‍ കാണും. മറ്റു ചിലവയ്ക്ക് വളരെ കുറച്ച് പൊതുഘടകങ്ങളേ കാണൂ. ചില ഉദാഹരണങ്ങള്‍ ഇതാ:

പൊതു ഘടകങ്ങള്‍

ആദ്യത്തെ സംഖ്യ	രണ്ടാമത്തെ സംഖ്യ	ആദ്യത്തെ സംഖ്യയുടെ ഘടകങ്ങള്‍	രണ്ടാമത്തെ സംഖ്യയുടെ ഘടകങ്ങള്‍	പൊതു ഘടകങ്ങള്‍
36	16	1, 2, 3, 4, 6, 9, 12, 18, 36	1, 2, 4, 8, 16	1, 2, 4
78	24	1, 2, 3, 6, 13, 26, 39, 78	1, 2, 3, 4, 6, 8, 12, 24	1, 2, 3, 6
120	35581	1, 2, 3, 4, 5, 6, 8, 10, 12, 15, 20, 24, 30, 40, 60, 120	1, 7, 13, 17, 23, 91, 119, 161, 221, 299, 391, 1547, 2093, 2737, 5083, 35581	1
48	210	1, 2, 3, 4, 6, 8, 12, 16, 24, 48	1, 2, 3, 5, 6, 7, 10, 14, 15, 21, 30, 35, 42, 70, 105, 210	1, 2, 3, 6
402	245	1, 2, 3, 6, 67, 134, 201, 402	1, 5, 7, 35, 49, 245	1

ലിസ്റ്റുകളെപ്പറ്റി രണ്ടുകാര്യങ്ങള്‍

കഴിഞ്ഞ പാഠത്തില്‍ for, range() എന്നിവയോടനുബന്ധിച്ച് നാം ലിസ്റ്റുകളെ പരിചയപ്പെട്ടിരുന്നല്ലോ? അവിടെ സൂചിപ്പിച്ചതുപോലെ പൈത്തണ്‍ ഉപയോഗിച്ച് പ്രോഗ്രാമുകള്‍ എഴുതുമ്പോള്‍ വളരെയധികം ഉപയോഗപ്പെടുന്ന ഒന്നാണ് ലിസ്റ്റ്. ലിസ്റ്റുകളെ കൈകാര്യം ചെയ്യുവാനുള്ള ഒട്ടേറെ ഉപാധികള്‍ പൈത്തണില്‍ ലഭ്യമാണ്. ഇവയില്‍ ലളിതമായ രണ്ട് ഉപാധികളെ ഈ പാഠത്തില്‍ നമുക്ക് പരിചയപ്പെടാം.

ആദ്യമായി നമ്മുടെ കൈയ്യിലുള്ള ഒരു ലിസ്റ്റില്‍ പുതിയ അംഗങ്ങളെ ചേര്‍ക്കുന്നതെങ്ങനെ എന്ന് നോക്കാം. ഒരു ലിസ്റ്റിലേക്ക് പുതിയ അംഗങ്ങളെ ചേര്‍ക്കാനുള്ള ഏറ്റവും ലളിതമായ വഴി ആ ലിസ്റ്റിന്റെ append() എന്ന ഏകദം ഉപയോഗിക്കുക എന്നതാണ്. കേള്‍ക്കുന്നയത്ര പ്രയാസമുള്ള കാര്യമല്ല ഇത്; താഴെക്കാണുന്ന ചെറിയ പ്രോഗ്രാമുകള്‍ പരീക്ഷിച്ചുനോക്കൂ:






ലിസ്റ്റിലേക്ക് ആളെക്കൂട്ടുന്ന വഴി മനസ്സിലായല്ലോ? myList എന്ന ലിസ്റ്റിലേക്ക് new_item എന്ന വസ്തു ചേര്‍ക്കാനായി myList.append(new_item) എന്ന് പ്രയോഗിക്കുക. ഇവിടെ new_item എന്നത് 5, "name" എന്നിങ്ങനെയുള്ള മൂല്യങ്ങളോ number, name എന്നിങ്ങനെ ചരങ്ങളോ ആകാം; ചരമാണെങ്കില്‍ അതിന്റെ വിലയാവും ലിസ്റ്റില്‍ കയറിക്കൂടുന്നത്.

പ്രവര്‍ത്തനങ്ങള്‍

പ്രവ. 1.

ഒരു എണ്ണല്‍സംഖ്യ ഇന്‍പുട്ട് ആയി എടുത്ത്, ആ സംഖ്യയുടെ ഘടകങ്ങളുടെ ഒരു ലിസ്റ്റ് ഔട്പുട്ട് ആയി തരുന്ന പ്രോഗ്രാം എഴുതുക. പ്രോഗ്രാമിന്റെ പ്രവര്‍ത്തനഫലം താഴെക്കാണുന്ന ചിത്രത്തിലെപ്പോലെ ആയിരിക്കണം (കുറച്ചുകൂടെ വ്യക്തമായ ചിത്രം കാണാന്‍ ഈ ചിത്രത്തില്‍ അമര്‍ത്തുക). ഇവിടെ ഈ പ്രോഗ്രാം മൂന്നു തവണ പ്രവര്‍ത്തിപ്പിച്ചിരിക്കുന്നു (IDLE-ല്‍ F5 മൂന്നു തവണ അമര്‍ത്തിയിരിക്കുന്നു).

പ്രവ. 2.

രണ്ട് എണ്ണല്‍സംഖ്യകള്‍ ഇന്‍പുട്ട് ആയി എടുത്ത്, ഈ സംഖ്യകളുടെ പൊതു ഘടകങ്ങളുടെ ഒരു ലിസ്റ്റ് ഔട്പുട്ട് ആയി തരുന്ന പ്രോഗ്രാം എഴുതുക. പ്രോഗ്രാമിന്റെ പ്രവര്‍ത്തനഫലം താഴെക്കാണുന്ന ചിത്രത്തിലെപ്പോലെ ആയിരിക്കണം (കുറച്ചുകൂടെ വ്യക്തമായ ചിത്രം കാണാന്‍ ഈ ചിത്രത്തില്‍ അമര്‍ത്തുക). ഇവിടെ ഈ പ്രോഗ്രാം മൂന്നു തവണ പ്രവര്‍ത്തിപ്പിച്ചിരിക്കുന്നു (IDLE-ല്‍ F5 മൂന്നു തവണ അമര്‍ത്തിയിരിക്കുന്നു).

---

ഒരു ലിസ്റ്റിന്റെ നീളം (അതില്‍ എത്ര അംഗങ്ങള്‍ ഉണ്ടെന്നുള്ളത്) കാണാനുള്ള വിദ്യയാണ് അടുത്തത്. ഇതിനുള്ള ലളിതമായ വഴി പൈത്തണിലെ len() എന്ന ഏകദം ഉപയോഗിക്കുക എന്നതാണ്. ഇത് എങ്ങനെയാണ് ചെയ്യുന്നതെന്ന് താഴെക്കാണുന്ന പ്രോഗ്രാമുകള്‍ പരീക്ഷിച്ചാല്‍ മനസ്സിലാകും.





രണ്ടാമത്തെ പ്രോഗ്രാമില്‍ ഒറ്റസംഖ്യകളുടെ എണ്ണം കാണുക മാത്രം ചെയ്യാന്‍ അവയുടെ ഒരു ലിസ്റ്റ് ഉണ്ടാക്കേണ്ട കാര്യമില്ല എന്നത് ശ്രദ്ധിക്കുക: ഒരു ചരത്തില്‍ ഈ എണ്ണം സൂക്ഷിച്ചാല്‍ മാത്രം മതിയാകും. len() എന്ന ഉപാധിയുടെ പ്രയോഗം ഉദാഹരിക്കാന്‍ മാത്രമാണ് ഇവിടെ odd_numbers എന്ന ലിസ്റ്റ് ഉണ്ടാക്കിയത്.

len() ഉപയോഗിച്ച് ലിസ്റ്റുകളുടെ മാത്രമല്ല, string-കളുടെയും നീളം (string-ല്‍ ഉള്ള സ്പേസും മറ്റു ചിഹ്നങ്ങളും ഉള്‍പ്പടെയുള്ള അക്ഷരങ്ങളുടെ എണ്ണം) കാണാം. പ്രയോഗരീതി മുകളിലത്തേതുപോലെ തന്നെ. ഈ സൗകര്യം ഉപയോഗിച്ച് കേരളത്തിലെ ഏത് ജില്ലയുടെ പേരിനാണ് ഇംഗ്ളീഷില്‍ എഴുതിയാല്‍ ഏറ്റവും നീളം എന്ന് കണ്ടുപിടിക്കുന്ന ഒരു പ്രോഗ്രാം ഇതാ:

പ്രവര്‍ത്തനം

പ്രവ. 3.

ഈ ഉദാഹരണങ്ങള്‍ മനസ്സിരുത്തി വായിക്കുക. ഇവ പ്രവര്‍ത്തിക്കുന്നത് എങ്ങനെയാണെന്ന് മനസ്സിലായി എന്ന് ഉറപ്പുവരുത്തുക. പ്രത്യേകിച്ച് മൂന്നാമത്തെ ഉദാഹരണത്തിന്റെ 13 മുതല്‍ 19 വരെയുള്ള വരികളില്‍ എന്താണ് സംഭവിക്കുന്നതെന്ന് കൃത്യമായി മനസ്സിലാക്കുക.

ഉത്തമ സാധാരണ ഘടകം

രണ്ട് പൂര്‍ണ്ണസംഖ്യകളുടെ ഏറ്റവും വലിയ പൊതുഘടകത്തെ അവയുടെ ഉത്തമ സാധാരണ ഘടകം (highest common factor, greatest common divisor) എന്ന് വിളിക്കുന്നു: ചുരുക്കത്തില്‍ ഉസാഘ (hcf, gcd) എന്നും. മുകളിലുള്ള പട്ടികയില്‍നിന്ന് നമുക്ക് കിട്ടുന്ന ഉദാഹരണങ്ങള്‍:

• ഉസാഘ(16, 36) = 4
• ഉസാഘ(78, 24) = 6
• ഉസാഘ(120, 35581) = 1
• ഉസാഘ(210, 48) = 6
• ഉസാഘ(402, 245) = 1

രണ്ട് പൂര്‍ണ്ണസംഖ്യകള്‍ ഇന്‍പുട് ആയി എടുത്ത് അവയുടെ ഉസാഘ കണ്ടുപിടിക്കുന്ന ഒരു പ്രോഗ്രാം നമുക്ക് എങ്ങനെ എഴുതാം? മുകളിലെ രണ്ടു പ്രവര്‍ത്തനങ്ങളും ചെയ്താല്‍ ഇതിനുള്ള ആശയം കിട്ടും. ലളിതമായ ഒരു രീതി ഇതാ:

1. ഇന്‍പുട്ട് ആയി കിട്ടിയ സംഖ്യകള്‍ num1, num2 എന്നിവയാണെന്നിരിക്കട്ടെ.
2. 1 മുതല്‍ num1 വരെയുള്ള ഓരോ സംഖ്യയും ക്രമത്തില്‍ num1, num2 എന്നിവ രണ്ടിനേയും നിശ്ശേഷം ഹരിക്കുന്നുണ്ടോ എന്ന് നോക്കുക.
3. ഇങ്ങനെ രണ്ടിനേയും ഹരിക്കുന്ന സംഖ്യ കാണുമ്പോള്‍ അത് ഒരു ചരത്തില്‍ (ഇതിനെ നമുക്ക് gcd എന്ന് വിളിക്കാം) സൂക്ഷിച്ചുവെക്കുക.
4. gcd-ന്റെ അവസാനമുള്ള വിലയാണ് num1, num2 എന്നിവയുടെ ഉസാഘ.

(ഇവിടെ ലിസ്റ്റ് ഉപയോഗിക്കേണ്ട ആവശ്യം ഇല്ല എന്നത് ശ്രദ്ധിക്കുക.)

പ്രവര്‍ത്തനങ്ങള്‍

പ്രവ. 4.

രണ്ട് സംഖ്യകളുടെ ഉസാഘ കണ്ടുപിടിക്കാന്‍ മുകളില്‍ കൊടുത്ത രീതി ശരിയാകുന്നത് എന്തുകൊണ്ടാണെന്ന് ആലോചിച്ച് മനസ്സിലാക്കുക.

പ്രവ. 5.

രണ്ട് എണ്ണല്‍സംഖ്യകള്‍ ഇന്‍പുട്ട് ആയി എടുത്ത്, ഈ സംഖ്യകളുടെ ഉസാഘ കണ്ടുപിടിക്കുന്ന പ്രോഗ്രാം മുകളില്‍ കൊടുത്ത രീതിയില്‍ എഴുതുക. പ്രോഗ്രാമിന്റെ പ്രവര്‍ത്തനഫലം താഴെക്കാണുന്ന ചിത്രത്തിലെപ്പോലെ ആയിരിക്കണം (കുറച്ചുകൂടെ വ്യക്തമായ ചിത്രം കാണാന്‍ ഈ ചിത്രത്തില്‍ അമര്‍ത്തുക). ഇവിടെ ഈ പ്രോഗ്രാം നാലു തവണ പ്രവര്‍ത്തിപ്പിച്ചിരിക്കുന്നു (IDLE-ല്‍ F5 നാലു തവണ അമര്‍ത്തിയിരിക്കുന്നു).

യൂക്ളിഡിന്റെ അല്‍ഗോരിതം

ഉസാഘ കണ്ടുപിടിക്കാന്‍ മുകളില്‍ വിവരിച്ച രീതി — രണ്ട് സംഖ്യകളെയും നിശ്ശേഷം ഹരിക്കുന്ന സംഖ്യകള്‍ എല്ലാം കണ്ടുപിടിച്ച് ഇവയില്‍വച്ച് ഏറ്റവും വലുത് ഉത്തരമായി നല്‍കുക എന്നത് — തികച്ചും ശരിയായ രീതി തന്നെയാണ്. ഉസാഘയുടെ നിര്‍വചനത്തിനോട് ഏറെ അടുത്തുനില്‍ക്കുന്ന രീതിയുമാണിത്. എന്നാല്‍ ഈ രീതിക്ക് ഒരു വലിയ പരിമിതിയുണ്ട്. അതെന്താണെന്നറിയാന്‍ പ്രവ. 4-ല്‍ എഴുതിയ പ്രോഗ്രാമിന് താഴെപ്പറയുന്ന ജോടികള്‍ ഇന്‍പുട്ട് ആയി കൊടുക്കുക (മുന്നറിയിപ്പ്: കംപ്യൂട്ടറില്‍ തുറന്നിരിക്കുന്ന പ്രമാണങ്ങളൊക്കെ സേവ് ചെയ്തതിനുശേഷം മാത്രം ഇത് പരീക്ഷിക്കുക) :

1. 287503, 646609
2. 4143937, 6487923
3. 55596155, 73187552

ഈ രീതിയുടെ പരിമിതി എന്താണെന്ന് മനസ്സിലായല്ലോ? ഇന്‍പുട് സംഖ്യകള്‍ വലുതാകുന്തോറും പ്രോഗ്രാം പൂര്‍ത്തിയാകാനെടുക്കുന്ന സമയവും ആനുപാതികമായി കൂടുന്നു. (സംഖ്യകളുടെ വലുപ്പം കുറച്ച് കൂടുമ്പോഴേക്കും ചിലപ്പോള്‍ കംപ്യൂട്ടര്‍ നിശ്ചലമായി എന്നും വരാം; ഇത് നാം ഉപയോഗിക്കുന്ന range() എന്ന ഏകദത്തിന്റെ പ്രവര്‍ത്തനരീതി കാരണമാണ്. range()-നു പകരം xrange() എന്ന് പ്രയോഗിച്ചാല്‍ ഈ പ്രശ്നം ഒഴിവാക്കാം. ഇപ്പോള്‍ കൂടുതല്‍ വിശദീകരിക്കുന്നില്ല.). ഇതു തന്നെയാണ് ഈ രീതിയുടെ വലിയ പരിമിതിയും. കുറച്ചൊന്നാലോചിച്ചാല്‍ ഇങ്ങനെ സംഭവിക്കുന്നത് എന്തുകൊണ്ടാണെന്ന് നമുക്ക് മനസ്സിലാക്കാം. തന്നിരിക്കുന്ന സംഖ്യകളിലൊന്നിന്റെ ഓരോ ഘടകത്തിനെക്കൊണ്ടും മറ്റേ സംഖ്യയെ ഹരിച്ചുനോക്കുക എന്നതാണല്ലോ ഇവിടെ ചെയ്യുന്നത്? ഇതിനായി ഒന്നു മുതല്‍ ആദ്യത്തെ സംഖ്യ വരെയുള്ള എല്ലാ സംഖ്യകളെക്കൊണ്ടും ആദ്യത്തെ സംഖ്യയെ ഹരിച്ചു നോക്കുന്നു. ആദ്യത്തെ സംഖ്യ വലുതാകുന്തോറും പ്രോഗ്രാം പ്രവര്‍ത്തിക്കാനെടുക്കുന്ന സമയം ആനുപാതികമായി കൂടുന്നത് ഇതുകൊണ്ടാണ്.

ഈ പരിമിതി ഒഴിവാക്കാനാകുന്നതാണോ? ഉസാഘയുടെ നിര്‍വചനത്തെ അതേപടി പകര്‍ത്തുകയാണ് ഈ രീതി ചെയ്യുന്നത്: ആദ്യത്തെ സംഖ്യയുടെ ഘടകങ്ങളില്‍വച്ച് രണ്ടാമത്തെ സംഖ്യയുടെ ഏറ്റവും വലിയ ഘടകത്തെ കണ്ടുപിടിക്കുക എന്നതാണ് ഇവിടെ സംഭവിക്കുന്നത്. ഇതുതന്നെയാണല്ലോ ഉസാഘയുടെ നിര്‍വചനവും? അങ്ങനെയിരിക്കെ ഇതിലും വേഗത്തില്‍ എങ്ങനെ ഈ പ്രശ്നത്തിന് ഉത്തരം കാണാന്‍ കഴിയും? ഇത് സാധ്യമല്ല എന്ന് ന്യായമായും സംശയിക്കാം.

ഇതിലും മികച്ച — താരതമ്യേന വളരെ കുറച്ച് സമയം മാത്രമെടുക്കുന്ന — രീതികള്‍ നിലവിലുണ്ട് എന്നതാണ് അത്ഭുതകരമായ വസ്തുത. ഇവയില്‍ ഏറ്റവും പ്രശസ്തമായ രീതിക്ക് രണ്ടായിരത്തിമുന്നൂറിലേറെ വര്‍ഷം പഴക്കമുണ്ട് എന്നതും അത്ഭുതകരം തന്നെ. ബി. സി. 300-നോടടുപ്പിച്ച് എഴുതപ്പെട്ട യുക്ളിഡിന്റെ 'എലമെന്റ്സ്' എന്ന പുസ്തകസഞ്ചയത്തില്‍ രണ്ട് സംഖ്യകളുടെ ഉസാഘ കണ്ടുപിടിക്കാനുള്ള മനോഹരമായ ഒരു രീതി വിവരിച്ചിട്ടുണ്ട്. "യൂക്ളിഡിന്റെ അല്‍ഗോരിതം" എന്ന പേരില്‍ ഈ രീതി പ്രശസ്തമാണ്. "അല്‍ഗോരിതം" എന്നതിന് "പ്രശ്നപരിഹാരത്തിനുള്ള വഴി" എന്ന് ഏകദേശം അര്‍ത്ഥം പറയാം. ഇനി നമുക്ക് യൂക്ളിഡിന്റെ അല്‍ഗോരിതം എന്താണെന്ന് മനസ്സിലാക്കാന്‍ ശ്രമിക്കാം.

യൂക്ളിഡിന്റെ അല്‍ഗോരിതത്തിന്റെ അടിസ്ഥാനം ഇതാണ്: a, b എന്നീ പൂര്‍ണ്ണസംഖ്യകളുടെ ഉസാഘ കണ്ടുപിടിക്കണമെന്ന് കരുതുക.

1. a = b ആണെങ്കില്‍ ഉസാഘ (a, b) = a. (എന്തുകൊണ്ട്?)
ഇനി a < b ആണെന്ന് കരുതുക (b < a ആണെങ്കില്‍ ഇനിയുള്ള വാദങ്ങളില്‍ aയും bയും തലതിരിച്ചിട്ടാല്‍ മതി.).
2. b-യെ a കൊണ്ട് ഹരിച്ചാല്‍ ശിഷ്ടം പൂജ്യമാണെങ്കില്‍ ഉസാഘ (a, b) = a. (എന്തുകൊണ്ട്?)
3. b-യെ a കൊണ്ട് ഹരിച്ചാല്‍ ശിഷ്ടം r എന്ന അധിസംഖ്യയാണെന്ന് കരുതുക. ഇങ്ങനെയാണെങ്കില്‍ ഉസാഘ(a, b) = ഉസാഘ(r, a).

ഇവയില്‍ ആദ്യത്തെ രണ്ട് കാര്യങ്ങളും ശരിയാണെന്ന് കാണാന്‍ വലിയ പ്രയാസമില്ല (ആലോചിച്ചുനോക്കൂ). മൂന്നാമത്തെ കാര്യം ശരിയാണോ എന്നത് ഒറ്റനോട്ടത്തില്‍ വ്യക്തമല്ല. ഇത് എന്തുകൊണ്ട് ശരിയാകുന്നു എന്ന് നമുക്കൊന്നു നോക്കാം.

മൂന്നാമത്തെ പിരിവില്‍ b-യെ a കൊണ്ട് ഹരിച്ചാല്‍ ശിഷ്ടം r എന്ന അധിസംഖ്യയാണല്ലോ? അപ്പോള്‍ b = ma + r എന്ന് എഴുതാന്‍ കഴിയുന്ന m എന്ന ഒരു അധിസംഖ്യ നിലവിലുണ്ട് : b-യെ a കൊണ്ട് ഹരിച്ചാല്‍ കിട്ടുന്ന ഉത്തരത്തിന്റെ പൂര്‍ണ്ണസംഖ്യാഭാഗമാണ് m. ഈ സമവാക്യത്തെ നമുക്ക് r = b - ma എന്നൊന്ന് മാറ്റി എഴുതാം.

a, b എന്നിവ രണ്ടിന്റേയും ഘടകമാണ് f എന്ന് കരുതുക. അപ്പോള്‍ a = pf, b = qf എന്നിങ്ങനെ എഴുതാവുന്ന p,q എന്ന രണ്ട് അധിസംഖ്യകള്‍ ഉണ്ട്. അതുകൊണ്ട് r = b - ma = qf - mpf = f(q - mp). ഇതില്‍നിന്ന് f എന്നത് r-ന്റെയും ഘടകമാണ് എന്ന് കിട്ടുന്നു. അതുകൊണ്ട് r, a എന്നിവ രണ്ടിന്റേയും ഘടകമാണ് f എന്ന് വരുന്നു.

ഇനി r, a എന്നിവ രണ്ടിന്റേയും ഘടകമാണ് g എന്ന് കരുതുക. അപ്പോള്‍ r = sg, a = tg എന്നിങ്ങനെ എഴുതാവുന്ന s,t എന്ന രണ്ട് അധിസംഖ്യകള്‍ ഉണ്ട്. അതുകൊണ്ട് b = ma + r = mtg + sg = g (mt + s). ഇതില്‍നിന്ന് g എന്നത് b-യുടെയും ഘടകമാണ് എന്ന് കിട്ടുന്നു. അതുകൊണ്ട് a,b എന്നിവ രണ്ടിന്റേയും ഘടകമാണ് g എന്ന് വരുന്നു.

ഇപ്പറഞ്ഞതില്‍നിന്ന് നമുക്ക് കിട്ടുന്നത്: a, b എന്നിവയുടെ ഏത് പൊതുഘടകവും r, a എന്നിവയുടെകൂടി പൊതുഘടകമാണ്. മറിച്ച് r, a എന്നിവയുടെ ഏത് പൊതുഘടകവും a, b എന്നിവയുടെ പൊതുഘടകവുമാണ്. അതുകൊണ്ട് a, b എന്നിവയുടെ പൊതുഘടകങ്ങള്‍ തന്നെയാണ് r, a എന്നിവയുടെ പൊതുഘടകങ്ങളും. a, b എന്നിവയുടെ ഏറ്റവും വലിയ പൊതുഘടകവും r, a എന്നിവയുടെ ഏറ്റവും വലിയ പൊതുഘടകവും ഒന്നുതന്നെയാണെന്ന് ഇതില്‍നിന്ന് വ്യക്തം. അതായത് ഉസാഘ(a,b) = ഉസാഘ(r, a).

അപ്പോള്‍ മുകളിലുള്ള മൂന്നാമത്തെ പിരിവും ശരിയാണ്. യൂക്ളിഡിന്റെ അല്‍ഗോരിതവും ഇതുതന്നെയാണ്: a, b എന്നീ സംഖ്യകളുടെ ഉസാഘ കാണാന്‍:

യൂക്ളിഡിന്റെ അല്‍ഗോരിതം

1. a = b ആണെങ്കില്‍ ഉസാഘ(a, b) = a
2. a < b എങ്കില്‍: b-യെ a കൊണ്ട് ഹരിച്ചാല്‍ കിട്ടുന്ന ശിഷ്ടം കണ്ടുപിടിക്കുക. ഇത് r ആണെന്നിരിക്കട്ടെ.
1. r = 0 ആണെങ്കില്‍ ഉസാഘ(a, b) = a
2. അല്ലെങ്കില്‍ r, a എന്നിവയുടെ ഉസാഘ കണ്ടുപിടിക്കുക; ഇതുതന്നെയാണ് a, b എന്നിവയുടെ ഉസാഘ.
3. അതല്ല a > b ആണെങ്കില്‍: a-യെ b കൊണ്ട് ഹരിച്ചാല്‍ കിട്ടുന്ന ശിഷ്ടം കണ്ടുപിടിക്കുക. ഇത് r ആണെന്നിരിക്കട്ടെ.
1. r = 0 ആണെങ്കില്‍ ഉസാഘ(a, b) = b
2. അല്ലെങ്കില്‍ r, b എന്നിവയുടെ ഉസാഘ കണ്ടുപിടിക്കുക; ഇതുതന്നെയാണ് a, b എന്നിവയുടെ ഉസാഘ.

പ്രവര്‍ത്തനം

പ്രവ. 5.

യൂക്ളിഡിന്റെ അല്‍ഗോരിതം മനസ്സിരുത്തി വായിക്കുക. ഇതിന്റെ പ്രവര്‍ത്തനരീതി മനസ്സിലായി എന്ന് ഉറപ്പുവരുത്താന്‍:

1. a, b എന്നിവയ്ക്ക് പല വിലകള്‍ കൊടുത്ത് ഈ രീതിയില്‍ (കടലാസും പേനയും ഉപയോഗിച്ച്) അവയുടെ ഉസാഘ കാണുക.
2. ഈ പാഠഭാഗത്തിന്റെ ആദ്യം കാണുന്ന മൂന്ന് ജോടി സംഖ്യകളുടെ ഉസാഘയും ഈ രീതി ഉപയോഗിച്ച് കണ്ടുപിടിക്കുക. മൂന്നാമത്തെ ജോടിയുടെ ഉസാഘ കണ്ടുപിടിക്കാന്‍ നിങ്ങളെടുത്ത സമയം കംപ്യൂട്ടര്‍ ഇതു ചെയ്യാന്‍ എടുത്ത സമയവുമായി താരതമ്യം ചെയ്യുക.
3. വളരെ വലിയ സംഖ്യകള്‍ (ഉദാ: പത്തക്ക സംഖ്യകള്‍) ഉള്‍പ്പെടുന്ന ഒരു ഉദാഹരണമെങ്കിലും യൂക്ളിഡിന്റെ രീതി ഉപയോഗിച്ച് ചെയ്തു നോക്കുക.


യൂക്ളിഡിന്റെ അല്‍ഗോരിതത്തെക്കുറിച്ച് ന്യായമായി ഉണ്ടാകാവുന്ന ചില സംശയങ്ങള്‍:



1. ഈ രീതിയില്‍ ഉസാഘ കണ്ടുപിടിക്കാന്‍ നോക്കിയാല്‍ അത് എപ്പോഴെങ്കിലും അവസാനിക്കുമെന്ന് എന്താണുറപ്പ്? ചില ജോടി സംഖ്യകള്‍ക്ക് ഇത് അനന്തമായി നീണ്ടുപോയെങ്കിലോ?
2. ഈ രീതി ശരിയാണോ? ഏതു ജോടി പൂര്‍ണ്ണസംഖ്യകളുടെ ഉസാഘയും ഇതുവഴി കിട്ടുമോ?
3. നാം ഇതിനുമുമ്പ് കണ്ട ലളിതമായ രീതിയെക്കാള്‍ വളരെ വേഗത്തില്‍ യൂക്ളിഡിന്റെ രീതി ഉത്തരം തരുമോ?

ആദ്യത്തെ സംശയത്തിന് പ്രധാന കാരണം ഇതാകാം: ഒരു ജോടി സംഖ്യകളുടെ ഉസാഘ കണ്ടുപിടിക്കാന്‍വേണ്ടി നാം മറ്റൊരു ജോടി സംഖ്യകളുടെ ഉസാഘ കണ്ടുപിടിക്കേണ്ടി വരുന്നു. ഇത് ഇങ്ങനെ അനന്തമായി നീണ്ടുപോയാലോ? ഇങ്ങനെ നീണ്ടുപോകില്ല എന്ന് കാണാന്‍ ഒരു കാര്യം ശ്രദ്ധിച്ചാല്‍ മതി: രണ്ടാമത്തെ ജോടിയിലെ ഒരു സംഖ്യ (r) ആദ്യത്തെ ജോടിയിലെ രണ്ടു സംഖ്യകളെക്കാളും ചെറുതാണ് (എന്തുകൊണ്ട്?). എല്ലാ സംഖ്യകളും അധിസംഖ്യകളുമാണ്. അധിസംഖ്യകളുടെ കുറഞ്ഞുവരുന്ന ഒരു ശ്രേണി അനന്തമായി നീളുകയില്ലല്ലോ? അതുകൊണ്ടുതന്നെ ഈ രീതിയുടെ പ്രവര്‍ത്തനവും അനന്തമായി നീളുകയില്ല.

രണ്ടാമത്തെ സംശയത്തിന്റെ ഉത്തരം നാം മുകളില്‍ കണ്ടുകഴിഞ്ഞു: ഏത് ജോടി പൂര്‍ണ്ണസംഖ്യകളുടെയും ഉസാഘ ഈ രീതിയില്‍ കണ്ടുപിടിക്കാനാകും.

ഈ രീതിയുടെ വേഗത്തെപ്പറ്റി ഒരു ഏകദേശ രൂപം കിട്ടാന്‍ പ്രവര്‍ത്തനം 5 സഹായിക്കും. ഇതുകൂടാതെ നാം പൈത്തണില്‍ ഈ രീതി എഴുതി പ്രവര്‍ത്തിപ്പിച്ച് നോക്കുമ്പോഴും ഇത് നമുക്ക് കൂടുതല്‍ ബോധ്യം വരും. യൂക്ളിഡിന്റെ അല്‍ഗോരിതം ഉസാഘ കണ്ടുപിടിക്കാനായി എത്ര സമയം വരെ എടുക്കാം എന്നതിന് (ഈ സമയം ഇന്‍പുട്ട് ആയി കിട്ടുന്ന സംഖ്യകളെ ആശ്രയിച്ചിരിക്കുന്നു എന്ന് വ്യക്തമാണല്ലോ?) കൃത്യമായ കണക്കുകളുണ്ട്. ഇവിടെ ഇതിനെപ്പറ്റി കൂടുതല്‍ വിശദീകരിക്കുന്നില്ല; ഈ സമയപരിധി ഫിബോനാച്ചി സംഖ്യകളുമായി നേരിട്ട് ബന്ധപ്പെട്ടിരിക്കുന്നു എന്ന അതിശയകരമായ കാര്യം മാത്രം സൂചിപ്പിക്കുന്നു.







യൂക്ളിഡിന്റെ അല്‍ഗോരിതം : പൈത്തണില്‍


ഇനി നമുക്ക് യൂക്ളിഡിന്റെ അല്‍ഗോരിതം പൈത്തണിലേക്ക് മൊഴിമാറ്റം നടത്താന്‍ ശ്രമിക്കാം. ഇതിന് ഒരു തുടക്കമായി ഈ അല്‍ഗോരിതത്തിലെ എളുപ്പമുള്ള ഭാഗങ്ങള്‍ പൈത്തണിലേക്ക് പകര്‍ത്തിനോക്കാം. പറയാനുള്ള സൗകര്യത്തിനായി a, b-യെക്കാള്‍ വലുതല്ല എന്ന് സങ്കല്‍പ്പിക്കാം:



ഈ പ്രോഗ്രാമില്‍ b -യെ a കൊണ്ട് ഹരിച്ചാല്‍ കിട്ടുന്ന r എന്ന ശിഷ്ടം പൂജ്യമാണെങ്കില്‍ നമുക്ക് വേണ്ട ഉസാഘ കിട്ടുന്നു. r പൂജ്യത്തെക്കാള്‍ വലുതാണെങ്കില്‍ r, a എന്നിവയുടെ ഉസാഘ കണ്ടുപിടിക്കണമല്ലോ? ഇതിനുള്ള കോഡ് നാം എഴുതിയിട്ടില്ല എന്നത് ശ്രദ്ധിക്കുക; ഇതിനുപകരം ഇങ്ങനെ ചെയ്യണം എന്ന് നമ്മെത്തന്നെ ഓര്‍മ്മിപ്പിക്കാനുള്ള ഒരു കമന്റ് മാത്രം യഥാസ്ഥാനത്ത് എഴുതിയിട്ടുണ്ട്.

ഈ കോഡ് നമുക്ക് എങ്ങനെ എഴുതാം? ഇത് മനസ്സിലാക്കാനായി പ്രവര്‍ത്തനം 5-ല്‍ ഈ ഭാഗം എങ്ങനെയാണ് ചെയ്തതെന്ന് ആലോചിച്ചു നോക്കുക. തുടക്കത്തില്‍ കൊടുത്ത a, b എന്നിവയ്ക്ക് പകരം r, a എന്നീ വിലകള്‍ പകരം വെച്ച് ആദ്യം മുതല്‍ ചെയ്താല്‍ മതിയാകും: കടലാസും പേനയും ഉപയോഗിച്ച് ചെയ്തപ്പോഴും ഇങ്ങനെയാണല്ലോ ചെയ്തത്? ഇങ്ങനെ രണ്ടാമതും ചെയ്യുമ്പോള്‍ a == b ആവുകയില്ലല്ലോ (എന്തുകൊണ്ട്?) അതുകൊണ്ട് ഇക്കാര്യം പരിശോധിക്കുന്ന വരി ഒഴിവാക്കാം. ഇങ്ങനെ ഒന്നുകൂടി വിസ്തരിച്ചെഴുതിയ പ്രോഗ്രാം ഇതാ:




ഈ പ്രോഗ്രാമില്‍ നാം എന്താണ് ചെയ്തത് എന്ന് ശ്രദ്ധിക്കുക. ആദ്യത്തെ പ്രോഗ്രാമില്‍ "r, a എന്നിവയുടെ ഉസാഘ കണ്ടുപിടിക്കൂ" എന്ന് കമന്റായി എഴുതിയ സ്ഥാനത്ത് നാം ഇക്കാര്യം ചെയ്യാനുള്ള കോഡ് എഴുതി. ഇതിനായി ആദ്യം r, a എന്നിവയെ യഥാക്രമം a, b എന്നിങ്ങനെ പേരുമാറ്റി; ഇങ്ങനെയാകുമ്പോള്‍ a, b എന്നിവയുടെ ഉസാഘ കാണാന്‍ മുകളില്‍ എഴുതിയ കോഡ് അതേപടി പകര്‍ത്തിയാല്‍ മതിയാകുമല്ലോ. പിന്നെ നാം ഈ കോഡ് മുകളില്‍നിന്ന് പകര്‍ത്തിയെഴുതി. ഇവിടെ രണ്ടാമത്തെ തവണ ഹരിക്കുമ്പോള്‍ കിട്ടുന്ന ശിഷ്ടം പൂജ്യമാണെങ്കില്‍ നമുക്കുവേണ്ടതായ ഉസാഘ കിട്ടും; ഇല്ലെങ്കിലാണ് പ്രശ്നം. ഇവിടെയും ശിഷ്ടം കിട്ടുന്ന r പൂജ്യമല്ലെങ്കില്‍ r, a എന്നിവയുടെ ഉസാഘ കണ്ടുപിടിക്കൂ എന്ന് കമന്റായി മാത്രം വീണ്ടും എഴുതിയത് ശ്രദ്ധിക്കുക.


ഈ രീതിയില്‍ പ്രോഗ്രാം വികസിച്ചുവന്നാലുള്ള കുഴപ്പം മനസ്സിലായല്ലോ? സ്ക്രീനിന്റെ വലതുവശത്തേക്ക് പ്രോഗ്രാം അടിവച്ച് നീങ്ങിപ്പോകുന്നതു പോകട്ടെ, എത്രതവണ ശിഷ്ടം കണ്ടാലാണ് ഉസാഘ കിട്ടുക എന്നത് പ്രോഗ്രാം എഴുതുന്ന സമയത്ത് നമുക്കറിഞ്ഞുകൂടാ എന്ന ഒരു വലിയ പ്രശ്നം ഈ രീതിക്കുണ്ട്: ഇന്‍പുട്ട് കിട്ടുന്ന സംഖ്യകള്‍ക്കനുസരിച്ച് ഇത് എത്രവേണമെങ്കിലും വരെ ആകാം. ഈ പ്രശ്നം എങ്ങനെ പരിഹരിക്കാം? ഇവിടെ നമ്മുടെ കോഡ് എത്ര വരെ പ്രവര്‍ത്തിക്കണം എന്നത് ഒരു വ്യവസ്ഥയെ (condition) ആശ്രയിച്ചിരിക്കുന്നു എന്നത് ശ്രദ്ധിക്കുക: ശിഷ്ടമായി കിട്ടുന്ന r എപ്പോള്‍ പൂജ്യമാകുന്നോ അപ്പോള്‍ നമുക്ക് പ്രോഗ്രാമിന്റെ പ്രവര്‍ത്തനം നിര്‍ത്താം — ഈ സമയത്തെ a-യുടെ വിലയാണ് നമുക്കുവേണ്ട ഉസാഘ.




വ്യവസ്ഥ ശരിയാകുന്നതുവരെ ആവര്‍ത്തിക്കാന്‍: while


ഇങ്ങനെ, ഒരു വ്യവസ്ഥ ശരിയാകുന്നതുവരെ കുറേക്കാര്യങ്ങള്‍ ആവര്‍ത്തിച്ച് ചെയ്യാന്‍ പൈത്തണിലും മറ്റ് മിക്ക കംപ്യൂട്ടര്‍ ഭാഷകളിലുമുള്ള ഉപാധിയാണ് while . ഇതിനുമുമ്പ് നാം പരിചയപ്പെട്ട if, for എന്നിവയുടെ സമ്മിശ്ര സ്വഭാവമുള്ള ഒരു ഉപാധിയാണ് ഇത്. ഇനി നമുക്ക് while -നെ പരിചയപ്പെടാം. ഇതിനായി താഴെക്കാണുന്ന പ്രോഗ്രാമുകള്‍ പ്രവര്‍ത്തിപ്പിച്ചുനോക്കുക.









while-നെപ്പറ്റി വിശദമായി


while പ്രോഗ്രാമില്‍ ഉപയോഗിക്കുന്ന വിധം നമുക്ക് കുറച്ചുകൂടി വിശദമായി പരിശോധിക്കാം:


1. while വരിയുടെ (ലഘുവായ) വ്യാകരണം ഇതാണ്: while condition : . പേരുസൂചിപ്പിക്കുന്നതുപോലെ ഇവിടെ condition എന്നത് ഒരു വ്യവസ്ഥ ആണ്. ഉദാഹരണങ്ങളിലെ വ്യവസ്ഥകളെല്ലാം സംഖ്യകളെ അധികരിച്ചാണെങ്കിലും, പൊതുവേ ഇത് എന്തുതരത്തിലുള്ള വ്യവസ്ഥ വേണമെങ്കിലും ആകാം. കൂടുതല്‍ വൈവിധ്യമുള്ള ഉദാഹരണങ്ങള്‍ നമുക്ക് വഴിയേ കാണാം. condition കഴിഞ്ഞുള്ള : പ്രത്യേകം ശ്രദ്ധിക്കുക.
2. while വരി കഴിഞ്ഞുവരുന്ന വരികളില്‍ while -ന്റെ പരിധിയില്‍പ്പെടുന്ന വരികള്‍ (ഒന്നോ അതിലധികമോ) എഴുതണം. ഇങ്ങനെയുള്ള വരികള്‍ എല്ലാം തന്നെ ഈ while വരിയെ അപേക്ഷിച്ച് ഒരു നിശ്ചിത അകലം വലതുവശത്തേക്ക് മാറി ആയിരിക്കണം തുടങ്ങേണ്ടത്.
3. മുകളിലെ ഉദാഹരണങ്ങളില്‍ നാലു സ്പേസ് വലത്തേക്ക് മാറിയാണ് എഴുതിയിട്ടുള്ളത്. ഇങ്ങനെ നാലു സ്പേസ് വിട്ടെഴുതുന്നതാണ് പൈത്തണ്‍ മാനകം (standard).
4. IDLE ഉപയോഗിച്ച് പ്രോഗ്രാം എഴുതുകയാണെങ്കില്‍ : എന്നെഴുതി Enter അമര്‍ത്തുമ്പോള്‍ IDLE തനിയെ തന്നെ എഴുതിത്തുടങ്ങാനുള്ള സൂചകം (cursor) പുതിയ വരിയില്‍ നാലു സ്പേസ് വലത്തേക്ക് മാറ്റിത്തരുന്നത് കാണാം. ഇതൊന്ന് പരീക്ഷിച്ചു നോക്കൂ! ഇങ്ങനെ മാറുന്നില്ലെങ്കില്‍ തൊട്ടുമുമ്പത്തെ വരിയുടെ വ്യാകരണം തെറ്റിയതാവും കാരണം. മിക്കവാറും ഇത് അവസാനം കൊടുക്കേണ്ടതായ : വിട്ടുപോയതുകൊണ്ടാവും.
5. condition എപ്പോള്‍ വരെ ശരിയായിരിക്കുന്നോ, അത്ര വരെ while -ന്റെ പരിധിയില്‍പ്പെടുന്ന വരികളെല്ലാം പ്രവര്‍ത്തിപ്പിക്കുക എന്നതാണ് while -ന്റെ അടിസ്ഥാന സ്വഭാവം. മുകളില്‍ ആദ്യത്തെ ഉദാഹരണം പ്രവര്‍ത്തിപ്പിച്ചു നോക്കിയാല്‍ ഇത് വ്യക്തമായി മനസ്സിലാകും. ഒരിക്കലും തെറ്റാത്ത ഒരു വ്യവസ്ഥയാണെങ്കില്‍ (ഉദാ: 1 == 1) ഈ വരികളെല്ലാം അനന്തകാലത്തേക്ക് (അല്ലെങ്കില്‍ പ്രോഗ്രാം പുറത്തുനിന്ന് നിര്‍ത്തുന്നതുവരെ) പ്രവര്‍ത്തിച്ചുകൊണ്ടേയിരിക്കും.
6. while -ന്റെ പരിധിയില്‍ വരേണ്ടുന്ന — വ്യവസ്ഥ ശരിയായിരിക്കുന്നിടത്തോളം കാലം പ്രവര്‍ത്തിപ്പിക്കേണ്ടുന്ന — വരികള്‍ എഴുതിക്കഴിഞ്ഞാല്‍ പിന്നീടുള്ള വരി while വരി തുടങ്ങുന്ന അതേ അകലം ഇടതുവശത്തുനിന്ന് വിട്ട് വേണം തുടങ്ങാന്‍. അതായത്, നാലു സ്പേസ് വലത്തേക്ക് മാറി എഴുതുന്നത് നിര്‍ത്തണം എന്നര്‍ത്ഥം. while -ന്റെ പരിധിയില്‍പ്പെടുന്ന വരികള്‍ ഏതൊക്കെയാണെന്ന് പൈത്തണ്‍ മനസ്സിലാക്കുന്നത് while -നു ശേഷവും while -ന്റെ അതേ നിരപ്പിലുള്ള ആദ്യത്തെ വരി കാണുന്നതിന് മുന്‍പും നാലു സ്പേസ് വലത്തേക്ക് മാറി വരുന്ന വരികള്‍ ഏതൊക്കെയാണ് എന്ന് നോക്കിയിട്ടാണ്. ഉദാഹരണങ്ങളില്‍ while -ന്റെ പരിധിക്ക് പുറത്തുള്ള വരികള്‍ എഴുതുന്ന വിലകള്‍ നോക്കിയാല്‍ ഇത് വ്യക്തമാകും.
7. ഇവിടെ നാലു സ്പേസ് എന്ന് പറഞ്ഞയിടത്തൊക്കെ അതിനു പകരം വേറെ ഏതെങ്കിലും ഒരു നിശ്ചിത അകലം ഇതേ ആവശ്യത്തിന് ഉപയോഗിക്കാം. ഉദാഹരണത്തിന്, ഒരു ടാബ് (കംപ്യൂട്ടറിന്റെ Tab കീ അമര്‍ത്തിയാല്‍ കിട്ടുന്നത്) ഇതിനായി ഉപയോഗിക്കാം. ഒരേ പ്രോഗ്രാമില്‍ ടാബുകളും സ്പേസുകളും രണ്ടുംകൂടി ഈ ആവശ്യത്തിന് ഉപയോഗിക്കരുത്. ഈ ആവശ്യത്തിന് നാലു സ്പേസ് ഉപയോഗിക്കുന്നതാണ് നല്ല പൈത്തണ്‍ ശൈലിയായി കണക്കാക്കുന്നത്.
8. ഇക്കാര്യങ്ങളിലെല്ലാം മുമ്പത്തെ പാഠത്തില്‍ നാം പരിചയപ്പെട്ട if, for എന്നിവയുടെ ഘടനയുമായുള്ള സാമ്യം ശ്രദ്ധിക്കുക.
9. if, for, while എന്നിവയുടെ പരിധിക്കുള്ളില്‍ എന്തുവേണമെങ്കിലും എത്രവേണമെങ്കിലും "ആഴത്തില്‍" എഴുതാം. ഇങ്ങനെ എഴുതുമ്പോള്‍ സ്പേസ് കൊടുക്കുന്ന കാര്യത്തില്‍ ഇതുവരെ പറഞ്ഞ (ലളിതങ്ങളായ) നിയമങ്ങള്‍ പാലിച്ചിരിക്കണമെന്ന് മാത്രം : പുതിയ ഒരു പരിധി തുടങ്ങുമ്പോള്‍ നാലു സ്പേസ് വലത്തേക്ക് മാറി എഴുതിത്തുടങ്ങുക. ഈ പരിധി അവസാനിക്കുമ്പോള്‍ ഇങ്ങനെ വലത്തേക്ക് മാറുന്നതും നിര്‍ത്തുക. ഇങ്ങനെയുള്ള അനേകം ഉദാഹരണങ്ങള്‍ വഴിയേ കാണാം.




പ്രവര്‍ത്തനം

പ്രവ. 6.

while-ല്‍ പറയുന്ന വ്യവസ്ഥ (condition) എപ്പോള്‍ വരെ ശരിയായിരിക്കുന്നോ, അപ്പോള്‍ വരെ while-ന്റെ പരിധിയില്‍പ്പെടുന്ന വരികള്‍ പ്രവര്‍ത്തിപ്പിക്കുക എന്നതാണല്ലോ while-ന്റെ സ്വഭാവം? ഇതുകൊണ്ടുതന്നെ while -ന്റെ പരിധിയില്‍പ്പെടുന്ന വരികള്‍ ഓരോ തവണ പ്രവര്‍ത്തിപ്പിക്കുമ്പോഴും ഈ വ്യവസ്ഥയെ (നേരിട്ടോ അല്ലാതെയോ)ബാധിക്കുന്ന എന്തെങ്കിലും മാറ്റം വരേണ്ടത് സാധാരണ ഗതിയില്‍ പ്രോഗ്രാം ശരിയാകാന്‍ ആവശ്യമാണ്. മുകളിലെ ഉദാഹരണങ്ങളില്‍ ഇങ്ങനെയുള്ളതരം മാറ്റം വരുത്തുന്ന വരികള്‍ ഏതാണെന്ന് കണ്ടുപിടിക്കുക.




4. 
   

   യൂക്ളിഡിന്റെ അല്‍ഗോരിതം : പൈത്തണില്‍ വീണ്ടും

   
   ഇനി നമുക്ക് while ഉപയോഗിച്ച് യൂക്ളിഡിന്റെ അല്‍ഗോരിതത്തിനെ എങ്ങനെ മുഴുമിപ്പിക്കാം എന്ന് നോക്കാം. നമ്മുടെ രണ്ടാമത്തെ പ്രോഗ്രാം ഒന്നുകൂടെ എടുത്തെഴുതുന്നു. പറയാനുള്ള സൗകര്യത്തിനായി a, b-യെക്കാള്‍ വലുതല്ല എന്ന് സങ്കല്‍പ്പിച്ചിരിക്കുന്നു എന്ന് ഓര്‍ക്കുക:
   
   
   
   while ഉപയോഗിച്ച് ഈ കോഡിനെ എങ്ങനെ മുഴുമിപ്പിക്കാം? ഇവിടെ r എന്ന ചരത്തിന്റെ വില പൂജ്യം ആകുന്നതുവരെയാണ് നമുക്ക് ശിഷ്ടം കാണുകയും മറ്റും വേണ്ടത്. ഇത് while ഉപയോഗിച്ച് എഴുതുമ്പോള്‍ ഇങ്ങനെയാകും:
   
   
   
   
   ഇവിടെ ചെയ്തിരിക്കുന്നത് ശ്രദ്ധിക്കുക. ഒമ്പതാമത്തെ വരിയില്‍ b-യെ a കൊണ്ട് ഹരിച്ചാല്‍ കിട്ടുന്ന ശിഷ്ടം r എന്ന ചരത്തില്‍ സൂക്ഷിച്ചുവെക്കുന്നു. r-ന്റെ വില പൂജ്യമാണെങ്കില്‍ നമുക്കുവേണ്ടതായ ഉസാഘ a-യുടെ വില തന്നെയാണെന്ന് നാം കണ്ടു. r-ന്റെ വില പൂജ്യം അല്ലെങ്കില്‍ ഈ വില പൂജ്യം ആകുന്നതുവരെ ഒരുകൂട്ടം കാര്യങ്ങള്‍ ചെയ്യണം. ഇത് സംഭവിക്കുന്നത് 11 മുതല്‍ 18 വരെയുള്ള വരികളിലാണ്. പതിനൊന്നാം വരിയില്‍ while-ന് തുടക്കമിട്ടിരിക്കുന്നു. ഈ while-ന്റെ പരിധി പതിനെട്ടാം വരി വരെയാണ്. പന്ത്രണ്ടുമുതല്‍ പതിനെട്ടുവരെയുള്ള വരികള്‍ എത്രത്തോളം ആവര്‍ത്തിക്കണം എന്നത് പതിനൊന്നാം വരിയില്‍ പറഞ്ഞിരിക്കുന്നു: "r-ന്റെ വില പൂജ്യം അല്ലാത്തിടത്തോളം".
   
   മുകളിലത്തെ പ്രോഗ്രാമിനെ നമുക്ക് കുറച്ചുകൂടെ ചെറുതാക്കാം. a == b ആണെങ്കില്‍ b-യെ a കൊണ്ട് ഹരിച്ചാല്‍ ശിഷ്ടം പൂജ്യമാണല്ലോ? ഇക്കാര്യം മുതലെടുത്ത് ആദ്യത്തെ വ്യവസ്ഥ പരിശോധിക്കുന്നത് നമുക്ക് ഒഴിവാക്കാം. ഇനി a, b-യെക്കാള്‍ വലുതാണെങ്കില്‍ b-യെ a കൊണ്ട് ഹരിച്ചാല്‍ ശിഷ്ടം b തന്നെയാണല്ലോ? അതുകൊണ്ട് while ആദ്യത്തെ തവണ പ്രവര്‍ത്തിക്കുമ്പോള്‍ a, b എന്നിവയുടെ വിലകള്‍ തമ്മില്‍ വെച്ചുമാറുകയും a,b-യെക്കാള്‍ ചെറുതാകുകയും ചെയ്യും. ഫലം : a, b-യെക്കാള്‍ വലുതായാല്‍ പോലും ഇതേ കോഡ് ശരിയായി പ്രവര്‍ത്തിക്കും. ഈ മാറ്റങ്ങളൊക്കെ വരുത്തിയ കോഡ് ഇതാ:
   
   
   
   

   പ്രവര്‍ത്തനം

   പ്രവ. 7.

   മുകളിലത്തെ പ്രോഗ്രാമും അതിന് തൊട്ടുമുമ്പ് കൊടുത്തിട്ടുള്ള പ്രോഗ്രാമും തമ്മിലുള്ള വ്യത്യാസങ്ങള്‍ എന്തൊക്കെയാണ്? ഈ വ്യത്യാസങ്ങളൊക്കെ ഉണ്ടായിട്ടും രണ്ടു പ്രോഗ്രാമും എന്തുകൊണ്ടാണ് ഒരേപോലെ പ്രവര്‍ത്തിക്കുന്നത്?

   രണ്ട് എണ്ണല്‍സംഖ്യകള്‍ ഇന്‍പുട്ട് ആയി എടുത്ത്, യൂക്ളിഡിന്റെ അല്‍ഗോരിതം ഉപയോഗിച്ച് ഈ സംഖ്യകളുടെ ഉസാഘ കണ്ടുപിടിക്കുന്ന പ്രോഗ്രാം മുകളില്‍ കൊടുത്ത രീതിയില്‍ എഴുതുക. പ്രോഗ്രാമിന്റെ പ്രവര്‍ത്തനഫലം താഴെക്കാണുന്ന ചിത്രത്തിലെപ്പോലെ ആയിരിക്കണം (കുറച്ചുകൂടെ വ്യക്തമായ ചിത്രം കാണാന്‍ ഈ ചിത്രത്തില്‍ അമര്‍ത്തുക). ഇവിടെ ഈ പ്രോഗ്രാം നാലു തവണ പ്രവര്‍ത്തിപ്പിച്ചിരിക്കുന്നു (IDLE-ല്‍ F5 നാലു തവണ അമര്‍ത്തിയിരിക്കുന്നു).

   

   മുകളില്‍ "യൂക്ളിഡിന്റെ അല്‍ഗോരിതം" എന്ന ഭാഗത്തിന്റെ തുടക്കത്തില്‍ കാണുന്ന മൂന്ന് ജോടി സംഖ്യകള്‍ ഈ പ്രോഗ്രാമിന് ഇന്‍പുട്ട് ആയി കൊടുക്കുക. ഈ പ്രോഗ്രാം ഇവയുടെ ഉത്തരം കണ്ടുപിടിക്കാന്‍ ഏറെ സമയം എടുക്കുന്നുണ്ടോ?
   

   വളരെ വലിയ സംഖ്യകള്‍ ഉള്‍പ്പെടുന്ന ജോടികള്‍ ഈ പ്രോഗ്രാമിന് ഇന്‍പുട്ട് ആയി കൊടുക്കുക. സംഖ്യകള്‍ വലുതാകുന്ന അതേ തോതില്‍ പ്രോഗ്രാം എടുക്കുന്ന സമയവും കൂടുന്നതായി തോന്നുന്നുണ്ടോ?