سلام. تعداد رشته هایی که فاقد یک زیررشته خاص هستن رو با روش بازگشتی محاسبه میکنیم. برای اینکه زیررشته ۰۱۰ نداشته باشیم به روش زیر عمل میکنیم:
فرض میکنیم Wn یک رشته بدون زیررشته ۰۱۰ باشه. تعداد Wnها رو برابر An میگیریم. رشته هایی که زیررشته ۰۱۰ ندارن و طولشون بزگترمساوی ۳ هست به یکی از حالتهای زیر ختم میشن:
۱ : در این حالت باید یک رشته Wn-1 قبل از این رشته بیاد. تعداد رشته های این حالت برابر An-1 میشه.
۱۱۰ : در این حالت باید یک رشته Wn-3 قبل از این رشته بیاد. تعداد رشته های این حالت برابر An-3 میشه.
۱۱۰۰ : ...
۱۱۰۰۰ : ...
....
۰۰۰///۰۰۰ : این رشته شامل n-1 رقم ۰ است. رقم آخر میتونه ۰ یا ۱ باشه.
با جمع موارد بالا خواهیم داشت:

[tex]A_n=A_{n-1} A_{n-3} A_{n-4} ... A_0 2[/tex]

برای حذف تناوب کافیه جمله nام رو منهای جمله n-1ام کنیم.

[tex]A_n-A_{n-1}=A_{n-1}-A_{n-2} A_{n-3}[/tex]

با ساده سازی داریم:

[tex]A_n=2A_{n-1}-A_{n-2} A_{n-3}[/tex]

(۲۲ مهر ۱۳۹۴ ۱۱:۱۴ ب.ظ)Jooybari نوشته شده توسط:  سلام. تعداد رشته هایی که فاقد یک زیررشته خاص هستن رو با روش بازگشتی محاسبه میکنیم. برای اینکه زیررشته ۰۱۰ نداشته باشیم به روش زیر عمل میکنیم:

خیلی ممنون بابت توضیحات کاملتون

---

(۲۲ مهر ۱۳۹۴ ۱۱:۲۷ ب.ظ)ali77 نوشته شده توسط:  چند تا نکته: طول رشته ممونه درجه معادله بازگشتی ر ومشخص میکنه
وقتی ممنوعه هست شما یه متغیر میگیری روش دوم میگی مثلا x این x برای +های تولیدی به ازای اضافه شدن یک بیت این رشته به چند حالت دیگه میتونه تبدیل میشه..... اخرش تعداد حالاتو جمع میزنی..... فرمولشو میسازی روش ۲رو بیخیال شو اگر متوجه نشدی بگو برات حل کنم بفرستم جمعه

خیلی ممنونم
فقط اون نکات و روش دوم رو متوجه نشدم! اگه میشه لطف کنید بیشتر توضیح بدین.

(۲۲ مهر ۱۳۹۴ ۱۱:۱۴ ب.ظ)Jooybari نوشته شده توسط:  سلام. تعداد رشته هایی که فاقد یک زیررشته خاص هستن رو با روش بازگشتی محاسبه میکنیم. برای اینکه زیررشته ۰۱۰ نداشته باشیم به روش زیر عمل میکنیم:
فرض میکنیم Wn یک رشته بدون زیررشته ۰۱۰ باشه. تعداد Wnها رو برابر An میگیریم. رشته هایی که زیررشته ۰۱۰ ندارن و طولشون بزگترمساوی ۳ هست به یکی از حالتهای زیر ختم میشن:
۱ : در این حالت باید یک رشته Wn-1 قبل از این رشته بیاد. تعداد رشته های این حالت برابر An-1 میشه.
۱۱۰ : در این حالت باید یک رشته Wn-3 قبل از این رشته بیاد. تعداد رشته های این حالت برابر An-3 میشه.
۱۱۰۰ : ...
۱۱۰۰۰ : ...
....
۰۰۰///۰۰۰ : این رشته شامل n-1 رقم ۰ است. رقم آخر میتونه ۰ یا ۱ باشه.
با جمع موارد بالا خواهیم داشت:

[tex]A_n=A_{n-1} A_{n-3} A_{n-4} ... A_0 2[/tex]

برای حذف تناوب کافیه جمله nام رو منهای جمله n-1ام کنیم.

[tex]A_n-A_{n-1}=A_{n-1}-A_{n-2} A_{n-3}[/tex]

با ساده سازی داریم:

[tex]A_n=2A_{n-1}-A_{n-2} A_{n-3}[/tex]

مرسی. خیلی خوب بود.اما کاش درست بودنش هم تایید میشد

(۲۲ مهر ۱۳۹۴ ۰۶:۵۶ ب.ظ)ƊƦЄƛM نوشته شده توسط:  سلام
لطفا راهنماییم کنید.

سوال سنگینیه تمرین روزن هست سخترین سوال ممکن توی نوشتن روابط بازگشتی ۲روش دار ه یه روش که همه کتابها بخصوص کتاب دکتر یوسفی تشریح کردن روش دوم هم یه روش جدیده کسی بلد نیست یه استادی بهم یا د داد که تستی میشه سریع حلش کردم اما روش اصولی و کلیش اینه روش کتابها و بخصوص پوران:
این رشته اخرین بیتش دوحالت داره یا ۰ هست یا ۱ هست اگر ۱ بود که n-1 بیت مابقی باید فاقد ۰۱۰ باشد an-1 اگر اخرش ۰ بود بیت ماقبلش یعنی بیت n-1 امی خودش دو حالت داره یا ۰ هست یا یک اگر ۱بود باید حتما بیت سومی از اخر یعنی n-3 1 باشد تا ۰۱۰ تولید نشود حال مابقی مسئله همین شرایط ر وداشته باشد میشه An-3 و اگر بیت دومی از اخرan-2 0 بود الان۲تای اخر ۰ شده پس بیت n-3 می هم ۲ حالت داره یا ۰ یا ۱ اگر ۰ بود باز خودش ۲ خالت داره.................... کاش گوشیم سالم بو د برات عکس میگرفتم توضیح میدادم این ی هسری دنباله بدست میاد که برای حلش میای توی اون سری جای n دررابطه n-1 قرار میدی و یه دنباله دیگه تولید میشه اون اولی رو از این دومی که n منهای گذاشتی کم میکنی تهش an=2an-1 - an-2 + an-3
چند تا نکته: طول رشته ممونه درجه معادله بازگشتی ر ومشخص میکنه
وقتی ممنوعه هست شما یه متغیر میگیری روش دوم میگی مثلا x این x برای +های تولیدی به ازای اضافه شدن یک بیت این رشته به چند حالت دیگه میتونه تبدیل میشه..... اخرش تعداد حالاتو جمع میزنی..... فرمولشو میسازی روش ۲رو بیخیال شو اگر متوجه نشدی بگو برات حل کنم بفرستم جمعه

مشابه این سوال من یه جایی دیدم ،اینطوری حل کرده بود.به صورت درختی.
An=An-1+An-2+An-3

(۰۷ فروردین ۱۳۹۵ ۰۲:۲۹ ق.ظ)peace2013 نوشته شده توسط:  مشابه این سوال من یه جایی دیدم ،اینطوری حل کرده بود.به صورت درختی.
An=An-1+An-2+An-3

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

این سوال سخت نیست
کسی اگر میتونه رشته های شامل ۰۱۰ رو بنویسه فرمولشو
دیروز ۱ساعت نیم شد نوشتمش
البته هردوموردش خیلی مهم هستن

(۰۷ فروردین ۱۳۹۵ ۱۱:۴۰ ب.ظ)good arman نوشته شده توسط:  این سوال سخت نیست
کسی اگر میتونه رشته های شامل ۰۱۰ رو بنویسه فرمولشو
دیروز ۱ساعت نیم شد نوشتمش
البته هردوموردش خیلی مهم هستن

سلام. مقدار [tex]A_n[/tex] که نشون دهنده تعداد زشته های بطول n بود که زیررشته ۰۱۰ نداشتن رو که حساب کردیم. تعداد رشته هایی که زیررشته ۰۱۰ دارن میشه [tex]2^n-A_n[/tex].

(۰۷ فروردین ۱۳۹۵ ۱۱:۵۶ ب.ظ)Jooybari نوشته شده توسط:  

(07 فروردین ۱۳۹۵ ۱۱:۴۰ ب.ظ)good arman نوشته شده توسط:  این سوال سخت نیست
کسی اگر میتونه رشته های شامل ۰۱۰ رو بنویسه فرمولشو
دیروز ۱ساعت نیم شد نوشتمش
البته هردوموردش خیلی مهم هستن

