یکی از راه حل ها که تقریبا از گسسته براش استفاده میکنیم این هستش:

ببینید کلا $1000$ تا کلید داریم که میخوایم $2$ تاشو انتخاب کنیم پس حالت کل انتخاب $2$ تا از $1000$تاست یعنی داریم:$\binom{1000}{2}$

حالا ببینید قبول دارید که کل کلیدا توی ۱۰ تا خونه تقسیم میشن؟؟؟
نشون میدیم اینو :
$0,10,20,30,40,...$ اینا به خونه ۰ نگاشت میشن
$1,11,21,31,41,...$ اینا به خونه ۱ نگاشت میشن
$2,12,22,32,42,...$ اینا به خونه ۲ نگاشت میشن
و.....
ما کلا ۱۰ تا دسته(حفره منظورمه) داریم درست؟؟هر دسته ای هم شامل ۱۰۰ تا کلیده درست؟؟؟
پس چیکار میکنیم !!!یکی از این ۱۰ تا دسته رو انتخاب میکنیم به صورت $\binom{10}{1}$ و حالا این دسته ای که ما انتخاب کردیم ۱۰۰ تا کلید داره که همه دارای نگاشت برابرن پس کافیه ۲ تا کلید دلخواه از این دسته انتخاب کنیم به صورت $\binom{100}{2}$

پس حالا احتمال رو به صورت زیر حساب میکنیم:

$\frac{\binom{10}{1}\binom{100}{2}}{\binom{1000}{2}}=\frac{(10\ast\frac{(100\ast9​9)}{2})}{\frac{(1000\ast999)}{2}}=\frac{(1000\ast99)}{1000\ast999}=\frac{99}{999​}\simeq0.1$

این راه حل ریاضیش.یه راه حل دیگه هم داره شاید برای ما جالبتر باشه.اونم میذارم حتما

(۰۳ دى ۱۳۹۳ ۰۸:۵۱ ب.ظ)miladcr7 نوشته شده توسط:  این راه حل ریاضیش.یه راه حل دیگه هم داره شاید برای ما جالبتر باشه.اونم میذارم حتما

اون راه حل جالبتره چیه؟

(۲۰ دى ۱۳۹۳ ۰۹:۵۳ ب.ظ)Ametrine نوشته شده توسط:  

(03 دى ۱۳۹۳ ۰۸:۵۱ ب.ظ)miladcr7 نوشته شده توسط:  این راه حل ریاضیش.یه راه حل دیگه هم داره شاید برای ما جالبتر باشه.اونم میذارم حتما

اون راه حل جالبتره چیه؟

سلام.تو حالت اول هر کلیدی دوست داشتی بردار یعنی از ۱۰۰۰ کلید هر کدوم که میخواستی پس میشه $\frac{1000}{1000}$
ولی عنصر دوم فقط باید هم اندیس با اولی باشه و ما میدونم هر ۱۰۰ تا کلیدی یه اندیس دارند پس الان از ۹۹۹ کلید باقیمونده ما ۹۹ کلید مجازیم انتخاب کنیم(دقت کن کلید اول رو انتخاب کردیم پس الان ۹۹ تا کلید هم اندیس باهاش باقیمونده) یعنی $\frac{99}{999}$
پس احتمال کل میشه:
$\frac{99}{999}\ast\frac{1000}{1000}\cong0.1$

(۲۰ دى ۱۳۹۳ ۱۰:۰۹ ب.ظ)miladcr7 نوشته شده توسط:  سلام.تو حالت اول هر کلیدی دوست داشتی بردار یعنی از ۱۰۰۰ کلید هر کدوم که میخواستی پس میشه $\frac{1000}{1000}$
ولی عنصر دوم فقط باید هم اندیس با اولی باشه و ما میدونم هر ۱۰۰ تا کلیدی یه اندیس دارند پس الان از ۹۹۹ کلید باقیمونده ما ۹۹ کلید مجازیم انتخاب کنیم(دقت کن کلید اول رو انتخاب کردیم پس الان ۹۹ تا کلید هم اندیس باهاش باقیمونده) یعنی $\frac{99}{999}$
پس احتمال کل میشه:
$\frac{99}{999}\ast\frac{1000}{1000}\cong0.1$

ممنون، این جالب بود واقعاً :دی

سوال Btree رو توی این لینک زیر یه جواب گذاشتم.

مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.


سوال درهم سازی هم حل شد و به نظرم خیلی جالب اومد.
من توان سوم اعداد ۱ تا ۱۰ رو حساب کردم و باقیمانده اونا رو نسبت به ۱۰ گرفتم و جالب این بود که جواب هر کدوم متمایز بود، یعنی این تابع درهم سازی که در سوال ذکر شده فقط میخواسته ما رو گیج کنه تا از خیر سوال بگذریم وگرنه فرقی با اینکه باقیمانده همون عدد اصلی رو نسبت به ۱۰ بگیریم نداره.
این جوری توی ۱۰۰۰ تا عدد، ۱۰۰ مورد هست که با این تابع به index یکسان اشاره می کنه، اگه احتمالش رو حساب کنیم میشه ۱۰۰ به ۱۰۰۰ یعنی ۰/۱

