زمان کنونی: ۱۰ فروردین ۱۴۰۳, ۰۶:۱۶ ب.ظ مهمان گرامی به انجمن مانشت خوش آمدید. برای استفاده از تمامی امکانات انجمن می‌توانید عضو شوید.
گزینه‌های شما (ورودثبت نام)

رابطه بازگشتی برای دنباله های n رقمی باشرط؟

ارسال:
  

۸۸۱۴۹۸۰۴ پرسیده:

رابطه بازگشتی برای دنباله های n رقمی باشرط؟

سلام.رابطه بازگشتی برای تعداد دنباله های n رقمی از ارقام ۰و ۱و۲و۳ که شامل دنباله های ۲۱و۱۲و۱۱ نباشد؟
لطفا راه حل رو هم توضیح بدین .ممنون
نقل قول این ارسال در یک پاسخ

۳
ارسال:
  

Jooybari پاسخ داده:

RE: رابطه بازگشتی برای دنباله های n رقمی باشرط؟

سلام. این سوال مشابه سوال کنکور سال ۹۱ بوده.
فرض کنید an تعداد رشته های صحیح بطول n باشه که به ارقام ۰ تا ۳ ختم میشن. اگه رقم سمت راست ۰ یا ۳ باشه پشت سرش یه دنباله بطول n-1 میتونه بیاد که این زیررشته هارو نداره. (یعنی همون جمله n-1ام دنباله) ولی اگه رقم سمت راست قراره ۱ باشه باید قبل از ۱ یک رقم ۰ یا ۳ داشته باشیم. قبل از اون ۰ و ۳ هم میتونه یه دنباله صحیح بطول n-2 بیاد. اگه رقم سمت راست ۲ باشه علاوه بر حالتی که برای رقم یکان ۱ داشتیم، میتونیم یه تعداد ۲ داشته باشیم و بعدش ۰ یا ۳ داشته باشیم. این رابطه با P نشون داده شده. اون ۱ آخر هم برای اینه که میشه تمام ارقام از ۲ تشکیل بشن. رابطه بصورت زیر نوشته میشه:

[tex]a_n=2a_{n-1} 4a_{n-2} p_{n-2} 1[/tex]
[tex]a_0=1[/tex]
[tex]a_1=4[/tex]
[tex]p_n=\sum_{i=0}^{n-1}2a_i[/tex]

ساده شدش میشه: (با محاسبه تفاضل ۲ جمله پشت سر هم میشه به این عبارت رسید.)

[tex]a_n=3a_{n-1} 2a_{n-2}-2a_{n-3}[/tex]
[tex]a_0=1[/tex]
[tex]a_1=4[/tex]
[tex]a_2=13[/tex]
نقل قول این ارسال در یک پاسخ

ارسال:
  

y.s پاسخ داده:

RE: رابطه بازگشتی برای دنباله های n رقمی باشرط؟

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

روش درست همینه، فقط ۲ تا اشتباه تایپی داره و [tex]a_n=2a_{n-1} 5a_{n-2}[/tex] نمیتونه درست باشه(با [tex]a_3=45[/tex] تست کنید).
اشتباهات تایپی این پاسخ هم یکی مربوط میشه به [tex]p_n[/tex] که در سیگما i باید از ۰ شروع بشه تا بتونه برای مثال [tex]2a_0[/tex] رو برای [tex]a_3[/tex] تولید کنه:
[tex]p_n=\sum_{i=0}^{n-1}2a_i[/tex]
و دومی مربوط میشه به تفاضل ۲ جمله پشت سر هم که میشه :
[tex]a_n=3a_{n-1} 2a_{n-2}-2a_{n-3}[/tex]
یافتن تمامی ارسال‌های این کاربر
نقل قول این ارسال در یک پاسخ

ارسال:
  

Jooybari پاسخ داده:

RE: رابطه بازگشتی برای دنباله های n رقمی باشرط؟

(۰۸ آبان ۱۳۹۳ ۰۶:۲۳ ب.ظ)y.s نوشته شده توسط:  
(22 مهر ۱۳۹۳ ۱۲:۰۶ ق.ظ)Jooybari نوشته شده توسط:  سلام. این سوال مشابه سوال کنکور سال ۹۱ بوده.
...

