زیرالگوریتم

زیرالگوریتم

اسلاید 1: 1زيرالگوريتم

اسلاید 2: 2الگوريتم و برنامه ای بنويسيد که ابتدا يک عدد صحيح مثبت n را, که فرض می شود n>1 , از ورودي بخواند. سپس درايه هاي سه ماتريس به اسامي A , B , و C را, که C معکوسپذير فرض می شود, به طور جداگانه خوانده و مقدار det(AB+C-1) را محاسبه و چاپ کند.

اسلاید 3: 3زيرالگوريتم ها: 1) ضرب کننده دو ماتريس؛ 2) جمع کننده دو ماتريس؛ 3) وارون کننده يک ماتريس؛ 4) محاسبه کننده دترمينان؛ 5) خواننده درايه هاي يک ماتريس. کار الگوريتم اصلی:

اسلاید 4: 4برخي انگيزه ها براي استفاده از زيرالگوريتم ها 1) نوشتن الگوريتم ساده تر می گردد چرا که، کار محاسبه ای بزرگ بين زيرالگوريتم هايي کوچک، به انضمام يک الگوريتم اصلي کوچک تقسيم می گردد. اکنون نوشتن زيرالگوريتمها به خاطر حجم آنها و محدوديت کارشان ساده خواهد بود. 2) آزمايش درستي الگوريتم به آزمايش يک به يک زيرالگوريتم ها خلاصه شده و در نتيجه مشکل آزمايش الگوريتم نيز حل می گردد. بويژه، اگر اشتباهات احتمالي وجود داشته باشند، اصلاح آنها در هر زيرالگوريتم مستقل راحتتر و سريعتر انجام می گيرد. 3) از تکرار برخي بخشها در قسمتهاي مختلف برنامه، و در نتيجه از اتلاف وقت، جلوگيري می شود. 4) هر زيرالگوريتم را می توان بطور مستقل براي استفاده هاي آتي در برنامه هاي ديگر، در حافظه هاي کمکي ذخيره نمود.

اسلاید 5: 5‼ يک زيرالگوريتم هيچ کاري انجام نمی دهد مگر اينکه يک زيرالگوريتم ديگر يا الگوريتم اصلي، که بعد از اين آن را الگوريتم (واحد) فراخوان خواهيم گفت، آن را فراخواند. در اينصورت, هيچ, يک, و يا چند مقدار به زيرالگوريتم داده شده و زيرالگوريتم شروع به اجرا می کند. در نتيجه اين اجرا، يا کاري انجام می شود (مثل خواندن و در حافظه ذخيره کردن، چاپ کردن، و يا يک پردازش ديگر) و يا يک يا چند مقدار به الگوريتم فراخوان باز می گردد.

اسلاید 6: 6قاعده. در شروع يک زيرالگوريتم، نام آن به انضمام متغيرهاي ورودي به زيرالگوريتم و خروجي از آن را در داخل يک بيضي قرار می دهيم. مثلاPower(x,n)Data_Reader(a,b,c)اتمام الگوريتم را نيز با يک بيضی با نوشته Return اعلام خواهيم کرد.

اسلاید 7: 7متغير هاي داخل پرانتز را آرگومانهاي صوري زيرالگوريتم می ناميم. اين آرگومانها بر دو دسته تقسيم می شوند. دسته اول، که آنها را پارامترهاي مقدار می ناميم، آرگومانهاي صوري ورودي به زيرالگوريتم می باشند؛ يعني مقادير را از الگوريتم فراخوان به زيربرنامه می آورند. دسته دوم، به نام پارامترهاي متغير، آرگومانهاي صوري خروجي از زيرالگوريتم می باشند؛ يعني مقاديري را که از اجراي زيرالگوريتم حاصل شده اند از آن خارج کرده و به الگوريتم فراخوان باز می گردانند.

اسلاید 8: 8قاعده. وقتي اجراي يک زيرالگوريتم تمام شد، کنترل اجراي برنامه به موقعيت بعد از نقطه ای که از آنجا زيرالگوريتم فراخواني شده بود منتقل می شود.

اسلاید 9: 9در ادامه خواهيم ديد که نوع زيرالگوريتمها، و همچنين نوع فراخواني آنها متفاوت است. ولي يک نکته در تمام اين فراخواني ها مشترک است و آن اينکه، ‼ در لحظه فراخواني يک زيرالگوريتم توسط الگوريتم فراخوان نام آن زيرالگوريتم به انضمام برخي متغيرها يا عبارتهايي ذکر می شود. مثلا Power(y,8) .

اسلاید 10: 10در Power(y,8) ، عبارتهاي داخل پرانتز را آرگومانهاي فعال می ناميم. آرگومانهاي فعال نيز به دو دسته ورودي به الگوريتم فراخوان و خروجي از آن تقسيم می شوند. آرگومانهاي ورودي به الگوريتم فراخوان حتما بايد متغير انتخاب شوند. اين آرگومانها با پارامترهاي متغير (آرگومانهاي صوري خروجي از زيرالگوريتم) متناظر هستند. آرگومانهاي خروجي از الگوريتم فراخوان می توانند يک مقدار (متغير، ثابت، يا يک عبارت جبري) باشند. اين آرگومانها با پارامترهاي مقدار (آرگومانهاي صوري ورودي به زيرالگوريتم) متناظر می باشند.

اسلاید 11: 11قاعده. تعداد، ترتيب، و نوع آرگومانهاي صوري بايد با تعداد، ترتيب و نوع آرگومانهاي فعال متناظر با آنها کاملا سازگار باشند. ‼ آرگومانهای فعال و صوري متناظر می توانند همنام و يا غير همنام باشند.

