PDA

نسخه کامل مشاهده نسخه کامل : یک سوال !!



soheilsmart
13-04-2009, 18:42
خودم خیلی رو این سوال فکر کردم ولی به نتیجه ی مطلوبی نرسیدم هنوز
اگه کسی میتونه حل کنه ممنون میشم!
a,e دو راس روبروی 8 ضلعی منتظم abcdefgh می باشند. قورباغه از راس a شروع به جهیدن می کند
و هر بار به راس مجاور می پرد ولی هر بار که به راس e رسید انجا توقف می کند.
a(n را تعداد مسیر هایی می گیریم که قورباغه از طریق انها با n جهش به e می رسد.
رابطه بازگشتی برای این مساله بیابید!نیاز به پیدا کردن تعداد جواب ها نیس ! فقط رابطه ی بازگشتی
ممنون!
واضح که به ازای n های فرد a(n صفر است!

saber57
13-04-2009, 19:58
قورباغه بار اول با 4 بار جهش به نقطه e میرسه که شد 1 مسیر و اونجا می ایسته حالا بین 4 و 8 هیچ اتفاقی نمیفته یعنی نهایتا با 8 با جهش به نقطه اولیه برمیگرده باز هم یک مسیر(دقت کنید از a به e) حالا 4 جهش دیگه یعنی مضرب 3 ضربدر 4 پس اینبار با 12 جهش 2 مسیر از a به e رسیده برای 16 (مضرب 4 )دوباره نقطه اولیه .
نتیجه میگیریم که به تعداد حاصلضرب 4 در مضرب فرد جهش ، مضرب فرد مسیر خواهیم داشت یعنی:


a( n)=2k-1 k>=1

(n=4* (2k-1


(a( n تعداد مسیر و n تعداد جهش

soheilsmart
13-04-2009, 20:08
دوست عزیز احساس می کنم منظور سوال رو اشتباه منوجه شدید!
در حالت n=4,
2 حالت داریم
abcde,ahgfe
در حالت n=6 وقتی می خواهیم بررسی کنیم!
مساله رو دوباره از اول پی می گیریم
یعنی فرض میکنیم قورباغه در نقطه a قرار دارد به چند حالت میتونه به e برسه!
اگه حالات مختلف را بنویسیم میشه 8 تا !

saber57
13-04-2009, 20:20
دوست عزیز احساس می کنم منظور سوال رو اشتباه منوجه شدید!
در حالت n=4,
2 حالت داریم
abcde,ahgfe
در حالت n=6 وقتی می خواهیم بررسی کنیم!
مساله رو دوباره از اول پی می گیریم
یعنی فرض میکنیم قورباغه در نقطه a قرار دارد به چند حالت میتونه به e برسه!
اگه حالات مختلف را بنویسیم میشه 8 تا !

ببینید قورباغه وقتی مسیر abcde رو میره می ایسته !!!! این 4 جهش و 1 مسیر . حالا از نقطه e با 4 حالت دیگه یا از همون مسیر قبلی abcde یا از مسیر efgha به نقطه a بر میگرده بنابراین تعداد مسیرهای از a به e در یک دور کامل معادل با 8 جهش یک دور میشه!!!! (دقت کنید از a به e نه از e به a )

saber57
13-04-2009, 20:25
اگر رفت و برگشت در صورت سوال مهم نیست چطور در 6 جهش 8 مسیر داریم.؟!!

soheilsmart
13-04-2009, 20:47
در n=6
داریم:
ahabcde
ababcde
abcbcde
abcdcde
,..که 8 تا میشه!
فک کنم شما کلمه مجاور رو نادیده گرفته اید!
رو هر نقطه که هس میتونه به یکی از 2 خونه مجاورش بره( به جز e که وایساده)!

soheilsmart
13-04-2009, 20:55
ببینید قورباغه وقتی مسیر abcde رو میره می ایسته !!!! این 4 جهش و 1 مسیر . حالا از نقطه e با 4 حالت دیگه یا از همون مسیر قبلی abcde یا از مسیر efgha به نقطه a بر میگرده بنابراین تعداد مسیرهای از a به e در یک دور کامل معادل با 8 جهش یک دور میشه!!!! (دقت کنید از a به e نه از e به a )
وقتی میخوایم حالت بعدی رو بررسی کنیم قورباغه رو به خونه a می بریم!
مثه اینکه یه قورباغه رو a
وایساده بعد فک میکنه به چند حالت میتونه بره به e!

saber57
13-04-2009, 21:14
پس رفت و برگشت براش فرقی نمیکنه

اگه 8 تا بشه 16
10 تا 32 الی آخر...............
پس تعداد جهش با متغیر n رو میشه به فرم n=2k بنویسیم با فرض k>=2

saber57
13-04-2009, 23:21
برای تعداد جهش 8 تا تمامی جوابها رو بررسی کردم ،تعداد مسیرهای ممکن 16 تا شد یعنی 4^2 .به همین ترتیب مشخص شد که جملات بالاتر یا مساوی n=2k=6 ، دارای تعداد مسیر دو به توان k میباشند.


تعداد جهش تعداد مسیر
-------------- ----------------
4 2
6 8
8 16
10 32
توضیح معادله تابع بازگشتی:
تعداد جهش با متغیر n بصورت 2k نوشته میشه به قسمی که k>=3 برای k=2 تعداد مسیرها برابر 2 و برای k>=3 بفرم 2 بتوان k نوشته میشه بنابراین :




a (2k)=2 , k=2


a( 2k)=2^k ,k>=3

n همیشه عددی زوج به فرم n=2k و بزرگتر یا مساوی 4 است

اگه اشکال داشت میبخشید

Molibden
22-04-2009, 17:00
خیلی سخته سهـــــــیل