دوشنبه ۳۱ ارديبهشت ۱۴۰۳   |  كاربر مهمان  |    
 علوم و فنون جدید

 نظرسنجي شماره 1
در مورد كدام‌يك از موضوعات مطرح شده مايل به كسب اطلاعات بيشتر هستيد؟


ارائه نظر 
 دست در دست (مسابقه‌ي شماره‌ي 43)
دست در دست (مسابقه‌ي شماره‌ي 43)مسابقه كامپيوتر
این مسابقه برای کسانی که مطالب این بخش رو دنبال می کنند و علاوه بر قدرت ابتکار، کمی هم به جستجو برای پیدا کردن جواب علاقه‌مند هستند (دانش‌اموزان کنجکاو!) بسیار بسیار ساده است ...

دست در دست








سؤال
فرض کنید که 10 نفر دور یک میز دایره‌ای نشسته‌اند. این 10 نفر به چند طریق می‌توانند دو به دو با هم دست بدهند به‌طوری که هیچ‌کدام از آن‌ها، آرنج یکدیگر را قطع نکنند؟


شکل ذيل چگونگی دست دادن 2 و 4 و 6 و 8 نفر را با هم نشان می‌دهد. «نقطه‌ها» بیانگر «افراد» و «خطوط» بیانگر «دست دادن» است.



راهنمایی 1
نکته‌ای که می‌توان به آن اشاره کرد در زنگ تفریح شماره‌ی 29 مستتر است!


راهنمایی 2
اگر به‌خاطر داشته باشید ما راجع به حل مسأله‌ی «اعداد کاتالان» توضیح زیادی ندادیم؛ کلید حل این مسأله در آن‌جاست!

سعی کنید رابطه‌ی این مسأله را با «اعداد کاتالان» پیدا کرده و چگونگی به‌دست آوردن فرمول «اعداد کاتالان» را بیابید!

جواب خود را توضیح دهید! بديهي است جواب‌هاي بدون توضيح پذيرفتني نيست. 

تشکر ویژه از کاربران شرکت‌کننده در‌ مسابقه‌ی شماره‌ي 43

باید واقعاٌ تشکر کرد از دوستانی که تلاش کردند و به توصیه ی ما توجّه کرند و با استدلال این مسأله رو حل کردند ویا به دنبال جواب آن گشته‌اند. به‌خصوص باید از آقایان «خرمند» و «شفائی» و هم‌چنین «خانم آذین» تشکر کرد. و تشکر ویژه ای بکنیم از «آقای شفائی» که code حل مسأله‌ی ما رو فرستادند. خیلی‌خوب بود!

