مسابقه‌ی تصادفی

 
 
 پستچی زحمتکش! (مسابقه‌ي شماره‌ي 33)
پستچی زحمتکش! (مسابقه‌ي شماره‌ي 33)مسابقه كامپيوتر
این بار هم در جهت بسط و گسترش توانایی‌های شما در حل مسائل تحلیلی، سری به مسابقه‌ای از جنس ترکیبیاتی زده‌ایم! بخوانید و لذت ببرید! ... سؤال همراه با جواب

پستچش زحمتكش




سؤال

مسابقه‌ي این هفته در رابطه با یک پستچی زحمتکش است!

 آقای پستچی زحمتکش، نامه‌ها را به 19 خانه‌ی ضلع شرقی خیابان مدرسه می‌برد. او متوجه شده است که هر روز از هر دو خانه‌ای که همسایه‌ي هم هستند حداکثر یکی نامه دارد و هر روز تعداد خانه‌هایی که پشت سر هم هستند و نامه ندارند بیش‌تر از دو تا نبوده است.

 حال سؤال ما از شما این است که چند طریق متمایز برای رساندن نامه‌ها وجود دارد!؟


راهنمايي
این سؤال آن‌قدر ساده است که با همان راهنمایی‌اي که در قسمت خلاصه گفته شده، حل می‌شود!

 جواب
رشته‌ي n رقمی از رقم‌های 0 و 1 را در نظر بگیرید که به‌ترتیب: 0 نشانه‌ی نامه نداشتن و 1 نشانه‌ی نامه داشتن باشد.
دنباله‌ای از 0 و 1ها را پذیرفتنی می‌نامیم هرگاه که در آن 11 و 000 وجود نداشته باشد، چون چنین رشته‌هایی برخلاف فرض‌های مسأله‌ي ما ساخته شده‌اند!

- شرط اول از دو خانه حداکثر یکی نامه دارد
- شرط دوم هر روز تعداد خانه‌هایی که پشت سر هم هستند و نامه ندارند بیش از دو تا نیست

حال فرض کنید  که برابر با تعداد رشته‌های n رقمی قابل‌قبول باشد.
برابر با تعداد رشته‌های n رقمی قابل‌قبولی باشند که در آن‌ها 00 پس از اولین رقم 1 از سمت چپ آمده است و  برابر با تعداد رشته‌های n رقمی باشد که در آن‌ها 01 پس از اولین رقم 1 در سمت چپ آمده است.

دقت داشته باشید که:
 

اگر .





اگر اولین 100 از سمت چپ را حذف کنیم معلوم می‌شود که:

 





و اگر اولین 101 از سمت چپ را حذف کنیم معلوم می‌شود که:
 





در نتیجه اگر n بزرگ‌تر یا مساوی 5 باشد آن‌گاه:
 



به‌سادگی می‌توان حساب کرد که:


 

اکنون می‌توان از رابطه‌ی بازگشتی به‌دست آمده استفاده کرد و نتیجه گرفت که:

1386/3/2 لينک مستقيم

فرستنده :
احسان HyperLink HyperLink 1386/5/19
مـتـن : راحت بود
پاسـخ : احسان جان!
دوست داريم شما نيز در پاسخگويي به سؤال‌ها مشاركت فعال داشته باشي.

فرستنده :
رضا HyperLink HyperLink 1386/4/16
مـتـن : احسنت به آقا کمال!
پاسـخ : بله !
آقا کمال درست جواب دادن !

فرستنده :
محمد محمودی HyperLink HyperLink 1386/4/16
مـتـن : سلام
ببخشید مثل اینکه ما هم از هول حلیم افتادیم تو دیگ
چون مسئله را در کمتر از 2 دقیقه حل کردم یه اشتباهاتی توحلش پیش اومد . یعنی اصلا صورت را درست نخوندم .
شمام لطف کنین حل من را نزارین .
ولی فکر می کنم اونقدر راحت باشه که کار را به جوون تر ها بسپاریم .

