الگوریتم و فلوچارت فصل سوم

الگوریتم و فلوچارت فصل سوم

اسلاید 1: 1الگوریتم و فلوچارتفصل سوم

اسلاید 2: 2 مراحل حل یک برنامه: 1- درک دقیق صورت مسئله- یافتن مفروضات مسئله. مسئله چه می خواهد ، در جستجوی چه باشیم و ارتباط منطقی بین مجهول و معلوم را بیابیم.2- طرح مناسبترین راه حل3- تحلیل راه حل4- نوشتن الگوریتم5- رسم فلوچارت6- نوشتن برنامه روی کاغذ7- وارد کردن برنامه به کامپیوتر8- اجرای برنامه به وسیلۀ کامپیوتر.

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

اسلاید 4: 4الگوریتم و فلوچارتهر دستورالعملی که مراحل انجام کاری را با زبانی دقیق و با جزئیات کافی بیان نماید بطوریکه ترتیب مراحل و شرط خاتمه عملیات در آن کاملا“ مشخص شده باشد را الگوریتم گویند.

اسلاید 5: 5 مراحل الگوريتم براي حل يك مسئله بايد الگوريتم آن مسئله را مشخص كنيم (يا بيابيم). كه اصطلاحاً طراحي الگوريتم براي آن مسئله ناميده مي‌شود. در طراحي الگوريتم معمولاً سه مرحله زير را از هم جدا مي‌كنند: خواندن داده‌ها انجام محاسبات خروجي‌ها

اسلاید 6: 6مثال : الگوريتمي بنويسيد كه دو عدد از ورودي دريافت كرده مجموع دو عدد را محاسبه و چاپ نمايد. خروجي‌ها انجام محاسبات وروديها مجموع دو عدد جمع دو عدد a , b 0ـ شروع 1ـ b ,a را بخوان.2ـ مجموع b , a را محاسبه و در sum قرار بده.3ـ sum را در خروجي چاپ كن 4ـ پايان

اسلاید 7: 7 مثال: الگوريتمي بنويسيد كه عدد برحسب سانتیمتر را از ورودی گرفته درحالت Negative مثبت آن را به متر تبدیل کرده و چاپ نماید، در غیر این صورت پیامچاپ گردد.0ـ شروع1ـ مقدار a را بخوان2ـ اگر a>0 است برو به مرحلۀ 5.3- چاپ کن Negative 4- برو به مرحلۀ 7.5- حاصل a/100 را بدست آورده و در s قرار بده.6- s را در خروجي چاپ كن.7- پايان. خروجي‌ها انجام محاسبات وروديها نمایش عدد تبدیل به متر در صورت مثبت بودن آن a Negative در غیر این صورت

اسلاید 8: 8خروجي‌ها انجام محاسبات وروديها چاپ مجموع محاسبه مجموع a چاپ ميانگين محاسبه ميانگين b c مثال: الگوريتمي بنويسيد كه سه عدد از ورودي دريافت كرده مجموع و ميانگين سه عدد را محاسبه و چاپ كند.0ـ شروع1ـ سه عدد از ورودي بخوان2ـ مجموع سه عدد را محاسبه و در sum قرار بده.3ـ sum را بر سه تقسيم كرده،در ave قرار بده.4ـ ave , sum را در خروجي چاپ كن.5ـ پايان.

اسلاید 9: 9معمولا درك يك الگوريتم با شكل راحتر از نوشتن آن بصورت متن مي‌باشد. لذا الگوريتم را با فلوچارت( flowchart )نمايش مي‌دهند. فلوچارت از شكل‌هاي زير تشكيل مي‌شود. (بیان تصویری الگوریتم)

اسلاید 10: 10startstopc←a+bd← iA,BA,B,”100”?ورودیخروجیخروجیخروجی

اسلاید 11: 11مثال1: فلوچارتی رسم کنید که دو عدد را خوانده ، حاصلضرب آنها محاسبه و نمایش داده شود.BeginRead(A,B)z←A*BWrite(A,B.z)End

اسلاید 12: 12BeginRead(a,b,c)Sum a+b+cAve sum/3Write(sum,ave)Endفلوچارت مجموع و میانگین سه عدد

