خوب اول از همه از یه مثال معروف شروع می کنیم
حالت اول جوریه که می خوای منابع سیستم رو نابود کنیم (منظورم اینه که بیشتر از حدی که احتیاج هست داریم استفاده می کنیم)
( اگه یه وقت صورت سواله به نظرتون مشکل بود یه وقت نگران نشید کلا خاصیت این نوع مسائل ترس اولیست که از صورت سوال به وجود میاد وگرنه خودشون هیچی ندارن )
سوال :
فرض کنید یک دنباله از اعداد صحیح داریم که شامل n عدد مثل a1,a2,a3,...an است.(منظورم همون یه دنبالست توی ویرگول یکم سخته نوشتنش)
اول از همه من یه توضیح کلی راجب به سوال میدم
سوال از ما می خواد که به چند تا سوال جواب بدیم (بهش می گیم q)
سوال ها اینطورین که چند تا عدد از دنباله از چیزی که سوال پرسیده کوچیکتر هستن
همین ....
بخش جزئی سوال رو می تونی پایین تر ببینی
ما می‌خواهیم به q تا سؤال جواب بدهیم. در هر سؤال i-ام، یک عدد صحیح به نام xi به ما داده می‌شود و باید تعداد اعدادی که در دنباله a1,a2,a3,...an کمتر از xi هستند را پیدا کنیم و چاپ کنیم.
Copy code 2 3 1 2 1 2 3
Copy code 0 1 2
راه حل اول :
می تونیم برای هر سوال به صورت جدا گونه جوابش رو بدست بیاریم اینطوری اول باید n ( تعداد دنباله) و q (تعداد سوال ها رو از کاربر بگیریم)
بعد از اون یه لیست تعریف کنیم که اعداد دنباله رو بتونیم بریزیم داخلش
حالا باید یه حلقه فور بزنیم ( به تعداد سوال هایی که قراره بپرسه همون q) یه مقدار شمارش گر تعریف کنیم که مقدار اولیش صفر باشه بعد یه حلقه دیگه داخلش بزنیم که روی دنباله حرکت می کنه اگه عدد از سوال کوچیکتر بود یدونه به شمارش گر اضافه بشه و در اخر جواب چاپ بشه
اینم کدش :
راه حل دوم :
خوب الان می خوایم کد رو با یه الگوریتم ساده حل کنیم
اول به صورت ساده توضیح میدم بعد از رو کد احتمالا متوجه بشید :)
اول باید فکر کنیم که لازمه برای هر سوال یه بار بیایم کل دنباله رو چک کنیم ببینم که چند تا از سوال ما بزرگتره و ما جواب رو بدیم برای 10 تا اوکیه ،برای 100 تا اوکیه، برای 100000 چی؟
خو معلومه که نه ! (چرایی این قضیه رو توی این مقاله توضیح دادم)
برای راحتی کار یه مجموعه مثال می زنم : 2-4-5-2-3-2-4
خوب ما اول بزرگترین عدد مجموعه رو پیدا می کنیم بعدش یه دنباله به طول اون عدد بزرگه می سازیم و توی هر خونه ش تعداد اعدادی که توی اون دنباله تکرار شدن رو می نویسیم مثلا برای نمونه مجموعه ما (شماره خونه پایین و تعداد بالاش)
003121
012345
(یدونه 5 داریم دو تا 4 داریم و ...)
حالا دوباره یه لیست می سازیم به طول بزرگترین عدد مجموعه ( همون 5) و داخل اون به صورت بازگشتی لیست قبلی رو جمع می کنیم می شه این
003467
012345
دلیل این حرکتمون اینه که این لیست اخریه در اصل جواب اینه که چند تا عدد بزرگترن از اون خونه ای که عدده توش هست
الان اگه دقت کنید اگه سوال ما 3 باشه توی خونه ی سوم ( به شماره لیست می شه دوم ) همون جوابه یعنی ما سه تا عدد تو دنباله داریم که از 3 کمترن
اینم کدش :
خوب فکر کنم برای این پست کافی باشه
اگه خودت نکته ای رو میشناسی که من اشاره نکردم توی کامنت بگو
امیدوارم این پست به دردتون خورده باشه
موفق و پیروز باشید ...
ان شاء الله راهی که میریم ختم بشه به ظهور سریعتر آقا امام زمان ...