1386/8/23لينک مستقيم
فرستنده :
عماد HyperLink HyperLink 1386/9/25
مـتـن : سلام...
وقتي 10 نفر با هم دور يک ميز دايره اي بنويسن: " اين 10 نفر به چند طريق مي توانند دو به دو با هم دست بدهند به طوري که هيچ کدام از آنها ، آرنج يکديگر را قطع نکنند ." احتمالاً از "اين" هم منظورشون خودشون هست پس حتماً براشون خيلي مهمه !
ميدانيم که هر نفر حداکثر با ½يک دوم بغيه افراد مي تواند دست بدهد،زيرا يا خود و نفرات يک در ميان بد از خود (يا کنار افرادي که با آنها دست مي دهد) نمي تواند دست بدهد ،در غير اين صورت آرنج يکديگر را قطع مي کنند.و همچنين در هر دور يه اندازه ½يک دوم افراد ارتباط ايجاد ميشود. و کل افراد هم n مي باشد. و در مجموع هر نفر با n-1 دست ميدهد.
پس n*n-1 ارطيات وجود دارد که n/2 براي هر نفر به دلايل بالا امکان پزير نيست.
10*9=90 ، 90/5=18 . پس به 18 صورت اين کار امکان پذير است.
شايد اين راه شبيه اعداد کاتالان نباشد ولي احتمالاً درست است. در بعضی موارد این فرمول باید دوباره تقسیم بر n/2 بشود! که به قول فرما "در اینجا جای کافی برای اثبات نداریم".
پاسـخ :سلام عماد جان!
متأسفانه شما اشتباه کردی نه‌تنها راهنمایی رو مارو گوش نکردی بلکه کلا تو یک مسیر دیگه رفتی و خواستی که مسأله رو حل کنی که اشتباه کردی!
به جواب نگاه کن! حتماٌ متوجه اشتباه خودت می‌شی!
موفق باشی!
فرستنده :
آذین ح HyperLink HyperLink 1386/8/30
مـتـن : سلام،
اولا این که مسابقه خیلی باحال بود!
دوما این که شما تقریبا جواب را به ما داده بودید و فقط ما یک محاسبه کوچولو انجام دادیم...!
اینم از جواب من :
جواب دقیقا مانند جواب مسئله اول "پرانتزهای بالانس" است. اگر دو نفر آدم داشته باشیم (n=1) به 1 حالت می توانند دست بدهند. . اگر چهار نفر آدم داشته باشیم (n=2) به2 حالت می توانند دست بدهند. اگر شش نفر آدم داشته باشیم (n=3) به5 حالت می توانند دست بدهند. اگر هشت نفر آدم داشته باشیم (n=4) به 14 حالت می توانند دست بدهندو اگر ده نفر آدم داشته باشیم (n=5) به42 حالت می توانند دست بدهند.
با تشکر از سوالات همیشه خوبتان!
پاسـخ :سلام آذین جان ،
آفرین !
درسته !
ایندفعه بالاخره به جواب درست رسیدی !
خیلی خوبه !
موفق باشی !
فرستنده :
Kherad HyperLink HyperLink 1386/8/30
مـتـن : >>>>> این با قبلیه که فرستادم یه خورده فرق داره . قبلیه سوتی داشت .

سلام

42
یه سوال شبیه این تو sgu هست .اون رو داینامیک حل کردم (البته به خاطر محدودیت حافظه) . اینم همون جوری می نویسم . نمی دونم شاید راه بهتری هم باشه

کلا واسه 2n تا آدم می گم
فرض می کنیم که f(n)
ّجوابمون واسه 2n ادم باشه
می دونیم که
f(1)=1
f=1(0)
فرض می کنیم
f n = sum
و در اول کار
sum=0 باشه
ادم ها به نام های 1و2و3و...2n
1 رو در نظر می گیریم . میایم شروع می کنیم هر دفعه بین 1 و i (بین 2 و 2n , و خود اونها که 2 تا 2 تا می ره بالا ) یک خط می کشیم ,
طبق اصل ضرب باید sum رو به علاوه ی ضرب f ادم های یک طرف خط در f ادم های طرف دیگه ی اون بکنیم .

و در آخر sum جواب ماست .
----------------------------------------
حالا واسه این که sum رو بتونیم حساب کنیم :
در عملیات بالا یک بار x*y رو حساب می کنیم (قبل از این که i مساوی n بشه) و یک بار y*x رو حساب می کنیم (بعد از اون) . پس می شه ما عملیاتمون رو تا n انام بدیم و جواب رو ضرب در 2 کنیم . البته اگه N فرد بود یه خورده قضیه فرق داره .
f (i-1/2)*f (i-1/2)
رو دیگه ضرب در 2 نمی کنیم .
f2 f3 f4 رو حساب میکنیم و از رو اون جواب واسه n5

2*f4*f0+2*f3*f1+1*f2*f2
=2*14+2*5+1*2

که می شه 42

