زمان کنونی: ۰۳ دى ۱۴۰۳, ۰۴:۴۴ ب.ظ مهمان گرامی به انجمن مانشت خوش آمدید. برای استفاده از تمامی امکانات انجمن می‌توانید عضو شوید.
گزینه‌های شما (ورودثبت نام)

تست ۸۲ علوم کامپیوتر ۹۱

ارسال:
  

آنجلا پرسیده:

تست ۸۲ علوم کامپیوتر ۹۱

سلام.. کسی این تست رو بلده ..تست علوم کامپیوتر سال ۹۱/////کلا اینجور سوالا که ضریب فرزندان یه عدد کسریه چه جوری با درخت بازگشتی حل میشه؟

T(n)= 3/2 T(n/2) - 1/2 T(n/4) - 1/n
نقل قول این ارسال در یک پاسخ

۰
ارسال:
  

آنجلا پاسخ داده:

RE: تست ۸۲ علوم کامپیوتر ۹۱

یعنی هیچ کسی این سوالو بلد نیست..
نقل قول این ارسال در یک پاسخ

ارسال:
  

vojoudi پاسخ داده:

RE: تست ۸۲ علوم کامپیوتر ۹۱

(۲۰ مهر ۱۳۹۲ ۰۸:۰۲ ب.ظ)آنجلا نوشته شده توسط:  یعنی هیچ کسی این سوالو بلد نیست..

سلام
[tex]T(n)=\frac{3}{2}T(\frac{n}{2})-\frac{1}{2}T(\frac{n}{4})-\frac{1}{n}[/tex]
[tex]n=2^k[/tex]
[tex]T(2^k)=\frac{3}{2}T(\frac{2^k}{2})-\frac{1}{2}T(\frac{2^K}{4})-\frac{1}{2^k}[/tex]
[tex]T(2^k)=G(k)[/tex]
[tex]G(k)=\frac{3}{2}G(k-1)-\frac{1}{2}G(k-2)-2^{-k}[/tex]
[tex]2G(k)=3G(k-1)-G(k-2)-2^{1-k}*[/tex]
[tex]G(k-1)=\frac{3}{2}G(k-2)-\frac{1}{2}G(k-3)-2^{1-k}**[/tex]
[tex]*-**=2G(k)-G(k-1)=3G(k-1)-\frac{5}{2}G(k-2) \frac{1}{2}G(k-3)[/tex]
[tex]G(k)=2G(k-1)-\frac{5}{4}G(k-2) \frac{1}{4}G(k-3)[/tex]
[tex]G(k)-2G(k-1) \frac{5}{4}G(k-2)-\frac{1}{4}G(k-3)=0[/tex]
[tex]G_k-2G_{k-1} \frac{5}{4}G_{k-2}-\frac{1}{4}G_{k-3}=0[/tex]
[tex]G^k-2G^{k-1} \frac{5}{4}G^{k-2}-\frac{1}{4}G^{k-3}=0[/tex]
[tex]\frac{G^k}{G^{k-3}}-\frac{2G^{k-1}}{G^{k-3}} \frac{5}{4}\frac{{}G^{k-2}}{G^{k-3}}-\frac{1}{4}\frac{{}G^{k-3}}{G^{k-3}}=0[/tex]
[tex]G^3-2G^2 \frac{5}{4}G-\frac{1}{4}=0[/tex]
[tex]r^3-2r^2 \frac{5}{4}r-\frac{1}{4}=0 \Rightarrow r_1=1,r_2=\frac{1}{2},r_3=\frac{1}{2}[/tex]
[tex]G(k)=c_1{1}^k c_2{\frac{1}{2}}^k c_3k{\frac{1}{2}}^k=\Theta (k{\frac{1}{2}}^k)[/tex]
[tex]G(k)=\Theta (k{\frac{1}{2}}^k)\Rightarrow T(2^k)=\Theta (k{\frac{1}{2}}^k)\Rightarrow T(n)=\frac{logn}{n}[/tex]
یافتن تمامی ارسال‌های این کاربر
نقل قول این ارسال در یک پاسخ



موضوع‌های مرتبط با این موضوع...
موضوع: نویسنده پاسخ: بازدید: آخرین ارسال
  جزوه برای درس نظریه علوم کامپیوتر matias ۱۳ ۱۵,۳۰۲ ۲۴ شهریور ۱۴۰۳ ۰۸:۳۳ ب.ظ
آخرین ارسال: shabankhah
  گرایش های علوم کامپیوتر alisaaa ۴ ۴,۳۷۰ ۱۳ آذر ۱۴۰۲ ۰۴:۲۷ ب.ظ
آخرین ارسال: hashemhamidi
  علوم کامپیوتر شریف یا نرم افزار تهران؟ ۴L1R3Z4 ۴۴ ۳۳,۲۴۵ ۰۶ شهریور ۱۴۰۲ ۰۸:۱۲ ب.ظ
آخرین ارسال: moeinbahari
  تست ۸۷ کامپیوتر مربوط به عامل ها Shekarchi_shab ۳ ۲,۵۸۴ ۲۰ بهمن ۱۴۰۱ ۰۷:۳۹ ب.ظ
آخرین ارسال: HamidReza1
  رتبه ۵۴ علوم کامپیوتر و ۷۶ ریاضی ارشد ۱۴۰۰ Computer92 ۰ ۲,۳۷۵ ۰۸ شهریور ۱۴۰۰ ۰۹:۴۶ ب.ظ
آخرین ارسال: Computer92
  سوال ۸ دکتری علوم کامپیوتر سال ۹۴ ss311 ۲ ۳,۵۱۵ ۲۶ اردیبهشت ۱۳۹۹ ۱۲:۳۷ ب.ظ
آخرین ارسال: ss311
  سوال ۱۴ علوم کامپیوتر ۹۶ ss311 ۴ ۳,۸۵۸ ۲۶ اردیبهشت ۱۳۹۹ ۱۲:۳۳ ب.ظ
آخرین ارسال: ss311
  جایگشت( ارشد علوم کامپیوتر ۹۸ ) ss311 ۰ ۱,۹۳۳ ۰۳ اسفند ۱۳۹۸ ۱۲:۴۵ ب.ظ
آخرین ارسال: ss311
  رنگ کردن رئوس گراف( ارشد علوم کامپیوتر ۹۸ ) ss311 ۰ ۲,۱۴۹ ۰۳ اسفند ۱۳۹۸ ۱۲:۴۳ ب.ظ
آخرین ارسال: ss311
  سوال ۳ دکتری علوم کامپیوتر ۹۷ ss311 ۲ ۲,۹۹۴ ۰۶ بهمن ۱۳۹۸ ۰۴:۴۵ ب.ظ
آخرین ارسال: ss311

پرش به انجمن:

Can I see some ID?

به خاطر سپاری رمز Cancel

Feeling left out?


نگران نباش، فقط روی این لینک برای ثبت نام کلیک کن. رمزت رو فراموش کردی؟ اینجا به یادت میاریم! close

رمزت رو فراموش کردی؟

Feeling left out?


نگران نباش، فقط روی این لینک برای ثبت نام کلیک کن. close