اسلاید 13: 13مثال: فلوچارتی رسم کنید که شعاع یک دایره را خوانده مساحت و محیط آنرا نمایش دهد.BeginEndRead(R)A←3.14*R²P←2*R*3.14Write(A,P)

اسلاید 14: 14مثال: فلوچارتی رسم نمائيد كه دو عدد از ورودي دريافت كرده سپس محتويات دو عدد را با هم جابجا ‌نمايد.راه اول : استفاده از متغیر کمکیبراي حل اين مسئله b , a را دو متغير كه در آنها دو عدد خوانده شده، قرار مي‌گيرند در نظر مي‌گيريم. سپس با استفاده از يك متغير كمكي محتويات اين دو عدد را جابجا مي‌كنيم :

اسلاید 15: 151215tempab1215abtemp1512abtemp1512abtemp

اسلاید 16: 16BeginRead(a,b)temp aa bWrite(a,b)Endb tempفلوچارت مسئله بالا بصورت زير خواهد بود:

اسلاید 17: 17روش دوم: استفاده ازعملیات ریاضی BeginRead(A,B)Write(A,B)َA←A+BB←A-BA←A-BWrite(A,B)End

اسلاید 18: 18 تمرين1ـ فلوچارتي رسم نمائيد كه طول و عرض مستطيل را از ورودي دريافت كرده محيط و مساحت آنرا محاسبه و چاپ كند.2ـ فلوچارتي رسم نمائيد كه عددي (درجه حرارت برحسب سانتيگراد) را از ورودي دريافت كرده سپس آنرا به درجه فارنهايت تبديل كند.

اسلاید 19: 19 دستورالعمل‌هاي شرطي در حل بسياري از مسائل يا تقريباً تمام مسائل نياز به استفاده از شروط جزء، نيازهاي اساسي محسوب مي‌شود. همانطور كه ما خودمان در زندگي روزمره با اين شرط‌ها سركار داريم. بطور مثال اگر هوا ابري باشد ممكن است چنين سخن بگوييم: اگر هوا باراني باشد سپس چتري برمي‌دارم. در غير اينصورت چتر برنمي‌دارم.

اسلاید 20: 20در حالت كلي شرط را بصورت زير نمايش مي‌دهند:If شرط یا شروط thenعمل يا اعمال yes NOعمل يا اعمال بعدي

اسلاید 21: 21مثال : فلوچارتي رسم نمائيد كه عددي را از ورودي دريافت كرده، فرد يا زوج بودن آن را تشخيص دهد.BeginRead(a)R a mod 2Write(‘odd’)Endif R=0 thenNoyesWrite(‘even’)

اسلاید 22: 22BeginRead(a,b)max a Write(max)Endif b>maxNoyes max bمثال : فلوچارتي رسم كنيد كه دو عدد از ورودي دريافت كرده بزرگترين عدد را پيدا كرده در خروجي چاپ نمايد.max b

اسلاید 23: 23فلوچارتی رسم کنید که سه عدد را خوانده و بصورت زیر تصمیم گیری نماید: - اگر عدد سوم صفر بود حاصل جمع دو عدد دیگر - اگر عدد سوم منفی بود تفاضل دو عدد دیگر - در غیر حالتهای فوق حاصل ضرب دو عدد دیگر را نمایش دهد.

اسلاید 24: 24شروعRead(A,B,C)C=0C<0D←A+BYND←A-BYD←A*BWrite(D)پایانN

اسلاید 25: 25مثال:فلوچارتی رسم کنید که سه ضلع یک مثلث را خوانده، تعیین کنید آیا مثلث قائم الزاویه است یا خیر؟ برای قائم الزاویه بودن مثلث اندازه اضلاع آن باید در یکی از عبارات زیر صدق کند.A²=B²+C² یا B²=A²+C² یا C²=A²+B²شروعRead(A,B,C)A²=B²+C²YNB²=A²+C²YNC²=B²+A²YNWrite(“NO”)Write(“YES”)پایان

