تعداد روش های حرکت مهره ی شاه با ۱۵ حرکت

Question

ما یک صفحه شطرنجی ۳*۳ و یک مهره ی شاه داریم که این مهره می تواند در هر جهتی یک قدم به خانه های همسایه خود ( ضلعی یا راسی ) برود. می خواهیم این مهره را در یکی از خانه های صفحه به عنوان مهره شروع قرار دهیم و با ۱۵ حرکت ، خود را به خانه وسط ضلع سمت چپ به عنوان خانه مقصد برسانیم. به چند روش این کار امکان پذیر است؟ عبور از خانه تکراری مجاز است و خانه شروع میتواند هر خانه ای از صفحه ( حتی خود نقطه مقصد) باشد.

Answer 1

مطابق شکل اولین کاری که میکنیم این است که مشخص میکنیم برای رفتن به هر خانه چند حالت وجود دارد. اگر تعداد حرکات ممکن 1 بود.انگاه 5 حالت وجود داشت که ان را با s1 برای مقصد نشان می دهیم. اگر توجه کنید در کنار هر خانه با شماره پنج،یک خانه شماره هشت و دو خانه شماره سه و دو خانه شماره پنج وجود دارد. همچنین برای هر خانه با شماره سه،دوخانه شماره شماره پنج و یک خانه شماره هشت هست و برای هر خانه شماره هشت،چهار خانه شماره سه و چهار خانه شماره پنج. با توجه به اینکه مقدار s2 برای مقصد معادل مقدار s1 برای خانه های مجاور آن است پس s2 برابر است با: $s2=3+5+8+5+3$
و به همین ترتیب: $s3=5+8+5+3+5+8+5+3+3+5+3+5+3+5+3+5+3+5+8+5+3+5+8+5=8 \times 3+12 \times 5+4 \times8$ به همین ترتیب اگر ادامه دهید s15به دست می آید فقط باید هر مرحله به جای 3 و5و8و مقدار های زیر را جای گذاری کنید: $3:2 \times 5+8$

$5:2 \times 3+2 \times 5+8$

$8:4 \times 3+4 \times 5$ منتها روش سریع تری به ذهن من نمیرسه اگه کسی میتونه روش بهینه تری پیدا کنید بگید لطفا

Comments

شما چگونه از s2 به s3 رسیده اید ? اگر بجای هر کدام از اعدادی که مجموع s2 را می سازند معادل ان طبق حرف شما را قرار دهیم حاصل با انچه که برای s3 نوشته اید تفاوت خواهد داشت . الان طبق حرف شما عبارتی که s15 را می سازد چگونه است؟

---

s2=2*3+2*5+8
s3=2*(2*5+8)+2*(2*5+2*3+8)+(4*3+4*5)=4*5+2*8+4*5+4*3+2*8+4*3+4*5=8*3+12*5+4*8
این فرایند s2به s3 فکر نمیکنم اینجا مشکلی داشته باشم.
اینحوری اگر ادامه بدیم خیلی طول میکشه تا به s15 برسیم ولی به نظر درست هست.
با کامپیوتر حساب کردم s15 میشود:
s15=1323532288*3+1871757312*5+661766144*8
که کد برنامه به زبان C++ هست:
main()
{
    long long int a[15][3];
    a[0][0]=0;
    a[0][1]=1;
    a[0][2]=0;
    for(int i=1;i<15;i++)
    {
        a[i][0]=a[i-1][1]*2+a[i-1][2]*4;
        a[i][1]=a[i-1][0]*2+a[i-1][1]*2+a[i-1][2]*4;
        a[i][2]=a[i-1][0]+a[i-1][1];
        cout<<a[i][0]<<"-"<<a[i][1]<<"-"<<a[i][2]<<"----------";
    }
}
که البته اگر یکم با c++اشنا باشید میدانید که ترتیب کد های هر خط هنگام کپی کردن یکم به هم ریخته است.
در هر صورت مشکلی من در روش حل نمیبینم ولی شاید روش سریع تری هم باشد...

---

@arashari44 بهتر است کدتان را در ادامهٔ پاسخ‌تان قرار می‌دادید تا هم خواناتر شود و هم مناسب‌تر است تا اینکه یک دیدگاه بلند بگذارید. و همینطور چون قسمتی از حل‌تان بوده‌است مربوط است.