سلام بچه ها چندتا سوال داشتم ممنون میشم اگه می تونید راهنمایی کنید
چند درخت دودویی متفاوت با n گره و ارتفاع n می توان داشت؟(سطح ریشه ۰ )
چند درخت دودویی متفاوت با n گره و ارتفاع n-1 می توان داشت؟(سطح ۰ ) و (سطح۱)
چه تعداد درخت دودویی محض با n گره میتوان داشت؟
بچه ها فکر کنم 2تا سوال اول رو فهمیدم جوابش اینجوری میشه؟اگه اشتباه نوشتم میشه راهنمایی کنید؟
اولی میشه 2 به توان n-1
دومی هم واسه سطح ریشه 0 میشه مثل اولی ، اما واسه سطح ریشه 1 میشه 2n-5*2^n-3
اما سومی رو میدونم که برای n>=3 ،واسه n=3 میشه 1درخت واسه n=5 میشه 2درخت... ،اما فرمولش نمی دونم چی میشه کسی میدونه؟
سوال سوم: من برای جند حالت پیش رفتم فکر کنم بشه بنویسیم
T(3)=1 ---->1
T(5)=2---->2
T(7)=5---->3
T(9)=14---->4
...
T(n)=3*T(n-1)-1
شایدم غلط باشه. بچه ها بحث کنن. در ضمن معادله بالا را می تونین توسط معادلات غیر همگن حل کنین و جواب مستقیم براش به دست بیارین.
T(n)-3T(n-1)=1
(r^2-3r)(r-1)=0
T(n)=c1*1^n+c2*3^n
T(n)=0.5*1^n+(1/6)*3^n
ممنون از جوابتون
اما اگه فرمولتون درست باشه فکر کنم باید اینجوری باشه
T(n)=3*T(n-2)-1
آخه فقط واسه تعداد گره های فرد درخت، دودویی محض میشه درسته؟ اونجوری n-1 شامل تعداد گره های زوج هم میشه اما با گره زوج، درختمون دودویی محض نمیشه..
اگه دقت کنین من این طوری نوشتم
T(3)=1 ---->1
T(5)=2---->2
یعنی جمله اول (3)Tو دوم(5)T. به عبارتی
T(1)=1
T(2)=2
من با شماره ها کار کردم یعنی 1و2. حرف شما هم درسته می تونین اون شکلی هم در نظر بگیرین هیچ تفاوتی نمی کنه فقط یه تغییر متغیره
ممنونم از جوابتون..مفید بود