سلام
با توجه به اینکه از شما راه حل بهینه نخواستن که در واقع اصلا سخت نیست
اگر کنکوری نیستید پیشنهادم اینه که حتما برای برنامه نویسی و درک الگوریتم ها و مساله ها وقت بذارید

###############################################

سوال ۱در واقع به یه زبون دیگه از شما K کمترین اعضای ارایه رو خواسته


می تونید اول ی ارایه کمکی بگیرید که دو بعدی باشه و هم حاوی مکان عدد ها در ارایه اولیه و حاوی داده ها باشه و مرتبش کنید (بر اساس سطری که مربوط به داده هاست ) بعدش k عضو اولش از روی سطر مکان ها رو به ترتیب چاپ کنینی یعنی ارایه کمکی اینه :
سطر ۱ : ۱۰ و ۴۰ و ۶۰ و ۵۰ و ۳۰
سط دوم : ۱ و ۲و ۳و ۴و ۵

بعد از مرتب سازی می شه :
سطر اول : ۱۰ و ۳۰ و ۴۰ و ۵۰ و ۶۰
سطر دوم : ۱ و ۵و ۲و ۴ و ۳


در واقع مرتبه n به توان ۲ می شه ولی سختیش استفاده از ارایه دو بعدی و استفاده از ارایه پویاست


ممکنه این راه حل براتون گیج کننده باشه پس از روی ارایه بخونید و کوچیک ترین عضو رو معرفی کنید با مکانش و بعد به جای اون عددی که انتخاب شده یه عدد به عنوان بی نهایت در نظر بگیرید
یعنی داریم یک حلقه رو به تعداد k بار تکرار می کنیم و محتوای این حلقه تعیین کوچیک ترین عضو ارایه است

یعنی داریم

۱۰ و۴۰ و ۶۰ و ۵۰ و ۳۰
وقتی یک بار حلقه عمل کرد عدد ۱۰ معرفی می شه و جایگاه یک
بعد از مشخص کردن توی خروجی میایم جای عدد ۱۰ مثلا می ذاریم ۱۰۰۰۰ که مطمین باشیم دیگه این عدد معرفی نیم شه


این الگوریتم مرتبه ش می شه n اما خوب برای k هایی ک مستقل از n باشن
دیدی که اصلا سخت نیست و جوابش عینا توی کتابتون هست
* راه حل دیگه اش استفاده از تورنومنت هست ک اگر ازش استفاده کنید شاید استادتون نمره اضافه هم بده

---

اگر متوجه حل شدید بریم مساله شماره ۲ ؟

---

###############################################


مساله ۲ می خواد گروه بندی کنه

بیاید مساله رو بفهمیم
اول که باید ارایه پویا داشته باشیم چون از ابتدا تعداد داده های ارایه مشخص نیست


بعدش می خوایم گروه بندی کنیم
در قدم اول اولین عدد رو می ذاریم به عنوانresult
فرض کنیم عضو اول ارایه ۲ و بعدی ۱۰ هست خوب اگر ۲ برای خودش ی گروه باشه چنین چیزی ممکنه ؟ نه چون ۱۰ خودش هنوز با هیچ عددی جمع نشده از result بیشتره
پس چی کار کنیم ؟ اهان ! resut به جای ۲ عدد ۱۲ هست حالا می ریم سراغ عدد بعدی
اگر فرضا ۱۴ باشه چی؟ می فهمیم که باز هم توی انتخاب result عجله کردیم و باید مقدارش رو به ۲۶ تغغیر بدیم واسه همینه اون ارایه ۱و۲و۳و۴و۵و۶و۷و رو نوشته فقط یک گروه داریم !

حالا اگر عدد سوم کمتر بود چی ؟ مثلا ۷ پس حدس می زنیم که result درست انتخاب شده و می ریم سراغ عدد بعد از ۷ و اونو با ۷ جمع می کنیم اگر جواب بیشتر از result شد یعنی بازم عجله کردیم و result 12 نبوده پس چی بوده ؟ قاعدتا ۱۲+۷ بوده
فرضا داریم :
۲و۱۰و۷و۸و ...
حاصل ۷+۸ شده ۱۵ که از ۱۲ بیشتره پس result می شه ۲+۱۰+۷ و باید بررسی رو از ۸ ادامه بدیم

فرض کنید بعد از ۷ داده ۵ رو داشته باشیم یعنی :
۲و۱۰و۷و۵و...
یعنی مقدار ۷+۵ دقیقا برابر result می شه این نتیجه ای هست که به نفع ۱۲ بودن مقدار result هست

اگر به جای ۸ داشتیم ۲ چی ؟ یعنی :
۲و۱۰و۷و۲
حالا result هست ۱۲ و مقدار ۲+۷ هست ۹ چیزی بر علیه ۱۲ بودن result پیدا نکردیم و باید عدد بعد از ۲ رو بررسی کنیم


امیدوارم این مثال رو فقط نخونین بلکه روی کاغذ بنویسید و استدلال کنید چون اگر این کار رو نکنید نمی فهمید چه اتفاقی افتاده هاااااا

اگر فهمیدین الگوریتمی که پیشنهاد دادم رو بنویسید (نمی خوام لقمه حاضری تحویلتون بدم چون تنها سوالی که ارزش حل داره از بین این چهار تا همینه فقط)

راهنمایی : این الگوریتم حد اقل از مرتبه n به توان ۲ هست

---

مساله سوم به سادگی مساله اوله و حتی باید بگم ساده تر از اون
قابل فهم ترین راه حلی ک می تونم پیشنهاد بدم یه الگوریتمه که از لحاظ حافظه و زمان از مرتبه n به توان ۲ هست

