06 مهر 1393, 10:32 ب.ظ
07 مهر 1393, 02:50 ق.ظ
سلام. کافیه 4 عدد با تکرار بین 0 تا n پیدا کنید و صعودی مرتبش کنید. درنظر بگیرید [tex]c_i[/tex] باشه تعداد دفعات انتخاب عدد i. مجموع [tex]c_0[/tex] تا [tex]c_n[/tex] میشه 4 پس تعداد حالاتش میشه [tex]\binom{n 4}{4}[/tex].
07 مهر 1393, 03:08 ق.ظ
(06 مهر 1393 10:32 ب.ظ)ldns0098 نوشته شده توسط: [ -> ]تعداد چهارتایی های (a,b,c,d) به ازای عدد صحیح و مثبت n.ما می خواهیم چهار تا عدد از بین 0 تا n انتخاب کنیم که این اعداد می تونن با هم مساوی باشن یا اعداد کنار هم مساوی باشن یا این که هر عدد از عدد چپی خودش بزرگتر باشه
طوری کهn>=d >=c>=b >=a>=0
تست ۴۲ صفحه ۵۵ پوران.
من متوجه نمیشم چطور میشه جوابو بدست اوورد.
خب اینا هر کدوم چندین وضعبت ختلف ایجاد می کنه (4 تا عدد یکسان- سه تا عدد یکسان و یکی متفاوت- دوتا عدد یکسان و دوتا متفاوت و...)
که بررسی هر کدوم باز حالت های جدیدی تولید می کنه مثلا اگه قرار باشه سه تا عدد یکسان و یک عدد متفوات باشه
می توان حالت های زیر را در نظر گرفت:
a<b=c=d
a=b=c<d
پس اگر بخواهیم مسئله را در حالت داده شده بررسی کنیم مشکله و چیی که مشکل ایجادم یکنه اینه که ما ننمی دونیم بالاخره a<b است یا a=b و اینکه b<c است یا b=c واینکه c<d است یا c=d .
خب ما کمی مسئله را تغییر می دیهم و به یک مساله ی هم ارز با پیچیدگی کمتر تبدیل می کنیم یعنی این مساله را به مساله ی دیگری تبدیل می کنیم که هم ارز است یعنی هر جواب برای مسئله ی جدید متناظر با یک ج.اب برای مساله ی اصلی است و بالعکس منتها حل کردن مساله ی جدید راحت تر است و دیگر این دردسرهارا ندارد
می داینم که اگر a<=b باشد حتما a<b+1 است. (چرا؟ با عدد گذاری به جای a و b امتحان کنید)
پس ما هر علامت "کوچکتر مساوی" که می بینیم می توانیم با اضافه کردن یک واحد به سمت راستی علاکت را به "کوچکتر" تبدیل کنیم
[tex]0<=a<=b<=c<=d<=n[/tex]
حالا a را دست نمی زینم و به سمت راستی ها یک واحد می افزاییم
می شه
[tex]0<=a<b 1<=c 1<=d 1<=n 1[/tex]
(قبوله ؟ بله چون اگه b<=c باشه b+1<=c+1 است )
حالا به b+1 دست نمی زینم و به سمت راستی های آن یک واحد می افزاییم
[tex]0<a<b 1<c 2<=d 2<=n 2[/tex]
و همین طور جلو می رویم:
[tex]0<a<b 1<c 2<d 3<=n 3[/tex]
خب این یعنی چی؟ یعنی از بین اعداد 0 تا n+3 چهار تا عدد متفاوت انتخاب کن
چند تا نکته: اولا اعدا می تواندد خود 0 یا خود n+3 باشند پس ما باید از بین n+4 تا عدد ، 4 عدد انتخاب کنیم
ثانیا هر چهار عددی که انتخاب کنیم می توانیم آن را به یک ترتیب بنویسیم و به فرم (a,b,c,d) بنویسیم
مثلا فرض کنید اعداد 5 و 9و 1و 6 انتخاب شده اند این ها رو مرتب می کنیم می شه (9و6و5و1)
پس مسئله را تبدیل کردیم به انخاب 4 عضو از میان n+4 عضو که می شه
[tex]\binom{n 4}{4}[/tex]
08 مهر 1393, 04:56 ب.ظ
(07 مهر 1393 03:08 ق.ظ)fatemeh69 نوشته شده توسط: [ -> ](06 مهر 1393 10:32 ب.ظ)ldns0098 نوشته شده توسط: [ -> ]تعداد چهارتایی های (a,b,c,d) به ازای عدد صحیح و مثبت n.ما می خواهیم چهار تا عدد از بین 0 تا n انتخاب کنیم که این اعداد می تونن با هم مساوی باشن یا اعداد کنار هم مساوی باشن یا این که هر عدد از عدد چپی خودش بزرگتر باشه
طوری کهn>=d >=c>=b >=a>=0
تست ۴۲ صفحه ۵۵ پوران.
من متوجه نمیشم چطور میشه جوابو بدست اوورد.
خب اینا هر کدوم چندین وضعبت ختلف ایجاد می کنه (4 تا عدد یکسان- سه تا عدد یکسان و یکی متفاوت- دوتا عدد یکسان و دوتا متفاوت و...)
که بررسی هر کدوم باز حالت های جدیدی تولید می کنه مثلا اگه قرار باشه سه تا عدد یکسان و یک عدد متفوات باشه
می توان حالت های زیر را در نظر گرفت:
a<b=c=d
a=b=c<d
پس اگر بخواهیم مسئله را در حالت داده شده بررسی کنیم مشکله و چیی که مشکل ایجادم یکنه اینه که ما ننمی دونیم بالاخره a<b است یا a=b و اینکه b<c است یا b=c واینکه c<d است یا c=d .
خب ما کمی مسئله را تغییر می دیهم و به یک مساله ی هم ارز با پیچیدگی کمتر تبدیل می کنیم یعنی این مساله را به مساله ی دیگری تبدیل می کنیم که هم ارز است یعنی هر جواب برای مسئله ی جدید متناظر با یک ج.اب برای مساله ی اصلی است و بالعکس منتها حل کردن مساله ی جدید راحت تر است و دیگر این دردسرهارا ندارد
می داینم که اگر a<=b باشد حتما a<b+1 است. (چرا؟ با عدد گذاری به جای a و b امتحان کنید)
پس ما هر علامت "کوچکتر مساوی" که می بینیم می توانیم با اضافه کردن یک واحد به سمت راستی علاکت را به "کوچکتر" تبدیل کنیم
[tex]0<=a<=b<=c<=d<=n[/tex]
حالا a را دست نمی زینم و به سمت راستی ها یک واحد می افزاییم
می شه
[tex]0<=a<b 1<=c 1<=d 1<=n 1[/tex]
(قبوله ؟ بله چون اگه b<=c باشه b+1<=c+1 است )
حالا به b+1 دست نمی زینم و به سمت راستی های آن یک واحد می افزاییم
[tex]0<a<b 1<c 2<=d 2<=n 2[/tex]
و همین طور جلو می رویم:
[tex]0<a<b 1<c 2<d 3<=n 3[/tex]
خب این یعنی چی؟ یعنی از بین اعداد 0 تا n+3 چهار تا عدد متفاوت انتخاب کن
چند تا نکته: اولا اعدا می تواندد خود 0 یا خود n+3 باشند پس ما باید از بین n+4 تا عدد ، 4 عدد انتخاب کنیم
ثانیا هر چهار عددی که انتخاب کنیم می توانیم آن را به یک ترتیب بنویسیم و به فرم (a,b,c,d) بنویسیم
مثلا فرض کنید اعداد 5 و 9و 1و 6 انتخاب شده اند این ها رو مرتب می کنیم می شه (9و6و5و1)
پس مسئله را تبدیل کردیم به انخاب 4 عضو از میان n+4 عضو که می شه
[tex]\binom{n 4}{4}[/tex]
دستتون درد نکنه. توضیح بسیار عالی ای دادین. کامل متوجه شدم :-)
(07 مهر 1393 02:50 ق.ظ)Jooybari نوشته شده توسط: [ -> ]سلام. کافیه 4 عدد با تکرار بین 0 تا n پیدا کنید و صعودی مرتبش کنید. درنظر بگیرید [tex]c_i[/tex] باشه تعداد دفعات انتخاب عدد i. مجموع [tex]c_0[/tex] تا [tex]c_n[/tex] میشه 4 پس تعداد حالاتش میشه [tex]\binom{n 4}{4}[/tex].
ممنونم. :-)