۰
subtitle
ارسال: #۱
  
سوال ۹۰ علوم ۹۱(ساختمان داده)
دوستان عزیز میشه توضیح بدید چرا گزینه ۱ میشه!؟
ممنون میشم.
ممنون میشم.
۰
ارسال: #۲
  
سوال ۹۰ علوم ۹۱(ساختمان داده)
on یکم مشکوکه. من نتونستم چیزی با این مرتبه به دست بیارم. چون گفته با هزینه مصرفی ثابت. اگه نمی گفت میشد به دست بیارین. nolgn که مشخصه میشه با مرتب سازی و بعدش پیدا کردن این عنصر با هزینه مصرفی ثابت
یه سوال کی میشه از هش استفاده کرد؟ اگه بگن یا نه و مرتبه اش به طور متوسط چقدره؟
یه سوال کی میشه از هش استفاده کرد؟ اگه بگن یا نه و مرتبه اش به طور متوسط چقدره؟
۰
ارسال: #۳
  
سوال ۹۰ علوم ۹۱(ساختمان داده)
من به نظرم اینجوریه که میایم تو o(n) آرایه رو از مکان n/3 پارتیشن میکنیم و از n/3 تا آخر رو هم روی ۲n/3 پارتیشن می کنیم. حالا ما آرایه رو به سه دسته ی مجزا تقسیم کردیم. از ۰ تا n/3 ، از n/3 تا ۲n/3 و از ۲n/3 تا آخر. من معتقدم مقدار مورد نظر ما یا عنصر n/3ام آرایه است یا ۲n/3. واسه اینکه بفهمیم کدومه کافیه تعداد اونهارو تو دسته های مجاورشون بشمریم و بینیم که بیشتر ار n/3 هست یا نه که مجموعه ی این کارا توی o)n) انجام میشه.
در مورد این که چرا مطمئنم می تونی هر آرایه ی دلخواهی که شرایط مسئله رو داره می خوای بنویسی و بعد مرتبش کنی و آیتم n/3 و ۲n/3 امش رو در نظر بگیری که میشه همون مقداری که از پارتیشن به دست میاد. بعد میبینی که حتما همون عدد جوابه.
دلیل قانع کننده ترش اینه که وقتی از یه عددی بیشتر از n/3 داریم و هر دسته هم n/3 تا ظرفیت داره حتما این عدد تو ۲ تا دسته حضور داره و این امکان نداره بعد از پارتیشن یک عدد هم در سمت چپ محور باشه هم سمت راست محور مگر اینکه مقدارش با محور برابر باشه.
خیلی فکر کردم تا این جوابو به دست بیارم. نمی تونم سر کنکور چجوری باید اینو می فهمیدن بیچاره ها
در مورد این که چرا مطمئنم می تونی هر آرایه ی دلخواهی که شرایط مسئله رو داره می خوای بنویسی و بعد مرتبش کنی و آیتم n/3 و ۲n/3 امش رو در نظر بگیری که میشه همون مقداری که از پارتیشن به دست میاد. بعد میبینی که حتما همون عدد جوابه.
دلیل قانع کننده ترش اینه که وقتی از یه عددی بیشتر از n/3 داریم و هر دسته هم n/3 تا ظرفیت داره حتما این عدد تو ۲ تا دسته حضور داره و این امکان نداره بعد از پارتیشن یک عدد هم در سمت چپ محور باشه هم سمت راست محور مگر اینکه مقدارش با محور برابر باشه.
خیلی فکر کردم تا این جوابو به دست بیارم. نمی تونم سر کنکور چجوری باید اینو می فهمیدن بیچاره ها
۰
ارسال: #۴
  
سوال ۹۰ علوم ۹۱(ساختمان داده)
(۱۷ بهمن ۱۳۹۱ ۰۵:۱۴ ب.ظ)armin_b00ter نوشته شده توسط: من به نظرم اینجوریه که میایم تو o(n) آرایه رو از مکان n/3 پارتیشن میکنیم و از n/3 تا آخر رو هم روی ۲n/3 پارتیشن می کنیم. حالا ما آرایه رو به سه دسته ی مجزا تقسیم کردیم. از ۰ تا n/3 ، از n/3 تا ۲n/3 و از ۲n/3 تا آخر. من معتقدم مقدار مورد نظر ما یا عنصر n/3ام آرایه است یا ۲n/3. واسه اینکه بفهمیم کدومه کافیه تعداد اونهارو تو دسته های مجاورشون بشمریم و بینیم که بیشتر ار n/3 هست یا نه که مجموعه ی این کارا توی o)n) انجام میشه.روشتو قبول دارم آرمین جان!ولی وقتی می دونیم گزینه ۱ درسته این مدلی تحلیل می کنیم!قبول داری؟!
در مورد این که چرا مطمئنم می تونی هر آرایه ی دلخواهی که شرایط مسئله رو داره می خوای بنویسی و بعد مرتبش کنی و آیتم n/3 و ۲n/3 امش رو در نظر بگیری که میشه همون مقداری که از پارتیشن به دست میاد. بعد میبینی که حتما همون عدد جوابه.
دلیل قانع کننده ترش اینه که وقتی از یه عددی بیشتر از n/3 داریم و هر دسته هم n/3 تا ظرفیت داره حتما این عدد تو ۲ تا دسته حضور داره و این امکان نداره بعد از پارتیشن یک عدد هم در سمت چپ محور باشه هم سمت راست محور مگر اینکه مقدارش با محور برابر باشه.
خیلی فکر کردم تا این جوابو به دست بیارم. نمی تونم سر کنکور چجوری باید اینو می فهمیدن بیچاره ها
یعنی بشخصه من اگه سر جلسه این سوالرو ببینم عمرا توی اون وقت با اطمینان بزنم گزینه یک رو!
بهرحال ممنون
۰
ارسال: #۵
  