اسلاید 12: 12مثلا اگر در دستور معرف Power(x,n): اعشاری x : صحيح nنوع آرگومانهاي x و n بصورتي که هست مشخص شده باشند، آنگاه به منظور فراخواني زيرالگوريتم براي مقدار اعشاري y (که فرض می شود از قبل در حافظه ذخيره شده) متناظر با آرگومان صوري x ، و مقدار صحيح 8 متناظر با آرگومان صوري n ، می توان فراخواني به صورت Power(y,8) را انجام داد ولي هيچيک از فراخواني هاي زير درست نمی باشند. Power(y,8.0) Power(8,y) Power(y)

اسلاید 13: 13زيربرنامه

اسلاید 14: 14در برنامه نويسی برگردان زيرالگوريتم را زيربرنامه (sub-program) و برگردان الگوريتم اصلي را برنامه اصلي (main program) می ناميم. موقعيت برنامه اصلي و يک زيربرنامه در برنامه نويسی پاسکال در نمودار (الف) صفحه بعد مشخص شده است. (از روی کتاب)

اسلاید 15: 15از اين به بعد، برنامه اصلي و هر يک از زيربرنامه ها را يک واحد خواهيم گفت. به برنامه اصلي به عنوان واحد اصلي و به هر يک از زيربرنامه ها با نام آن واحد ارجاع خواهيم نمود. يک برنامه قابل اجرا، شامل برنامه اصلی و زيربرنامه هايش، را يک برنامه کامل می ناميم. نمودار (ب) يک برنامه کامل شامل چند واحد تودرتو را نشان می دهد.

اسلاید 16: 16‼ دستور معرف برنامه اصلي، همان دستور ; اسم برنامه Program است و دستورهاي معرف زيربرنامه ها بعداً مورد مطالعه قرار خواهند گرفت.

اسلاید 17: 17متغيرهايی را که در بلوک Var برنامه اصلی تعريف می شوند متغيرهای سراسری و آنهايی را که بلوک Var يک زيربرنامه تعريف می شوند متغيرهای موضعی می نامند. قاعده حوزه عمل پارامترهاي مقدار و متغيرهاي موضعي. پارامترهاي مقدار و متغيرهاي موضعي تعريف شده در يک واحد زيربرنامه، فقط در خود آن واحد و واحدهاي داخلي آن قابل دسترسي (استفاده) هستند. اينها در هيچ واحد خارجی زيربرنامه نمی توانند استفاده شوند.