روش درست همینه، فقط ۲ تا اشتباه تایپی داره و [tex]a_n=2a_{n-1} 5a_{n-2}[/tex] نمیتونه درست باشه(با [tex]a_3=45[/tex] تست کنید).
اشتباهات تایپی این پاسخ هم یکی مربوط میشه به [tex]p_n[/tex] که در سیگما i باید از ۰ شروع بشه تا بتونه برای مثال [tex]2a_0[/tex] رو برای [tex]a_3[/tex] تولید کنه:
[tex]p_n=\sum_{i=0}^{n-1}2a_i[/tex]
و دومی مربوط میشه به تفاضل ۲ جمله پشت سر هم که میشه :
[tex]a_n=3a_{n-1} 2a_{n-2}-2a_{n-3}[/tex]

سلام. متشکر. مقدار تفاضل رو درست کردم. در محاسبه اختلاف pها ضریب ۲ رو لحاظ نکرده بودم. ولی اشکالی که در p بود رو متوجه نمیشم. دنباله p باری تعداد ۲ های پشت سر همه. این تکرار ۲ مشکلی نداره ولی بعدش نباید ۱ بیاد. عدد ۱ در جمله اول هم برای اینه که این رقم میتونه تا رقم یکان تکرار بشه و لزومی نداره بعدش حتماً ۰ و ۳ بیاد.
یافتن تمامی ارسال‌های این کاربر
نقل قول این ارسال در یک پاسخ

ارسال:
  

y.s پاسخ داده:

RE: رابطه بازگشتی برای دنباله های n رقمی باشرط؟

(۰۹ آبان ۱۳۹۳ ۰۳:۴۱ ب.ظ)Jooybari نوشته شده توسط:  
(08 آبان ۱۳۹۳ ۰۶:۲۳ ب.ظ)y.s نوشته شده توسط:  
(22 مهر ۱۳۹۳ ۱۲:۰۶ ق.ظ)Jooybari نوشته شده توسط:  سلام. این سوال مشابه سوال کنکور سال ۹۱ بوده.
...

روش درست همینه، فقط ۲ تا اشتباه تایپی داره و [tex]a_n=2a_{n-1} 5a_{n-2}[/tex] نمیتونه درست باشه(با [tex]a_3=45[/tex] تست کنید).
اشتباهات تایپی این پاسخ هم یکی مربوط میشه به [tex]p_n[/tex] که در سیگما i باید از ۰ شروع بشه تا بتونه برای مثال [tex]2a_0[/tex] رو برای [tex]a_3[/tex] تولید کنه:
[tex]p_n=\sum_{i=0}^{n-1}2a_i[/tex]
و دومی مربوط میشه به تفاضل ۲ جمله پشت سر هم که میشه :
[tex]a_n=3a_{n-1} 2a_{n-2}-2a_{n-3}[/tex]

سلام. متشکر. مقدار تفاضل رو درست کردم. در محاسبه اختلاف pها ضریب ۲ رو لحاظ نکرده بودم. ولی اشکالی که در p بود رو متوجه نمیشم. دنباله p باری تعداد ۲ های پشت سر همه. این تکرار ۲ مشکلی نداره ولی بعدش نباید ۱ بیاد. عدد ۱ در جمله اول هم برای اینه که این رقم میتونه تا رقم یکان تکرار بشه و لزومی نداره بعدش حتماً ۰ و ۳ بیاد.

سلام
هر رشته به طول n یک حالت داره که همه ۲ باشن که لحاظ شده، ۲ حالت هم داره که n-1 رقم سمت راست ۲ باشه و n امین رقم ۰ یا ۳ باشه که [tex]p_n[/tex] نمیتونه این ۲ حالت رو تولید کنه، یا باید به جای اضافه کردن یک واحد ۳ واحد به رابطه اضافه کنیم و یا چون [tex]a_0=1[/tex] باید مقدار [tex]2a_0[/tex] رو به رابطه اضافه کنیم، برای مثال در [tex]a_3[/tex] داریم:
برای حالتی که رقم سمت راست ۰ یا ۳ باشد داریم : [tex]2a_2[/tex]
برای حالتی که رقم سمت راست ۱ باشد داریم : [tex]2a_1[/tex]
برای حالتی که رقم سمت راست ۲ باشد و رقم دوم ۰ یا ۳ باشد داریم : [tex]2a_1[/tex]
برای حالتی که دو رقم سمت راست ۲ باشند و رقم سوم(آخر) ۰ یا ۳ باشد ۲ حالت داریم یا : [tex]2a_0[/tex]
و در آخر برای حالتی که همه ۲ هستند ۱ حالت داریم و در مجموع:
[tex]a_3=2a_2 4a_1 2a_0 1[/tex]