سوال ۹۰ علوم ۹۱(ساختمان داده)
(۱۷ بهمن ۱۳۹۱ ۰۵:۳۳ ب.ظ)۸Operation نوشته شده توسط: روشتو قبول دارم آرمین جان!ولی وقتی می دونیم گزینه ۱ درسته این مدلی تحلیل می کنیم!قبول داری؟!به نظر من که اصلا نباید سر همچین سوالایی واسیتاد. باید ردشون کنی و وقتی وقت اضافه داشتی بیای سرشون. بعدشم باید نگاه کنی به گزینه ها. logn که یه جورایی معلومه نمیشه. nlogn هم که راحت میشه واسش جواب پیدا کرد. پس اینجا می مونه n. حالا باید زور بزنی با استفاده از ابزارایی که داری و بلدی یه راه حل پیدا کنی واسش. اگه تونستی میزنی n اگر نتونستی نمی زنی سوالو
یعنی بشخصه من اگه سر جلسه این سوالرو ببینم عمرا توی اون وقت با اطمینان بزنم گزینه یک رو!
بهرحال ممنون
۰
ارسال: #۶
  
سوال ۹۰ علوم ۹۱(ساختمان داده)
عالی
برای این مثال لطفا توضیح بدین
۱۲۳۴۵۶۳۳۳۳۴۴۳۳۵۵۵۵
۱۲۳۴۵۶
۳۳۳۳۴۴
۳۳۵۵۵۵
n=18
جواب سه هست
الآن بیشینه ها رو باید محاسبه کنیم تو هر بخش؟
یکیش که اصلا مشخص نیست بیشینه چیه. بعدیش میشه سه و بعدیش هم میشه پنج
اون طوری که من فهمیدم، با محاسبه بیشینه در هر بخش، حتما یکی از بیشینه ها عدد موردنظر است که استدلال درستی است.
برای مثالی مثل n=18
۳و۲و۳و۴و۲و۴
۵و۳و۵و۳و۱و۱
۳و۸و۳و۸و۳و۸
که جزو سخت ترین مثالهاست کاری که باید بکنیم اول محاسبه بیشینه است در هر بخش.
که میشه ۲و۳و۴ هر کدام دو در بخش اول، ۱و۳و۵ هر کدام دو در بخش دوم و ۳و۸ هر کدام سه در بخش سوم با داشتن تعداد آنها و جمعشان سه عدد موردنظر است.
می توان اثبات کرد که برای نگه داری اطلاعات بیشینه ها به تعداد خانه های ثابت نیاز است
برای این مثال لطفا توضیح بدین
۱۲۳۴۵۶۳۳۳۳۴۴۳۳۵۵۵۵
۱۲۳۴۵۶
۳۳۳۳۴۴
۳۳۵۵۵۵
n=18
جواب سه هست
الآن بیشینه ها رو باید محاسبه کنیم تو هر بخش؟
یکیش که اصلا مشخص نیست بیشینه چیه. بعدیش میشه سه و بعدیش هم میشه پنج
اون طوری که من فهمیدم، با محاسبه بیشینه در هر بخش، حتما یکی از بیشینه ها عدد موردنظر است که استدلال درستی است.
برای مثالی مثل n=18
۳و۲و۳و۴و۲و۴
۵و۳و۵و۳و۱و۱
۳و۸و۳و۸و۳و۸
که جزو سخت ترین مثالهاست کاری که باید بکنیم اول محاسبه بیشینه است در هر بخش.
که میشه ۲و۳و۴ هر کدام دو در بخش اول، ۱و۳و۵ هر کدام دو در بخش دوم و ۳و۸ هر کدام سه در بخش سوم با داشتن تعداد آنها و جمعشان سه عدد موردنظر است.
می توان اثبات کرد که برای نگه داری اطلاعات بیشینه ها به تعداد خانه های ثابت نیاز است
Can I see some ID?
Feeling left out?
نگران نباش، فقط روی این لینک برای ثبت نام کلیک کن. رمزت رو فراموش کردی؟ اینجا به یادت میاریم! close