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

[attachment=14547]
در صورتی که a_n تعداد کلمات n حرفی با حروف a,bو cباشد که در آن ها هر حرف a حداقل با یک حرف b مجاور است رابطه بازگشتی برای a_n معادل کدام یک از گزینه های زیر است؟
ج:
a_n+1=2a_n+a_n-1+2a_n-2

a_n:یعنی a اندیس n

ممنون میشم یکی این ج را به صورت تشریحی یا با یک عکس یا شکلی توضیح بده ج پارسه رو من گذاشتم ولی به صورت ریاضی گفته من متوجه نمی شم مخصوصا اون قسمت ۲a_n-2 را که چرا اضافه کرده ممنون میشم اگه کسی توضیح واضح تری داره بگه!ممنون.

(19 دى 1392 08:05 ب.ظ)mahsalove نوشته شده توسط: [ -> ]در صورتی که a_n تعداد کلمات n حرفی با حروف a,bو cباشد که در آن ها هر حرف a حداقل با یک حرف b مجاور است رابطه بازگشتی برای a_n معادل کدام یک از گزینه های زیر است؟
ج:
a_n+1=2a_n+a_n-1+2a_n-2

a_n:یعنی a اندیس n

ممنون میشم یکی این ج را به صورت تشریحی یا با یک عکس یا شکلی توضیح بده ج پارسه رو من گذاشتم ولی به صورت ریاضی گفته من متوجه نمی شم مخصوصا اون قسمت ۲a_n-2 را که چرا اضافه کرده ممنون میشم اگه کسی توضیح واضح تری داره بگه!ممنون.

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