[tex]a_3=45[/tex]
اگر با رابطه ای که شما نوشتید جلو بریم برای [tex]a_3[/tex] خواهیم داشت:
[tex]a_3=2a_2 4a_1 p_1 1[/tex]
[tex]p_1=0[/tex] خواهد بود و خواهیم داشت:
[tex]a_3=2a_2 4a_1 1[/tex]

[tex]a_3=43[/tex]
ولی اگه در [tex]p_n[/tex] ، سیگما از i=0 شروع بشه [tex]p_1=2a_0[/tex] خواهد شد و برای تمام n ها هم اون ۲ حالتی که n-1 رقم ۲ هست و رقم آخر ۰ یا ۳ هست رو لحاظ میکنه
یافتن تمامی ارسال‌های این کاربر
نقل قول این ارسال در یک پاسخ

ارسال:
  

Jooybari پاسخ داده:

RE: رابطه بازگشتی برای دنباله های n رقمی باشرط؟

(۰۹ آبان ۱۳۹۳ ۰۸:۴۶ ب.ظ)y.s نوشته شده توسط:  اگر با رابطه ای که شما نوشتید جلو بریم برای [tex]a_3[/tex] خواهیم داشت:
[tex]a_3=2a_2 4a_1 p_1 1[/tex]
[tex]p_1=0[/tex] خواهد بود و خواهیم داشت:
[tex]a_3=2a_2 4a_1 1[/tex]

[tex]a_3=43[/tex]
ولی اگه در [tex]p_n[/tex] ، سیگما از i=0 شروع بشه [tex]p_1=2a_0[/tex] خواهد شد و برای تمام n ها هم اون ۲ حالتی که n-1 رقم ۲ هست و رقم آخر ۰ یا ۳ هست رو لحاظ میکنه

بله درسته. متوجه شدم. چون مقدار P از عبارت حذف شده بود دقت نکردم.

[tex]a_3=3a_2 2a_1-2a_0=3*13 2*4-2*1=39 8-2=45[/tex]
یافتن تمامی ارسال‌های این کاربر
نقل قول این ارسال در یک پاسخ

۰
ارسال:
  

۸۸۱۴۹۸۰۴ پاسخ داده:

Smile RE: رابطه بازگشتی برای دنباله های n رقمی باشرط؟

دوستان خیلی ممنون.کاملا متوجه شدم.
نقل قول این ارسال در یک پاسخ

ارسال:
  

Donna پاسخ داده:

Re: رابطه بازگشتی برای دنباله های n رقمی باشرط؟

سلام.
اگر an تعداد رشته های n رقمی باشه که از ۰ و ۱ و ۲ و ۳ تشکیل شده و شامل دنباله های ۱۲ و ۲۱ و ۱۱ نباشد. میشه گفت این رشته ها سه دسته اند. رشته هایی که با ۱ ختم میشوند و رشته هایی که با ۲ ختم میشوند و رشته هایی که با ۳ و ۴ ختم میشوند.
تعداد رشته هایی که با ۱ ختم میشوند ۲-۲an هست چرا که رقم قبلی یک باید ۱ یا ۲ نباشه یعنی یا ۰ باشه یا ۳/و ۲-n رقم قبلی هم بطور بازگشتی همین شرایط رو خواهد داشت که به تعداد an-2 حالت خواهد بود.یعنی تعداد رشته های ۲ - nرقمی که شامل ۰ ۱ ۲ ۳ باشه و اون دنباله ها رو نداشته باشه.

بهمین ترتیب تعداد رشته هایی که به ۲ ختم میشوند ۲-۳anتاس. رقم قبلی دو باید یا ۰ یا ۲ یا ۳ باشه.یعنی سه حالت ممکن برای رقم دهگان موجوده. و برای ۲-n رقم قبلی هم که باز ۲-an تا.

