تالار گفتمان مانشت
درخواست پاسخ تشریحی گسسته علوم کامپیوتر ۹۲ - نسخه‌ی قابل چاپ

درخواست پاسخ تشریحی گسسته علوم کامپیوتر ۹۲ - arefeh.hp - 27 دى ۱۳۹۳ ۰۱:۴۱ ق.ظ

سلام

اگه کسی از دوستان پاسخ تشریحی رو داره میشه لطف کنه بذاره؟
پیشاپیش ممنون

RE: درخواست پاسخ تشریحی گسسته علوم کامپیوتر ۹۲ - Jooybari - 27 دى ۱۳۹۳ ۰۴:۵۶ ق.ظ

سلام. این متن برای حدود ۲ سال پیشه. اگه جاییش اشکال داشت مشخص کنید. متشکر.

۶۶- گزینه ۱
این سوال بکمک اصل لانه کبوتری قابل حل است. جواب مسئله حد بالای تقسیم ۳۶۵۵ بر ۳۶۵ میشود. یعنی

[tex]\left \lceil \frac{3655}{365} \right \rceil=11[/tex]


۶۷- گزینه ۴
این سوال بکمک اصل شمول و طرد قابل حل است. جواب مسئله برابر مجموع تعداد اعدادی که بر ۲ بخشپذیرند، بعلاوه تعداد اعدادی که بر ۳ بخشپذیرند، بعلاوه اعدادی که بر ۵ بخشپذیرند، منهای اعدادی که هم بر ۲ و هم بر ۳ یعنی بر ۶ بخشپذیرند. منهای اعدادی که بر ۱۰ و منهای تعداد اعدادی که بر ۱۵ بخشپذیرند و بعلاوه اعدادی که هم بر ۲ و هم بر ۳ و هم بر ۵ یعنی بر ۳۰ بخشپذیرند خواهد شد. میتوان نوشت

[tex]\left \lfloor \frac{300}{2} \right \rfloor \left \lfloor \frac{300}{3} \right \rfloor \left \lfloor \frac{300}{5} \right \rfloor-\left \lfloor \frac{300}{6} \right \rfloor-\left \lfloor \frac{300}{10} \right \rfloor-\left \lfloor \frac{300}{15} \right \rfloor \left \lfloor \frac{300}{30} \right \rfloor[/tex]

[tex]=150 100 60-50-30-20 10=220[/tex]


۶۸- گزینه ۲
رابطه بازگشتی را حل میکنیم:

[tex]b_n-2b_{n-1}-2b_{n-2}=0[/tex]

[tex]r^2-2^r-2=0[/tex]

[tex]\Rightarrow r_1=\frac{2 \sqrt{(-2)^2-4\times (-2)}}{2}=1 \sqrt{3}[/tex]

[tex]\Rightarrow r_2=\frac{2-\sqrt{(-2)^2-4\times (-2)}}{2}=1-\sqrt{3}[/tex]

پس جواب مسئله بفرم

[tex]b_n=a(1 \sqrt{3})^n b(1-\sqrt{3})^n[/tex]

خواهد بود. با توجه به گزینه ها فقط گزینه ۲ بفرم جواب مسئله است. برای حل کامل سوال مقادیر اولیه را جایگزین میکنیم:

[tex]b_0=a b=0\Rightarrow a=-b[/tex]
[tex]b_1=a b (a-b)\sqrt{3}=1\Rightarrow a=-b=\frac{1}{2\sqrt{3}}[/tex]

با ساده سازی به گزینه ۲ میرسیم.

۶۹- گزینه ۲
برای دوبخشی بودن یک گراف و مکملش نیاز است که دور بطول فرد نداشته باشیم. درصورتی که در یک بخش از یک گراف حداقل سه راس داشته باشیم؛ در مکملش حداقل یک دور بطول سه خواهیمداشت. پس در هر بخش از گراف، حداکثر دو راس داریم. گرافهای زیر، گرافهایی هستند که هم خودشان و هم متممشان دوبخشی هستند.

(شکل P69)

۷۰- گزینه ۳

در صورتی که گراف H از حذف یک راس از گراف G ساخته بشود، هیچکدام از رئوس گراف H از رئوس متناظرشان در گراف G بزرگتر نیست. پس ماکزیمم درجه رئوس در H از ماکزیمم درجه رئوس در G کوچکتر خواهد بود.

۷۱- گزینه ۴
گراف خواسته شده بیطوقه و بدون یال مضاعف است. با ۱۹ یال اول یک درخت میتوان رسم کرد. با اضافه کردن هر یال حداقل یک دور به تعداد دورهای گراف اضافه خواهدشد. پس با اضافه کردن ۱۱ یال به درخت، حداقل ۱۱ دور خواهیم داشت.

۷۲- گزینه ۳
با حل یک دستگاه دو معادله با دو مجهول تعداد جابجایی به راست و بالا را محاسبه میکنیم.

