سرگرم کننده با مرتب سازی

ساخت مصالح (برای هر تیم)

مواد مورد نیاز

• مقوا یا کاغذ ساختمانی
• 1 نشانگر بزرگ
• با کف دست زدن
• بلوک های پلاستیکی بزرگ
• جعبه های مقوایی بزرگ

چالش طراحی

شما بخشی از یک تیم مهندس هستید که چالش مرتب سازی اشیا in را در لیست با پرسیدن س specificال های خاص مانند مقایسه دو شی بر اساس مقدار عددی آنها در اختیار دارید.

ضوابط

• اشیا with با شماره پنهان لیست را تشکیل می دهند.
• باید لیست ها را با پرسیدن یک سری سوال مرتب کنید.

محدودیت ها

• اعداد فقط برای "کنترل کننده" قابل مشاهده هستند.

1. کلاس را به تیم های 3-5 نفره تقسیم کنید.
2. اگر دوست دارید دانش آموزان س questionsالات مربوط به کاربرگ را تکمیل کنند ، صفحه کار را با مرتب سازی تفکیک کنید. در غیر این صورت ، می توانید فعالیت را بدون کاربرگ انجام دهید.
3. برای نکات و عیب یابی به بخش مفاهیم پیشینه مراجعه کنید.
4. یک مرتب سازی اساسی و سپس چهار فعالیت وجود دارد. فعالیت شماره 2 و # 3 باید با هم تکمیل شود. و ، فعالیت شماره 3 و # 4 باید با هم تکمیل شود. تخمین زده می شود که هر کدام از آنها 90 دقیقه به طول بیانجامد.
5. دستورالعمل های مرتب سازی اساسی زیر را با کلاس مرور کنید و از دانش آموزان بخواهید فعالیت مرتب سازی اساسی را انجام دهند.
   دستورالعمل های اساسی مرتب سازی:
   ● مرحله 1: دانش آموزان 8 شی را برای نمایش لیست طبقه بندی شده انتخاب می کنند. آنها ممکن است هر چیزی را برای نشان دادن لیست اعداد خود انتخاب کنند. برخی از ایده های لیست عبارتند از: الف. بلوک های بزرگ پلاستیکی بازی ب. جعبه های مقوایی بزرگ
   ● مرحله 2: دانش آموزان یک نفر را در تیم انتخاب می کنند تا "کنترل کننده" باشد.
   ● مرحله 3: کنترل کننده باید اعداد تصادفی را بر روی یک کاغذ بنویسد و آنها را به اشیا tape بچسباند تا از دید سایر دانش آموزان پنهان بمانند. فقط کنترل کننده باید قادر به دیدن آنها باشد.
   ● مرحله 4: تیم اکنون تلاش می کند تا لیست را به ترتیب صعودی مرتب کند. برای این کار دانش آموزان می توانند این سه کار را انجام دهند:
   آ. از کنترل کننده بپرسید "آیا این عدد از آن عدد بزرگتر است؟" که به دانشجویان امکان مقایسه هر دو عدد را می دهد. کنترل کننده فقط ممکن است با بله یا نه پاسخ دهد.
   ب از کنترل کننده بخواهید هر دو شی را عوض کند. سپس کنترل کننده اشیا را با یکدیگر عوض می کند و اطمینان حاصل می کند که اعداد روی آنها مشخص نشود.
   ج از کنترل کننده بخواهید هر شی را به یک موقعیت خاص منتقل کند ، یعنی "این شی را به موقعیت سوم منتقل کنید" یا "این شی را بین آن دو جسم قرار دهید."
   ● مرحله 5: کنترل کننده تعداد س yesالات بله / خیر را پرسیده است. دانش آموزان باید سعی کنند اعداد را مرتب کنند در حالی که شمارش س countال ها را به حداقل برسانند.
   ● مرحله 6: هنگامی که دانش آموزان احساس می کنند لیست مرتب شده است ، از کنترل کننده می خواهند اعداد را فاش کند. اگر لیست مرتب نشده باشد ، کنترل کننده لیست را مرتب کرده و از ابتدا شروع می کند.