اسلاید 26: 26مثال:ریشه های یک معادله درجه دومAX²+BX+C=0D=B²-4ACاگر D<0 ، معادله ریشه ندارداگر D=0 ، حاصل عبارت –B/2A را در X1و X2 قرار بدهحاصل عبارت را در X1 قرار بدهحاصل عبارت را در X2 قرار بدهمقادیر X1 و X2 را نمایش بده

اسلاید 27: 27شروعA,B,CD<0YND=0YNX1← -B/2AX2← X1“No root”X1,X2پایان

اسلاید 28: 28 حلقه‌ها(Loop) در حل بسياري از مسائل با عملياتي روبرو مي‌شويم ، كه نياز به تكرار دارند و عمل تكرار آنها به تعداد مشخص یا نامشخصی انجام مي‌گيرد.

اسلاید 29: 29انواع حلقه هاحلقه های با تکرار مشخصحلقه های با تکرار نا مشخص

اسلاید 30: 30حلقه های با تکرار مشخص ( به حلقه for مشهورند.)در اين نوع حلقه‌ها تعداد تكرار مشخص مي‌باشد اين حلقه ها از اجزاء زير تشكيل مي‌شود:1ـ انديس حلقه 2ـ مقدار اوليه براي انديس حلقه 3- مقدار افزاينده براي انديس حلقه (معمولا يك واحد در هر مرحله)4ـ مقدار نهايي (تعداد تكرار حلقه)5ـ شرطي براي كنترل تعداد تكرار حلقه

اسلاید 31: 31i 1 if i<=n yesNoمجموعه دستورات حلقه i i+1اتمام كار حلقه اين حلقه‌ها را غالباً با فلوچارت بصورت زير نمايش مي‌دهند:

اسلاید 32: 32مثال : فلوچارتي رسم نمائيد كه عدد n را از ورودي دريافت كرده، مجموع اعداد از يك تا n را محاسبه كند.i انديس حلقه n مقدار نهايي

اسلاید 33: 33BeginRead(n)I 1 sum 0if I<=nyesNoWrite(sum)Endsum sum+II I+1حلقه

اسلاید 34: 34مثال : فلوچارت برنامه ای را رسم کنید که 10 عدد را گرفته و تعیین کند کدام زوج و کدام فرد است.شروعi ← 0Read (p)k ← p-INT(p/2)*2K=0ynp, “odd”i ← i+1i< 10nyپایانP, “even”

اسلاید 35: 35مثال : فلوچارت برنامه ای را رسم کنید که عدد طبیعی N>1 را خوانده و مقسوم علیه های آن را نمایش دهد شروعNM ← 1K=0YNMM ← M+1M<=NYNپایان

اسلاید 36: 36مثال : فلوچارتي رسم كنيد كه n عدد از ورودي دريافت كرده، بزرگترين مقدار از بين n عدد را پيدا كرده در خروجي چاپ نمايد.انديس حلقه iمقدار نهايي nبزرگترين مقدار Max

اسلاید 37: 37BeginI 2 max a if i<=n thenyesNowrite(max)Endi i+1حلقهRead(a)Read(n,a)if a > maxmax aNoyesn تعداد اعدادa اولین عدد

اسلاید 38: 38مثال : فلوچارتي رسم نمائيد كه n , x ، دو عدد صحيح مثبت را از ورودي دريافت كرده سپس x به توان n را محاسبه كند.انديس حلقه iمقدار نهايي nعدد به توان n pow

اسلاید 39: 39Begini 1 pow 1 if i<=n thenyesNowrite(pow)Endpow pow*xحلقهRead(n,x)i i+1

اسلاید 40: 40 حلقه‌هايي كه تعداد تكرار آنها مشخص نيست ( به حلقه while مشهورند.)در اين حلقه‌ها با توجه به ورودي، تعداد تكرار مشخص مي‌شود. و دقيقاً نمي‌‌توان تعداد تكرار حلقه را بدون ورودي معين كرد. اين حلقه ها فقط شامل شرطي هستند كه تا زمانيكه برقرار باشد حلقه اجرا مي‌شود.

