سلام
سوالاتی مشابه ۸/۱ یا ۱۶/۱ توی عکس های زیر رو چطور میشه با روشی تحلیلی حل کرد ؟ یعنی بدون استفاده از معادله ها و استقرا . مثلا رسم درخت بازگشت . چون من بیشتر سوالات رو با درخت بازگشت حل میکنم ولی این تیپ سوال رو نمیدونم چطور باید حل کنم
![[تصویر: 433683_bfvr_img_۲۰۱۷۰۳۲۴_۱۸۲۳۱۵.jpg]](https://img.manesht.ir/433683_bfvr_img_۲۰۱۷۰۳۲۴_۱۸۲۳۱۵.jpg)
![[تصویر: 433683_h7yg_img_۲۰۱۷۰۳۲۴_۱۸۲۳۲۸.jpg]](https://img.manesht.ir/433683_h7yg_img_۲۰۱۷۰۳۲۴_۱۸۲۳۲۸.jpg)
سلام
دوست گرامی روش حل کلاسیک روابط بازگشتی از مباحث مهم به شمار می اید که گاها در تست ها مطرح می شود از جمله در سوالات ۱/۸ و ۱/۱۶ که شما مطرح کردید.اینکه بخواهید از روش دیگری مثلا درختی به جواب برسید گاهی سوال طوری است که بر مبنای خود مفاهیم روش کلاسیک است و استفاده از روش دیگر گاها غیرممکن ویا زمان بر است.بیشتر از روش های درختی و قضیه اصلی و قضیه اکرا و ... برای یافتن مرتبه استفاده می شود و لی گاها در سوال حل رابطه بازگشتی را می خواهد مثل ۱/۱۶ که صریحا عنوان پاسخ رابطه بازگشتی همگن را می خواهد.
در این دو سوال که شما عنوان کردید حتی اگر روش حل اصلی روابط بازگشتی را بلد نباشیم هم می توانیم جواب دهیم
در ۱/۱۶ گزینه ۱ مرتبه را مشخص میکند نه حل رابطه پس رد می شود. مقادیر توقف رابطه که در سوال ذکر شده در رابطه نهایی که در گزینه ها امده هم باید صدق کند[tex]T(0)=0\: \: \: \: \: \: T(1)=1\: \: \: \: \: T(2)=2[/tex]
برای گزینه ۳ [tex]T(0)=2^0-0\ast2^{-1}+C=0\: \: \rightarrow\: \: C=-1\: \: \: \: \: \: \: \: \: \: T(1)=2-1+C=1\: \: \: \rightarrow\: C=0[/tex]
که رد می شود چون دو مقدار متفاوت برای c بدست امد
برای گزینه ۴ هم [tex]T(0)=1+C=0\: \: \rightarrow\: \: C=-1\: \: \: \: \: \: T(1)=2-\frac{1}{2}+C=1\: \: \: \rightarrow\: \: C=-\frac{1}{2}[/tex]
که رد می شود پس گزینه دو درست است اگر رابطه را حل کنیم همیمن گزینه ۲ بدست می اید با C= -2
در ۱/۸ هم نیازی به حل کامل نیست
[tex]G_i=G_{i-1}+2G_{i-2}+G_{i-3}\le4G_{i-1}=4^iG_0[/tex]
که [tex]G_0=1[/tex] پس گزینه ۱ صحیح است شاید این سوال پیش اید که گزینه ۴ هم می تواند جواب باشد ولی در عنوان سوال گفته کدام یک جواب بهتری است.
سلام ، دوست گرامی ، در تکمیل صحبت های دوست گرامی آقای منصور عرض کنم که برای حل معادلات بازگشتی فقط به روش درخت بازگشتی اکتفا نکن ، روش های خوبی برای حل وجود داره که اساتید و دوستان نمونه زیادی ازشون حل کردن ( اکرا بازی - جایگزاری - قضیه اصلی و ... ) سعی کنید تا حد امکان همشونو یاد بگیرید . یا مهم ترین هاشو بررسی کنید ...
سوال ۱/۱۷ که تو عکستون علامت زدید سوال سختی هست با روش قضیه اصلی به راحتی قابل حل است ، به این صورت که مقدار [tex]n^c=n^{\log_b^a}=n^{\log_3^9}=n^2[/tex] که زمانی مقدار [tex]T(n)=\theta(f(n))[/tex] میشه که مقدار [tex]f(n)\ge n^2[/tex] حال باید بدانیم از بین مقدار های داده شده کدام یک از این مقدار بیشتر است . که ۴ عبارت [tex]\{n^2\: ,\: n^3\: ,\: n^2\log n\: ,n^2\log^2\: n\: \: \: \}[/tex] فقط این شرطو دارن یعنی گزینه ۴ .
سوال ۱۶/۱ هم با همین قضیه اصلی به راحتی حل میشه کافیه معادله عمومی رو تشکیل بدیم که به فرم [tex]x^3-5x^2+8x-4=(x-2)^2(x-1)[/tex] تبدیل کنیم که در نهایت به فرم [tex]T(n)=C_02^n+C_1n2^n+C[/tex] میشه که اگه مقادیر مرزی سوال که رو داده وارد کنیم در نهایت [tex]C=-2\: ,\: C_0=2\: ,\: C_1=-\frac{1}{2}[/tex] و مقدار کلی برابر [tex]T(n)=2^{n+1}-n2^{n-1}-2[/tex] یعنی گزینه ۲
(۰۵ فروردین ۱۳۹۶ ۱۲:۵۶ ق.ظ)alireza01 نوشته شده توسط: سلام ، دوست گرامی ، در تکمیل صحبت های دوست گرامی آقای منصور عرض کنم که برای حل معادلات بازگشتی فقط به روش درخت بازگشتی اکتفا نکن ، روش های خوبی برای حل وجود داره که اساتید و دوستان نمونه زیادی ازشون حل کردن ( اکرا بازی - جایگزاری - قضیه اصلی و ... ) سعی کنید تا حد امکان همشونو یاد بگیرید . یا مهم ترین هاشو بررسی کنید ...آقا گیر دادی اسم ایشون منصور هستا :D
سوال ۱/۱۷ که تو عکستون علامت زدید سوال سختی هست با روش قضیه اصلی به راحتی قابل حل است ، به این صورت که مقدار [tex]n^c=n^{\log_b^a}=n^{\log_3^9}=n^2[/tex] که زمانی مقدار [tex]T(n)=\theta(f(n))[/tex] میشه که مقدار [tex]f(n)\ge n^2[/tex] حال باید بدانیم از بین مقدار های داده شده کدام یک از این مقدار بیشتر است . که ۴ عبارت [tex]\{n^2\:,\:n^3\:,\:n^2\log n\:,n^2\log^2\:n\:\:\:\}[/tex] فقط این شرطو دارن یعنی گزینه ۴ .
سوال ۱۶/۱ هم با همین قضیه اصلی به راحتی حل میشه کافیه معادله عمومی رو تشکیل بدیم که به فرم [tex]x^3-5x^2+8x-4=(x-2)^2(x-1)[/tex] تبدیل کنیم که در نهایت به فرم [tex]T(n)=C_02^n+C_1n2^n+C[/tex] میشه که اگه مقادیر مرزی سوال که رو داده وارد کنیم در نهایت [tex]C=-2\:,\:C_0=2\:,\:C_1=-\frac{1}{2}[/tex] و مقدار کلی برابر [tex]T(n)=2^{n+1}-n2^{n-1}-2[/tex] یعنی گزینه ۲
سوال دیگه هم که مشکل داشتین جناب منصور زحمتش رو کشیدن .
(۰۶ فروردین ۱۳۹۶ ۰۶:۱۶ ب.ظ)Behnam نوشته شده توسط: آقا گیر دادی اسم ایشون منصور هستا
شرمنده فک کردم منصوره ، مگه نیست ؟
دیگه اگه خواستم با اسم پروفایل صداشون میکنم ... 