تالار گفتمان مانشت

نمی دونم استرس دارم که نمی تونم حلش کنم یا ....
اینو قبلا راحت حل می کردم الان نمی دونم چطوری بود
یکی کمکم کنههههههههههههه

[tex][(7/10)^i]*n<=1 \Rightarrow n<=(10/7)^i \Rightarrow i=log _{10/7}^{n}[/tex]
[tex]t(n)=\sum_{i=0}^{log_{10/7}^{n}}(9/10)^i*n[/tex]
[attachment=2686]

میشه واضح‌تر بگید.
آخه من از روی درخت تشخیص میدادم
الان جالبه واسم که هنگ کردم
همین هم یادم رفته

اینم همون درخته دیگه.
اومده هزینه های سطوح درخت رو با سیکما جمع زده.
ارتفاع درخت هم از اون جمله ای بدست میاد که فاصله بیشتری تا برگ داره (دیرتر تقسیم می شه) یعنی 7n/10

درخت براش بکشید. متوجه میشید.

[attachment=2688]

مال استرس بود
امروز با آرامش حلش کردم به جواب رسیدم
ممنونم از کمکتون

من با ارتفاع بدست آوردن مشکل دارم. کسی می تونه کمک کنه؟

(12 دى 1391 10:42 ب.ظ)egm1176 نوشته شده توسط: [ -> ]من با ارتفاع بدست آوردن مشکل دارم. کسی می تونه کمک کنه؟

دوستان کسی میتونه محاسبه ارتفاع رو بگه؟!

تو این مسئله درختمون دو تا شاخه داره .چون [tex]\frac{7}{10}[/tex] بزرگتر از [tex]\frac{1}{5}[/tex] هست پس این زیر شاخه بزرگتر هست و ارتفاع به اون بستگی داره.(یعنی هر سری چون ذر یک عدد بزرگتر ضرب می شه دیر تر کاهش پیدا می کنه نسبت به اون شاخه).بنابراین می تونیم این طوری در نظرش بگیریم:
[tex]T(n)=T(\frac{7n}{10})[/tex]
که برای رابطه هایی به فرم [tex]T(n)=T(\frac{an}{b})[/tex] ارتفاع برابر می شه با : log n بر مبنای [tex]\frac{b}{a}[/tex]
که اینجا می شه: log n بر مبنای [tex]\frac{10}{7}[/tex]

این که خیای سادست.
تو نگاه اول 7/10 و 1/5 رو جمع می کنیم میشه 9/10 پس گزینه های 3 یا 4 درست است.
سپس می بینیم باید F(n) که در اینجا n هست در 9/10 به توان i ضرب بشه. و ازش زیکما بگیریم.
زیکما معمولا از 0 شروع میشه تا لگاریتم T ای که رشدش بیشتره(یا عددی که n داره بهش تقسیم میشه کمتر هست)
دقت کنید که 7n/10 یعنی n تقسیم بر 10/7 .
یه جا هم داریم n/5
حالا n/5 بزرگتر هست یا n تقسیم بر 10/7 ؟
دقت کنید که 10/7 تقریبا میشه 1.4 که از 5 خیلی کمتره. پس پایه ی لگاریتم باید 10/7 باشه و گزینه ی 3 میشه جواب

مبحث ارتفاع درخت و سطح(عمق) رو با این بخش قاطی نکنید.
ارتفاع هر گره، طولانی ترین مسیر رو به پایین از آن گره تا برگ است.جزوه ی قدسی رو بخونید. مشکلی بود یه تاپیک دیگه بزنید. یا خصوصی بپرسید