(۰۳ شهریور ۱۳۹۶ ۰۵:۲۲ ب.ظ)amir_ghanati نوشته شده توسط:  سلام

در مبحث روابط بازگشتی کتاب پوران مثال ۶ تعداد حالات چرا برابر ۲ به توان n-2 شده؟
نباید به توان n-3 بشه؟


و همچنین مثال ۸

لطفا اگر کسی از مانشتی ها بلده توضیح بدن ممنون میشم

سلام.
در اصل توی سوال ۶ داره فقط دو بیت اخر رو برسی میکنه یعنی تو حالت اول میگه اگه بیت nام برابر با ۱
باشه پس an-1 رو برسی میکنیم که شرط مارو داره یا نه اگر هم بیت nام برابر با ۰ باشه پس
باید بیت n-1 نیز برسی بشه که اونم دگ حالت داره یا ۱ هست که باز باید an-2 برسی بشه
یا اینکه ۰ هست پس شرط ما درسته و دوتا بیت از n بیت ما شرط مارو دارن و n-2 بیت دیگه
باقی میمونه که ۲^n-2 حالت رو بوجود میارن پس جواب میشه
an=an-1 + an-2 + 2^n-2

درمورد سوال ۸ من نمییدونم استدلالم درسته یا نه ولی به نظرم اینطوری میشه
بدستش اورد که یه نکته هست : در اصل تابع ما میشه
an= an-1 + an-2 + 2^n-2
که این از برسی این موضوع به وجود میاد که بیت nام ما اگر ۰ باشد پس an-1 باید برسی بشه
و اگرم بیتم nام ۱ باشه خودش دو حالت به وجود میاره که برسی بشه به این صورت میشه که
یا بیت n-1ام برابر با ۱ هستش ویا اینکه برابر با ۰ هستش که شامل جملات
an-2 + 2^n-2 میشه ولی میتونیم کلی تر نگاه کنیم و بگیم حالت ۱۱ رو حذف کنیم از کل حالات پس
n-1 ^ 2) - 1) حالت رو به وجود میاره پس میتونیم.بنویسیم
an=an-1 + 2^n-1 - 1

عکس زیرم برای تکمیل صحبتام.

مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.

(۰۳ شهریور ۱۳۹۶ ۰۸:۲۵ ب.ظ)hun73r.9h0s7 نوشته شده توسط:  

(03 شهریور ۱۳۹۶ ۰۵:۲۲ ب.ظ)amir_ghanati نوشته شده توسط:  سلام

در مبحث روابط بازگشتی کتاب پوران مثال ۶ تعداد حالات چرا برابر ۲ به توان n-2 شده؟
نباید به توان n-3 بشه؟


و همچنین مثال ۸

لطفا اگر کسی از مانشتی ها بلده توضیح بدن ممنون میشم

سلام.
در اصل توی سوال ۶ داره فقط دو بیت اخر رو برسی میکنه یعنی تو حالت اول میگه اگه بیت nام برابر با ۱
باشه پس an-1 رو برسی میکنیم که شرط مارو داره یا نه اگر هم بیت nام برابر با ۰ باشه پس
باید بیت n-1 نیز برسی بشه که اونم دگ حالت داره یا ۱ هست که باز باید an-2 برسی بشه
یا اینکه ۰ هست پس شرط ما درسته و دوتا بیت از n بیت ما شرط مارو دارن و n-2 بیت دیگه
باقی میمونه که ۲^n-2 حالت رو بوجود میارن پس جواب میشه
an=an-1 + an-2 + 2^n-2

درمورد سوال ۸ من نمییدونم استدلالم درسته یا نه ولی به نظرم اینطوری میشه
بدستش اورد که یه نکته هست : در اصل تابع ما میشه
an= an-1 + an-2 + 2^n-2
که این از برسی این موضوع به وجود میاد که بیت nام ما اگر ۰ باشد پس an-1 باید برسی بشه
و اگرم بیتم nام ۱ باشه خودش دو حالت به وجود میاره که برسی بشه به این صورت میشه که
یا بیت n-1ام برابر با ۱ هستش ویا اینکه برابر با ۰ هستش که شامل جملات
an-2 + 2^n-2 میشه ولی میتونیم کلی تر نگاه کنیم و بگیم حالت ۱۱ رو حذف کنیم از کل حالات پس
n-1 ^ 2) - 1) حالت رو به وجود میاره پس میتونیم.بنویسیم
an=an-1 + 2^n-1 - 1

عکس زیرم برای تکمیل صحبتام.

مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.

ممنون از پاسختون درباره مثال ۸ مثل شما حل کرده بودم ولی دیدم جواب جوری دیگه هست شک کردم

ببخشید این که در مثال هایی که درباره فاقد بودن یک رشته مطرح شده چرا مثال گفته n-3 بیت قبل و شده an-3 ولی اینجا حالات رو در نظر گرفته و شده ۲^n-1 مثلا؟
این که یه جا حالات رو در نظر گرفته یه جا دیگه بیت ها رو متوجه نمیشم چه طوریه
لطفا اینم توضیح میدید با تشکر

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

