فصل۴ برنامه نویسی

فصل۴ برنامه نویسی

اسلاید 1: مبانی کامپیوتر و برنامه سازیفصل چهارم : آرایه هامدرس : مهدی اکبری زرکش

اسلاید 2: 4 متغیرهای اندیسدار یا آرایه هادر مثالهایی که در فصل قبل بیان گردید، از متغیرهای معمولی استفاده گردید. اما گاهی نیاز به تعداد زیادی متغیر برای نگاهداری داده ها داریم. درچنین مواردی نه تنها برای نامگذاری این متغیرها دچار مشکل می شویم، بلکه دسترسی به تک تک آنها نیز مشکل است. مثال ) الگوریتمی بنویسید که شماره دانشجویی، نام و معدل تعدادی دانشجو را بخواند و مشخصات دانشجویانی را که معدل آنها از میانگین معدل کلاس بیشتر است را چاپ کند.برای حل این مثال ابتدا باید مشخصات و معدل کلیه دانشجویان دریافت شود تا بتوانیم میانگین معدل های آنان را محاسبه کنیم. سپس باید معدل تک تک دانشجویان با میانگین کلاس مقایسه گردد. مسلما نمی توانیم مجددا از کاربر بخواهیم که همان اطلاعات قبلی را مجددا وارد کند، بلکه باید از قبل آنها را در درون متغیرهایی ذخیره کرده باشیم تا اکنون بتوانیم مقایسه را انجام دهیم. برای اینکار نیاز به تعدادی متغیر (به تعداد دانشجویان مثلا 100 عدد) داریم که ما را دچار 2 مشکل اساسی می کند :این متغیرها را چگونه نامگذاری کنیم ؟بر فرض نامگذاری متغیرها برطبق یک روش خاص، چگونه تک تک آنها را با میانگین کل مقایسه کنیم؟ آیا باید برای مقایسه هر کدام یک دستور مجزا بنویسیم ؟

اسلاید 3: 1-4 آرایه های یک بعدی تعریف آرایه : مجموعه ای از داده های همنوع است که تحت یک نام مشترک ذخیره می گردند.برای دسترسی به هریک از اعضا یا عناصر آرایه از نام آرایه بعلاوه یک اندیس استفاده می شود. بنابراین هر عنصر آرایه درحقیقت یک متغیر مستقل از همان نوع مورد نظر است.یک آرایه پیش از آنکه استفاده گردد باید اعلان شود. اعلان آرایه شامل نام آرایه و اندازه آن است. عناصر آرایه برای سهولت در دسترسی (معمولا) در خانه های پشت سرهم حافظه ذخیره می گردند.مثال) آرایه A را با 100 عضو درنظر بگیر..........A(1)A(2)A(3)A(4)A(i)A(100)

اسلاید 4: 1-4 آرایه های یک بعدیمثال) الگوریتمی بنویسید که شماره دانشجویی، نام و معدل تعدادی دانشجو را بخواند و مشخصات دانشجویانی را که معدل آنها از میانگین معدل کلاس بیشتر است را چاپ کند n را بخوانآرایه های idList و nameList و aveList را با n عنصر درنظر بگیر.i ← 1 و sum ← 0تازمانیکه ( i ≤ n ) دستورات 5 تا 8 را تکرار کنچاپ کن مشخصات دانشجوی ، i ، را وارد کنیدidList(i) و nameList(i) و aveList(i) را بخوانsum ← sum + aveList(i)i ← i + 1totalAve ← sum / ni ← 1 تازمانیکه ( i ≤ n ) دستورات 12 تا 13 را تکرار کناگر ( aveList(i) ≥ totalAve) آنگاهidList(i) و nameList(i) و aveList(i) را چا پ کنi ← i +1 توقف کن