(۰۲ دى ۱۳۹۳ ۰۳:۳۰ ب.ظ)ana9940 نوشته شده توسط:  سوال Btree رو توی این لینک زیر یه جواب گذاشتم.

مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.


سوال درهم سازی هم حل شد و به نظرم خیلی جالب اومد.
من توان سوم اعداد ۱ تا ۱۰ رو حساب کردم و باقیمانده اونا رو نسبت به ۱۰ گرفتم و جالب این بود که جواب هر کدوم متمایز بود، یعنی این تابع درهم سازی که در سوال ذکر شده فقط میخواسته ما رو گیج کنه تا از خیر سوال بگذریم وگرنه فرقی با اینکه باقیمانده همون عدد اصلی رو نسبت به ۱۰ بگیریم نداره.
این جوری توی ۱۰۰۰ تا عدد، ۱۰۰ مورد هست که با این تابع به index یکسان اشاره می کنه، اگه احتمالش رو حساب کنیم میشه ۱۰۰ به ۱۰۰۰ یعنی ۰/۱

ببخشید به نظرم این نوع تقسیم درست نباشه.شما اومدید ۱۰۰ کلید از کل کلید ها رو در نظر گرفتید که این درست نیست ممکنه اون ۱۰۰ تا کلید صرفا تو یه حفره نباشن

(۰۲ دى ۱۳۹۳ ۰۸:۰۷ ب.ظ)miladcr7 نوشته شده توسط:  ببخشید به نظرم این نوع تقسیم درست نباشه.شما اومدید ۱۰۰ کلید از کل کلید ها رو در نظر گرفتید که این درست نیست ممکنه اون ۱۰۰ تا کلید صرفا تو یه حفره نباشن

چرا درست نباشه؟خب احتمالش گرفتم دیگه. اینو قبول کردی که ده تا عدد ده اندیس متفاوت رو از تابع درهم سازی میگیرند ؟ مثلا اعداد یک تا ۱۰، حالا عدد یازده قطعا جواب تابع درهم سازی اون یکی از اعداد قبلیه، چون هزار تا عدد متوالی رو گفته شده، پس هر ۱۰۰ تایی از اون ها احتمال یکسان شدن تابع درهم سازیشون هست که نسبتش میشه ۰/۱
اگه اون قسمت حلم درست باشه، احتمالش میشه همون ۰/۱ . یعنی اعداد ۱ تا ۱۰ که من حساب کردم و باقیمانده توان سومشون متمایز شد و همین فرض رو برای اعداد ۱۱ تا ۲۰ کردم ممکنه جامعیت نداشته باشه؟!؟!

ببین الان شما اومدی گفتی هر ۱۰۰ تا عدد دارای یه اندیسن.قبول.!!!ولی از کجا معلوم اون دوتایی که انتخاب میشه دارای یک اندیسن؟؟؟؟
شما اینو به نظرم در نظر نگرفتی!!!
ببین صورت سوال گفته ۲ عدد که انتخاب میکنیم دارای یک اندیس باشن

(۰۲ دى ۱۳۹۳ ۱۱:۴۹ ب.ظ)miladcr7 نوشته شده توسط:  ببین الان شما اومدی گفتی هر ۱۰۰ تا عدد دارای یه اندیسن.قبول.!!!ولی از کجا معلوم اون دوتایی که انتخاب میشه دارای یک اندیسن؟؟؟؟
شما اینو به نظرم در نظر نگرفتی!!!
ببین صورت سوال گفته ۲ عدد که انتخاب میکنیم دارای یک اندیس باشن

الان متوجه شدم منظورتون چیه. من اصلا روی مبحث احتمالش دقت نکردم.
ببین نگفته که ما دو عنصر را به تصادف انتخاب میکنیم . همین جوری در ساده ترین حالت برای احتمال گرفتن جواب میشه ۰/۱/ ولی الان گیج شدم، نمیدونم منظور سوال چیه!!
البته چون مربوط به ساختمان داده است حس می کنم منظور همونی که من حل کردم ولی بد گفته.

---

(۰۲ دى ۱۳۹۳ ۱۱:۴۹ ب.ظ)miladcr7 نوشته شده توسط:  ببین الان شما اومدی گفتی هر ۱۰۰ تا عدد دارای یه اندیسن.قبول.!!!ولی از کجا معلوم اون دوتایی که انتخاب میشه دارای یک اندیسن؟؟؟؟
شما اینو به نظرم در نظر نگرفتی!!!
ببین صورت سوال گفته ۲ عدد که انتخاب میکنیم دارای یک اندیس باشن

واسه اینکه گیج نشیم میشه اینجوری گفت.
فرض کن عدد اول ۰ انتخاب شده که مثلا طبق تابع به اندیس ۰ رجوع میشه، حالا عدد بعدی که انتخاب میشه جواب تابعش قطعا یکی از اعداد ۰ تا ۹ هست، که به احتمال ۰/۱ میتونه جواب تابعش ۰ باشه.

ببینید صورت سوال میخواد دقیقا دو تا رو انتخاب کنی که دارای یک اندیس باشن.
این سوال اصلا جواب دقیق نداره.تقریبیه.من جوابشو براتون مینویسم.بعد مقایسه میکنیم ببینیم چی به چیه