اسلاید 18: 18در نمونه (ب: (

اسلاید 19: 19‼ اگر متغير موضعي يک زيربرنامه در حوزه عمل خود در يکي از زيربرنامه ها نوعش عوض شود آنگاه در آن زيربرنامه با همان نوع کار خواهد کرد.

اسلاید 20: 20‼ اگر متغيری هم در زيربرنامه و هم در يک واحد فراخوان خارجی آن استفاده شده باشد، آنگاه در صورتيکه استفاده آنها با هم تداخل نداشته باشند می توان به تعريف آن در واحد فراخوان (خارجی) اکتفا کرده و در زيربرنامه از تعريف مجدد آن صرفنظرنمود؛ ولی در صورتيکه استفاده آنها با هم تداخل داشته باشند بايد هم در زيربرنامه و هم در آن واحد فراخوان آن متغير را تعريف کرد؛ در غير اينصورت اثرات مخربی در نتايج خواهيم داشت که تشخيص و اصلاح آن بسيار مشکل است.

اسلاید 21: 21قاعده فراخواني واحدهاي تو در تو. براي اينکه حوزه عمل واحدهاي زيربرنامه ها را همواره به خاطر داشته باشيم، يک شيوه بسيار ساده را ارائه می دهيم. فرض می کنيم که هر واحد با يک کادر مرز بندي شده باشد (مثل نمودار (ب)). واحدي را می توان در واحدي ديگر فراخواني کرد که مرزهاي آن دو را بتوان، بدون برخورد با هيچ مرزي ديگر، توسط يک خط پيوسته به همديگر وصل کرد. البته يک واحد خارجی را نمی توان در يک واحد داخلی فراخوانی کرد.

اسلاید 22: 22در نمونه (ب: (

اسلاید 23: 23 زیرالگوريتمها به دو دسته تقسيم می شوند: 1. زيرالگوريتم تابع

اسلاید 24: 24اين زيرالگوريتم را زماني بکار می بريم که بخواهيم تابعي بسازيم (تعريف کنيم) که اين تابع در فهرست توابع مترجم زبان برنامه نويسی موجود نباشد.

اسلاید 25: 25قاعده. يک تابع، معمولاً، حداقل يک آرگومان صوري داشته و دقيقا يک مقدار به الگوريتم فراخوان باز می گرداند. اين مقدار بازگشتي توسط اسم خود تابع انجام می گيرد. به همين علت, براي تعريف مقدار تابع، اسم تابع بايد حداقل يک بار در سمت چپ يک دستور انتساب ظاهر شود تا مقدار تابع را در خود بگيرد. به علاوه، نوع نتيجه تابع نيز بايد تعيين گردد.

اسلاید 26: 26‼ در اينجا آرگومانهاي صوري همه از دسته پارامترهاي مقدار (ورودي به زيرالگوريتم) می باشند و هيچ پارامتر متغير (خروجی از زيرالگوريتم) نداريم چون اسم تابع است که نتيجه را به واحد فراخوان برمی گرداند.

اسلاید 27: 27قاعده. هيچيک از آرگومانهاي صوری تابع را ديگر نبايد در زيرالگوريتم تابع توسط دستورهاي خواندن بخوانيم. مقادير اين آرگومانها از طريق واحد فراخوان به زيرالگوريتم می آيند. همچنين مقدار تابع را نبايد در زيرالگوريتم چاپ کنيم. اين مقدار قرار است به واحد فراخوان بازگردد.

اسلاید 28: 28تابع علامت sign برای يک عدد حقيقی x با ضابطه زير تعريف می شود:

اسلاید 29: 29x<0x=0sign←1sign←0sign← -1sign(x)Return

اسلاید 30: 30قاعده. فراخواني توابع درست مثل استفاده از توابع تعريف شده براي مترجم هر زبان می باشد. همانطوريکه براي يک مقدار تعريف شده x در برنامه از تابع سينوس sin(x) استفاده می کنيم، از تابع sign(x) نيز به همان شکل استفاده می نماييم.

اسلاید 31: 31x<0x=0sign←1sign←0sign← -1sign(x)Returns≠ts,tys←sign(sin(y))t←sin(sign(y))EndStart

اسلاید 32: 32قاعده. در برنامه نويسي، دستور معرف زيربرنامه های تابع بصورت زير نوشته می شود: ; نوع مقدار تابع ): آرگومانهاي صوري (اسم تابع Function

اسلاید 33: 33 ممکن است هيچ آرگومان صوري نداشته باشيم. چنين وضعيتی امکان دارد زمانی رخ دهد که بخواهيم مقداری را برای يک متغير بخصوصی تعريف کنيم. مثلاً در زيربرنامه تابع زير مقدار عدد نپری e تعريف می گردد:Function e:real; Begin e:=exp(1.0) End;

اسلاید 34: 34اما، در صورت وجود آرگومانهای صوری، آنها به شکل زير (از چپ به راست) ظاهر خواهند شد. نوع دسته آخر:دسته آخر . . . ; نوع دسته 2:دسته 2; نوع دسته 1:دسته 1

اسلاید 35: 35مثلا در دستور معرف Function Pad(x,y:real;i,j,k:integer):char; دسته متغيرهای x و y از نوع حقيقی, و متغيرهای i , j , و k از نوع صحيح بوده, و نوع تابع Pad نيز کاراکتری می باشد.

اسلاید 36: 36قاعده. هيچيک از آرگومانهاي صوري در يک زيربرنامه را ديگر نبايد در بلوک Var آن زيربرنامه تعريف کرد. به عبارت ديگر يک آرگومان صوري نمی تواند در عين حال يک متغير موضعي نيز باشد.

اسلاید 37: 37‼ با توجه به اينکه اسم تابع مقدار تابع را با خود به واحد فراخوان باز می گرداند، پس نوع مقدار تابع نيز بايد مشخص باشد. زيرالگوريتم sign و الگوريتم (اصلي) فراخوان آن در برنامه P4_1 آمده است.

اسلاید 38: 38{A program containing two units: A function sub-program called sign, and a main program} Program P4_1; Uses wincrt; Var y,t:real; s:integer; (*****************************) Function sign(x:real):integer; Begin If x<0 then sign:=-1 else if x=0 then sign:=0 else sign:=1 End;{sign} (*****************************) Begin Write(Enter a real number: ); Readln(y); s:=sign(sin(y)); t:=sin(sign(y)); If s<>t then begin Writeln(sign(sin(,y,)=,s); Writeln(sin(sign(,y,)=,t:8:4) end End.

اسلاید 39: 39اينک به چگونگی اجرای برنامه دو واحدی بالا می پردازيم، ولی قبلا لازم است مطالبی در مورد حافظه زيربرنامه و برنامه اصلی بيان کنيم.

اسلاید 40: 40قاعده. براي هر يک از پارامتر هاي مقدار (آرگومانهاي صوري) تابع، و همجنين برای هر يک از متغيرهای موضعی، يک حافظه موقت در هنگام اجراي زيربرنامه رزرو می شود که با پايان اجراي آن (با اجراي دستور End;) اين حافظه هاي موقت نيز بطور کلي پاک می شوند. تمام متغيرهای سراسری در حافظه ای به نام حافظ دائم ذخيره می گردند. اين حافظه تا پايان اجرای برنامه باقی می ماند.

اسلاید 41: 41‼ حافظه موقت دو زيربرنامه در کامپيوتر کاملا از همديگر جدا هستند. بنابراين اگر يک متغير همنام در دو حافظه ظاهر شده باشد, آنگاه حافظه های اين دو متغير همنام هيچ برخوردي با هم نخواهند داشت زيرا وقتي يک زيربرنامه اجرايش تمام می شود حافظه موقت مربوط به آن از حافظه کامپيوتر پاک می شود. پس برخوردي وجود نخواهد داشت. اين مطلب براي حافظه موقت و حافظه دائمي نيز معتبر است.

اسلاید 42: 42Sin(10) : - 0.544Program P4_1; Uses wincrt; Var y,t:real; s:integer; (*****************************) Function sign(x:real):integer; Begin If x<0 then sign:=-1 else if x=0 then sign:=0 else sign:=1 End;{sign} (*****************************) Begin Write(Enter a real number: ); Readln(y); s:=sign(sin(y)); t:=sin(sign(y)); If s<>t then begin Writeln(sign(sin(,y,)=,s); Writeln(sin(sign(,y,)=,t:8:4) end End. 10.0y-0.544x-1st

اسلاید 43: 43Program P4_1; Uses wincrt; Var y,t:real; s:integer; (*****************************) Function sign(x:real):integer; Begin If x<0 then sign:=-1 else if x=0 then sign:=0 else sign:=1 End;{sign} (*****************************) Begin Write(Enter a real number: ); Readln(y); s:=sign(sin(y)); t:=sin(sign(y)); If s<>t then begin Writeln(sign(sin(,y,)=,s); Writeln(sin(sign(,y,)=,t:8:4) end End. 10.0y-1st

اسلاید 44: 44Sin(1) : 0.841Program P4_1; Uses wincrt; Var y,t:real; s:integer; (*****************************) Function sign(x:real):integer; Begin If x<0 then sign:=-1 else if x=0 then sign:=0 else sign:=1 End;{sign} (*****************************) Begin Write(Enter a real number: ); Readln(y); s:=sign(sin(y)); t:=sin(sign(y)); If s<>t then begin Writeln(sign(sin(,y,)=,s); Writeln(sin(sign(,y,)=,t:8:4) end End. 10.0y10.0x-1s0.841t

اسلاید 45: 45Program P4_1; Uses wincrt; Var y,t:real; s:integer; (*****************************) Function sign(x:real):integer; Begin If x<0 then sign:=-1 else if x=0 then sign:=0 else sign:=1 End;{sign} (*****************************) Begin Write(Enter a real number: ); Readln(y); s:=sign(sin(y)); t:=sin(sign(y)); If s<>t then begin Writeln(sign(sin(,y,)=,s); Writeln(sin(sign(,y,)=,t:8:4) end End. 10.0y-1s0.841t

اسلاید 46: 46قاعده. در زيربرنامه هاي تابع, اسم تابع به تنهايي (بدون ذکر آرگومانهايش) نبايد در سمت راست هيچ دستور انتسابي ظاهر شود. مثلا در بدنه تابعي که با دستور معرف Function Power(x:real;n:integer):real تعريف شده است, نوشتن دستوري مثل دستور زير غير مجاز است: Power:=Power*x;

اسلاید 47: 47 زیرالگوريتمها به دو دسته تقسيم می شوند: 1. زيرالگوريتم تابع 2. زيرالگوريتم رويه

اسلاید 48: 48هنگامي که بخواهيم در زيرالگوريتم کاري مثل چاپ، خواندن داده ها و ذخيره کردن آنها در حافظه، و يا هر پردازش ديگر انجام گيرد, و يا زماني که لازم باشد بيش از يک مقدار از زيرالگوريتم به الگوريتم فراخوان باز گردد، از زيرالگوريتم رويه (procedure) استفاده می کنيم.

اسلاید 49: 49طريقه تنظيم اين زيرالگوريتم مثل زيرالگوريتم تابع است ولي با توجه به اينکه اينجا، اسم زيرالگوريتم هيچ مقداري را با خود به الگوريتم فراخوان باز نمی گرداند؛ پس قاعده. در طول زيرالگوريتم رويه اسم آن نبايد ظاهر شود.

اسلاید 50: 50Procedure Heading; Begin Writeln(******************************************); Writeln(* Sub-program to investigate the roots *); Writeln(* of the equation a*x^2+b*x+c=0 *); Writeln(******************************************) End;{Heading}Headingيک عنوانReturnهيچ آرگومان صوری نداريم

اسلاید 51: 51قاعده. در برنامه نويسي، دستور معرف زيربرنامه هاي رويه بصورت زير نوشته می شود:Procedure اسم زيربرنامه (آرگومانهای صوری ) ;

اسلاید 52: 52اگر آرگومانهاي صوري داشته باشيم، آنها به شکل زير (از چپ به راست) ظاهر خواهند شد. نوع دسته آخر: دسته آخر [م]; . . . ; نوع دسته 2: دسته 2 [م]; نوع دسته 1: دسته 1 [م] که در آن [م] برای دسته پارامترهاي متغير var و برای دسته پارامتر هاي مقدار خالي است (م اول کلمه مشخصه است).

اسلاید 53: 53مثلا در دستور معرف Procedure Pol_Cart(ro,theta:real;var x,y:real); دو متغير حقيقی ro و theta پارامتر مقدار بوده و قبل از آنها خالي است، در حاليکه متغيرهای حقيقی x و y پارامترهاي متغير بوده و قبل از آنها var نوشته شده است.

اسلاید 54: 54Procedure Roots(a,b,c:real); Var d,x,x1,x2:real; Begin d:=b*b-4*a*c; If d>0 then begin x1:=(-b+sqrt(d))/(2*a); x2:=(-b-sqrt(d))/(2*a); Writeln(Two roots: ,x1:4:2,x2:4:2) end else if d=0 then begin x:=-b/(2*a); Writeln(One root: ,x:4:2) end else Writeln(No real roots) End;{Roots}d←b*b-4*a*cd=0d>0x1←(-b+√d)/(2*a)x2←(-b-√d)/(2*a)x← -b/(2*a)Roots(a,b,c)Return‘Two roots:’,x1,x2‘One root:’,x‘No real roots’آرگومانها همه پارامتر مقدارند

اسلاید 55: 55قاعده. هيچيک از پارامترهای مقدار را ديگر نبايد در آن زيرالگوريتم توسط دستورهاي خواندن بخوانيم. مقادير اين آرگومانها از طريق واحد فراخوان به زيرالگوريتم می آيند. همچنين هيچيک از پارامترهای متغير را نبايد در زيرالگوريتم چاپ کنيم. اين مقادير قرار است به واحد فراخوان بازگردند. در زيربرنامه بالا، دستور خواندن برای a ، b ، يا c کاملا مضحک خواهد بود.

اسلاید 56: 56قاعده. هيچيک از آرگومانهاي صوري در يک زيربرنامه را ديگر نبايد در بلوک Var آن زيربرنامه تعريف کرد. به عبارت ديگر يک آرگومان صوري نمی تواند در عين حال يک متغير موضعي نيز باشد. در زيربرنامه بالا، آوردن a ، b ، يا c در فهرست Var کاملا مضحک خواهد بود.

اسلاید 57: 57قاعده. در الگوريتم نويسي, يک زيرالگوريتم رويه به صورت زير فراخواني می شود:و در برنامه نويسي, براي فراخواني يک زيربرنامه رويه دستور زير بکار برده می شود:); آرگومانهاي فعال ( اسم رويه ( آرگومانهای فعال) اسم رويه

اسلاید 58: 58Pol_Cart(r,t,u,v);Pol_Cart(r,t,u,v)

اسلاید 59: 59EndStartu,v,wRoots(u,v,w)Headingd←b*b-4*a*cd=0d>0x1←(-b+√d)/(2*a)x2←(-b-√d)/(2*a)x← -b/(2*a)Roots(a,b,c)Return‘Two roots:’,x1,x2‘One root:’,x‘No real roots’Headingيک عنوانReturn

اسلاید 60: 60Program P4_2; Uses wincrt; Var u,v,w:real; (*******************************************************) Procedure Heading; Begin Writeln(******************************************); Writeln(* Sub-program to investigate the roots *); Writeln(* of the equation a*x^2+b*x+c=0 *); Writeln(******************************************) End;{Heading} (*******************************************************) Procedure Roots(a,b,c:real); Var d,x,x1,x2:real; Begin d:=b*b-4*a*c; If d>0 then begin x1:=(-b+sqrt(d))/(2*a); x2:=(-b-sqrt(d))/(2*a); Writeln(Two roots: ,x1:6:2, and ,x2:6:2) end else if d=0 then begin x:=-b/(2*a); Writeln(Just one root: ,x:6:2) end else Writeln(No real roots) End;{Roots} (**************************************************) Begin Heading; Writeln; Write(Enter the coefficients: ); Readln(u,v,w); Roots(u,v,w); End.

اسلاید 61: 61 مختصات کارترين يک نقطه از روي مختصات قطبي آن، ، بصورت زير محاسبه می شود: يک زيرالگوريتم رويه بنويسيد که مختصات قطبي يک نقطه را گرفته و مختصات کارترين آن را محاسبه و بازگرداند. سپس زيرالگوريتم (زيربرنامه) اخير را براي مقاديری از و که از ورودي خوانده می شود فراخواني ونتيجه را چاپ کنيد.

اسلاید 62: 62u,vr,tx←ro*cos(theta)y←ro*sin(theta)EndStartPol_Cart(ro,theta,x,y)ReturnPol_Cart(r,t,u,v){Program to convert the polar coordinates to Cartesia coordinates, using a procedure} Program P4_3;Uses wincrt;Var r,t,u,v:real;(**********************************************)Procedure Pol_Cart(ro,theta:real;var x,y:real);Begin x:=ro*cos(theta); y:=ro*sin(theta)End;{Pol_Cart}(**********************************************)Begin Write(Enter the polar coordinates Ro and Theta: ); Readln(r,t); Pol_Cart(r,t,u,v); Write(The Cart. coordinates are (,u:4:2,,,v:4:2,))End.هم پارامتر مقدار داريم و هم پارامتر متغير

اسلاید 63: 63قاعده. در زيربرنامه هاي رويه سه نوع حافظه داريم : 1) حافظه دائم، که مثل قبل مختص متغيرهای سراسری (متغيرهاي برنامه اصلي) بوده و تا اتمام اجراي برنامه ماندگار است. 2) حافظه موقت زيربرنامه، که به پارامتر هاي مقدار و متغيرهای موضعی اختصاص دارد و اين حافظه پس از اتمام اجراي زيربرنامه مربوطه، بطور کامل پاک می گردد. 3) حافظه مشترک (بين واحد فراخوان و زيربرنامه)، که مخصوص پارامترهاي متغير بوده و با آرگومانهاي فعال متناظر با آنها به اشتراک گذاشته می شود. اين نوع حافظه تا پايان اجرای واحد فراخوان باقی می ماند.

اسلاید 64: 64حافظه دائمحافظه مشترکحافظه موقتruxrotvytheta

اسلاید 65: 65Program P4_3; Uses wincrt; Var r,t,u,v:real; (**********************************************) Procedure Pol_Cart(ro,theta:real;var x,y:real); Begin x:=ro*cos(theta); y:=ro*sin(theta) End;{Pol_Cart} (*****************) Begin Readln(r,t); Pol_Cart(r,t,u,v); Write(u,v) End.0.01.00.01.00.01.0uvtryxthetaro

اسلاید 66: 66Program P4_3; Uses wincrt; Var r,t,u,v:real; (**********************************************) Procedure Pol_Cart(ro,theta:real;var x,y:real); Begin x:=ro*cos(theta); y:=ro*sin(theta) End;{Pol_Cart} (*****************) Begin Readln(r,t); Pol_Cart(r,t,u,v); Write(u,v) End.0.01.00.01.0uvtr

اسلاید 67: 67سؤال. اگر var قبل از آرگومانهاي x و y را برداريم خروجی چه می شود؟

اسلاید 68: 68Program P4_3; Uses wincrt; Var r,t,u,v:real; (**********************************************) Procedure Pol_Cart(ro,theta,x,y:real); Begin x:=ro*cos(theta); y:=ro*sin(theta) End;{Pol_Cart} (*****************) Begin Readln(r,t); Pol_Cart(r,t,u,v); Write(u,v) End.0.01.00.01.00.01.0tryxthetaro

اسلاید 69: 69Program P4_3; Uses wincrt; Var r,t,u,v:real; (**********************************************) Procedure Pol_Cart(ro,theta,x,y:real); Begin x:=ro*cos(theta); y:=ro*sin(theta) End;{Pol_Cart} (*****************) Begin Readln(r,t); Pol_Cart(r,t,u,v); Write(u,v) End.0.01.0tr

اسلاید 70: 70ممکن است يک آرگومان صوري، هم نقش يک پارامتر مقدار را بازي کند و هم نقش يک پارامتر متغير. در اينصورت بايد قاعده زير رعايت گردد. قاعده. يک آرگومان صوري اگر هم پارامتر مقدار و هم پارامتر متغير باشد، حتما بايد با var (قبل از آن) همراه باشد.

اسلاید 71: 71 زيرالگوريتم بعدي کار الگوريتم ماهي طلايي را انجام می دهد؛ يعني دو مقدار m و n را گرفته و مقادير آنها را تعويض کرده و به همان اسامي آنها را باز می گرداند. Program P4_4;Uses wincrt;Var m,n:integer;(*******************************)Procedure Swap(var m,n:integer);Var k: integer;Begin k:=m; m:=n; n:=kEnd;{Swap}(*******************************)Begin Write(Enter two integers: ); Readln(m,n); Swap(m,n); Writeln(The interchanged values: ,m, ,n)End.k←mm←nn←kSwap(m,n)Return

اسلاید 72: 72ارتباط بين زيرالگوريتم های تابع و رويه را قاعده زير مشخص می کند. قاعده. هر زيرالگوريتم تابع را می توان همواره بصورت يک زيرالگوريتم رويه در آورد ولی برعکس، در حالتيکه بازگشتی از زيربرنامه بيش از يکی باشد، ممکن نيست.

اسلاید 73: 73x<0x=0sign←1sign←0sign← -1P_sign(x,sign)Returnx<0x=0sign←1sign←0sign← -1sign(x)Return چه چيز تغيير کرد؟ چون قبلا متغير sign (اسم تابع) نتيجه خواسته شده را به واحد فراخوان بازمی گرداند، پس برای اينکه sign همان نقش قبلی را ايفا کند نام زيرالگوريتم را تغيير داديم. ‼ توجه کنيد که اينجا sign يک پارامتر متغير است!

اسلاید 74: 74s≠ts,tyt←sin(w)EndStartP_sign(sin(y),s)P_sign(y,w)s≠ts,tys←sign(sin(y))t←sin(sign(y))EndStart‼ مجدداً تاکيد می کنيم هنگامی که يک مقدار بازگشتی داريد از زيرالگوريتم تابع استفاده کنيد چون هم نوشتن آن راحت است و هم فراخوانی آن.

اسلاید 75: 751) اگر دقيقا يک مورد بازگشتی به واحد فراخوان داريم از تابع استفاده می کنيم، وگرنه رويه را بکار می گيريم. 2) آرگومانهاي ورودي به زيرالگوريتم (پارامترهاي مقدار) را ديگر نبايد در آن زيرالگوريتم توسط دستورهاي خواندن بخوانيم. 3) هيچيک از آرگومانهاي صوري در يک زيربرنامه را ديگر نبايد در بلوک Var آن زيربرنامه تعريف کرد. به عبارت ديگر يک آرگومان صوري نمی تواند در عين حال يک متغير موضعي نيز باشد.

اسلاید 76: 764) اگر از تابع استفاده می کنيم بايد موارد زير را درنظر بگيريم. 4. 1) به معرفی تابع در الگوريتم، و نوشتن دستور معرف در برنامه دقت می کنيم. 4. 2) بازگشت نتيجه اجرای زيرالگوريتم (زيربرنامه) توسط اسم زيربرنامه انجام می گيرد. در نتيجه اسم تابع بايد حداقل يک بار در سمت چپ يک دستورعمل (دستور) انتساب ظاهر شود. 4. 3) اسم تابع (بدون آرگومان) نبايد در سمت راست هيچ دستورعمل (دستور) انتساب ظاهر شود. 4. 5) به فراخوانی درست دقت می کنيم ( فراخواني در دستور مستقل انجام نمی گيرد).

اسلاید 77: 775) اگر از رويه استفاده می کنيم بايد موارد زير را درنظر بگيريم. 5. 1) به معرفی رويه در الگوريتم، و نوشتن دستور معرف در برنامه دقت می کنيم. 5. 2) بازگشت نتيجه اجرای زيرالگوريتم (زيربرنامه) توسط پارامترهای متغير انجام می گيرد. در نتيجه قبل از آنها مشخصه var نوشته می شود. 5. 3) اسم رويه نبايد درطول زيرالگوريتم (زيربرنامه) ظاهر شود. 5. 4) فراخوانی در يک دستور مستقل انجام می گيرد.