اسلاید 5: 1-4 آرایه های یک بعدیالگوریتمی بنویسید که تعدادی عدد را دریافت و سپس ابتدا اعداد مثبت و سپس اعداد منفی را بطور جداگانه چاپ کند.n را بخوانآرایه های positive و negative را با n عنصر درنظر بگیرi ← 1 و posCount ← 0 و negCount ← 0تازمانیکه ( i ≤ n ) دستورات 5 تا 7 را تکرار کنadad را بخواناگر ( adad ≥ 0 ) آنگاه posCount ← posCount + 1 و positive(posCount) ← adadدر غیراینصورت negCount ← negCount + 1 و negative(negCount) ← adadi ← i + 1چاپ کن لیست اعداد مثبتi ← 1تازمانیکه ( i ≤ posCount ) دستورات 11 تا 12 را تکرار کنچاپ کن positive(i)i ← i + 1چاپ کن لیست اعداد منفیi ← 1تازمانیکه ( i ≤ negCount ) دستورات 16 تا 17 را تکرار کنچاپ کن negative(i)i ← i + 1توقف کن

اسلاید 6: 1-4 آرایه های یک بعدیالگوریتمی بنویسید که دو مجموعه از اعداد را خوانده و در دو آرایه قرار دهد. سپس اشتراک آن دو را محاسبه و در یک آرایه دیگر قرار دهد. در پایان اشتراک حاصل را چاپ کند.n و m را بخوانآرایه A را با n عنصر و آرایه B را با m عنصر در نظر بگیر.آرایه C را با min(n,m) عنصر درنظر بگیرآرایه های A با n عنصر و B با m عنصر را بخوان (البته نیاز به حلقه دارد)aCount ← 1 و cCount ← 0تا زمانیکه ( aCount ≤ n) دستورات 7 تا 11 را تکرار کنbCount ← 1 و sw ← 1تازمانیکه ( bCount ≤ m and sw = 1) دستورات 9 تا 10 را تکرار کناگر ( A(aCount) = B(bCount) ) آنگاهcCount ← cCount + 1 و C(cCount) ← A(aCount) و sw ← 0bCount ← bCount + 1aCount ← aCount + 1چاپ کن اشتراک دو مجموعه برابر است با :i ← 1تازمانیکه ( i ≤ cCount ) دستورات 15 تا 16 را تکرار کنC(i) را چاپ کنi ← i + 1توقف کن

اسلاید 7: 1-4 آرایه های یک بعدیآزمایش الگوریتم اشتراک23103517234510358172612A19352333172110BCaCountbCountcCount

اسلاید 8: 1-4 آرایه های یک بعدیالگوریتمی مثال قبل را برای اجتماع دو مجموعه تکرار کنید.n و m را بخوانآرایه A را با n عنصر و آرایه B را با m عنصر در نظر بگیر.آرایه C را با n+m عنصر درنظر بگیرآرایه های A با n عنصر و B با m عنصر را بخوان (البته نیاز به حلقه دارد)i ← 1تا زمانیکه ( i ≤ n ) دستورات 7 تا 8 را تکرار کنC(i) ← A(i)i ← i + 1bCount ← 1 و cCount ← nتا زمانیکه ( bCount ≤ m) دستورات 11 تا 16 را تکرار کنaCount ← 1 و sw ← 1تازمانیکه ( aCount ≤ n and sw = 1) دستورات 13 تا 14 را تکرار کناگر ( A(aCount) = B(bCount) ) آنگاه sw ← 0aCount ← aCount + 1 اگر (sw = 1) آنگاه cCount ← cCount + 1 و C(cCount) ← B(bCount)bCount ← bCount + 1چاپ کن اجتماع دو مجموعه برابر است با :i ← 1تازمانیکه ( i ≤ cCount ) دستورات 15 تا 16 را تکرار کنC(i) را چاپ کنi ← i + 1توقف کن

اسلاید 9: 1-4 آرایه های یک بعدیالگوریتمی بنویسید که یک لیست را گرفته و پس از حذف اعداد تکراری آن، حاصل را در یک لیست دیگر قرار دهد.n را بخوانآرایه A و B را با n عنصر درنظر بگیرآرایه A را با n عنصر بخوانB(1) ← A(1)i ← 2 و k ← 1تا زمانیکه ( i ≤ n ) دستورات 7 تا 11 را تکرار کنj ← 1تازمانیکه ( j ≤ k and A(i) ≠ B(j) ) دستور 9 را تکرار کنj ← j + 1اگر ( j > k) آنگاه k ← k + 1 و B(k) ← A(i)i ← i + 1لیست B را با k عضو چاپ کن (نیاز به حلقه دارد)توقف کن