6. فعالیت شماره 1 - دستورالعمل های مرتب سازی درج تک را در زیر با کلاس مرور کنید و از دانش آموزان بخواهید یک مرتبه مرتب سازی درج کنند.
   فعالیت شماره 1 - دستورالعمل های مرتب سازی درج تک:
   ● مرحله 1: با استفاده از بلوک ها یا جعبه ها ، لیست اولیه را به صورت زیر تنظیم کنید: یکی از اعداد را باید جدا کرد و بقیه را باید به ترتیب صعودی تنظیم کرد. سپس شماره جدا شده باید در انتهای قسمت مرتب شده لیست قرار گیرد. تیم نباید اعداد را ببیند اما باید بداند که کل لیست مرتب شده است ، به جز یک عدد در انتها ، که جای آن نیست.
   
   ● مرحله 2: دانش آموزان سپس باید دستورالعمل های مرحله 4 را که در بخش اصلی در بالا مرتب شده است ، دنبال کنند و سعی کنند لیست را کاملا مرتب کنند. این Single Insertion نامیده می شود و به عنوان یک بلوک اصلی برای الگوریتم های مرتب سازی دیگر مانند Insertion Sort کمک می کند.
   ● مرحله 3: برای دانش آموزان توضیح دهید که اگر آنها می توانستند اعداد را ببینند ، بدیهی است که آنها به راحتی می توانند 4 را بین 3 تا 5 قرار دهند و لیست کاملا مرتب می شود. با این حال ، این روش رایانه نیست. بنابراین ، دانش آموزان باید با مقایسه اعداد و سپس سفارش مبادله و / یا حرکت شروع کنند. در این حالت دانش آموزان می دانند که به جز شماره آخر ، لیست کامل به ترتیب صعودی است. دانش آموزان به طور طبیعی باید بدانند که آنها به سادگی باید موقعیتی را که باید آخرین عدد مرتب نشده را وارد کنند ، شناسایی کنند. 6 مثال مثال را در اینجا وارد کنید
   توالی نمودار فوق نشان می دهد چه اتفاقی باید در کلاس بیفتد. در طول فعالیت ، دانش آموزان از اعداد موجود در لیست آگاهی ندارند و به سادگی مجموعه ای از دستورالعمل ها را برای کنترل اعداد به کنترل کننده می دهند.
   این فعالیت دانش آموزان را با مفهوم تکرار آشنا می کند. تکرار یک گام در فرایند طراحی مهندسی است. دانش آموزان برای مرتب سازی صحیح اعداد باید بارها و بارها تکرار کنند.
7. فعالیت شماره 2 - دستورالعمل های مرتب سازی درج را در زیر با کلاس مرور کنید و از دانش آموزان بخواهید مرتب سازی درج را انجام دهند.
   فعالیت شماره 2 - دستورالعمل های مرتب سازی درج:
   # مرحله شماره 1: با استفاده از بلوک ها یا جعبه ها ، لیست را به صورت تصادفی مرتب کنید.
   ● مرحله شماره 2: دانش آموزان اکنون باید سعی کنند آن را با استفاده از دانش قبلی خود در مورد تک درج مرتب کنند.
   # مرحله شماره 3: دانش آموزان باید مسئله را به یک سری از درجهای منفرد تقسیم کنند. یک عدد به تنهایی یک لیست مرتب شده است. به عنوان مثال ، می توان گفت که عدد منفرد در سمت چپ انتهای لیست مرتب شده به طور تصادفی یک لیست مرتب شده است.
   # مرحله شماره 4: دانش آموزان اکنون باید این لیست طبقه بندی شده با 1 عنصر را در نظر بگیرند و مرتب سازی درج را انجام دهند و عنصر دوم را به عنوان شماره خارج از مکان در Single Insertion در نظر بگیرند.
   # مرحله شماره 4: پس از اتمام ، دانش آموزان اکنون دارای یک لیست طبقه بندی شده با 2 عنصر هستند. این روش سپس با در نظر گرفتن عنصر سوم به عنوان شماره خارج از مکان تکرار می شود ، بنابراین ما یک لیست طبقه بندی شده 3 عنصر را دریافت می کنیم.
   # مرحله شماره 5: دانش آموزان همچنان این دنباله از Single Insertings را تکرار می کنند تا اینکه سرانجام کل لیست طبقه بندی شده را بدست آورند. توالی زیر نمودارها نشان می دهد که دانش آموزان به طور ایده آل باید چه تلاش کنند. توجه کنید که جعبه زرد ، که قسمت مرتب شده لیست را نشان می دهد ، با گذشت زمان رشد می کند. توجه داشته باشید که Single Insertion با استفاده از قسمت زرد لیست به عنوان لیست مرتب شده و عنصر بعدی در سمت راست به عنوان شماره خارج از مکان ، بارها و بارها انجام می شود. این روش در نهایت کل لیست را مرتب می کند!
   10 مثال مثال را در اینجا وارد کنید