اسلاید 78: 78خودفراخواني

اسلاید 79: 79خودفراخواني (Recursion) فني است که در آن يک زيربرنامه، در روند اجراي ناتمام خود، يک يا چند بار خودش را فراخواني می کند. در اينصورت، در روند اجراي اين فراخواني ها کارهاي زير انجام می گيرند که توجه به آنها موجب فراگيري بهتر مفهوم خودفراخواني خواهد شد.

اسلاید 80: 801) هر بار که فراخواني صورت می گيرد، زيربرنامه شروع به اجرا کرده و ابتدا يک لايه در حافظه موقت لايه لايه ای به نام حافظه پشته (Stack memory) توليد، و در هر لايه پارامترهاي مقدار و متغيرهاي موضعي جديد را ذخيره می کند بطوريکه هر لايه از لايه قبلي خود متمايز بوده و می توان تصور نمود که روي آن قرار می گيرد.

اسلاید 81: 812) اين خودفراخواني هاي مکرر تا نقطه برگشت پيش می روند. نقطه برگشت به اولين اجراي کامل زيربرنامه در آخرين فراخواني می گوييم که در آن، ديگر خودفراخواني انجام نمی گيرد و زيربرنامه به طور کامل اجرا می شود.

اسلاید 82: 82با تصور اينکه لايه هاي متمايز حافظه پشته، که هر يک مربوط به يک فراخواني است، روي هم به ترتيب فراخواني چيده شده اند، در نقطه برگشت، لايه مربوط به آخرين فراخواني بالاي تمام لايه ها قرار می گيرد. حال با اتمام اجراي کامل اين زيربرنامه، لايه بالايي از حافظه موقت پاک می شود. سپس کنترل اجرا، به نقطه ای بلافاصله بعد از جايي که آخرين فراخواني صورت گرفته بود منتقل گشته و اجراي ناتمام اين زيربرنامه کامل می گردد.