اسلاید 10: 1-4 آرایه های یک بعدیالگوریتم مثال قبل را بگونه ای تغییر دهید که عملیات حذف داده های تکراری را درخود آرایه اصلی (بدون کمک آرایه دیگر) انجام دهد.n را بخوانلیست A را با n عنصر در نظر بگیرلیست A را با n عنصر بخوان (نیاز به حلقه دارد)i ← 1تازمانیکه ( i ≤ n ) دستورات 6 تا 9 را تکرار کنj ← i + 1تازمانیکه ( j ≤ n ) دستور 8 را تکرار کناگر ( A(i) = A(j) ) آنگاه A(j) ← A(n) و n ← n - 1i ← i + 1لیست A را با n عضو چاپ کنتوقف کن

اسلاید 11: 1-4 آرایه های یک بعدیالگوریتمی بنویسید که یک لیست مرتب بصورت صعودی از اعداد و یک عدد را از کاربر دریافت و سپس بدنبال داده در لیست جستجو کند و آن را حذف نماید.n را بخوانآرایه A را با n عنصر درنظر بگیرآرایه A را با n عنصر بخوان (بصورت مرتب شده)x را بخوان i ← 1تازمانیکه ( i ≤ n and x≠A(i) ) دستور 7 را تکرار کنi ← i + 1اگر ( i > n ) چاپ کن عدد پیدا نشد و توقف کنتازمانیکه ( i < n ) دستورات 10 تا 11 را تکرار کنA(i) ← A(i + 1) i ← i + 1n ← n -1آرایه A را با n عضو چاپ کنتوقف کن

اسلاید 12: 1-4 آرایه های یک بعدیآزمایش الگوریتم حذف از لیست مرتب1218213538424448Ai5258n = 10x = 38n = 9

اسلاید 13: 1-4 آرایه های یک بعدیالگوریتمی بنویسید که یک لیست مرتب بصورت صعودی از اعداد را از کاربر دریافت و سپس با دریافت یک عدد جدید از کاربر آن را درمکان مناسب لیست درج کند بطوریکه ترتیب حفظ شود.n را بخوانآرایه A را با n + 1 عنصر درنظر بگیرآرایه A را با n عنصر بخوان (بصورت مرتب شده)x را بخوان i ← nتازمانیکه ( i ≥ 1 and x < A(i) ) دستورات 7 تا 8 را تکرار کنA(i + 1) ← A(i)i ← i – 1A(i + 1) ← xn ← n + 1آرایه A را با n عضو چاپ کنتوقف کن

اسلاید 14: 1-4 آرایه های یک بعدیآزمایش الگوریتم درج در لیست مرتب1218213538424448Ai5258n = 10x = 3939n = 11

اسلاید 15: 1-4 آرایه های یک بعدیالگوریتمی بنویسید که یک عدد را دریافت و عددی که بیشترین تکرار را دارد چاپ کند.n را بخوانآرایه های A و sw را با n عضو درنظر بگیرآرایه A را با n عضو بخوانتمام عناصر آرایه sw را برابر 0 قرار بده mod ← 0 و modNo ← 0i ← 1تازمانیکه ( i ≤ n) دستورات 7 تا 8 را تکرار کناگر ( sw(i) = 0 ) آنگاهsw(i) ← 1j ← i + 1 و sum ← 0تازمانیکه ( j ≤ n ) دستورات d تا e را تکرار کناگر ( A(i) = A(j) ) آنگاه sum ← sum + 1 و sw(j) ← 1j ← j + 1اگر ( sum > modNo) آنگاه mod ← A(i) و modNo ← sumi ← i + 1mod و modNo را چاپ کنتوقف کن

اسلاید 16: 1-4 آرایه های یک بعدیالگوریتمی بنویسید که برای تعداد دانشجو، کد رشته (از 1 تا 15) را خوانده و سپس تعداد دانشجویان هررشته را به تفکیک چاپ کند.آرایه count را با 15 عضو درنظر بگیرتمام عناصر آرایه count را برابر 0 قرار بدهn را بخوانi ← 1تازمانیکه ( i ≤ n) دستورات 6 تا 8 را تکرار کنcode را بخوانcount(code) ← count(code) + 1i ← i + 1آرایه count را با 15 عضو چاپ کنتوقف کن

