سلام دوستان
من تازه عضو اینجا شدم، 2 ترم دیگم مونده و امسال می خوام کنکور بدم، چند روزی هست شروع کردم، ساختمان گسسته را به عنوان درس اول انتخاب کردم، و از کتاب پوران پژوهش می خونم، تازه رسیدم به فصل 3 و توابع بازگشتی، ولی تو تابع مولد گیر کردم، البته می تونم خودما قانع کنم، و جواب را که بخونم می فهمم ولی نمی دونم به چه دردی می خوره، چی طوری ازش سوال می آد، می شه یه چند نمونه مثال بگید و اینکه کلا
چیه را بگین، به صورت مفهومی، فرمولی بلدم....
ممنون از همگی
منم این مسئله رو دارم ولی
دیدم که برای حل روابط بازگشتی از توابع مولد استفاده می کنند. و این در طراحی الگوریتم خیلی بدرد می خوره
اینکه به چه دردی می خوره خوب یکیش همین حل روابط بازگشتی هستش.اینکه تیپ سوالات مربوط به تابع مولد چطوری هست میتونید همون تست های فصل روابط بازگشتی پوران رو ببینید تا تیپ سوالات دستتون بیاد.
یک مثال از مفهوم تابع مولد:
عبارت [tex](1 x)^{n}[/tex] رو در نظر بگیرید.اگر این عبارت رو بسط بدیم به صورت زیر در می یاد:
[tex]\binom{n}{0}x^{0} \binom{n}{1}x^{1} \binom{n}{2}x^{2} ... \binom{n}{n}x^{n}[/tex]
توی عبارت بالا هر x دارای یک ضریب هست.این ضرایب عبارت اند از:
[tex]\binom{n}{0},\binom{n}{1},\binom{n}{2},...,\binom{n}{n}[/tex]
حالا اگر از شما بپرسن که تابع مولد دنباله اعداد بالا چی هستش باید بگید [tex](1 x)^{n}[/tex]
در واقع شما باید یک تابعی رو پیدا کنید که به صورت [tex]f(x)=\sum_{i=0}^{infinity}\binom{n}{i}x^{i}[/tex] باشه و اون تابع چیزی نیست جز [tex](1 x)^{n}[/tex]
من هنوز قانع نشدم، آخه وقتی می شه از طریق معادله مشخصه حل کرد چه کاریه اینقدر خودمونا درگیر کنیم....،
من هنوز به تست هاش نرسیدم، یعنی تست هایی هست که می گه تابع مولد کدام است؟؟
تابع مولد در اعداد کاتالان هم کاربرد دارد.
اینکه بدتر شد.. اعداد کاتالان به چه درد می خوره؟!؟ از کجا بفهمیم باید از کاتالان استفاده کنیم؟؟ تازه اگه هم فهمیدیم چه ربطی به تابع مولد داره؟؟
(29 مرداد 1390 02:21 ب.ظ)lvlina_r نوشته شده توسط: [ -> ]اینکه بدتر شد.. اعداد کاتالان به چه درد می خوره؟!؟ از کجا بفهمیم باید از کاتالان استفاده کنیم؟؟ تازه اگه هم فهمیدیم چه ربطی به تابع مولد داره؟؟
گفته شده که تابع مولد در اعداد کاتالان کاربرد داره نه اینکه باید از اعداد کاتالان استفاده کرد.
ببینید بعضی از روابط بازگشتی رو خیلی راحت میشه با استفاده از تابع مشخصه حل کرد اما بعضی مسائل به این راحتی نیستن.مثلا شما یک دستگاه معادلات بازگشتی به صورت زیر رو در نظر بگیرید:
[tex]a_{n 1}=2a_{n}-b_{n} 2 , n\geqslant 0[/tex]
[tex]b_{n 1}=-2a_{n} 2b_{n}-1 , n\geqslant 0[/tex]
چنین دستگاهی رو بعید میدونم بشه با تابع مشخصه حل کرد(من تا حالا امتحان نکردم)اما جواب این دستگاه خیلی راحت با استفاده از تابع مولد به دست می یاد.
(29 مرداد 1390 02:21 ب.ظ)lvlina_r نوشته شده توسط: [ -> ]اینکه بدتر شد.. اعداد کاتالان به چه درد می خوره؟!؟ از کجا بفهمیم باید از کاتالان استفاده کنیم؟؟ تازه اگه هم فهمیدیم چه ربطی به تابع مولد داره؟؟
مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.
تو CLRS هم توضیح داده. تو problem هاشه.