۰
subtitle
ارسال: #۱
  
سوال درهم سازی و btree سال ۹۳
کسی میتونه این سوالارو حل کنه ؟؟؟؟؟؟؟؟؟؟؟
سوال در هم سازی جوابش گزینه ۳
سوال btree گزینه ۴
سوال در هم سازی جوابش گزینه ۳
سوال btree گزینه ۴
۱
ارسال: #۲
  
RE: سوال درهم سازی و btree سال ۹۳
یکی از راه حل ها که تقریبا از گسسته براش استفاده میکنیم این هستش:
ببینید کلا [tex]1000[/tex] تا کلید داریم که میخوایم [tex]2[/tex] تاشو انتخاب کنیم پس حالت کل انتخاب [tex]2[/tex] تا از [tex]1000[/tex]تاست یعنی داریم:[tex]\binom{1000}{2}[/tex]
حالا ببینید قبول دارید که کل کلیدا توی ۱۰ تا خونه تقسیم میشن؟؟؟
نشون میدیم اینو :
[tex]0,10,20,30,40,...[/tex] اینا به خونه ۰ نگاشت میشن
[tex]1,11,21,31,41,...[/tex] اینا به خونه ۱ نگاشت میشن
[tex]2,12,22,32,42,...[/tex] اینا به خونه ۲ نگاشت میشن
و.....
ما کلا ۱۰ تا دسته(حفره منظورمه) داریم درست؟؟هر دسته ای هم شامل ۱۰۰ تا کلیده درست؟؟؟
پس چیکار میکنیم !!!یکی از این ۱۰ تا دسته رو انتخاب میکنیم به صورت [tex]\binom{10}{1}[/tex] و حالا این دسته ای که ما انتخاب کردیم ۱۰۰ تا کلید داره که همه دارای نگاشت برابرن پس کافیه ۲ تا کلید دلخواه از این دسته انتخاب کنیم به صورت [tex]\binom{100}{2}[/tex]
پس حالا احتمال رو به صورت زیر حساب میکنیم:
[tex]\frac{\binom{10}{1}\binom{100}{2}}{\binom{1000}{2}}=\frac{(10\ast\frac{(100\ast99)}{2})}{\frac{(1000\ast999)}{2}}=\frac{(1000\ast99)}{1000\ast999}=\frac{99}{999}\simeq0.1[/tex]
این راه حل ریاضیش.یه راه حل دیگه هم داره شاید برای ما جالبتر باشه.اونم میذارم حتما
ببینید کلا [tex]1000[/tex] تا کلید داریم که میخوایم [tex]2[/tex] تاشو انتخاب کنیم پس حالت کل انتخاب [tex]2[/tex] تا از [tex]1000[/tex]تاست یعنی داریم:[tex]\binom{1000}{2}[/tex]
حالا ببینید قبول دارید که کل کلیدا توی ۱۰ تا خونه تقسیم میشن؟؟؟
نشون میدیم اینو :
[tex]0,10,20,30,40,...[/tex] اینا به خونه ۰ نگاشت میشن
[tex]1,11,21,31,41,...[/tex] اینا به خونه ۱ نگاشت میشن
[tex]2,12,22,32,42,...[/tex] اینا به خونه ۲ نگاشت میشن
و.....
ما کلا ۱۰ تا دسته(حفره منظورمه) داریم درست؟؟هر دسته ای هم شامل ۱۰۰ تا کلیده درست؟؟؟
پس چیکار میکنیم !!!یکی از این ۱۰ تا دسته رو انتخاب میکنیم به صورت [tex]\binom{10}{1}[/tex] و حالا این دسته ای که ما انتخاب کردیم ۱۰۰ تا کلید داره که همه دارای نگاشت برابرن پس کافیه ۲ تا کلید دلخواه از این دسته انتخاب کنیم به صورت [tex]\binom{100}{2}[/tex]
پس حالا احتمال رو به صورت زیر حساب میکنیم:
[tex]\frac{\binom{10}{1}\binom{100}{2}}{\binom{1000}{2}}=\frac{(10\ast\frac{(100\ast99)}{2})}{\frac{(1000\ast999)}{2}}=\frac{(1000\ast99)}{1000\ast999}=\frac{99}{999}\simeq0.1[/tex]
این راه حل ریاضیش.یه راه حل دیگه هم داره شاید برای ما جالبتر باشه.اونم میذارم حتما
ارسال: #۳
  
RE: سوال درهم سازی و btree سال ۹۳
ارسال: #۴
  