اسلاید 17: 2-4 آرایه های چندبعدیمسائلی که تاکنون حل شدند نیاز به آرایه های یک بعدی داشتند. هر عنصر از این آرایه ها تنها با یک اندیس مشخص می گردد. اما گاهی در مسائل پیچیده تر نیاز به آرایه هایی است که هر عضو آنها نیاز به بیش از یک اندیس دارد، که به آنها آرایه های چند بعدی گفته می شود. چنانچه هر عنصر آرایه به 2 اندیس نیاز داشته باشد، به آن آرایه دو بعدی می گوییم. برای تعریف یک آرایه دوبعدی باید تعداد سطرها و ستونهای آن را مشخص کنیم. معمولا یک آرایه دو بعدی بصورت m × n اعلان می گردد که m تعداد سطرها و n تعداد ستونها است.

اسلاید 18: 2-4 آرایه های چندبعدیبعنوان مثال چنانچه آرایه A را بعنوان یک آرایه دوبعدی به ابعاد 5 × 8 تعریف کنیم، آنگاه داریم : سطرستون1234512345678A(3,4)A(2,7)

اسلاید 19: 2-4 آرایه های چندبعدیبرای آرایه های سه بعدی نیز مفاهیم مشابهی قابل طرح است. در این آرایه ها هر عنصر نیاز به 3 اندیس دارد و برای تعریف آنها را بصورت p × m × n اعلان می کنیم که p عمق، m تعداد سطرها و n تعداد ستونها است. بعنوان مثال چنانچه آرایه B بعنوان یک آرایه سه بعدی به ابعاد 3 × 4 × 6 تعریف شود، خواهیم داشت :سطرستونعمقB(2,6,1)B(1,4,2)

اسلاید 20: 2-4 آرایه های چندبعدیالگوریتمی بنویسید که برای تعدادی دانشجو، شماره دانشجویی و کد رشته (از 1 تا 15) را خوانده و سپس دانشجویان هررشته را به تفکیک چاپ کند.n را بخوانآرایه دوبعدی student را به ابعاد 15 × n در نظر بگیرآرایه count را با 15 عنصر در نظر بگیر و تمام عناصر آن را برابر 0 قرار بدهi ← 1تازمانیکه ( i ≤ n ) دستورات 6 تا 9 را تکرار کنid و code را بخوانcount(code) ← count(code) + 1student( code , count(code) ) ← idi ← i + 1چاپ کن لیست دانشجویانi ← 1تازمانیکه ( i ≤ 15) دستورات 13 تا 18 را تکرار کنچاپ کن رشته ، ij ← 1تازمانیکه ( j ≤ count(i) ) دستورات 16 تا 17 را تکرار کنstudent( i , j ) را چاپ کنj ← j + 1i ← i + 1توقف کن

اسلاید 21: 2-4 آرایه های چندبعدیالگوریتمی بنویسید که برای تعدادی دانشجو، شماره دانشجویی و کد محل تحصیل (از 1 تا 10) و کد رشته (از 1 تا 15) را خوانده و سپس دانشجویان هر رشته را به تفکیک چاپ کند.n را بخوانآرایه سه بعدی student را به ابعاد 10 × 15 × n در نظر بگیرآرایه count را با 1510 × عنصر در نظر بگیر و تمام عناصر آن را برابر 0 قرار بدهi ← 1تازمانیکه ( i ≤ n ) دستورات 6 تا 9 را تکرار کنid و cityCode و studyCode را بخوانcount(cityCode,studyCode) ← count(cityCode,studyCode) + 1student( cityCode , studyCode , count(cityCode , studyCode) ) ← idi ← i + 1چاپ کن لیست دانشجویانi ← 1تازمانیکه ( i ≤ 10) دستورات 13 تا 22 را تکرار کنچاپ کن محل ، ij ← 1تازمانیکه ( j ≤ 15 ) دستورات 16 تا 21 را تکرار کنچاپ کن کد رشته ، j k ← 1تازمانیکه ( k ≤ count(i,j) ) دستورات 19 تا 20 را چاپ کنstudent( i , j , k) را چاپ کنk ← k + 1j ← j + 1i ← i + 1توقف کن