[tex]\left\{\begin{matrix} 3r u=29\\ r 2u=18 \end{matrix}\right. \Rightarrow \left\{\begin{matrix} r=8\\ u=5 \end{matrix}\right.[/tex]

کافیست تعداد کل جایگشتهای این ۱۳ شیء را محاسبه کنیم که برابرست با [tex]\binom{13}{5}[/tex].

۷۳- گزینه ۱
دنباله خواستهشده برابر [tex]f(x)=x 4x^2 9x^3 ... n^2x^n ...[/tex] است. میخواهیم به تابع خواستهشده برسیم. برای این کار از تابع زیر دوبار مشتق میگیریم و در x ضرب میکنیم.

[tex]\frac{1}{1-x}=1 x x^2 ...[/tex]
[tex]\Rightarrow x(\frac{1}{1-x})'=\frac{x}{(1-x)^2}=x(1 x x^2 ...)'=x 2x^2 3x^3 4x^4 ...[/tex]
[tex]\Rightarrow x(\frac{x}{(1-x)^2})'=\frac{x(x 1)}{(1-x)^3}=x(x 2x^2 3x^3 ...)'=x 4x^2 9x^3=f(x)[/tex]


۷۴- گزینه ۱
عدد ۳۴ بر ۲ و ۱۷ بخشپذیر است. اگر قرار باشد یالهای این گراف بین دو راسی باشند که ب.م.م اختلاف شماره راسشان و عدد ۳۴ برابر ۱ باشد، هیچ دو راس با شماره زوج و هیچ دو راس با شماره فرد باهم مجاور نیستند. پس گراف مسئله حتماً دوبخشی است. (البته راسهای با اختلاف شماره ۱۷ هم نمیتوانند مجاور باشند. ولی این نتیجه به حل مسئله کمکی نمیکند.) گراف دوبخشی هم دور بطول فرد ندارد. پس هیچ مثلثی در گراف نخواهیم داشت.

۷۵- گزینه ۳
گزینه ۱ غلط است. مثال نقض: (شکل P75)
گزینه ۲ غلط است. مثال نقض: گراف تشکیلشده از دو گراف کامل یکی با ۴ و یکی با ۵ راس.
گزینه ۳ صحیح است. اگر قرار باشد گراف دوبخشی با دنباله درجات داده شده موجود باشد درصورتی که راس از درجه ۶ و ۷ مجاور باشند، نباید هردو باهم به یک راس از هفت راس درجه ۳ متصل باشند. این حالت ممکن نیست. چون راس به تعداد کافی نداریم. اگر قرار باشند این دو راس مجاور نباشند، در یک بخش گراف هستند. پس راس از درجه ۷ با هر هفت راس از درجه ۳ و راس از درجه ۶ با شش راس از درجه مجاور است. هیچ جفت از رئوس درجه ۳ نباید مجاور باشند. چون شرط دوبخشی بودن گراف نقض میشود. با متصل نشدن این رئوس هم درجه آنها به درجه خواسته شده نمیرسد. پس گرافی با این مشخصات موجود نیست.
گزینه ۴ غلط است. مجموعه درجات رئوس نباید فرد باشد.

۷۶- گزینه ۲
اگر قرار باشد تعداد رئوسمان فرد باشد، مجموع مقادیر درجه این رئوس فرد خواهد بود. مجموع مقادیر تمام یالها برابر نصف مجموع درجات رئوس خواهد بود. این مقدار یک عدد صحیح نیست. پس تعداد رئوس حتماً زوح است.

۷۷- گزینه ۴
ماتریس زیر گزینههای ۱ تا ۳ را رد میکند.

[tex]\begin{bmatrix} 0 & 1 & 0 & 0 & 0\\ 1 & 0 & 0 & 0 & 0\\ 0 & 0 & 0 & 1 & 0\\ 0 & 0 & 0 & 0 & 1\\ 0 & 0 & 1 & 0 & 0 \end{bmatrix}[/tex]


۷۸- گزینه ۳
فرض میکنیم A تعداد حالاتی باشد تعداد مهراهای ۹ جعبه اول زوج و B حالاتی که تعداد مهرههای ۹ جعبه اول فرد است باشد. میخواهیم حاصل A+B را محاسبه کنیم. تعداد حالات برابر حاصل [tex](9 11)^6[/tex] خواهد بود. حاصل A-B هم برابر [tex](9-11)^6=2^6[/tex] خواهد شد. اگر این پرانتز را تجذیه کنیم خواهیم دید جملات مثبت جملاتی هستند که تعداد انتخابهای عدد ۹ زوج و جملات منفی تعداد حالاتی هستند که تعداد انتخابهای عدد ۹ فرد است. از حل دستگاه دو معادله و دو مجهول از A و B مقدار A برابر [tex]\frac{20^6 2^6}{2}[/tex] میرسیم. با تقسیم مقدار A به مجموع A و B به گزینه ۳ میرسیم.

۷۹- گزینه ۲
تعداد حالاتی که رقم صدگان برابر ۵ باشد برابر با تعداد اعداد دورقمی بدون تکرار با ۴ رقم است یعنی ۱۲ عدد است. همین تعداد حالات را برای هر پنج رقم و برای هر سه مرتبه یکان و دهگان و صدگان داریم.
مجموع پنج رقم برابر ۱۵ است. هر رقم ۱۲ مرتبه در یکان، دهگان و صدگان تکرار میشود. مجموع ارزشها برای یکان و دهگان و صدگان برابر ۱۱۱ است. جواب مسئله برابر میشود با [tex]111\times 12\times 15= 19980[/tex].

۸۰- گزینه ۱
برای حل این مسئله باید هریک از اعداد ۱ تا ۶ را در مجموعههایمان قرار دهیم. برای هر رقم ۷ حالت داریم:
الف: در یکی از سه زیرمجموعه باشد. (۳ حالت)
ب: در دوتا از ۳ مجموعه باشد. (۳ حالت)
ج: در هرسه مجموعه باشد. (۱ حالت)
جواب مسئله برابر [tex]7^6=49^3[/tex] خواهد بود.