8. فعالیت شماره 3 - دستورالعمل های مرتب سازی ادغام دو لیست را در زیر با کلاس مرور کنید و از دانش آموزان بخواهید مرتب سازی ادغام دو لیست را انجام دهند.
   فعالیت شماره 3 - دستورالعمل های مرتب سازی ادغام دو لیست:
   # مرحله شماره 1: لیست اولیه را به صورت زیر تنظیم کنید: 8 آبجکت را به 2 لیست از هر 4 شی تقسیم کنید و دو لیست باید به طور مستقل مرتب شوند.
   # مرحله شماره 2: لیست ها باید در کنار هم قرار بگیرند و اکنون دانش آموزان باید با دنبال کردن دستورالعمل های مرتب سازی اساسی ، سعی کنند "دو لیست مرتب شده" را در یک لیست مرتب شده "ادغام" کنند.
   مرحله شماره 3: این مرتب سازی یک نقطه شروع و بلوک مفید برای یک الگوریتم پیچیده تر است: مرتب سازی ادغام. این امر همچنین دانش آموزان را به یادآوری و استفاده مجدد از دانش خود در مورد تک درج نیاز دارد.
   # مرحله شماره 4: لیست سمت چپ مرتب شده است ، بنابراین می توانید شماره 5 را به عنوان شماره خارج از مکان در نظر بگیرید و آن را در لیست سمت چپ مرتب کنید. با این حال ، چیزی وجود دارد که دانش آموزان باید خودشان کشف کنند. آنها باید از این واقعیت استفاده کنند که لیست سمت راست نیز مرتب شده است ، بنابراین شماره بعدی که قرار داده می شود همیشه از آخرین شماره درج شده بیشتر است.
   # مرحله شماره 5: هنگامی که دانش آموزان می خواهند عنصر دوم را در لیست سمت راست در لیست سمت چپ ادغام کنند ، نیازی به اجرای مجدد Single Insertion از سمت راست چپ نیست ، بلکه به سادگی از نقطه ای که آخرین مورد را وارد کرده اند شروع می کنند عنصر
   INSERT 3 EXAMPLE IMAGES INS توجه داشته باشید که در مرحله بالا ، سوالات را از ابتدا لیست زرد شروع نمی کنید ، همان کاری که در Insertion Sort انجام شده است. این بدان دلیل است که می دانیم شماره بعدی که باید در لیست زرد وارد شود از عددی که در گذشته وارد شده بزرگتر است ، زیرا لیست صورتی قبلا مرتب شده است. INSERT 4 EXAMPLE IMAGES اینجا