RE: سوال درهم سازی و btree سال ۹۳
(۲۰ دى ۱۳۹۳ ۰۹:۵۳ ب.ظ)Ametrine نوشته شده توسط:(03 دى ۱۳۹۳ ۰۸:۵۱ ب.ظ)miladcr7 نوشته شده توسط: این راه حل ریاضیش.یه راه حل دیگه هم داره شاید برای ما جالبتر باشه.اونم میذارم حتمااون راه حل جالبتره چیه؟
سلام.تو حالت اول هر کلیدی دوست داشتی بردار یعنی از ۱۰۰۰ کلید هر کدوم که میخواستی پس میشه [tex]\frac{1000}{1000}[/tex]
ولی عنصر دوم فقط باید هم اندیس با اولی باشه و ما میدونم هر ۱۰۰ تا کلیدی یه اندیس دارند پس الان از ۹۹۹ کلید باقیمونده ما ۹۹ کلید مجازیم انتخاب کنیم(دقت کن کلید اول رو انتخاب کردیم پس الان ۹۹ تا کلید هم اندیس باهاش باقیمونده) یعنی [tex]\frac{99}{999}[/tex]
پس احتمال کل میشه:
[tex]\frac{99}{999}\ast\frac{1000}{1000}\cong0.1[/tex]
ارسال: #۵
  
RE: سوال درهم سازی و btree سال ۹۳
(۲۰ دى ۱۳۹۳ ۱۰:۰۹ ب.ظ)miladcr7 نوشته شده توسط: سلام.تو حالت اول هر کلیدی دوست داشتی بردار یعنی از ۱۰۰۰ کلید هر کدوم که میخواستی پس میشه [tex]\frac{1000}{1000}[/tex]ممنون، این جالب بود واقعاً :دی
ولی عنصر دوم فقط باید هم اندیس با اولی باشه و ما میدونم هر ۱۰۰ تا کلیدی یه اندیس دارند پس الان از ۹۹۹ کلید باقیمونده ما ۹۹ کلید مجازیم انتخاب کنیم(دقت کن کلید اول رو انتخاب کردیم پس الان ۹۹ تا کلید هم اندیس باهاش باقیمونده) یعنی [tex]\frac{99}{999}[/tex]
پس احتمال کل میشه:
[tex]\frac{99}{999}\ast\frac{1000}{1000}\cong0.1[/tex]
۰
ارسال: #۶
  
RE: سوال درهم سازی و btree سال ۹۳
سوال Btree رو توی این لینک زیر یه جواب گذاشتم.
مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمیباشید. جهت مشاهده پیوندها ثبت نام کنید.
سوال درهم سازی هم حل شد و به نظرم خیلی جالب اومد.
من توان سوم اعداد ۱ تا ۱۰ رو حساب کردم و باقیمانده اونا رو نسبت به ۱۰ گرفتم و جالب این بود که جواب هر کدوم متمایز بود، یعنی این تابع درهم سازی که در سوال ذکر شده فقط میخواسته ما رو گیج کنه تا از خیر سوال بگذریم وگرنه فرقی با اینکه باقیمانده همون عدد اصلی رو نسبت به ۱۰ بگیریم نداره.
این جوری توی ۱۰۰۰ تا عدد، ۱۰۰ مورد هست که با این تابع به index یکسان اشاره می کنه، اگه احتمالش رو حساب کنیم میشه ۱۰۰ به ۱۰۰۰ یعنی ۰/۱
مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمیباشید. جهت مشاهده پیوندها ثبت نام کنید.
سوال درهم سازی هم حل شد و به نظرم خیلی جالب اومد.
من توان سوم اعداد ۱ تا ۱۰ رو حساب کردم و باقیمانده اونا رو نسبت به ۱۰ گرفتم و جالب این بود که جواب هر کدوم متمایز بود، یعنی این تابع درهم سازی که در سوال ذکر شده فقط میخواسته ما رو گیج کنه تا از خیر سوال بگذریم وگرنه فرقی با اینکه باقیمانده همون عدد اصلی رو نسبت به ۱۰ بگیریم نداره.
این جوری توی ۱۰۰۰ تا عدد، ۱۰۰ مورد هست که با این تابع به index یکسان اشاره می کنه، اگه احتمالش رو حساب کنیم میشه ۱۰۰ به ۱۰۰۰ یعنی ۰/۱
ارسال: #۷
  
RE: سوال درهم سازی و btree سال ۹۳
(۰۲ دى ۱۳۹۳ ۰۳:۳۰ ب.ظ)ana9940 نوشته شده توسط: سوال Btree رو توی این لینک زیر یه جواب گذاشتم.
مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمیباشید. جهت مشاهده پیوندها ثبت نام کنید.
سوال درهم سازی هم حل شد و به نظرم خیلی جالب اومد.
من توان سوم اعداد ۱ تا ۱۰ رو حساب کردم و باقیمانده اونا رو نسبت به ۱۰ گرفتم و جالب این بود که جواب هر کدوم متمایز بود، یعنی این تابع درهم سازی که در سوال ذکر شده فقط میخواسته ما رو گیج کنه تا از خیر سوال بگذریم وگرنه فرقی با اینکه باقیمانده همون عدد اصلی رو نسبت به ۱۰ بگیریم نداره.
این جوری توی ۱۰۰۰ تا عدد، ۱۰۰ مورد هست که با این تابع به index یکسان اشاره می کنه، اگه احتمالش رو حساب کنیم میشه ۱۰۰ به ۱۰۰۰ یعنی ۰/۱
ببخشید به نظرم این نوع تقسیم درست نباشه.شما اومدید ۱۰۰ کلید از کل کلید ها رو در نظر گرفتید که این درست نیست ممکنه اون ۱۰۰ تا کلید صرفا تو یه حفره نباشن
ارسال: #۸
  