سلام. مقدار [tex]A_n[/tex] که نشون دهنده تعداد زشته های بطول n بود که زیررشته ۰۱۰ نداشتن رو که حساب کردیم. تعداد رشته هایی که زیررشته ۰۱۰ دارن میشه [tex]2^n-A_n[/tex].

===============
فرض کن فرمولشو ازمون خواستن و اعداد کوچیک هم نمیشه توش جایگذاری کنیم اونوقته که مجبوریم فرمول رشته های شامل رو هم بنویسیم که از اخر که بررسی میکنیم ۴ شاخه میشه ۲تاشو بعد یک مرحاه میشه ببندیم که میشنan1 و an.3 اما اون ۲شاخه هه که از اخرش همش۰۰۰ میاد هی هر بار ۲شاخه میشه ویکیشون ۰ و یکیشون ۱ که هر بار نمایی ئ..
البته دیروز تو حل تست اصفهان دکتر یوسفی گفت این خیلی سنگینه بعیده تو کنکور بیاد و البته حل اش هم کرده بود واسه دوستم

(۰۸ فروردین ۱۳۹۵ ۱۱:۱۲ ب.ظ)good arman نوشته شده توسط:  فرض کن فرمولشو ازمون خواستن و اعداد کوچیک هم نمیشه توش جایگذاری کنیم اونوقته که مجبوریم فرمول رشته های شامل رو هم بنویسیم که از اخر که بررسی میکنیم ۴ شاخه میشه ۲تاشو بعد یک مرحاه میشه ببندیم که میشنan1 و an.3 اما اون ۲شاخه هه که از اخرش همش۰۰۰ میاد هی هر بار ۲شاخه میشه ویکیشون ۰ و یکیشون ۱ که هر بار نمایی ئ..
البته دیروز تو حل تست اصفهان دکتر یوسفی گفت این خیلی سنگینه بعیده تو کنکور بیاد و البته حل اش هم کرده بود واسه دوستم

شما تعداد رشته ها رو قصد دارید حساب کنید یا یک رابطه بازگشتی؟ وقتی بشه با یه تفریق ساده و یک رابطه بازگشتی که محاسبش ساده تره این کار رو انجام بدیم چرا باید رابطه بازگشتی به این شکل رو محاسبه کنیم؟ سوال به این شکل هم تو کنکور دکتری دو یا سه سال اخیر اومده بود. رابطه بازگشتی رو هم اگه قصد دارید حساب کنید میشه: (این رابطه رو از رابطه سوال اول گرفتم.)

(۰۹ فروردین ۱۳۹۵ ۰۲:۵۴ ق.ظ)Jooybari نوشته شده توسط:  

(08 فروردین ۱۳۹۵ ۱۱:۱۲ ب.ظ)good arman نوشته شده توسط:  فرض کن فرمولشو ازمون خواستن و اعداد کوچیک هم نمیشه توش جایگذاری کنیم اونوقته که مجبوریم فرمول رشته های شامل رو هم بنویسیم که از اخر که بررسی میکنیم ۴ شاخه میشه ۲تاشو بعد یک مرحاه میشه ببندیم که میشنan1 و an.3 اما اون ۲شاخه هه که از اخرش همش۰۰۰ میاد هی هر بار ۲شاخه میشه ویکیشون ۰ و یکیشون ۱ که هر بار نمایی ئ..
البته دیروز تو حل تست اصفهان دکتر یوسفی گفت این خیلی سنگینه بعیده تو کنکور بیاد و البته حل اش هم کرده بود واسه دوستم

شما تعداد رشته ها رو قصد دارید حساب کنید یا یک رابطه بازگشتی؟ وقتی بشه با یه تفریق ساده و یک رابطه بازگشتی که محاسبش ساده تره این کار رو انجام بدیم چرا باید رابطه بازگشتی به این شکل رو محاسبه کنیم؟ سوال به این شکل هم تو کنکور دکتری دو یا سه سال اخیر اومده بود. رابطه بازگشتی رو هم اگه قصد دارید حساب کنید میشه: (این رابطه رو از رابطه سوال اول گرفتم.)

[tex]B_n=2^n-A_n=2^n-2A_{n-1} A_{n-2}-A_{n-3}=2^n-2(2^{n-1}-B_{n-1}) (2^{n-2}-B_{n-2})-(2^{n-3}-B_{n-3})[/tex]
[tex]B_n=2B_{n-1}-B_{n-2} B_{n-3} 2^{n-3}[/tex]

ممنونم