اگر (a(n را تعداد حالتهایی در نظر بگیریم که در آن a و b کنار هم هستند داریم:
اگر خانه آخر a نباشد (یعنی b یا c باشد) ، (a(n-1 خانه بعدی باید حالت مسئله را داشته باشند
اگر خانه آخر a باشد و خانه قبل از آن a یا c باشد (a(n-2 خانه بعدی باید حالت مسئله داشته باشند
اگر خانه آخر a باشد و خانه قبل از آن b باشد در دیگر خانه هیچ محدودیتی نداریم و به طریق میتوانیم آنرا پر کنیم. البته چون جای a و b میتواند عوض شود باید در 2 ضرب کرد.
در مجموع همان میشود که آوردم.


امیدوارم بقیه دوستان هم کمک کنند تا به نتیجه برسیم

سلام. اینجا یه دنباله جدید تعریف کرده که حل مسئله رو یکم پیچونده. رشته های این مجموعه بطول n به یکی از سمبلهای a,b,c ختم میشن:
تعداد رشته هایی که به c ختم میشن برابر رشته های بطول n-1 خواهد بود که آخرش c قرار میدیم. [tex](a_{n-1})[/tex]
** تعداد رشته هایی که با a ختم میشن برابر رشته های بطول n-2 خواهد بود که آخرش ba قرار میدیم بعلاوه رشته هایی که به a بدون b ختم میشوند. [tex](a_{n-2} ...)[/tex]
تعداد رشته هایی که به b ختم میشن برابر مجموع حالت های زیر میشه:
رشته های بطول n-1 که آخرش b قرار میدیم. [tex](a_{n-1})[/tex]
رشته های بطول n-2 که به a ختم میشن و آخرش ab قرار میدیم. [tex](a_{n-4})[/tex]
رشته های بطول n-2 که به c ختم میشن و آخرش ab قرار میدیم. [tex](a_{n-3})[/tex]
جواب میشه همون جواب پارسه [tex]a_n=2a_{n-1} a_{n-2} 2a_{n-3}[/tex].

اشتباهم توی عدم شمارش رشته هایی بود که خودشون جزء زبان نیستن ولی با قرار دادن b در آخرشون جزء زبان میشن. روش پارسه مطمئن تر بود. یعنی بهتر بود از دنباله b استفاده میکردم.

روش پارسه:
در تعریف a:
[tex]b_{n-1}[/tex] برای تعداد رشته هایی که به a ختم میشن.
[tex]b_{n}[/tex] برای تعداد رشته هایی که به b ختم میشن.
[tex]a_{n-1}[/tex] برای تعداد رشته هایی که به c ختم میشن.
در تعریف b:
[tex]a_{n-2}[/tex] برای تعداد رشته هایی که حرف یکی مونده به آخرشون a هست.
[tex]b_{n-1}[/tex] برای تعداد رشته هایی که حرف یکی مونده به آخرشون b هست.
[tex]a_{n-2}[/tex] برای تعداد رشته هایی که حرف یکی مونده به آخرشون c هست.

از تفریق دو رابطه به [tex]2b_n=a_n-a_{n-1} 2a_{n-2}[/tex] میرسیم. با جایگزینی مقادیر به [tex]a_n=2a_{n-1} a_{n-2} 2a_{n-3}[/tex] میرسیم.

بابت پاسخ اولیه اشتباهم عذرخواهی میکنم.
موفق باشید.

---

(19 دى 1392 09:42 ب.ظ)wokesh نوشته شده توسط: [ -> ]اگر خانه آخر a نباشد (یعنی b یا c باشد) ، (a(n-1 خانه بعدی باید حالت مسئله را داشته باشند

اگه حرف آخر b باشد تعداد حالت از جمله n-1 بیشتر خواهد بود. به رشته cab دقت کنید. ca جزء جمله n-1ام نیست.

(19 دى 1392 09:42 ب.ظ)wokesh نوشته شده توسط: [ -> ]...اگر خانه آخر a باشد و خانه قبل از آن a یا c باشد (a(n-2 خانه بعدی باید حالت مسئله داشته باشند...

این حالت کاملاً اشتباهه. حرف قبل از a فقط میتونه b باشه.

(19 دى 1392 09:42 ب.ظ)wokesh نوشته شده توسط: [ -> ]...اگر خانه آخر a باشد و خانه قبل از آن b باشد در دیگر خانه هیچ محدودیتی نداریم و به طریق میتوانیم آنرا پر کنیم....

اینجا هم محدودیت داریم. باید جمله n-2 رو قرار بدید.

(20 دى 1392 12:12 ق.ظ)Jooybari نوشته شده توسط: [ -> ]سلام. اینجا یه دنباله جدید تعریف کرده که حل مسئله رو یکم پیچونده. رشته های این مجموعه بطول n به یکی از سمبلهای a,b,c ختم میشن:
تعداد رشته هایی که به c ختم میشن برابر رشته های بطول n-1 خواهد بود که آخرش c قرار میدیم. [tex](a_{n-1})[/tex]
تعداد رشته هایی که با a ختم میشن برابر رشته های بطول n-2 خواهد بود که آخرش ba قرار میدیم. [tex](a_{n-2})[/tex]
تعداد رشته هایی که به b ختم میشن برابر مجموع حالت های زیر میشه:
رشته های بطول n-1 که آخرش b قرار میدیم. [tex](a_{n-1})[/tex]
رشته های بطول n-2 که به a ختم میشن و آخرش ab قرار میدیم. [tex](a_{n-4})[/tex]
رشته های بطول n-2 که به c ختم میشن و آخرش ab قرار میدیم. [tex](a_{n-3})[/tex]
جواب میشه [tex]a_n=2a_{n-1} a_{n-2} a_{n-3} a_{n-4}[/tex].

پارسه روش درستی انتخاب کرد ولی رابطه بازگشتی b رو به اشتباه بدست آورد. رابطه بازگشتی [tex]b_n=a_{n-2} b_{n-1} b_{n-2}[/tex] میشه.

موفق باشید.

---

(19 دى 1392 09:42 ب.ظ)wokesh نوشته شده توسط: [ -> ]اگر خانه آخر a نباشد (یعنی b یا c باشد) ، (a(n-1 خانه بعدی باید حالت مسئله را داشته باشند

اگه حرف آخر b باشد تعداد حالت از جمله n-1 بیشتر خواهد بود. به رشته cab دقت کنید. ca جزء جمله n-1ام نیست.

(19 دى 1392 09:42 ب.ظ)wokesh نوشته شده توسط: [ -> ]...اگر خانه آخر a باشد و خانه قبل از آن a یا c باشد (a(n-2 خانه بعدی باید حالت مسئله داشته باشند...

این حالت کاملاً اشتباهه. حرف قبل از a فقط میتونه b باشه.

(19 دى 1392 09:42 ب.ظ)wokesh نوشته شده توسط: [ -> ]...اگر خانه آخر a باشد و خانه قبل از آن b باشد در دیگر خانه هیچ محدودیتی نداریم و به طریق میتوانیم آنرا پر کنیم....

اینجا هم محدودیت داریم. باید جمله n-2 رو قرار بدید.

خوب اگه هر کی بخواهد یه ج بده که نمیشه چون از نظر منم یه ج دیگه میتونه داشته باشه!
2 حالت با b یا c تموم میشه پس روی بقیه بازگشت میزنیم!میشه 2a_n-1
حالا اگر آخریش a باشه باید قبلش حتما b باشه پس رو a_n-2 بازگشت میزنیم!
یعنی a_n=2a_n-1+a_n-2
که ج من تو گزینه ها هست ولی ج که شما دادید نیست!

(20 دى 1392 12:12 ق.ظ)Jooybari نوشته شده توسط: [ -> ]سلام. اینجا یه دنباله جدید تعریف کرده که حل مسئله رو یکم پیچونده. رشته های این مجموعه بطول n به یکی از سمبلهای a,b,c ختم میشن:
تعداد رشته هایی که به c ختم میشن برابر رشته های بطول n-1 خواهد بود که آخرش c قرار میدیم. [tex](a_{n-1})[/tex]
تعداد رشته هایی که با a ختم میشن برابر رشته های بطول n-2 خواهد بود که آخرش ba قرار میدیم. [tex](a_{n-2})[/tex]
تعداد رشته هایی که به b ختم میشن برابر مجموع حالت های زیر میشه:
رشته های بطول n-1 که آخرش b قرار میدیم. [tex](a_{n-1})[/tex]
رشته های بطول n-2 که به a ختم میشن و آخرش ab قرار میدیم. [tex](a_{n-4})[/tex]
رشته های بطول n-2 که به c ختم میشن و آخرش ab قرار میدیم. [tex](a_{n-3})[/tex]
جواب میشه [tex]a_n=2a_{n-1} a_{n-2} a_{n-3} a_{n-4}[/tex].

پارسه روش درستی انتخاب کرد ولی رابطه بازگشتی b رو به اشتباه بدست آورد. رابطه بازگشتی [tex]b_n=a_{n-2} b_{n-1} b_{n-2}[/tex] میشه.

موفق باشید.

آنوقت معادله شما برای ۳=n چه جوابی میدهد؟ به نظرم برای آن جواب صفر میدهد که واضح است که اشتباه است.

(20 دى 1392 01:57 ق.ظ)wokesh نوشته شده توسط: [ -> ]
آنوقت معادله شما برای ۳=n چه جوابی میدهد؟ به نظرم برای آن جواب صفر میدهد که واضح است که اشتباه است.

به ازای n=0 برابر 1
به ازای n=1 برابر 2
به ازای n=2 برابر 6
به ازای n=3 برابر 16
به ازای nهای بزرگتر از 3 از رابطه استفاده میشه. به تعداد اختلاف جملات اندیس به مقدار اولیه نیاز داریم. بهتره که جمله چهارم رو هم دستی محاسبه کنیم و برای مقدار بازگشتی از جمله 0ام استفاده نکنیم.

---

(20 دى 1392 01:10 ق.ظ)mahsalove نوشته شده توسط: [ -> ]خوب اگه هر کی بخواهد یه ج بده که نمیشه چون از نظر منم یه ج دیگه میتونه داشته باشه!
۲ حالت با b یا c تموم میشه پس روی بقیه بازگشت میزنیم!میشه ۲a_n-1
حالا اگر آخریش a باشه باید قبلش حتما b باشه پس رو a_n-2 بازگشت میزنیم!
یعنی a_n=2a_n-1+a_n-2
که ج من تو گزینه ها هست ولی ج که شما دادید نیست!

من هم به همین جواب شما فکر کردم. مورد نقض این جواب رو هم گفتم. رشته cab جزء جواب برای حالات بطول 3 هست ولی ca جزء حالات بطول 2 نیست.

عذرخواهی میکنم. یه حالت رو درنظر نگرفته بودم که توی ارسال اولم ویرایش میکنم. با ** مشخص کردم. جواب پارسه درسته.