صفحهها: ۱ ۲
در هر سری چند تست یا سوال از منابع یا کنکور ارشد سالهای قبل درج میشود. چون مبحث آنالیز ترکیبی و شمارش با ساختمانهای گسسته مشترک است ،سوالها از تستهای گسسته نیز میباشند.میتوان جوابها را بصورت تستی داد و بعد در صورت وجود اشکال یا اختلاف بحث در مورد سوال مورد نظر انجام خواهد شد.
سوال اول:کنکور۹۰ مهندسی کامپیوتر:
![[تصویر: 36431_1_1379098141.jpg]](https://img.manesht.ir/36431_1_1379098141.jpg)
سوال دوم:
![[تصویر: 36431_2_1379098141.jpg]](https://img.manesht.ir/36431_2_1379098141.jpg)
سوال سوم:
![[تصویر: 36431_3_1379098141.jpg]](https://img.manesht.ir/36431_3_1379098141.jpg)
سوال اول گزینه ۲
سوال دوم گزینه ۲
سوال سوم گزینه ۲
سوال اول:
از ۱۵ صندلی روی ۱۰ صندلی ۱۰ نفر قرار میگیرند که جایگشت این ۱۰ نفر برابر !۱۰ است
حال باید ۵صندلی خالی باقی مانده را طوری قرار دهیم که هیچ دوتایی از انها کنار هم قرار نگیرند و همینطور اینکه بین و کنار ۱۰ صندلی پر ۱۱ مکان برای قرار گرفتن این ۵ صندلی وجود دارد پس [tex]\binom{11}{5}[/tex]
که برابر ۴۶۲ است
پس تعداد حالات کل ۴۶۲*!۱۰ است که گزینه دوم میباشد
سوالات سخت بودند یا آسون؟بهر حال مربوط به کنکور سالهای قبل بودند. انگار تمایلی به بحث در موردشون نیست.
قبل از اینکه این قسمت راه بیافته مدام درخواست حل مسائل شمارش را داشتیم.
نظر بدید و حل کنید ولو اشتباه!!!
سوالها یکم مشکل هستند لطفا در مورد حلشون راهنمایی کنید
برای حل سوال دوم فکر میکنم باید ۱۰ خانه راباید سه تا سه تا تقسیم کرد و بین هر سه خانه یک خانه در نظر گرفت که حتما باید سیاه باشد که حالات زیر اتفاق میفتد: (خ--->خانه خالی و س---->سیاه)
۱-خ خ خ س خ خ خ س خ خ
۲-س خ خ خ س خ خ خ س خ
۳-خ س خ خ خ س خ خ خ س
حال باید حالات خالی را طوری پر کنیم که سه رنگ سفید کنار هم قرار نگیرد
که برای هر سه خانه خالی ۶ حالت سیاه کردن وجود دارد که سه خانه باهم سفید نباشد و همینطور برای دو خانه خالی در کنار هم ۳ حالت سیاه کردن وجود دارد و یک حالت هم سفید گذاشتن انها چون (دوخانه هست پس مجازیم هردوی انها را سفید بگذاریم) پس در کل ۴حالت و برای تک خانه خالی ۲حالت وجود دارد یکی سفید و یکی سیاه
پس داریم ۶*۶*۴+۶*۶*۲+۶*۶*۲=۲۸۸
البته در این راه حالات تکراری بوجود میاید چون مثلا هرسه طریق ۱و ۲ و۳ هرسه حالت اینکه تمام خانهها سیاه باشند را تولید میکنند
در مورد مسئله دوم:
همانطور که میدونید اینجور مسائل دو حالت برای حل دارند راه اول شمارش مستقیم حالات و راه دوم شمارش متمم و کسر از کل حالات. باید دید کدام راه حل کوتاهتره.
اگر راه اول را انتخاب کنیدحالاتی که خانه های سفید بصورت تکی باشد و نیز دوتایی باشد را حساب کنیم. اگر سه یا چهار یا ...سفید کنار هم باشند شمارش نمیشوند.
اگر راه دوم را انتخاب کنید کل حالات ۲ بتوان ده است. حالاتی که سه خانه سفید میتونند کنار هم باشند را حساب کنید ازش کم کنید.بدیهی است که وقتی ۴ خانه یا پنج خانه یا ... کنار هم باشند هم جزء این حالت است. وقتی حساب کردیم از دو بتوان ده کم میکنیم.
بنظر شما کدام حالت محاسبه کمتری دارد؟ آیا در برخورد با اینگونه سوالات براحتی میشه فهمید کدام راه را باید بریم؟
طبیعی است که مسئله میتونست بصورت رشته های صفر ویک یا قراردادن خانمها و آقایان یا مهرهای سفید و سیاه ...مطرح شوند.میخواهیم ببینیم میشه یک راه کلی داد.
فکر میکنم بهتر باشه حالاتی که میتوان دو خانه سفید کنار هم داشته باشیم ویا خانه های سفید تکی باشد (هر خانه سفید درکنار خود خانه های سیاه داشته باشد) حساب کنیم راحتتر و بهتر باشه
سوال اول
![[تصویر: 0a70bb05b08d.png]](http://www.iranpicture.tk/images/0a70bb05b08d.png)
f(n)=f(n-1)+f(n-2)+f(n-3)
f(1)=2 f(2)=2^2=4 f(3)=2^3-1=7
f(4)=f(1)+f(2)+f(3)=13 , f(5)=24,f(6)=44,f(7)=81,f(8)=149,f(9)=274,f(10)=504
سوال ۳
تعداد دست دادنها را برابر با x در نظر بگیریم:[tex]0\geqslant x\geqslant36[/tex]
اگر تعداد صفر دست دادن وجود داشته باشد: [tex]0\geqslant x\geqslant35[/tex]
اگر تعداد صفر دست دادن وجود نداشته باشد: [tex]1\geqslant x\geqslant36[/tex]
در هر دو حالت ۳۶ لانه(تعداد دست دادن ها)داریم و ۳۷ کبوتر(نفر)
ضمن تشکر از milestone سعی داشتیم سوال دوم را از راه شمارش حل کنیم.
کد:
(۲^۱۰)-[ C(8,1) + C(9,2) + C(10,3) ]فک نمی کنم چندان درست باشه اما فعلا به همین رسیدم
اینطور حساب کردم که در ترکیب اول ۳ مربع سفید رو یکی فرض کردم. ترکیب دوم دو تا مربع سفید رو یک مربع گرفتم به همراه انتخاب یک مربع آزاد و دسته بندی نشده و ترکیب سوم هم سه تا مربع تکی در نظرر گرفتم. جمع این سه تا رو از مجموع کم کردم. یه جاییش فک کنم ایراد داشته باشه منتها دقیقا نمیدونم کجا!
(۱۶ مرداد ۱۳۹۰ ۱۲:۵۱ ق.ظ)ehsan_nekooee نوشته شده توسط:اشکالش اینه که حالات دیگری هم هست که سه تا سفید کنار هم قرار میگیرند. مثلا" ممکن است ۵ خانه سفید داشته باشیم که ۳ سفید کنار هم و دو سفید هم کنار هم باشند.در این مسئله برای استفاده از شمارش اگر فکر کنید بنظر من شمارش مستقیم راحتتر است.کد:
(۲^۱۰)-[ C(8,1) + C(9,2) + C(10,3) ]
فک نمی کنم چندان درست باشه اما فعلا به همین رسیدم
اینطور حساب کردم که در ترکیب اول ۳ مربع سفید رو یکی فرض کردم. ترکیب دوم دو تا مربع سفید رو یک مربع گرفتم به همراه انتخاب یک مربع آزاد و دسته بندی نشده و ترکیب سوم هم سه تا مربع تکی در نظرر گرفتم. جمع این سه تا رو از مجموع کم کردم. یه جاییش فک کنم ایراد داشته باشه منتها دقیقا نمیدونم کجا!
البته راه حل milestoneشاید ساده ترین راهه ولی شمارش میتونه تمرین خوبی برای حل مسائل مشابه یا کوچکتر باشه. من اینجوری این مسئله را از شمارش حل میکنم:
حالات مختلف اینها هستند:
۱- فقط یک خانه سفید در نوار داشته باشیم:C(10,9
۲- فقط دو خانه سفید داشته باشیم:C(10,2
۳- فقط سه خانه سفید داشته باشیم ولی سه خانه کنار هم نباشد.پس کل سه حالتها را حساب و حالاتی که سه تا کنار هم باشه را ازش کم میکنیم:C(10,3)-C(8,1
برای اینکه بدونید چرا حالاتی که سه تا کنار هم باشه میشه C(8,1
استدلال احسان بکار میاد یعنی سه تا خونه سفید کنار هم را یکی و ۷ خونه باقیمانده هم هست پس ۸ جا میمونه که یک محل انتخاب میشه .
۴- فقط ۴ خانه سفید داشته باشیم ولی حالتی که چهار خانه شامل ۳ خانه سفید کنار هم باشه ویکی جدا و یا ۴ خانه سفید پهلوی هم باشه ازش کم میشه.
بهمین ترتیب ادامه بدیم این روش بشما کمک میکنه بتونید در تصور حالات تبحر پیدا کنید.
چون تایپش اینجا با نوشتن فرمول سخته اگه حل کردید و نشد .بگید تروی کاغذ حل کنم اسکن کنم و بگذارم.
این مسئله را مجددا" در روابط بازگشتی در گسسته حل میکنیم.
حالا مسئله آخر هم اگه سوالی هست بپرسید تا بعدش بریم سری بعدی سوالات.
ممنون از پاسختون فقط یک سوال؟
چرا در حالت ۲نوشتید c(10,2 ? باید مینوشتید c(10,8 همانطور که برای یک خانه سفید نوشتید c(10,9 درسته؟
(۱۷ مرداد ۱۳۹۰ ۰۱:۱۷ ق.ظ)narges_r نوشته شده توسط: ممنون از پاسختون فقط یک سوال؟
چرا در حالت ۲نوشتید c(10,2 ? باید مینوشتید c(10,8 همانطور که برای یک خانه سفید نوشتید c(10,9 درسته؟
چون جفتشون یکی هستن. فرقی نمی کنه
هردو شون برابرن با:
(!۲*!۸) / !۱۰
چه قدر فرمول نوشتن سخته. یکی به راه چاره پیشنهاد بده اینقدر سختی نکشیم!
درسته
من تازه شروع کردم به خوندن امار خیلی مبتدی هستم یکمی باید بیشتر دقت کنم
ممنون
در واقع یکی شمارش روی خانه های سفید و دیگری شمارش روی سیاههاست که فرقی نمیکنند.