خیلی تند نوشتم . فکر کنم حرفام سوتی داشت . چون قبلا حل کرده بودم رو نوشته ها الانم دقت نکردم .
پاسـخ :باز هم سلام !
کاش به جای اینکه 2باره کلش رو copy و paste کنی ، فقط به گفتن تفاوت این جواب با جوابی که قبلاٌ داده بودی اشاره میکردی ، ما خودمون بررسی می کردیم !
خیلی خوبه !
باز هم در مسابقات ما شرکت کن !
بازهم موفق باشی !
فرستنده :
علیرضا شفائی HyperLink HyperLink 1386/8/30
مـتـن : به 42 حالت این کار امکان پذیره!
یک تابع داینامیک میشه از روی این درست کرد به این صورت که
اعداد را به صورت 2k در نظر میگیریم
در ان صورت برای
2 خواهیم داشت 2k=2 پس k=1
f(1)=1
چون برای 2 فقط 1 حالت داریم
4 خواهیم داشت 2k=4 پس k=2
f(2)=2
زیرا چهارتا رو میشه با دو حالت زد.
حالا میگیم چیه؟ میگیم که فرض میکنیم دایره ی ما دارای 2k نقطه باشه
هر نقطه را میتونیم به نقاط دیگه وصل کنیم.
فرض کنید نقطه 1 را به نقطه 2 وصل کنیم . اینطوری شکل به دو تکه
تبدیل میشه که در یکی از آنها 0 نقطه (1 و 2 دنبال هم هستن برای همین نقطه ای بینشان نیست) و در قسمتی دیگه 2k-2 نقطه وجود دارد.
برای این حالت میشه تعداد حالاتی که دایره با صفر نقطه + تعدا حالاتی که دایره با 2k-2 وجود دارد. برای درک بهتر به شکل توجه کنید:
http://ashafaei.persiangig.com/ashafaei/Det1.jpg

حالا میاییم و هر بار نقطه ی 1 را به بقیه نقاط میچسبانیم! و با محاسبه تعداد وجود دو دایره جدید. و مجموعه کل حالات(یعنی حاصل هر بار تقسیم دایره به دو دایره جدید) جواب را بدست میاریم
به طور خلاصه بگم
1- نقطه ی a را به نقطه ای که تا حالا وصل نشده وصل کن!
2- تعداد حالات ممکن برای دایره ساخته چپی را با تعداد حالا ممکن برای دایره ساخته شده ی راستی جمع کن و به ans اضافه کن
3-اگر a را با تمام نقاط در صفحه جفت نکردی به 1 بپر
4- ans را به عنوان خروجی بده!

اینم کد c++ اش! (توجه کنید که که باید k را در 2k بگید! یعنی در این مثال برای ورودی باید بدید 5 تا 2k که برابر با 10 است را حساب کند!)

//In the name of GOD;
//Alireza Shafaei
#include
using namespace std;
long long arr[31];
int part(int n);
void num(int n);

int main(){
int k;
cin>>k;
num(k);
cout<cin>>k;
return 0;
}
void num(int n){
arr[0]=1;
arr[1]=1;
arr[2]=2;
for(int i=3;i<=n;i++){
for(int x=0;x arr[i]+=arr[x]*arr[i-1-x];
}
}
}
پاسـخ :سلام علیرضا جان ،
خیلی خوب و عالی جواب دادین ، جواب آخرت که کاملا درست بود ، توضیحاتت هم جالب و خوب ، راستی ، شکل جالبی هم سشخته بودی ، می تونی بیشتر راجع به کارهایی که در زمینه ی کامپیوتر تا حالا کردی و راجع به مقطع تحصیلیت ما بیشتر در جریان بذاری ؟
خیلی خوشحال میشیم !
راستی ، code که فرستاده بودی درست عمل نمی کنه که بخشی تقصیر شماست ، چون اشتباه نوشتی و بخشیش تقصیر این editor ماست !
ولی این مسئله رو باید به صورت dynamic حل کرد.
موفق باشی !
فرستنده :
عماد HyperLink HyperLink 1386/8/30
مـتـن : سلام...
وقتي 10 نفر با هم دور يک ميز دايره اي بنويسن: " اين 10 نفر به چند طريق مي توانند دو به دو با هم دست بدهند به طوري که هيچ کدام از آنها ، آرنج يکديگر را قطع نکنند ." احتمالاً از "اين" هم منظورشون خودشون هست پس حتماً براشون خيلي مهمه !
ميدانيم که هر نفر حداکثر با ½يک دوم بغيه افراد مي تواند دست بدهد،زيرا يا خود و نفرات يک در ميان بد از خود (يا کنار افرادي که با آنها دست مي دهد) نمي تواند دست بدهد ،در غير اين صورت آرنج يکديگر را قطع مي کنند.و همچنين در هر دور يه اندازه ½يک دوم افراد ارتباط ايجاد ميشود. و کل افراد هم n مي باشد. و در مجموع هر نفر با n-1 دست ميدهد.
پس n*n-1 ارطيات وجود دارد که n/2 براي هر نفر به دلايل بالا امکان پزير نيست.
10*9=90 ، 90/5=18 . پس به 18 صورت اين کار امکان پذير است.
شايد اين راه شبيه اعداد کاتالان نباشد ولي احتمالاً درست است. در بعضی موارد این فرمول باید دوباره تقسیم بر n/2 بشود! که به قول فرما "در اینجا جای کافی برای اثبات نداریم".
پاسـخ :باز هم سلام عماد خان !
شما همه ی حرفهای فرما رو انقدر خوب گوش می دی !؟
موفق باشی !
فرستنده :
Kherad HyperLink HyperLink 1386/8/30
مـتـن : سلام