RE: سوال درهم سازی و btree سال ۹۳
(۰۲ دى ۱۳۹۳ ۰۸:۰۷ ب.ظ)miladcr7 نوشته شده توسط: ببخشید به نظرم این نوع تقسیم درست نباشه.شما اومدید ۱۰۰ کلید از کل کلید ها رو در نظر گرفتید که این درست نیست ممکنه اون ۱۰۰ تا کلید صرفا تو یه حفره نباشن
چرا درست نباشه؟خب احتمالش گرفتم دیگه. اینو قبول کردی که ده تا عدد ده اندیس متفاوت رو از تابع درهم سازی میگیرند ؟ مثلا اعداد یک تا ۱۰، حالا عدد یازده قطعا جواب تابع درهم سازی اون یکی از اعداد قبلیه، چون هزار تا عدد متوالی رو گفته شده، پس هر ۱۰۰ تایی از اون ها احتمال یکسان شدن تابع درهم سازیشون هست که نسبتش میشه ۰/۱
اگه اون قسمت حلم درست باشه، احتمالش میشه همون ۰/۱ . یعنی اعداد ۱ تا ۱۰ که من حساب کردم و باقیمانده توان سومشون متمایز شد و همین فرض رو برای اعداد ۱۱ تا ۲۰ کردم ممکنه جامعیت نداشته باشه؟!؟!
۰
ارسال: #۹
  
RE: سوال درهم سازی و btree سال ۹۳
ببین الان شما اومدی گفتی هر ۱۰۰ تا عدد دارای یه اندیسن.قبول.!!!ولی از کجا معلوم اون دوتایی که انتخاب میشه دارای یک اندیسن؟؟؟؟
شما اینو به نظرم در نظر نگرفتی!!!
ببین صورت سوال گفته ۲ عدد که انتخاب میکنیم دارای یک اندیس باشن
شما اینو به نظرم در نظر نگرفتی!!!
ببین صورت سوال گفته ۲ عدد که انتخاب میکنیم دارای یک اندیس باشن
ارسال: #۱۰
  
RE: سوال درهم سازی و btree سال ۹۳
(۰۲ دى ۱۳۹۳ ۱۱:۴۹ ب.ظ)miladcr7 نوشته شده توسط: ببین الان شما اومدی گفتی هر ۱۰۰ تا عدد دارای یه اندیسن.قبول.!!!ولی از کجا معلوم اون دوتایی که انتخاب میشه دارای یک اندیسن؟؟؟؟
شما اینو به نظرم در نظر نگرفتی!!!
ببین صورت سوال گفته ۲ عدد که انتخاب میکنیم دارای یک اندیس باشن
الان متوجه شدم منظورتون چیه. من اصلا روی مبحث احتمالش دقت نکردم.
ببین نگفته که ما دو عنصر را به تصادف انتخاب میکنیم . همین جوری در ساده ترین حالت برای احتمال گرفتن جواب میشه ۰/۱/ ولی الان گیج شدم، نمیدونم منظور سوال چیه!!
البته چون مربوط به ساختمان داده است حس می کنم منظور همونی که من حل کردم ولی بد گفته.
(۰۲ دى ۱۳۹۳ ۱۱:۴۹ ب.ظ)miladcr7 نوشته شده توسط: ببین الان شما اومدی گفتی هر ۱۰۰ تا عدد دارای یه اندیسن.قبول.!!!ولی از کجا معلوم اون دوتایی که انتخاب میشه دارای یک اندیسن؟؟؟؟
شما اینو به نظرم در نظر نگرفتی!!!
ببین صورت سوال گفته ۲ عدد که انتخاب میکنیم دارای یک اندیس باشن
واسه اینکه گیج نشیم میشه اینجوری گفت.
فرض کن عدد اول ۰ انتخاب شده که مثلا طبق تابع به اندیس ۰ رجوع میشه، حالا عدد بعدی که انتخاب میشه جواب تابعش قطعا یکی از اعداد ۰ تا ۹ هست، که به احتمال ۰/۱ میتونه جواب تابعش ۰ باشه.
۰
ارسال: #۱۱
  
RE: سوال درهم سازی و btree سال ۹۳
ببینید صورت سوال میخواد دقیقا دو تا رو انتخاب کنی که دارای یک اندیس باشن.
این سوال اصلا جواب دقیق نداره.تقریبیه.من جوابشو براتون مینویسم.بعد مقایسه میکنیم ببینیم چی به چیه
این سوال اصلا جواب دقیق نداره.تقریبیه.من جوابشو براتون مینویسم.بعد مقایسه میکنیم ببینیم چی به چیه
Can I see some ID?
Feeling left out?
نگران نباش، فقط روی این لینک برای ثبت نام کلیک کن. رمزت رو فراموش کردی؟ اینجا به یادت میاریم! close