اسلاید 41: 41If شرط يا شروطمحموعه دستورالعملها و جاگزينها yesNo در حالت كلي اين نوع حلقه‌ها بصورت زير نمايش داده مي‌شوند:

اسلاید 42: 42مثال: فلوچارتي رسم كنيد كه عددي را از ورودي دريافت كرده سپس تعداد ارقام آن را شمرده در خروجي چاپ نمايد.عدد خوانده شده N تعداد ارقام count

اسلاید 43: 43Begincount 0 if N>0 thenyesNowrite(count)EndN N div 10حلقهRead(N)count count+1

اسلاید 44: 44مثال : فلوچارتي رسم نمائيد كه 20 جمله اول، سري فيبوناچي را توليد نمايد.در سری فیبوناچی هر عدد برابر است با مجموع دو عدد قبلی خود.1,1,2,3,5,8,13,21,…

اسلاید 45: 45s=0A=1B=0C=1+0=1 1A=0B=1S=0+1=1 1<20 “yes”C=0+1=1 1A=1B=1S=1+1=22<20 “yes”C=1+1=2 2A=1B=2S=2+1=33<20 “yes”……شروعS ← 0A ← 1B ← 0C ← A+BC A ← BB ← CS ← S+1S < 20NپایانY

اسلاید 46: 46الگوریتم برنامه ای را بنویسید که یک عدد صحیح مثبت را خوانده جذر آن را نمایش دهد. در این روش جذر دقیق عدد N عبارت است از شمارش کلیه اعداد فردی که مجموع آنها برابر N باشد و اگر کاملا“ برابر نبودند جذر تقریبی گفته می شود.مثال:

اسلاید 47: 47شروعNS ← 0C ← 0A ← 1S ← S+AS > = NNYC ← C+1A ← A+2N,CپایانN=16S=0C=1A=1مقادیر اولیهS=0+1=1 NoC=1+1=2A=1+2=3S=1+3=4 NOC=2+1=3A=3+2=5S=4+5=9 NOC=3+1=4A=5+2=7S=9+7=16 YES 16 , 4 مجموعS شمارندهC تولید اعداد فردA

اسلاید 48: 48 حلقه‌هاي تودرتو الگوريتم‌‌هايي كه تا حال بكار برديم، فقط شامل يك حلقه بودند.در صورتي كه در بسياري از مسائل ممكن است نياز به استفاده از چندحلقه در داخل هم باشيم. در اين نوع حلقه‌ها بايد دقت بيشتري به خرج دهيم، تا مشكلي پيش نيايد. اگر از حلقه‌هاي نوع اول بصورت تودرتو استفاده كنيم در اينصورت براي هر حلقه شرط نهايي و انديس اوليه جداگانه بايد تعريف كنيم .

اسلاید 49: 49در حلقه‌هاي تودرتو به ازاي يكبار تكرار حلقه اوليه، حلقه داخلي به اندازه مقدار نهايي خود تكرار مي‌شود. در كل اگر حلقه اوليه n بار تكرار شود وحلقه داخلي m بار، در اينصورت كل حلقه : بار تكرار خواهد شد.

اسلاید 50: 50فلوچارت حلقه‌هاي تودرتو را مي‌توان بصورت زير نشان داد:i 1 if j<=m thenNoحلقه داخلی j j+1yes...if i<=n thenj 1مجموعه دستورات و جايگزيني ها مجموعه دستورات و جايگزيني ها i i+1AAyesNoاتمام كار حلقه هاي تو در تو

اسلاید 51: 51فلوچارت برنامه ای را رسم نمایید که جدول ضرب 1 تا 10 را با استفاده از حلقه های تو در تو ایجاد نماید.

اسلاید 52: 52starti ← 1i >=10YstopNj ← 1j >=10p ← i * jj ← j+1i ← i+1pYNداخلیخارجی

اسلاید 53: 53 را خوانده، عبارت زیر را N و Xالگوریتم برنامه ای را بنویسید که دو عدد محاسبه و نمایش دهد.N تعداد جملات سریعلامت ! فاکتوریل عدد را نشان می دهد