اسلاید 83: 83با اتمام اجراي اين زيربرنامه نيز, لايه ماقبل آخر از حافظه پشته پاک می گردد. اين روند تا اتمام آخرين اجراي کامل زيربرنامه در اثر اولين فراخواني (صورت گرفته از واحد فراخوان)، و به دنبال آن پاک شدن آخرين (پايين ترين) لايه حافظه پشته، ادامه پيدا می کند. بدين ترتيب اجرای زيربرنامه تمام شده و کنترل اجرا به موقعيتي بلافاصله بعد از جايي که اولين فراخواني توسط واحد فراخوان صورت گرفته بود منتقل می شود.

اسلاید 84: 84يکي از مهمترين کاربردهاي خودفراخواني در محاسبه روابط تراجعي، يا توابع تراجعي، می باشد. متداولترين مثال در اين مورد، رابطه (تابع) فاکتوريل می باشد که با رابطه تراجعي 0!=1 n!=n(n-1)1, و يا با تابع تراجعي تعريف می شود.

اسلاید 85: 85واکنش ذهن براي محاسبه اين رابطه (تابع) براي يک مقدار n ، مثلا 3 ، اين است که بلافاصله به سراغ 0! می رود. آن را برداشته و کار محاسبه را با استفاده از قاعده رابطه (تابع) تا رسيدن به 3! تکرار می کند. اين واکنش سريع را با بياني ساده تجزيه و تحليل می کنيم.