9. فعالیت شماره 4 را مرور کنید - دستورالعمل های مرتب سازی زیر را با کلاس ادغام کنید و از دانش آموزان بخواهید مرتب سازی درج را انجام دهند.
   فعالیت شماره 4 - دستورالعمل های مرتب سازی را ادغام کنید:
   # مرحله شماره 1: لیست را به صورت تصادفی تنظیم کنید. دانش آموزان باید سعی کنند لیست را با استفاده از دانش قبلی خود در مورد ادغام دو لیست مرتب کنند.
   ● مرحله شماره 2: ایده اصلی پشت Merge Sort اصل تقسیم و پیروزی است. این یکی از مفاهیم اساسی در پشت هر الگوریتم مرتب سازی پیشرفته امروزی است. دانش آموزان باید هر شماره را به عنوان لیست طبقه بندی شده جداگانه با اندازه 1 در نظر بگیرند.
   # مرحله شماره 3: از آنجا ، دانش آموزان سعی می کنند ادغام شناخته شده دو لیست را در لیست ها انجام دهند. با این حال ، در نگاه اول ، آنچه دانشجویان تلاش خواهند کرد ، با مرتب سازی درج تفاوت چندانی نخواهد داشت. آنها ابتدا دو عدد را ادغام می کنند و سپس یک سوم و یک شماره چهارم و غیره را ادغام می کنند. این اساساً مرتب سازی درج است.
   # مرحله شماره 4: ترفند ادغام مرتب سازی به شرح زیر است:
   ○ از لیست تصادفی ، با هر شماره به عنوان یک لیست طبقه بندی شده با اندازه 1 رفتار کنید.
   ○ سپس ، جفت لیست های مجاور را تشکیل دهید و آنها را ادغام کنید ، به طوری که اکنون 4 لیست مرتب شده داریم که هر کدام از آنها به اندازه 2 هستند.
   ○ سپس ، دوباره جفت های لیست را تشکیل داده و ادغام کنید ، تا 2 لیست ، هر یک از اندازه 4 ، بدست آورید.
   ○ یک ادغام نهایی ، و ما یک لیست طبقه بندی شده کامل از اندازه 8. به دست می آوریم. این روش تضمین می کند که تکرارهای مربوط به هر شماره به حداقل می رسد ، بنابراین تعداد س ofالات بله / خیر نیز به حداقل می رسد.
10. برای کسب مطالب بیشتر در مورد موضوع ، به بخش "حفاری عمیق تر" مراجعه کنید.

این درس را می توان در کمتر از 1 دوره کلاس برای دانش آموزان مسن انجام داد. با این حال ، برای کمک به دانش آموزان از احساس عجله و تضمین موفقیت دانش آموزان (به ویژه برای دانش آموزان جوان) ، این درس را به دو دوره تقسیم کنید و به دانشجویان فرصت بیشتری برای طوفان فکری ، آزمایش ایده ها و نهایی کردن طرح آنها دهید. تست و تست را در دوره کلاس بعدی انجام دهید.

نکات و عیب یابی

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

ترسیم تصاویر و نمودارها می تواند در انتقال این موضوع خاص به دانش آموزان بسیار مثر باشد. از گرافیک ارائه شده در بخش دستورالعمل های فعالیت می توان به عنوان راهنمای نحوه ترسیم مراحل مختلف استفاده کرد. همچنین می توان دانش آموزان را ترغیب به ترسیم نمودارهایی نمود که الگوریتم ها و راه حل های پیشنهادی خود را به تصویر می کشند.

اگر دانش آموزان برای شروع کار مشکل دارند ، در اینجا چند نکته در مورد چگونگی قرار دادن دانش آموزان در مسیر درست آورده شده است:

