کمک در حل سوال المپیاد کامپیوتر و ریاضی

[Mohammad Sadegh Rostami]

پاسخ : پاسخ : کمک در حل سوال المپیاد کامپیوتر و ریاض

و همیطور که پیش بریم می بینیم که با داشتن 524800 صفحه چرک نویس میشه با یک بار نگاه کردن به چرک نویس جواب پادشاه را داد
نمیدونم از مرتبه اجرای الگوریتم چیزی می دونید یا نه ولی اگر میدونید بهتره که بدونید مرتبه اجرایی این الگوریم O(nهستش

روش خیلی قشنگی بود
کاملا الگوریتمی و کامپیوتری
اما صورت مساله گفته: 52400 صفحه و نه 524800 صفحه :sad:
باید دنبال روش پیدا کردن ماکزیمم عدد بین تعداد اعداد تصادفی باشیم
البته: 1) با یکبار رجوع 2) با دوبار رجوع :read:

[Mohammad Sadegh Rostami]

پاسخ : کمک در حل سوال المپیاد کامپیوتر و ریاضی

حالت دوم رو فهمیدم چطوری میشه!
اول راهنمایی میکنم!
بعد از اینگه راهنمایی رو خوندید
یک تلاشی برای حلش بکنید
بعد در پست بعدی جواب روببینید
این راهنمایی اینطوریه:
طبق نظریه ی دوستمون در دو پست قبل
که با روشی جالب اومدن در هر مرحله اعداد رو به صورت زیر چیدن:
بزرگترین عدد بین ص1 تا 1024
بزرگترین عدد بین ص1 تا 1023
بزرگترین عدد بین ص1 تا 1022
...
بزرگترین عدد بین ص1 تا 4
بزرگترین عدد بین ص1 تا 3
بزرگترین عدد بین ص1 تا 2
عدد صفحه ی 1
بزرگترین عدد بین ص 2 تا 1024
بزرگترین عدد بین ص 2 تا 1023
...
بزرگترین عدد بین ص 2 تا 3
عدد صفحه ی 2
الی آخر
که میشه: 1024+1023+1022+...+2+1 صفحه
و با همون فرمول: 524800 صفحه!
حالا ما هم از این روش استفاده میکنیم!
اما نه به اینصورت که بزرگترین عدد بین 1 تا 1024 بعد 1 تا 1023 الی ...
به یک صورت دیگه!
چون در این مرحله ما میتونیم 2 تا صفحه رو نگاه کنیم
پس میایم از دوتا دسته بندی استفاده میکنیم!
یعنی چی؟
یعنی اینکه به جای اینکه همینطوری یهو از 1 تا 1024 رو بچینیم
قبلش یک دسته بندی میکنیم
بعد میایم چینش رو انجام میدیم!
چی میگه؟ :eek:
این داستان ادامه دارد انشالله

[Mohammad Sadegh Rostami]

پاسخ : کمک در حل سوال المپیاد کامپیوتر و ریاضی

ادامه:
خب قرار بود بیایم دسته بندیمونو تغییر بدیم!
حالت های مختلفی میشه اینکارو کرد!
ابتدا حالتی که به جواب میرسیم رو میگم
بعد حالت های دیگه رو حساب میکنیم
1024 = 16*64
خب که چی؟
یعنی ما 64 تا دسته ی 16 تایی داریم!
خب منظور؟
میایم اینکارو میکنیم: از دفتر پادشاه 16 صفحه 16 صفحه جدا میکنیم
یعنی چند تا بخش میشه اون دفتره؟ آفرین، 64 بخش.
حالا اونکاری که قبلا کرده بودیم رو میایم برای این 16 تا انجام میدیم!
یعنی برای هر 16 تا اینکار:
بزرگترین عدد بین صفحه ی 1 تا 16
بزرگترین عدد بین صفحه ی 1 تا 15
بزرگترین عدد بین صفحه ی 1 تا 14
الی آخر!
طبق محاسبات قبلی میشه: 16+15+...+2+1=136
اما ما چند تا از این 16 تا داریم؟
64 تا! پس میشه: 136*64=8704 صفحه
حالا نوبت قسمت دومه
یعنی چی؟
یعنی برای این 64 حالت باید مشخص کنیم کدومیکیشون بزرگتره کدوم کوچیکتر
یعنی اینجا هم داریم:
بزرگترین عدد بین بخش (دقت کنید! ننوشتم صفحه، نوشتم بخش) 1 و 64
بزرگترین عدد بین بخش 1 و 63
بزرگترین عدد بین بخش 1 و 62
...
یعنی 64+63+...+2+1= 2080
حالا از جمع دو حالت قبل داریم: 10784
این عدد به 10240 نزدیکه و فقط 544 تا باهاش فاصله داره
و بخاطر تکرارهای اضافی که در صفحات ایجاد شده هستش
544= 8*64 + 8*4 و 16/2=8 ...
:read:

[Mohammad Sadegh Rostami]

پاسخ : کمک در حل سوال المپیاد کامپیوتر و ریاضی

حالا دوستان به عنوان تمرین حالت های زیر رو امتحان کنید:
1024 = 512*2
1024 = 256*4
1024 = 128*8
1024 = 64*16 (برعکس حالت قبل)
1024 = 32*32
...

[rezabagheri]

پاسخ : پاسخ : کمک در حل سوال المپیاد کامپیوتر و ریاض

روش خیلی قشنگی بود
کاملا الگوریتمی و کامپیوتری
اما صورت مساله گفته: 52400 صفحه و نه 524800 صفحه :sad:
باید دنبال روش پیدا کردن ماکزیمم عدد بین تعداد اعداد تصادفی باشیم
البته: 1) با یکبار رجوع 2) با دوبار رجوع :read:

اخ اخ اخ
من اشتباه تایپ کردم 524800 درسته
ببخشید

[Mohammad Sadegh Rostami]

پاسخ : پاسخ : کمک در حل سوال المپیاد کامپیوتر و ریاض

اخ اخ اخ
من اشتباه تایپ کردم 524800 درسته
ببخشید

بنابراین این سوال شما هم حل شد ...

[rezabagheri]

پاسخ : پاسخ : کمک در حل سوال المپیاد کامپیوتر و ریاض

بنابراین این سوال شما هم حل شد ...

ممنون
می دونید اینها سوالات مسابقات ملی دانش آموزی شریف بود که 15 تا سوال در 5 زمینه ریاضی فیزیک شیمی نجوم و کامپیوتر به ما داده بودند ما 15 روز وقتی داشتیم جوابارو براشون بفرستیم (لازم نبود همه رو باهم بفرستیم تکی تکی هم میشد)
از این 4 سوالی که اینجا مطرح کردم 2 تاشو براشون جواباشو فرستادم اما این یکی آخری رو (که امتیاز بالای هم داشت) رو دیشت دیدم چواب رو گذاشتید اما چون دیشب شب آخر بود اینو دیگه نتونستم بفرستم
در هر صورت ممنون

[maysam.azizi]

پاسخ : کمک در حل سوال المپیاد کامپیوتر و ریاضی

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

[rezabagheri]

پاسخ : کمک در حل سوال المپیاد کامپیوتر و ریاضی

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

(برا همین از اول نگفتم اینا مال شرفیه!!! :mrgreen
بله حق با شماست
اما من دیدم خیلی ها سوالارو تو سایت هایی مثل هوپا و... مطرح کردن اونا بهشون جواب دادن اینجوری اگه من نمی پرشیدم حق من ضایع میشد :biggrin: :biggrin:
البته تو دفترچه اش نوشته بود از هر منبعی یا سایت اینتر نتی میشه استفاده کرد(چون آخه این المپیاد برا هر سه سال اول دوم و سوم دبیرستان برگزار میشه و خداییش از سال های اول و دوم از جایی کمک نگیرن شاید خیلی از سوالا رو نتونن جواب بدن) خوب منبع منم سایت eca و جناب عزیزی و رستمی بود دیگه :mrgreen:

[rezabagheri]

پاسخ : کمک در حل سوال المپیاد کامپیوتر و ریاضی

دوستان اگه وقت و حوصله دارید می خواید بقیه سوالارو هم کم کم بزارم تا با هم روش فکر کنیم؟(من که خوشحال میشم )

[maysam.azizi]

پاسخ : کمک در حل سوال المپیاد کامپیوتر و ریاضی

همین که علاقمند به این موضوعات هستید خودش خیلی خوبه و امیدوارم موفق باشید

[Mohammad Sadegh Rostami]

پاسخ : کمک در حل سوال المپیاد کامپیوتر و ریاضی

دوستان اگه وقت و حوصله دارید می خواید بقیه سوالارو هم کم کم بزارم تا با هم روش فکر کنیم؟(من که خوشحال میشم )

من که از این سوالا خوشم میاد!
در طراحی برخی سیستم ها کمکمون میکنه!
به قول یکی از دوستام، همیشه میگفت: Challenge every day
این سوالا خیلی ذهنو باز میکنه
سبب میشه از جنبه های مختلف به مسایل متفاوت نگاه کنیم