اسلاید 86: 86تصور کنيد که در پشت بام يک آپارتمان سه طبقه (به انضمام يک طبقه همکف) قرار گرفته ايد. فرض کنيد که از محاسبه فاکتوريل يک عدد هيچ اطلاع قبلی نداريد و براي محاسبه 3! از شما خواسته شده که کارهای زير را انجام دهيد: ابتدا تمام طبقات را يک به يک در يک مسير يکطرفه رو به پايين طي کنيد (منظور از يکطرفه يعني اينکه طي عکس مسير امکان پذير نيست).

اسلاید 87: 87در اين مسير يکطرفه رو به پايين، به هر طبقه که وارد می شويد پردازش زير صورت می گيرد: عدد حاصل از پردازش طبقه پايين × شماره اين طبقه = عدد حاصل از پردازش اين طبقه در يک جاي اين پردازش، محاسبه ناتمام باقي مانده و رفتن به طبقه پايين درخواست می گردد. اين کار تا رسيدن به طبقه همکف تکرار می شود. در اين طبقه پردازش زير انجام می شود: = 1 عدد حاصل از پردازش اين طبقه اينجا نقطه برگشت است.

اسلاید 88: 88از اين به بعد، مسيري يکطرفه رو به طبقه بالا را بايد طي کنيد. در اين مسير، به هر طبقه که وارد می شويد محاسبه ای که ناتمام باقي مانده بود، اکنون، با در دست داشتن عدد حاصل از پردازش طبقه پايين تکميل گشته و عدد حاصل به طبقه بالا برده می شود. اين کار تا رسيدن به پشت بام ادامه پيدا می کند. وقتي به پشت بام رسيديد عددي که در دست داريد 3! است.