• دانش آموزان را تشویق کنید تا درباره وظیفه پیش رو بحث کنند. در بیشتر مواقع ، دانش آموزان وقتی "با صدای بلند فکر می کنند" و درمورد مسئله و یا راه حل آن با همسالان خود بحث می کنند ، ناخواسته خودشان به راه حل می رسند.
• بحث را با پرسیدن نظرات دانش آموزان و تشویق دانش آموزان با دیدگاه های متفاوت به بحث های فعال آغاز کنید.
• یک راه حل بالقوه ارائه دهید و از دانش آموزان بپرسید اگر فکر می کنند چه اتفاقی می افتد؟ چنین سوالی به احتمال زیاد روند جدیدی از تفکر را در ذهن دانشجویان ایجاد می کند و به آنها کمک می کند تا ببینند از کجا خارج می شوند. این س mightال ممکن است به همان چیزی که کلاس قبلاً درباره آن بحث کرده بود ، اشاره کند ، یا می تواند یک فکر کاملاً جدید باشد ، اما لزوماً درست نیست. هدف ارائه پاسخ صحیح نیست ، بلکه دانش آموزان را تشویق می کند تا راه حل های احتمالی را ارزیابی کرده و برای خود بیاندیشند.

از مسابقات بین تیمی به طور موثر استفاده کنید. سعی کنید و بین تعداد س askedالات مطرح شده در مقایسه با زمان برای مرتب سازی لیست ، و اینکه آیا بین برنده شدن و س askingالات کمتر همبستگی وجود دارد ، همبستگی را ترسیم کنید.

اتصال به اینترنت

• مرتب سازی انیمیشن های الگوریتم

خواندن توصیه می شود

• هنر برنامه نویسی رایانه ، جلد 3 ، توسط دونالد ای.نوت (شابک: 0321751043)

فعالیت نوشتن

رایانه ها معمولاً حدود یک چهارم کامل از پردازش خود را برای مرتب سازی داده های مختلف خرج می کنند. به عنوان مثال ، یک رایانه در بیمارستان ممکن است یک پایگاه داده بسیار گسترده از همه بیمارانی داشته باشد که در 5 سال گذشته برای معالجه در بیمارستان بوده اند. افراد مختلف در بیمارستان ممکن است لیست های مختلفی از بیماران را بخواهند. فردی که امور مالی بیمارستان را مدیریت می کند ممکن است لیستی از بیماران را که با توجه به هزینه های بیمارستان آنها سفارش می شود ، بخواهد. یک محقق ممکن است لیستی را بخواهد که طبق بیماری برای آن درمان شده باشد. یک مدیر ممکن است لیستی را که پزشکی که بیمار را معالجه می کند ، بخواهد. هنگام تولید این لیست ها ، رایانه مجبور است هر بار داده ها را مجدداً بر اساس نیاز کاربر مرتب کند. آیا می توانید به سناریوی دیگری که مرتب سازی در آن مهم است فکر کنید؟ حفظ داده های مرتب شده نسبت به داده های مرتب نشده چه مزایایی دارد؟ معایب احتمالی چیست؟

تراز به چهارچوب برنامه درسی

توجه داشته باشید: برنامه های درسی در این مجموعه با یک یا چند مجموعه از استانداردهای زیر مطابقت دارد:  