(03 شهریور ۱۳۹۶ ۰۸:۲۵ ب.ظ)hun73r.9h0s7 نوشته شده توسط:  

(03 شهریور ۱۳۹۶ ۰۵:۲۲ ب.ظ)amir_ghanati نوشته شده توسط:  سلام

در مبحث روابط بازگشتی کتاب پوران مثال ۶ تعداد حالات چرا برابر ۲ به توان n-2 شده؟
نباید به توان n-3 بشه؟


و همچنین مثال ۸

لطفا اگر کسی از مانشتی ها بلده توضیح بدن ممنون میشم

سلام.
در اصل توی سوال ۶ داره فقط دو بیت اخر رو برسی میکنه یعنی تو حالت اول میگه اگه بیت nام برابر با ۱
باشه پس an-1 رو برسی میکنیم که شرط مارو داره یا نه اگر هم بیت nام برابر با ۰ باشه پس
باید بیت n-1 نیز برسی بشه که اونم دگ حالت داره یا ۱ هست که باز باید an-2 برسی بشه
یا اینکه ۰ هست پس شرط ما درسته و دوتا بیت از n بیت ما شرط مارو دارن و n-2 بیت دیگه
باقی میمونه که ۲^n-2 حالت رو بوجود میارن پس جواب میشه
an=an-1 + an-2 + 2^n-2

درمورد سوال ۸ من نمییدونم استدلالم درسته یا نه ولی به نظرم اینطوری میشه
بدستش اورد که یه نکته هست : در اصل تابع ما میشه
an= an-1 + an-2 + 2^n-2
که این از برسی این موضوع به وجود میاد که بیت nام ما اگر ۰ باشد پس an-1 باید برسی بشه
و اگرم بیتم nام ۱ باشه خودش دو حالت به وجود میاره که برسی بشه به این صورت میشه که
یا بیت n-1ام برابر با ۱ هستش ویا اینکه برابر با ۰ هستش که شامل جملات
an-2 + 2^n-2 میشه ولی میتونیم کلی تر نگاه کنیم و بگیم حالت ۱۱ رو حذف کنیم از کل حالات پس
n-1 ^ 2) - 1) حالت رو به وجود میاره پس میتونیم.بنویسیم
an=an-1 + 2^n-1 - 1

عکس زیرم برای تکمیل صحبتام.

مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.

ممنون از پاسختون درباره مثال ۸ مثل شما حل کرده بودم ولی دیدم جواب جوری دیگه هست شک کردم

ببخشید این که در مثال هایی که درباره فاقد بودن یک رشته مطرح شده چرا مثال گفته n-3 بیت قبل و شده an-3 ولی اینجا حالات رو در نظر گرفته و شده ۲^n-1 مثلا؟
این که یه جا حالات رو در نظر گرفته یه جا دیگه بیت ها رو متوجه نمیشم چه طوریه
لطفا اینم توضیح میدید با تشکر

خواهش میکنم.
در حقیقت این که توی جواب دادن به اینجور سوالات اون حالت رو در نظر نگیریم
و جواب کلی رو بدیم یعنی مثلا
an = an-1 + an-2 + 2^n-3
بنویسیم یا اینکه اون جواب رو بدیم که یک حالت رو حذف کنه یعنی
an = an-1 + 2^n-1 - 1
کدوم رو انتخاب کنیم و درست تره رو جوابشو نمیدونم ولی به نظرم
چیزی که هست اینه که توی این جور سوالات جواب ها میتونه متفاوت باشه و استدلال
خاصی نداره که حتما از یک روش خاص حل بشن مثلا اگه شما دقت کنین توی همون صفحه
مثال ۷ هم میتونه همینطوری بهش نگاه کنیم
جواب خود کتاب :
an = an-1 + an-2 + an-3 + 2^ n-3
ولی میشه اینطور هم نوشتش که
an = an-1 + an-2 + 2 ^ n-2 -1
این جوابم باید درست باشه با توجه به مثال ۸
من خودم اینطور برداشت میکنم که ما اگه بخواییم یکی از
جملات یعنی جمله اخر an-3 رو حذف کنیم ( طبق مثال ۷ )
لازمه تمام رشته هایی که با n-2 بیت باقی مونده میشه رو حساب کنیم
منهای یه رشته خاص که بیت اخر از سمت راستش ۱ هست کنیم
یعنی
۱ - (۲^ n-2)
اگه بهتر بخوام بگم ما جمله
an-3 + 2 ^ n-3
رو میخواییم حذف کنیم پس
میاییم n-2 بیت رو تمام حالتاشو حساب میکنیم
منهای یک حالت میکنیم.
امید وارم متوجه صحبتام شده باشید

تشکر

ببخشید مثال ۱۲ و ۱۳ چه طوری حلش میشه این دوتا رو هم توضیح بدید؟
مثال ۱۲ از رابطه فیبوناچی چه روش حلی دارد؟