و اگه به رقم ۳ یا ۰ ختم بشه هم که ۱-۲an حالت. چرا که رقم یکان دو حالت داره و محدودیتی برای رقم قبلیشان وجود نداره و ۱-n رقم قبلی هم که همین شرایط رو خواهد داشت و به تعداد ۱-an

پس کلن رابطه بازگشتی میشه:
an=5an-2 + 2an-1
تو عکس هم واضحتر نشون دادم. امیدوارم توضیحاتم کامل باشه



نقل قول این ارسال در یک پاسخ

ارسال:
  

Pakniat پاسخ داده:

RE: رابطه بازگشتی برای دنباله های n رقمی باشرط؟

[tex]A(n)=2A(n-1) 5A(n-2)\: ;\: A(1)=4,A(2)=13[/tex]
عنصر آخر اگر ۰ یا ۳ باشد جواب را برای n-1 عنصر دیگر به صورت بازگشتی می یابیم و اگر عنصر آخر ۱ باشد عنصر قبلی آن باید ۳ یا ۰ باشد و اگر عنصر آحر ۲ باشد عنصر قیلی می تواند ۲ یا ۳ یا ۰ باشد که مجموعا ۵ بار n-2 را بازگشنی حل می کنیم
نقل قول این ارسال در یک پاسخ



موضوع‌های مرتبط با این موضوع...
موضوع: نویسنده پاسخ: بازدید: آخرین ارسال
  نظر در رابطه با استاد داور علیصا ۰ ۱,۴۳۴ ۱۴ مهر ۱۴۰۰ ۰۶:۰۵ ب.ظ
آخرین ارسال: علیصا
  تعداد اعداد ۵ رقمی هم ارز ss311 ۲ ۲,۳۳۹ ۰۶ بهمن ۱۳۹۸ ۰۴:۳۹ ب.ظ
آخرین ارسال: ss311
  سوالی از دنباله ها و قوانین سیگما fendi ۱ ۲,۷۳۴ ۰۶ اردیبهشت ۱۳۹۸ ۰۲:۱۱ ق.ظ
آخرین ارسال: Saman
Question مشکل با درک توابع دنباله دار و مولد ؟؟؟؟ radar ۰ ۲,۴۸۷ ۱۶ دى ۱۳۹۷ ۰۴:۳۶ ب.ظ
آخرین ارسال: radar
  درخواست(محاسبه پیچیدگی زمانی)(بخش روابط بازگشتی) Saman ۶ ۶,۸۱۴ ۲۷ خرداد ۱۳۹۷ ۰۳:۲۴ ب.ظ
آخرین ارسال: saeed_vahidi
  رابطه n~1 Mr.R3ZA ۰ ۱,۷۲۳ ۲۰ خرداد ۱۳۹۷ ۰۱:۳۵ ق.ظ
آخرین ارسال: Mr.R3ZA
  توصیه های مهم در رابطه با انتخاب رشته (مهم) Happiness.72 ۰ ۱,۹۳۳ ۱۹ خرداد ۱۳۹۷ ۱۲:۳۶ ق.ظ
آخرین ارسال: Happiness.72
  بهترین زمان بهینه برای مساله بزرگترین زیر دنباله صعودی(LIS) امیدوار ۳ ۴,۱۲۶ ۱۲ خرداد ۱۳۹۷ ۰۵:۴۳ ق.ظ
آخرین ارسال: Mr.R3ZA
  رابطه چند به یک somayeh afsh ۰ ۱,۵۴۰ ۰۷ خرداد ۱۳۹۷ ۱۲:۲۸ ب.ظ
آخرین ارسال: somayeh afsh
  رسم درخت بازگشتی برای t(n)=9t(n/3)+n jumper ۶ ۶,۰۳۸ ۱۷ دى ۱۳۹۶ ۰۶:۱۶ ب.ظ
آخرین ارسال: jumper

پرش به انجمن:

Can I see some ID?

به خاطر سپاری رمز Cancel

Feeling left out?


نگران نباش، فقط روی این لینک برای ثبت نام کلیک کن. رمزت رو فراموش کردی؟ اینجا به یادت میاریم! close

رمزت رو فراموش کردی؟

Feeling left out?


نگران نباش، فقط روی این لینک برای ثبت نام کلیک کن. close