اسلاید 89: 89حال به نوشتن الگوريتم می پردازيم. ابتدا يک زيرالگوريتم برای ساختن تابع fact با ضابطه بالا می نويسيم. اين زيرالگوريتم يک عدد صحيح نامنفي را گرفته و فاکتوريل آن را با استفاده از ضابطه تابع محاسبه و برگرداند.

اسلاید 90: 90fact(n)n=0Returnfact←1fact←n*fact(n-1)StartEndm<0f←fact(m)mm,’!=’,fm,’is negative’Program P4_5; Uses wincrt; Var m:integer; f:longint; (*******************************) Function fact(n:integer):longint; Begin If n=0 then fact:=1 else fact:=n*fact(n-1) End;{fact} (*******************************) Begin Write(Enter an integer: ); Readln(m); If m<0 then Writeln(m, is negative) else begin f:=fact(m); Writeln(m,!=,f) end End.

اسلاید 91: 91نقطه برگشت6211nnnnBegin Readln(m); . . f:= fact(m); . . .End.Function fact(n:integer):integer;Begin If n=0 then fact:=1 else fact:=n * fact(n-1);End;Function fact(n:integer):integer;Begin If n=0 then factt:=1 else fact:=n * fact(n-1);End;Function fact(n:integer):integer;Begin If n=0 then fact:=1 else fact:=n * fact(n-1);End;Function fact(n:integer):integer;Begin If n=0 then fact:=1 else fact:=n * fact(n-1);End;0123

اسلاید 92: 92در الگوريتم قبلی يک زيرالگوريتم تابع داشتيم که در محاسبه مقدار آن، و در لابلاي محاسبه، خود زيرالگوريتم را فراخواني می کرد. در مثال زير يک زيرالگوريتم رويه خودفراخواني می شود.