پاسـخ : ای بابا !
با با پیر مرد !

فرستنده :
محمد محمودی HyperLink HyperLink 1386/4/16
مـتـن : سلام
جواب 17 میشه
استدلال :
یکی از هزاران راه حل ممکن و مبسوط ترین راه حل ممکن و گلابی ترین آن:
هر 4 خانه متوالی خارج از این 3 حالت نیست :
A: 0101
B: 1010
C: 1001
حالا میایم میگیم اگه چهار تای اول A باشه چهار تای بعدی میتونه از هر سه نوع باشه .
اگه B یا C باشه بعدی فقط میتونه B باشه .
حالا همچین درختی را تا 4 تا 4 تایی ادامه میدیم .
اما برای سه تای آخر : اون 3 تا را با یکی آخر 4تایی چهارم یه چهارتایی جدید در نظر میگیریم
حالا اگه چهار تایی چهارم A باشه چهارتایی جدید فقط میتونه B باشه
C: A, C یا
B: A, Cیا
که وقتی همه را بشماریم میشه 17 تا ................ حسن این روش اینه که راحت استقرا میزنیم و میگیم برای 4n-1 خانه تعداد روش ها میشه 4n-3
پاسـخ : سلام محمد جان متاسفانه جواب شما نادرست است !

فرستنده :
hasan HyperLink HyperLink 1386/4/16
مـتـن : baba in ke kheili sadeh bood.
rah hal sade ter az shoma ham dare.
soalhaye sakht tar bedid.
پاسـخ : چشم حسن جان !

فرستنده :
kamal HyperLink HyperLink 1386/4/16
مـتـن : khob vase halle in soal ma miaym ye donbale bazgashti misazim ke tedad rahhaye momken baraye "n" khoonaro be ma neshoon bede
donbale bazgashtimoon in mishe: f(n)=f(n-2)+f(n-3) hala esbat mikonim chenin donbaleyi doroste
mikhaym vase "n" ta khoone tedadesho be dast biarim
adade samte raste reshtamoon ya 0 hast ya 1
agar 1 bashe ke adade ghabl az oon hatman bayad 0 bashe va adade ghabl az oon sefre ham ya 1 hast ya 0 hala tedad rahhaye baraye gharar dadane baghieye adad be andazeye f(n-3) tast va hamasho ham mipooshoone
dar sooratiam ke raghame samte rastemoon 0 bashe ghabl az oon ya 1 hast ya sefr va tedade rahhaye chidane baghie ham be andazeye f(n-2) tast
pas didim ke f(n)=f(n-2)+f(n-3) ye donbaleye doroste
va hamchenin darim: f(1)=2 va f(2)=3 va f(3)=4 va be in tatib sayere f(n) haro be dast miarim
man f(19) ro hesab kardam shod 351
pas tedade rahhayi ke postchi mitoone name bebare "351" ta hast
پاسـخ : سلا م کمال جان خیلی عالیه !
جواب تو کاملا درست !
خیلی خوبه !
آفرین !

نظر شما پس از تاييد در سايت قرار داده خواهد شد
نام :
پست الکترونيکي :
صفحه شخصي :
نظر:
تایید انصراف
 المپیاد کامپیوتر

 

     

 

 

صفحه‌ي اصلي

     

 

راهنماي سايت

     

 

 

آموزش

     

 

بانك سوال

     

 

 

مسابقه

     

 

 

زنگ تفريح

     

 

 

مصاحبه و گزارش

     

 

 

معرفي كتاب

     

 

 

مشاوره

     

 

 

پرسش‌و‌پاسخ‌علمي

     

 

اخبار

 

فعاليت‌هاي علمي

 بازديدها
خطایی روی داده است.
خطا: بازديدها فعلا" غیر قابل دسترسی می باشد.