حل رابطه بازگشتی - نسخهی قابل چاپ |
حل رابطه بازگشتی - ziba_khofte - 22 آبان ۱۳۹۵ ۱۱:۳۷ ق.ظ
سلام . میشه در حل این رابطه بازگشتی به من کمک کنید؟ |
RE: حل رابطه بازگشتی - Behnam - ۲۲ آبان ۱۳۹۵ ۰۵:۰۶ ب.ظ
(۲۲ آبان ۱۳۹۵ ۱۱:۳۷ ق.ظ)ziba_khofte نوشته شده توسط: سلام . میشه در حل این رابطه بازگشتی به من کمک کنید؟ از براکتها که میشه صرف نظر کرد: [tex]T(n)=2T(\frac{n}{2})+2[/tex] که این رو هم میشه به روش Akra-Bazi یا بسط دادن حل کرد. در مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمیباشید. جهت مشاهده پیوندها ثبت نام کنید. که P=1 بدست میاد، پس [tex]T(n)=n^{1\: }(1+\int_1^n\frac{2}{x^2}dx)=n(1-\frac{2}{n} + 2)=3n[/tex] در روش بسط دادن هم: [tex]T(n)=2T(\frac{n}{2})+2=2(2T(\frac{n}{4})+2)+2=4T(\frac{n}{4})+4+2=8T(\frac{n}{8})+8+4+2=...=2^kT(\frac{n}{2^k})+2^k+2^{k-1}+...+4+2[/tex] که K رو میتونیم تا [tex]2^k=n\: \rightarrow\: k=\lg(n)[/tex] جلو ببریم. پس [tex]T(n)=2^{\log n}+\frac{2^{\log n}}{2\: }+\frac{2^{\log n}}{\: 4}+...+8+4+2=n+\frac{n}{2}+\frac{n}{4}+...+4+2\approx2n=\theta(n)[/tex] |
RE: حل رابطه بازگشتی - ziba_khofte - 23 آبان ۱۳۹۵ ۱۰:۴۹ ق.ظ
ممنونم.چیزی که من رو به شک انداخته بود که چند جایی دیدم که این رابطه را به عنوان رابطه بازگشتی برای پیدان کردن همزمان عنصر ماکزیمم و مینمم ارایه نوشته بود و نوشته بود که بعد از حل میرسیم به رابطه زیر.منم هر کار کردم نتوانستم این رابطه رو بدست بیاورم. .left\{\begin{matrix}\frac{3n}{2}-2 \: \: if(n=2k) \\ \frac{3n}{2}-\frac{3}{2} \: \: \: \: \: \: \: \: \: if(n=2k+1)\end{matrix}\right\ |
RE: حل رابطه بازگشتی - Alirezaj - 25 آبان ۱۳۹۵ ۰۲:۵۲ ب.ظ
[tex]T(n)=2T(\frac{n}{2})+2[/tex] که این رو هم میشه به روش Akra-Bazi یا بسط دادن حل کرد. در مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمیباشید. جهت مشاهده پیوندها ثبت نام کنید. که P=1 بدست میاد، پس [tex]T(n)=n^{1\: }(1+\int_1^n\frac{2}{x^2}dx)=n(1-\frac{2}{n} + 2)=3n[/tex] وقت بخیر ببخشید ممکن بگید انتگرال این رابطه چطوری محاسبه میشود؟!!! |
RE: حل رابطه بازگشتی - Pure Liveliness - 25 آبان ۱۳۹۵ ۰۸:۰۰ ب.ظ
(۲۵ آبان ۱۳۹۵ ۰۲:۵۲ ب.ظ)Alirezaj نوشته شده توسط: [tex]T(n)=2T(\frac{n}{2})+2[/tex]سلام. برای محاسبه ی انتگرال: [tex]\int^n_1\frac{2}{x^2}dx=2\int^n_1\frac{1}{x^2}dx=2\int^n_1x^{-2}dx=\frac{2x^{-2+1}}{-2+1}=-2x^{-1}|_{x=1}^{x=n}=-2n^{-1}-(-2\cdot(1)^{-1})=-\frac{2}{n}+2[/tex] |
RE: حل رابطه بازگشتی - Alirezaj - 26 آبان ۱۳۹۵ ۱۲:۱۴ ق.ظ
[ وقت بخیر ببخشید ممکن بگید انتگرال این رابطه چطوری محاسبه میشود؟!!! [/quote] سلام. برای محاسبه ی انتگرال: [tex]\int^n_1\frac{2}{x^2}dx=2\int^n_1\frac{1}{x^2}dx=2\int^n_1x^{-2}dx=\frac{2x^{-2+1}}{-2+1}=-2x^{-1}|_{x=1}^{x=n}=-2n^{-1}-(-2\cdot(1)^{-1})=-\frac{2}{n}+2[/tex] [/quote] سلام خیلی ممنون. |