نمونه سوالات المپیاد کامپیوتر سال های گذشته

[lighting]

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

سوال اول:
در شکل مقابل به چند طریق می توان سه مثلث با اضلاع به طول 1 انتخاب کرد به طوری که مثلث های انتخاب شده در راس و ضلع با یکدیگر اشتراک نداشته باشند.فرض کنید مثلث اصلی دارای اضلاع به طول 3 است و تمام خطوط رسم شده موازی اضلاع مثلث اصلی باشند

 

[lighting]

سوال دوم

سوال دوم:
در یک جدول 3*3 یک اسب شطرنج در خانه وسط ستون سمت چپ قرار دارد. در هر مرحله در یکی از 7 خانه ی کناری جدول که اسب در انجا نیست یک سرباز قرار میدهیم.سپس، اسب از خانه ای که هست با کمترین حرکت خود را به سرباز میرساند و ان را میزند.
می خواهیم مرحله فوق را 1387 بار تکرار کنیم،و در هرمرحله سرباز را در جایی بگذاریم که اسب در مجموع بیشترین تعداد حرکت را انجام دهد. اگر تعداد بیشینه ی حرکت اسب را x بنامیم، باقیمانده X بر 5 چند خواهد شد؟

 

[lighting]

سوال سوم

سوال سوم:
دو عدد 1 روی تخته سیاه نوشته شده است. شما می توانید یکی از سه کار زیر را بر روی این اعداد اینجام دهید:
عملیات " دوبرابر " : یکی از اعداد روی تخیته سیاه را پاک کنید و دو برابر آن را بنویسید
عملیات " سه برابر " : یکی از اعداد روی تخیته سیاه را پاک کنید و سه برابر آن را بنویسید
عملیات " جمع " : دوتا از اعداد روی تخته سیاه را پاک کنید و جمع آن ها را بنویسید

هدف این است که با کمترین تعداد استفاده از عملیات " سه برابر " عدد x را روی تخته سیاه نوشته.این کمترن تعداد را nx می نامیم. برای مثال n3=0 خواهد بود.چون بدون استفاده از عملیات " سه برابر " می توان عدد 3 را با یک بار استفاده از عملیات " دو برابر " و یک بار استفاده از عملیات " جمع " نوشت.

n30 و n40 چه اعدادی هستند؟
n40=0 ,n30=2
n40=0,n30=0
n40=1,n30=1
n40=1,n30=0
n40=0,n30=1

 

[lighting]

سوال چهارم

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

 

[MagicalBOY]

پاسخ : نمونه سوالات المپیاد کامپیوتر سال های گذشته

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

سوال اول:
در شکل مقابل به چند طریق می توان سه مثلث با اضلاع به طول 1 انتخاب کرد به طوری که مثلث های انتخاب شده در راس و ضلع با یکدیگر اشتراک نداشته باشند.فرض کنید مثلث اصلی دارای اضلاع به طول 3 است و تمام خطوط رسم شده موازی اضلاع مثلث اصلی باشند

4 تا


http://up.persianbax.ir/do.php?imgf=18_13Untitled_60503.png

 

[Java.Her]

پاسخ : نمونه سوالات المپیاد کامپیوتر سال های گذشته

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

با توجه به مطالب ریاضی گسسته در کل 512 (2 به توان9 ) حالت مختلف داریم !

> حالتهای همه ی خانه ها 2 است (یعنی دو حالت ) به جز 2 خانه ی باقی مانده تا هر مربع سیاه که فقط یک حالت برای عبور دارند ، سپس با توجه به اصل ضرب احتمال هر خانه را در هم ضرب میکنیم و جواب پیدا می شه :

عکس

 

[Night Spirit]

پاسخ : نمونه سوالات المپیاد کامپیوتر سال های گذشته

این کار نمیشه؟:ناراحت
http://up.persianbax.ir/do.php?imgf=18_1348.jpg

 

[lighting]

پاسخ : نمونه سوالات المپیاد کامپیوتر سال های گذشته

با توجه به مطالب ریاضی گسسته در کل 512 (2 به توان9 ) حالت مختلف داریم !

> حالتهای همه ی خانه ها 2 است (یعنی دو حالت ) به جز 2 خانه ی باقی مانده تا هر مربع سیاه که فقط یک حالت برای عبور دارند ، سپس با توجه به اصل ضرب احتمال هر خانه را در هم ضرب میکنیم و جواب پیدا می شه :

عکس

تو این حالتی که شما حساب کردین راه های تکراری بوجود میاد
این مسئله با دنباله فیبونانچی حل میشه

 

[Java.Her]

پاسخ : نمونه سوالات المپیاد کامپیوتر سال های گذشته

تو این حالتی که شما حساب کردین راه های تکراری بوجود میاد
این مسئله با دنباله فیبونانچی حل میشه

آهان درسته ! الان دقت کردم درست میگید ! ولی من از فیبو ناتچی بلد نیستم !؟!؟؟!

 

[lighting]

پاسخ : نمونه سوالات المپیاد کامپیوتر سال های گذشته

آهان درسته ! الان دقت کردم درست میگید ! من از فیبو ناتچی بلد نیستم !؟!؟؟!

جواب این مسئله اینجوری هست که ما تعداد حالاتی که باید مهره برسه به خونه قبل از خونه های رنگی رو حساب کنیم
برای این کار از سری فیبونانچی استفاده می کنیم
برای قسمت اول اینجوری میشه که 5 تا خونه ی سفید قبل از خونه مشکی هست پس تعداد حالاتش طبق سری فیبونانچی میشه 5
برای قسمت دوم 3 تا خونه قبل از خونه مشکی هست که میشه 2 حالت
و برای قسمت سوم 6 تا خونه هست که میشه 8 حالت و قسمت اخر هم باز میشه 2 حالت
حالا اگه تمام این حالات رو در هم ضرب کینم در کل میشه 160 حالت
پس جواب ایین مسئله میشه 160 حالت