42
یه سوال شبیه این تو sgu هست .اون رو داینامیک حل کردم (البته به خاطر محدودیت حافظه) . اینم همون جوری می نویسم . نمی دونم شاید راه بهتری هم باشه

کلا واسه 2n تا آدم می گم
فرض می کنیم که f(n)
ّجوابمون واسه 2n ادم باشه
می دونیم که
f(1)=1
f=1(0)
فرض می کنیم
f n = sum
و در اول کار
sum=0 باشه
ادم ها به نام های 1و2و3و...2n
1 رو در نظر می گیریم . میایم شروع می کنیم هر دفعه بین 1 و i (بین 2 و 2n , و خود اونها ) یک خط می کشیم ,
طبق اصل ضرب باید sum رو به علاوه ی ضرب f ادم های یک طرف خط در f ادم های طرف دیگه ی اون بکنیم . اگه تعداد ادم ها فرد بود f کف تعداد ادم ها به 2 رو می گیریم

و در آخر sum جواب ماست .
----------------------------------------
حالا واسه این که sum رو بتونیم حساب کنیم :
در عملیات بالا یک بار x*y رو حساب می کنیم (قبل از این که i مساوی n بشه) و یک بار y*x رو حساب می کنیم (بعد از اون) . پس می شه ما عملیاتمون رو تا n انام بدیم و جواب رو ضرب در 2 کنیم . البته اگه N فرد بود یه خورده قضیه فرق داره

f2 f3 f4 رو حساب میکنیم و از رو اون جواب واسه n5

2*f4*f0+2*f3*f1+1*f2*f2
=2*14+2*5+1*2

که می شه 42

خیلی تند نوشتم . فکر کنم حرفام سوتی داشت . چون قبلا حل کرده بودم رو نوشته ها الانم دقت نکردم .
پاسـخ :سلام دوست عزیز ،
کلاص می تونم بگم که خیلی عالی بود ، جواب آخرتون که در هر 2مورد درست بود ، راه حلتون هم مستقل از توضیحاتتون (که بعضاٌ یه خورده ای مشکل داشت !) خیلی خوب بود و به هوبی تونسته بودید که راه حل بازگشتی برای این مسئله رو پیدا کنید ، خوب بود !
معلوم که اهل تحقیق و پژوهش هستید !
خیلی خوبه !
موفق باشی !
نظر شما پس از تاييد در سايت قرار داده خواهد شد
نام :
پست الکترونيکي :
صفحه شخصي :
نظر:
تاییدانصراف

 فعاليت هاي علمي
 تماس با ما
 بازديدها
كاربران غيرعضو آنلاينكاربران غيرعضو آنلاين:  2
 كاربران عضو آنلاين:  0
  کل كاربران آنلاين:  2

سرویس‌های رشد:

فهرست:

وزارت آموزش و پرورش > سازمان پژوهش و برنامه‌ريزی آموزشی
شبکه ملی مدارس ایران (رشد)