المپیاد کامپیوتر مرحله 2 (بخش تشریحی)
- ارسال ها
- 6
- لایک ها
- 0
- امتیاز
- 0
سوال 1
برهان خلف
سوال 2
الف ) در هر مرحله تعداد نابجایی ها ( یعنی حالتی که \pi(i) به غیر از i باشه ) نصف می شه
ب) با ساختار استقرایی
سوال 3
ریشه یابی درخت ، برای ب مثال با اعداد پیشنهادی (0،k )
سوال 4
خیییییییییلللللللییییییی تابلوه ( چون گراف همبند داریم)
سوال 5
این طوریه
1,2
3,4
5,6
7,8
9,10
11,12
13,14
15,16
2,4
6,8
10,12
14,16
4,8
12,16
8,16
قست ب رو نمی دونم
برهان خلف
سوال 2
الف ) در هر مرحله تعداد نابجایی ها ( یعنی حالتی که \pi(i) به غیر از i باشه ) نصف می شه
ب) با ساختار استقرایی
سوال 3
ریشه یابی درخت ، برای ب مثال با اعداد پیشنهادی (0،k )
سوال 4
خیییییییییلللللللییییییی تابلوه ( چون گراف همبند داریم)
سوال 5
این طوریه
1,2
3,4
5,6
7,8
9,10
11,12
13,14
15,16
2,4
6,8
10,12
14,16
4,8
12,16
8,16
قست ب رو نمی دونم
با این حال من فقط تونستم سوالای 1،2،4 رو کامل حل کنم . سوال 5 قسمت الف رو حل کردم . سوال 4 ...
.... اول فکر کردم درسته راه حلم بعدش فهمیدم چه سوتیی دادم ... ولی چون ایده ی اصلی رو زدم فکر کنم در کل 70 شم ... از اونجایی که تعداد افرادی که با ایده ی ریشه یابی آشنا هستند کم اند تعداد افرادی که سوال 3 رو کامل حل کردند کم خواهد بود ( البته به نظر می یاد این طوری باشه ) ... در مورد قسمت ب سوال 5 چون اکثر بچه هامون روش نتونستند اصلا فکر کنند نظری ندارم ...
راستی قسمت ب سوال 2 هم من اینطوری حلش کردم
البته مثل این که راه حله دیگری هم داره )
ابتدا تعریف می کنیم < a[SUB]1[/SUB]=<2,1
بدیهیست که در شرط صدق می کند ... حالا
رو دنباله ی برعکس
تعریف کنید . حالا تعریف کنید :
[center:ff44ec9de6]
راستی قسمت ب سوال 2 هم من اینطوری حلش کردم
البته مثل این که راه حله دیگری هم داره )ابتدا تعریف می کنیم < a[SUB]1[/SUB]=<2,1
بدیهیست که در شرط صدق می کند ... حالا
[center:ff44ec9de6]
با یک بار انجام دادن این الگوریتم به دست می یاد :
مثلا به دست می یاد :< a[SUB]2[/SUB]=<4,3,1,2
[/center:ff44ec9de6]
در مورد کف نظر خاصی ندارم (بعضی ها می گن 60 هستش) ...
راه حل من هم اینه :
اگه v_1 راسی باشه که ازش شروع می کنه اتومبیل مسیر یکتایی رو طی می کنه ... حالا فرض کنید در طول این مسیر نتونسته باشه یک سری از رئوس رو بازدید کنه.
مثلا v_k,...,v_n رو نتونسته بازدید کنه. در اون صورت همواره باید یک مسیر رو هی بره و هی بیاد و رئوس{v_1,...,v_{k-1 رو تونسته بازدید کنه. اما چون یالی بین مجموعه رئوس
v_k,...,v_n و {v_1,...,v_{k-1 وجود داره مثلا v_iv_m در اون صورت زمانی می رسه که اتومبیل از v_i می گذره و در اون لحظه یال v_iv_m بازه .
پس مسئله حله
راه حل من هم اینه :
اگه v_1 راسی باشه که ازش شروع می کنه اتومبیل مسیر یکتایی رو طی می کنه ... حالا فرض کنید در طول این مسیر نتونسته باشه یک سری از رئوس رو بازدید کنه.
مثلا v_k,...,v_n رو نتونسته بازدید کنه. در اون صورت همواره باید یک مسیر رو هی بره و هی بیاد و رئوس{v_1,...,v_{k-1 رو تونسته بازدید کنه. اما چون یالی بین مجموعه رئوس
v_k,...,v_n و {v_1,...,v_{k-1 وجود داره مثلا v_iv_m در اون صورت زمانی می رسه که اتومبیل از v_i می گذره و در اون لحظه یال v_iv_m بازه .
پس مسئله حله