اسلاید 54: 54شروعN , Xe ← 0I ← 0Fact ← 1J ← 1Fact ← Fact * jJ ← J+1J <=INYI <NNYe پایانI ← I+1برای چهار جمله اول:N=4 , X=2 مقادیر اولیه:e=0 ,I=0FACT=1 , J=1FACT=1* 1=1J=1+1=22<= 0 “NO”e=0+Xº / 1=1I=0+1=11<4 “YES”FACT=1 , J=1FACT=1* 1=1 , J=22<=1 “NO”e=1+ X¹ /1 =1+XI=1+1=22<4 “YES”FACT=1 , J=1FACT=1*1=1J=1+1=22< = 2 “YES”FACT= 1*2=2J=2+1=33<=2 “NO”e=1+X+X² / 2I=2+1=33<4 “YES”FACT=1 , J=1FACT=1*1=1J=1+1=22<= 3 “YES”FACT=1* 2=2J=2+1=33<=3 “YES”FACT=2*3=6J=3+1=44 < 3 “NO”e=1+x+x²/2 +x³/6I=3+1=44 < 4 “NO”E=1+x+x²/2+x³/6

اسلاید 55: 55انديس حلقه اول I ورودي N ‌محاسبه فاكتوريل fact انديس حلقه داخلي j مجموع Sum مثال : فلوچارتي رسم نمائيد كه N را از ورودي دريافت كرده، مجموع سري زير را محاسبه نمايد:

اسلاید 56: 56i 2sum 1 Aif j<=i Nofact fact*jyesif i<=N fact 1j 2i i+1yesNoRead(N)Endsum sum+i/factAj j+1Write(sum)

اسلاید 57: 57كاربرد آرايه ها در الگوريتم ها

اسلاید 58: 58مقدمهفرض كنيد بخواهيم اطلاعات 100 كارمند را از ورودي بخوانيم و سپس آنها را مرتب كنيم، در اينصورت بايد وروديها را در جايي از حافظه ذخيره كنيم. در زبانهاي برنامه‌نويسي معمولا از آرايه براي ذخيره اطلاعات در حافظه استفاده مي‌كنند. در آرايه‌ها ما با توجه به تعداد وروديها، طول آن را مشخص مي‌كنيم. سپس داده‌ها را خوانده در آن قرار مي‌دهيم.

اسلاید 59: 59 تعريف آرايهخانه‌هاي پشت سر هم از حافظه، كه همنوع بوده و توسط يك اسم معرفي مي‌شوند، آرايه نام دارد. نحوه دسترسي به هر يك از اعضاء آرايه، از طريق انديس آرايه امكانپذير است . براي تعريف آرايه ابتدا طول آرايه كه در حقيقت تعداد خانه‌هاي آن را مشخص مي‌كند، معين مي‌كنيم. سپس نوع خانه‌ها بايد معين شوند.در فلوچارت‌ها آرايه‌ها را بصورت زير نمايش مي‌دهيم:Name[ 1 .. Length ] طول آرايه اسم آرايه

اسلاید 60: 60براي خواندن يك آرايه از ورودي از حلقه‌ها استفاده مي‌كنيم. فلوچارت خواندن آرايه از ورودي بصورت زير مي‌باشد:a[1..100]if i<=100 Noyes Read(a[i])i i+1i 1

اسلاید 61: 61با توجه به فلوچارت بالا براي دسترسي به عنصر iام آرايه در حالت كلي بصورت : Nam [ index ] انديس آرايه اسم آرايه عمل مي‌كنند.مثال: فلوچارتي رسم كنيد كه يك آرايه حداكثر 100 عنصري را از ورودي دريافت كرده، سپس آن را خروجي نمايش دهد.

اسلاید 62: 62a[1..100]i 1if i<=N Noyes Read(a[i])i i+1BeginRead(N)i 1if i<=N yes write(a[i])i i+1NoEnd

اسلاید 63: 63مثال : فلوچارتي رسم كنيد كه عددي را از ورودي دريافت كرده آن را به مبناي 2 ببرد.a[1..20]i 1if N>0 NoyesN N div 2Read(N)i i-1if i >0 yes write(a[i])i i-1NoEnd a[i] N mod 2i i+1