اولین کار اینه که فاصله ها رو برای هر خونه حساب کنیم
به عنوان مثال نمونه خود تمرین رو در نظر بگیرید
۳و۲و۴و۶
یک ارایه کمکی می خوایم که فاصله خانه شماره ۱ رو از بقیه خونه ها توش ذخیره کنیم
فاصله ها با تفریق به دست میان
پس داریم ۰و۱و۱و۳
حالا برای بقیه خونه ها چطوری می شه ؟
خانه ی شماره ۱: ۰و۱و۱و۳
خانه شماره ۲ : ۱و۰و۲و۴
خانه شماره ۱:۳و۲و۰و۲
خانه شماره ۴: ۳و۴و۲و۰

یعنی الان من ۴ تا ارایه کمکی دارم که هر کدوم ۴ تا خونه دارن
یعنی من باید یک ارایه پویا بگیرم به اندازه n به توان ۲ که مقدار n رو هم باید داشته باشیم (موقع دریافت ورودی بخواهیدش از کاربر)


خوب حالا من اختلاف های هر خونه رو از بقیه خونه ها دارم از اونجایی که اختلاف مصافت هر خونه با خودش ۰ هست و از اونجایی ک صورت مساله هم اشاره کرده که اختلاف با خانه های دیگر کم ترین باشد شما می تونید یک راه برای تصمیم گیری کم بودن اختلاف در نظر بگیرید

درس امار یادتون هست ؟ میانگین ، اختلاف پراکندگی و واریانس همه می تونن راه حل این مساله باشن!!!

می تونید میانگین مسافت ها رو در نظر بگیرید و بگید هر کدوم میانگین کمتری داشت پس اون نزدیک تره میانگین فواصل رو از روی ارایه کمکی با کمک جمع همه فاصله ها و تقسیم بر تعداد به دست بیارید
برای خانه اول می شه ۱/۲۵ برای خانه شماره ۲ می شه ۱/۷۵ برای خانه شماره ۳ می شه ۱/۲۵ و برای خانه شماره ۴ می شه ۲/۲۵

اما اگر دو تا باهم مساوی در اومدن چی؟ الان برای خانه ۱ و خانه ۳ هر دو مقدار ۱/۲۵ به دست اومده !
کلا از هر راه استفاده کنین می تونه این تساوی وجود داشته باشه پس یک راه حل دوم هم می تونید در نظر بگیریم اون چی باشه ؟ با توجه به سادگی پیاده سازی اختلاف پراکندگی رو پیشنهاد می دم

بین دو تا خانه ای که توی مقایسه اول بهترین نتیجه رو کسب کردن یعنی خانه شماره ۱ و ۳ یک مسابقه دیگه ترتیب می دیم

می ریم توی ارایه های کمکی شون و می بینیم که بیشترین مسافت برای هر خانه چی هست ؟
برای خانه شماره ۱ بیشترین مسافت ۳ و باری خانه شماره ۳ بیشترین مسافت ۲ هست پس توی مقایسه بعدی خانه شماره ۳ برنده می شه که همون result= 4 می شه



می تونید از برعکس عمل کنین یعنی اول کمترین فاصله رو بررسی کنید و بعدش میانگین رو ولی به هر حال باید حد اقل دو راه رو معرفی کنین چون این دو تا راه حل چنان ک باید و شاید قوی نیستین از لحاظ اماری

پیاده سازی واریانس رو پیشنهاد نکردم چون پیچیده می شد و خودمم حس توضیحش رو نداشتم ولی اگر دستتون اومد چ باید بکنید از واریانس استفاده کنین چون از لحاظ قدرت اماری بهتر از این دو راه هست


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


########################################################



مساله ۴ هم ک اگر منظور از به دست اوردن عدد این باشه که جمع اعداد اول بشه یه عدد اول دیگه که اخر سادگیه

می گه شما عدد های اول رو ردیف کنین توی ارایه : ۲و ۳و ۵و۷و۱۱و۱۷و۱۹و ...
از اول شروع کنین به جمع زدن بعد از هر جمع ببینید حاصل جمع عدد اول هست ؟
یعنی ۲+۳ که می شه ۵
یا ۲+۳+۵+۷ که می شه ۱۷
ولی باید دقت کنین مثلا ۲رو نمی شه با ۵ جمع کنین بگید افرین ۷ پیدا شد چرا ؟ چون ۲ و ۵ اول متوالی نیستن


برای اینکه وقتی یه حاصل جمع رو می خواید ببینید اول هست یا نه بیخودی کد ننویسین واسش چه می کنین ؟
اگر که ارایه اعداد اول رو با فرمول پر کردین که همون کد رو کپی می کنین اما اگر از حفظ پرکردین می تونین توی ارایه سرچ بزنین مثلا وقتی ۲+۳+۵ رو که می شه ۸ جمع زدید برید توی ارایه اعداد اول بگرید ببینید ۸ هست یا نه ؟ شرط پایان جستجو هم رسیدن به عدد اولیه که از ۸ بزرگتره یعنی وقتی توی جستجو به ۱۱ رسیدید مطمینید که ۸ اول نیست
( توی ماشین حساب ها یه سری داده ها از قبل ذخیره شدن که من خودم این از قبل ذخیره کردن رو خیلی دوست دارم)

امیدوارم تا اخر مهلت بتونین کد ها رو هم پیاده سازی کنین

دوست گرامی اینجا سایت حل المسائل یا حل تمرینات کلاسی افراد نیست.
هر سوال باید در یک تاپیک مطرح شود موضوع بسته میشود.

چی شد پس توروخدا لازم دارم بخدااااااااااااااااااااااااااا