اسلاید 22: 2-4 آرایه های چندبعدی50 موضوع مختلف را به رای گذاشته ایم و هرکس می تواند آرای خود را بشرح زیر اعلام کند:1- موافق2- مخالف3- ممتنع4- بی اطلاعالگوریتمی بنویسید که تعداد افراد رای دهنده را دریافت و سپس پس از دریافت آرای هریک از آنان برای هر 50 موضوع، تعداد آرای مختلف هر موضوع را به تفکیک چاپ کند.n را بخوانi ← 1تازمانیکه ( i ≤ n ) دستورات را 5 تا 11 تکرار کنj ← 1تازمانیکه ( j ≤ 50 ) دستورات 7 تا 10 را تکرار کنچاپ کن موضوع ، jvote را بخوانcount(j , vote) ← count(j , vote) + 1j ← j + 1i ← i + 1آرایه count را به ابعاد 50 × 4 چاپ کن (نیاز به حلقه دارد)توقف کن

اسلاید 23: 2-4 آرایه های چندبعدیالگوریتمی بنویسید که دو ماتریس را از کاربر دریافت و حاصلضرب آن دو را محاسبه و چاپ کند.m و n را بخوان (ابعاد ماتریس اول m × n)p و q را بخوان (ابعاد ماتریس دوم p × q)اگر ( n ≠ p ) آنگاه چاپ کن ماتریسها قابل ضرب نیستند و توقف کنآرایه A را به ابعاد m × n و آرایه B را به ابعاد p × q درنظر بگیرآرایه C را به ابعاد m × q درنظر بگیرآرایه A را به ابعاد m × n بخوانآرایه B را به ابعاد p × q بخوانi ← 1تازمانیکه ( i ≤ m) دستورات 10 تا 18 را تکرار کنj ← 1تازمانیکه ( j ≤ q) دستورات 12 تا 17 را تکرار کنsum ← 0 و k ← 1تازمانیکه (k ≤ n) دستورات 14 تا 15 را تکرار کنsum ← sum + A(i,k) × B(k,j)k ← k + 1C(i,j) ← sumj ← j + 1i ← i + 1آرایه C را به ابعاد m × q چاپ کنتوقف کن

اسلاید 24: 2-4 آرایه های چندبعدیدریک آزمون دانشجویان باید به 20 سوال 4 گزینه ای جواب بدهند. الگوریتمی بنویسید که ابتدا جواب درست سوالات را دریافت و سپس برای تعدادی دانشجو برگه پاسخنامه را دریافت و نمره آنها را محاسبه و چاپ کند. پاسخنامه ها در یک آرایه دوبعدی 20 × 4 است که در جاهایی که دانشجو علامت زده است کاراکتر X قرار گرفته است و سایر مکانها خالی است. هر پاسخ غلط ⅓ نمره منفی دارد.آرایه correct را با 20 عضو درنظر بگیرآرایه answers را به ابعاد 20 × 4 در نظر بگیرi ← 1تازمانیکه (i ≤ 20) دستورات 5 تا 7 را تکرار کنچاپ کن پاسخ درست سوال، icorrect(i) را بخوانi ← i + 1n را بخوانi ← 1تازمانیکه ( i ≤ n) دستورات 11 تا 22 را تکرار کنآرایه answers را بخوان (از داخل فایل یا ورودی صفحه کلید)grade ← 0j ← 1تازمانیکه ( j ≤ 20) دستورات 15 تا 20 را تکرار کنk ← 1 و count ← 0تازمانیکه (k ≤ 4) دستورات 17 تا 18 را تکرار کناگر ( answers(j , k) = ‘X’ ) آنگاه count ← count + 1k ← k + 1اگر ( count > 1) آنگاه grade ← grade – 1/3درغیراینصورت اگر (count = 1) آنگاه اگر ( answers(j , correct(j) ) = ‘X’) grade ← grade + 1 درغیراینصورت grade ← grade – 1/3j ← j + 1چاپ کن نمره این دانشجو برابر است با ، gradei ← i + 1توقف کن