پاسخ : >>سوال ترکیبیات <<*
سلام
من می دونم چه جوری بدون رابطه ی بازگشتی حل می شه , منتهی اول پیشنهاد می دم این سوال رو حل کنین :
درچند جایگشت از اعداد 1 تا n هیچ عددی بیش از یک واحد از عدد بعدی خودش بزرگتر نیست ؟
همون سوال شماست , منتهی به جای دو واحد , نوشتم یک واحد
این سوالی که من گفتم رو اگر حل کنین , اون یکی هم به راحتی حل می شه ,
یکم روش فکر کنین , اگر نتونستین حل کنید , بگید تا راهنمایی کنم
خوب من راه حل سوال خودم رو می گم , راه حل سوال شما هم تقریبا همینجوریه :
یکی از کارهایی که شما برای بعضی از مسائلی که مربوط به جایگشت می شن , می تونین انجام بدین , اینه که به جای اینکه بیاین حالات قرار گیری کل اشیا رو مستقیم حساب کنین , اول بیاین یه شی رو قرار بدین ( طبیعتا به یه حالت) و اشیا بعدی رو بین فضاهای خالی قرار بدین ...
برای این سوال :
شما اول عدد ۱ رو به یک طریق قرار می دین
برای عدد ۲ : ۲ حالت دارین , یا آخر آخر جایگشت فعلی , یا سمت چپ ۱
برای عدد ۳ : ۲ حالت دارین , یا آخر جایگشت فعلی , یا سمت چپ ۲ ( به دلیل فرض مسئله اینجوریه , چون سوال من گفته حداکثر یک واحد بزرگ تر باشه)
.
.
.
برای عدد n هم ۲ حالت دارین , یا آخر جایگشت , یا سمت چپ n-1
که می شه 2 به توان n-1
سوال شما هم تقریبا همینجوریه :
برای عدد ۱ , یک حالت داریم
برای عدد ۲ , دو حالت داریم
برای عدد ۳ , سه حالت داریم , یا سمت چپ ۲ , یا سمت چپ ۱ , یا آخر جایگشت
برای عدد ۴ : سه حالت داریم , یا سمپت چپ ۳ , یا سمت چپ ۲ , یا آخر جایگشت ( باز هم به دلیل فرض مسئله اینجوریه , چون سوال شما گفته , هر هدد حداکثر ۲ واحد از عدد بعدی خود بزرگ تر باشد)
.
.
.
برای عدد n هم سه حالت داریم : یا سمت چپ n-1 , یا سمت چپ n-2 ; یا آخر جایگشت
که می شه 2 ضربدر (سه به توان n-2)
جواب همینه دیگه ؟
خطاب به
Sharifi_M :
من هر چی فکر می کنم , می بینم که راه حل سوال من هم خیلی به بازگشتی شبیهه
یعنی من اگر می خواستم راه حل بازگشتی برای سوال بگم , تقریبا راه حلم همین بود , با یکم تغییر
نمی دونم راه شما چیه البته D: فکر کنم همینجوری باشه تقریبا