اسلاید 93: 93Count(n)n<3Count(n+1)nReturnCount(1)StartEndProgram P4_6; Uses wincrt; (**************************) Procedure Count(n:integer); Begin If n<3 then Count(n+1); Writeln(n) End;{Count} (**************************) Begin Count(1) End.

اسلاید 94: 94نقطه برگشتProcedure Count(n:integer);Begin If n<3 then Count(n+1) Writeln(n)End;Procedure Count(n:integer);Begin If n<3 then Count(n+1) Writeln(n)End;Begin Count(1)End;Procedure Count(n:integer);Begin If n<3 then Count(n+1) Writeln(n)End;nnn321

اسلاید 95: 95در هر زيربرنامه خودفراخوان بايد يک نقطه برگشت وجود داشته باشد. براي اينکه ببينيم در غير اينصورت چه اتفاق می افتد، فرض کنيد که به جاي دستور If n<3 then Count(n+1) فقط دستور Count(n+1) را داشته باشيم.

اسلاید 96: 96Count(1)StartEndProgram P4_6; Uses wincrt; (**************************) Procedure Count(n:integer); Begin If n<3 then Count(n+1); Writeln(n) End;{Count} (**************************) Begin Count(1) End.Count(n)Count(n+1)nReturn

اسلاید 97: 97در اينصورت، نقطه برگشت وجود نخواهد داشت و زيربرنامه بطور بي پايان خودش را فرا خواهد خواند. ولي از آنجا که در هر بار فراخواني يک لايه در حافظه پشته تشکيل می شود، و با توجه به محدود بودن ظرفيت حافظه پشته، پس از مدتي اين حافظه سرريز شده و در نتيجه اعلام خطاي سرريز “Stack over flow” باعث از دست رفتن برنامه، بدون هيچ نتيجه ای خواهد شد.

اسلاید 98: 98يکي ديگر از مثالهاي کلاسيک براي خودفراخوانی زيربرنامه های رويه، معماي تاريخي برجهاي هانوي است. اين مسئله در شکل زير نشان داده شده است. در اين معما بايد ديسکها را از ستون A به ستون C منتقل کنيم مشروط بر اينکه: 1- اگر ديسکي برداشته شد، بايد در يک ستون ديگر قرار داده شود؛ 2- در هر حرکت فقط يک ديسک و آنهم بالاترين ديسک را می توان جابجا کرد؛ 3- يک ديسک بزرگ را نمی توان روي يک ديسک کوچک قرار داد. ABC

اسلاید 99: 99اگر فقط يک ديسک در ستون A وجود داشته باشد، آنگاه بسادگي می توان آنرا با يک حرکت به ستون C منتقل نمود, وگرنه (اگر تعداد ديسکها, n, بيش از يکی باشد) راه حل مسئله به صورت تراجعي انجام می گيرد: الف) تعداد n-1 ديسک از بالاي ستون A را به کمک ستون C به ستون B منتقل می کنيم. ب) تنها ديسک باقي مانده در ستون A را با يک حرکت به ستون C منتقل می نماييم. ج) تعداد n-1 ديسک را از ستون B به کمک ستون A به ستون C حرکت می دهيم.

اسلاید 100: 100با توجه به الگوريتم شفافی که در بالا گفته شد, می توان برنامه را مستقيما، بدون نياز به رسم نمودار گردشی آن، نوشت.

اسلاید 101: 101Number of disks: 4 Move a disk from A to B Move a disk from A to C Move a disk from B to C Move a disk from A to B Move a disk from C to A Move a disk from C to B Move a disk from A to B Move a disk from A to C Move a disk from B to C Move a disk from B to A Move a disk from C to A Move a disk from B to C Move a disk from A to B Move a disk from A to C Move disk from B to CProgram P4_7;Uses wincrt;Const peg1=A; peg2=B; peg3=C;Var n:integer; {Number of disks}(***********************************************)Procedure Move(n:integer;pegA,pegB,pegC:char);Begin If n=1 then Writeln(Move a disk from ,pegA, to ,pegC) else begin Move(n-1,pegA,pegC,pegB); Move(1,pegA,pegB,pegC); Move(n-1,pegB,pegA,pegC) endEnd;{Move}(***********************************************)Begin Write(Number of disks: ); Readln(n); Move(n,peg1,peg2,peg3)End.همانطوريکه می بينيم، هفت حرکت اول سه ديسک را به کمک C به B منتقل می کنند، حرکت هشتم بزرگترين ديسک را از A به C حرکت می دهد. بالاخره هفت حرکت آخر سه ديسک موجود در B را به کمک A به C منتقل می سازند.

اسلاید 102: 102خروج و دستور Exit اجراي دستور Exit باعث می شود که خروج از زيربرنامه انجام گرفته و کنترل اجراي برنامه به بعد از لحظه فراخواني منتقل شود.

اسلاید 103: 103‼ استفاده از Exit در يک زيربرنامه، خروج از آن زيربرنامه را سبب می گردد، ولي اگر از Exit در برنامه اصلي استفاده شود رفتاري مانند Halt داشته و اجراي برنامه را متوقف می سازد. در برنامه P3_18 به جاي Halt می توانستيم Exit را نيز بنويسيم. ‼ برای اينکه ابهامی پيش نيايد به جای Halt از Exit استفاده نکنيد.

اسلاید 104: 104Program P4_8; Uses wincrt; Var a:real; (********************************************) Procedure Test(a:real); Begin If a>0 then begin Writeln(We are in the range of then); Exit end else begin Writeln(We are in the range of else); Halt end End;{Test} (********************************************) Begin Write(Enter a number: ); Readln(a); Test(a); Writeln(We are in the main program) End.