• استانداردهای آموزش علوم ایالات متحده (http://www.nap.edu/catalog.php?record_id=4962)
• استانداردهای علمی نسل بعدی ایالات متحده (http://www.nextgenscience.org/) 
• استانداردهای سواد فناوری انجمن بین المللی آموزش فناوری (http://www.iteea.org/TAA/PDFs/xstnd.pdf)
• اصول و معیارهای شورای ملی معلمان ریاضیات ریاضیات مدارس ایالات متحده (http://www.nctm.org/standards/content.aspx?id=16909)
• استانداردهای هسته هسته ای مشترک ایالات متحده برای ریاضیات (http://www.corestandards.org/Math)
• استانداردهای علوم کامپیوتر K-12 انجمن معلمان علوم کامپیوتر (http://csta.acm.org/Curriculum/sub/K12Standards.html)

استانداردهای ملی آموزش علوم کلاس K-4 (سنین 4 تا 9 سال)

استاندارد استاندارد A: علم به عنوان تحقیق

در نتیجه فعالیت ها ، همه دانش آموزان باید رشد کنند

• توانایی های لازم برای انجام تحقیقات علمی 

استاندارد B محتوا: علوم فیزیکی

در نتیجه فعالیت ها ، همه دانش آموزان باید درک درستی از آنها داشته باشند

• خصوصیات اشیا and و مواد 

استاندارد استاندارد E: علم و فناوری 

در نتیجه فعالیت ها ، همه دانش آموزان باید رشد کنند

• توانایی طراحی فن آوری 
• درک در مورد علم و فناوری 

استاندارد F محتوا: علم در دیدگاه های شخصی و اجتماعی

در نتیجه فعالیت ها ، همه دانش آموزان باید درک درستی از آنها داشته باشند

• انواع منابع 
• علم و فناوری در چالش های محلی 

استاندارد G محتوا: تاریخ و ماهیت علم

در نتیجه فعالیت ها ، همه دانش آموزان باید درک درستی از آنها داشته باشند

• علم به عنوان یک تلاش انسانی 

استانداردهای ملی آموزش علوم کلاس 5-8 (سن 10 - 14)

استاندارد استاندارد A: علم به عنوان تحقیق

در نتیجه فعالیت ها ، همه دانش آموزان باید رشد کنند

• توانایی های لازم برای انجام تحقیقات علمی 
• تفاهماتی در مورد تحقیق علمی 

استاندارد B محتوا: علوم فیزیکی

در نتیجه فعالیتهایشان ، همه دانش آموزان باید درک درستی از آنها داشته باشند

• خصوصیات و تغییر خصوصیات در ماده 

استاندارد استاندارد E: علم و فناوری

در نتیجه فعالیت های کلاس 5-8 ، همه دانش آموزان باید رشد کنند

• توانایی طراحی فن آوری 
• تفاهماتی در مورد علم و فناوری 

استانداردهای ملی آموزش علوم پایه های 5-8 (10 تا 14 سال) (ادامه)

استاندارد F محتوا: علم در دیدگاه های شخصی و اجتماعی

در نتیجه فعالیت ها ، همه دانش آموزان باید درک درستی از آنها داشته باشند

• خطرات و مزایا 
• علم و فناوری در جامعه 

اصول و استانداردهای ریاضیات مدرسه (سنین 6 تا 18 سال)

اندازه گیری

• ویژگی های قابل اندازه گیری اشیا and و واحدها ، سیستم ها و فرایندهای اندازه گیری را درک کنید. 
• از تکنیک ها ، ابزارها و فرمول های مناسب برای تعیین اندازه گیری ها استفاده کنید. 

حل مشکل

• ایجاد دانش جدید ریاضی از طریق حل مسئله.
• حل مسائلی که در ریاضیات و سایر زمینه ها بوجود می آیند.
• انواع استراتژیهای مناسب را برای حل مشکلات به کار گرفته و انطباق دهید. 
• نظارت و تأمل در روند حل مسئله ریاضی. 

اتصالات

• ریاضیات را در متن خارج از ریاضیات تشخیص داده و به کار ببندید.

نمایندگی

• برای سازماندهی ، ثبت و برقراری ارتباط ایده های ریاضی نمایندگی ایجاد و استفاده کنید. 
• برای حل مشکلات ، از بین نمایش های ریاضی انتخاب ، اعمال و ترجمه کنید. 

استانداردهای سواد فناوری - همه اعصار

ماهیت فناوری

• استاندارد 1: دانش آموزان درک درستی از ویژگی ها و دامنه فناوری پیدا می کنند.
• استاندارد 3: دانش آموزان درک درستی از روابط بین فن آوری ها و ارتباطات بین فناوری و سایر زمینه های تحصیل خواهند داشت.

فناوری و جامعه

• استاندارد 4: دانش آموزان درک درستی از تأثیرات فرهنگی ، اجتماعی ، اقتصادی و سیاسی فناوری خواهند داشت.
• استاندارد 6: دانش آموزان درک درستی از نقش جامعه در توسعه و استفاده از فناوری خواهند داشت.

طرح

• استاندارد 9: دانش آموزان درک درستی از طراحی مهندسی خواهند داشت.

استانداردهای سواد فناوری - همه اعصار (ادامه)

توانایی هایی برای یک دنیای فناوری

• استاندارد 13: دانش آموزان توانایی ارزیابی تأثیر محصولات و سیستم ها را پیدا می کنند.

جهان طراحی شده

• استاندارد 14: دانش آموزان درك فن آوري هاي پزشكي را درك كرده و قادر به انتخاب و استفاده از آنها خواهند بود.
• استاندارد 19: دانش آموزان درک درستی از فن آوری های تولید را به دست می آورند و قادر به انتخاب و استفاده هستند.

جلسه 1 - مرتب سازی درج

این یک تمرین گروهی است. قبل از شروع ، لطفاً گروهی متشکل از 3-5 دانشجو تشکیل دهید.

درج تک

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

کنترل کننده باید کارت های Single Insertion را تنظیم کند ، و دیگران باید برای مرتب سازی لیست بازی کنند. این کار را حداقل 5 بار انجام دهید و جدول زیر را پر کنید.

با توجه به اطلاعاتی که در بالا وارد کردید ، به س questionsالات زیر پاسخ دهید:

1. به طور متوسط ​​تعداد س questionsالات در یک دور چقدر است؟

______________________

2. فرض کنید که شما باید جدول فوق را برای 5000 درج تک پر کنید. فکر می کنید بیشترین مقدار ممکن در ستون دوم (تعداد س yesال های بله / خیر) کدام است؟

______________________

3. فرض کنید به جای 10 با یک لیست 8 عددی کار می کنید ، در این صورت پاسخ شما به سوال 2 چیست؟

______________________

4. آیا اکنون می توانید اندازه لیست را به تعداد سوالات مطرح شده در بدترین حالت مرتبط کنید؟ در مورد چگونگی فکر کردن در مورد اندازه لیست و سوالات مطرح شده در بدترین حالت ، یک پاسخ بسیار مختصر دهید (به یاد داشته باشید ، هرچه تعداد س questionsالات کمتر باشد ، بهتر است. بنابراین وقتی می گوییم "بدترین حالت" ، منظور ما بیشترین تعداد ممکن است از س askedالات پرسیده شده)

__________________________________________________________________

__________________________________________________________________

__________________________________________________________________

__________________________________________________________________

درج مرتب سازی

حالا ، با همان کارت ها ، بازی Insertion Sort را انجام دهید. به یاد داشته باشید که ابتدا با یک لیست کاملاً تصادفی شروع کنید.

حداقل 5 مرتبه وارد کردن را مرتب کنید ، و جدول زیر را پر کنید. کنترل کننده باید قبل از شروع مرتب سازی ستون سوم را ثبت کند و پس از مرتب سازی لیست آن را فاش کند.

با توجه به اطلاعاتی که در بالا وارد کردید ، به س questionsالات زیر پاسخ دهید:

1. به طور متوسط ​​تعداد س questionsالات در یک دور چقدر است؟

______________________

2. حتماً فهمیده اید که Insertion Sort فقط یک سری از Insertings Single است. در مورد چگونگی ارتباط تعداد درجهای منفرد با اندازه لیستی که مرتب می شود ، یک پاسخ بسیار مختصر بدهید.

__________________________________________________________________

__________________________________________________________________

__________________________________________________________________

__________________________________________________________________

3. پاسخ خود را به سوال 2 از تمرین Single Insertion به خاطر بسپارید. از این پاسخ برای محاسبه تعداد س youالاتی که می خواهید در "درج مرتب سازی" در "بدترین حالت" بپرسید استفاده کنید. مراحل خود را نشان دهید.

جواب نهایی: __________________

4. در یک مسابقه مرتب سازی با یک گروه دیگر رو در رو شوید تا ببینید چه کسی می تواند لیست تصادفی را سریعتر مرتب کند. به نفع انصاف از هر تیم یک کنترل کننده وجود دارد. قوانین بازی باید کاملاً رعایت شود ، اما شما می توانید از هر روشی که می خواهید استفاده کنید.

تعداد س questionsالاتی که پرسیدید: _______________________

تعداد سوالات حریف شما: _______________________

برنده شدی؟ _______________________

جلسه 2 - مرتب سازی را ادغام کنید

این یک تمرین گروهی است. قبل از شروع ، لطفاً گروهی متشکل از 3-5 دانشجو تشکیل دهید.

ادغام دو لیست

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

کنترل کننده باید کارت های Two-list Merge را تنظیم کند و بقیه برای مرتب سازی لیست بازی کنند. این کار را حداقل 5 بار انجام دهید و جدول زیر را پر کنید.

با توجه به اطلاعاتی که در بالا وارد کردید ، به س questionsالات زیر پاسخ دهید:

1. به طور متوسط ​​تعداد س questionsالات در یک دور چقدر است؟

______________________

2. فرض کنید که شما برای 5000 ادغام دو لیست باید جدول بالا را پر کنید. فکر می کنید بیشترین مقدار ممکن در ستون دوم (تعداد س yesال های بله / خیر) کدام است؟

______________________

3. فرض کنید به جای 10 با یک لیست 8 عددی کار می کنید ، در این صورت پاسخ شما به سوال 2 چیست؟

______________________

4. حالا برگردید و نگاهی به جوابهایی که برای تمرین در تک درج داده اید ، بیاندازید. چه شباهت هایی را می بینید؟ چه تفاوت هایی؟ اعداد چگونه تغییر می کنند؟ آیا آنها کمی متفاوت هستند ، یا تفاوت زیادی دارند؟ نظرات خود را در این مورد بنویسید.

__________________________________________________________________

__________________________________________________________________

__________________________________________________________________

__________________________________________________________________

__________________________________________________________________

__________________________________________________________________

__________________________________________________________________

__________________________________________________________________

__________________________________________________________________

ادغام مرتب سازی

اکنون ، با همان کارت ها ، بازی Merge Sort را انجام دهید. به یاد داشته باشید که ابتدا با یک لیست کاملاً تصادفی شروع کنید.

حداقل 5 مرتبه مرتب سازی را انجام دهید و جدول زیر را پر کنید. کنترل کننده باید قبل از شروع مرتب سازی ستون سوم را ثبت کند و پس از مرتب سازی لیست آن را فاش کند.

با توجه به اطلاعاتی که در بالا وارد کردید ، به س questionsالات زیر پاسخ دهید:

1. به طور متوسط ​​تعداد س questionsالات در یک دور چقدر است؟

______________________

2. حتماً فهمیده اید که Merge Sort فقط یک سری ادغام دو لیست است. چند ادغام دو لیسته برای ادغام مرتب سازی لیست 8 عددی انجام داده اید؟

______________________

3. پاسخ خود را در سوال 2 از تمرین ادغام دو لیست به خاطر بسپارید. از این پاسخ برای محاسبه تعداد س youالاتی که باید در "ادغام مرتب سازی" در "بدترین حالت" بپرسید استفاده کنید. مراحل خود را نشان دهید.

جواب نهایی: __________________

4. در یک مسابقه مرتب سازی با یک گروه دیگر رو در رو شوید تا ببینید چه کسی می تواند لیست تصادفی را سریعتر مرتب کند. به نفع انصاف از هر تیم یک کنترل کننده وجود دارد. قوانین بازی باید کاملاً رعایت شود ، اما شما می توانید از هر روشی که می خواهید استفاده کنید.

تعداد س questionsالاتی که پرسیدید: _______________________

تعداد سوالات حریف شما: _______________________

برنده شدی؟ _______________________

ترجمه طرح درس

[تغییر دهنده زبان]