تست ۴۴ ساختمان داده ۸۸ - نسخهی قابل چاپ |
تست ۴۴ ساختمان داده ۸۸ - m_sardaari - 21 مهر ۱۳۹۱ ۱۰:۵۲ ب.ظ
دوستان اگه کسی میتونه این تست رو تشریح کنه و جوابشو با دلیل بگه ممنون میشم |
RE: تست ۴۴ ساختمان داده ۸۸ - masoud.bala - 22 مهر ۱۳۹۱ ۱۰:۱۵ ق.ظ
(۲۱ مهر ۱۳۹۱ ۱۰:۵۲ ب.ظ)m_sardaari نوشته شده توسط: دوستان اگه کسی میتونه این تست رو تشریح کنه و جوابشو با دلیل بگه ممنون میشم سلام خوبی ببین واسه حل این جور حلقه ها باید این کاری که بهت می گم را انجام بدی شما الان ۳ تا حلقه for می بینی for اول را ندید بگیر کلاً برو تو for دوم و سوم این دو تا به هم وابسته هستند این نکته را یادت باشه که چوت توان ۲ داریم حتماً جواب دو تا حلقه ات logn است حالا باید بری تریس کنی کامل متوجه می شی حلقه ائل هم n بار اجرا می شودپس مرتبه اجرایی می شه گزینه ۳ بازم نفهمیدی بگو |
تست ۴۴ ساختمان داده ۸۸ - m_sardaari - 22 مهر ۱۳۹۱ ۱۰:۵۹ ق.ظ
ممنون دوست عزیز. اگر تعداد اجرای دستور x++ رو بخوایم چی میشه نه مرتبه؟ بعد مگه هر بار i در دو ضرب نمیشه پس کلا حلقه اول n/2 بار اجرا میشه؟! |
تست ۴۴ ساختمان داده ۸۸ - *Najmeh* - 23 مهر ۱۳۹۱ ۱۲:۰۷ ب.ظ
من توضیحات رو درست متوجه نشدم اگه می شه روشن تر توضیح بدید این رو میدونم که حتم جواب لوگاریتم وتوضیحات رو متوجه نشدم |
RE: تست ۴۴ ساختمان داده ۸۸ - masoud.bala - 23 مهر ۱۳۹۱ ۰۴:۴۸ ب.ظ
(۲۳ مهر ۱۳۹۱ ۱۲:۰۷ ب.ظ)*Najmeh* نوشته شده توسط: من توضیحات رو درست متوجه نشدم اگه می شه روشن تر توضیح بدید ببین دوست عزیز یک عدد دارای اوگاریتم به حلقه دوم بده رفتارشو را میبینی در واقع i^2 می شه بعد i^4 همینجورب می ره تا به I^k می رسه متوجه شدی |
RE: تست ۴۴ ساختمان داده ۸۸ - naderx - 23 مهر ۱۳۹۱ ۰۸:۱۹ ب.ظ
سلام (داستان یک شاگرد شوت و یک استاد با حوصله) حلقه فور اولی رو بیخیال شو ، پس اول برو سراغ دو تا حلقه فور پاینی، اوکی ؟ خوب چرا این کارو کردیم ؟ چون حلقه اول کاری به دو تا حلقه بعدی نداره یعنی واسه خودش مستقله مستقل بودن یعنی چی ؟ یعنی این که اندیس حلقه اول که همان i هست داخل حلقه های دیگه وجود نداره آقا اجازه ؟ بله بفرما ، پس میشه گفت چون اندیس حلقه دوم توی حلقه سوم هست ( j ) پس حلقه سوم و دوم به هم وابسته هستند ؟ بله درست گفتی ! آفرین حالا بریم ادامه کار .... قبول داری حلقه دوم اینجوری میشمارد : ۱ بعد ۲ بعد ۴ بعد ۸ بعد ۱۶ و الی آخر ؟ بله قبول دارم حالا که قبول داری،اینم قبول داری که حلقه سوم به اندازه مقدار اندیس حلقه دوم اجرا میشه ؟ نه قبول ندارم ! یعنی نمیفهمم چی میگین ! بترکی ! آی کیو اندازه جلبک دریایی ! باشه یکم آسون تر میگم : توی حلقه سوم متغییرش چیه ؟ مگه k نیست ؟ بله، خوب مگه از یک شروع نشده ؟ بله ، خوب جونت در بیاد ! مگه تا j پیش نمیره ؟ بله پیش میره ، خوب پس قبول داری حلقه سومی به اندازه j دستور زیرش رو اجرا میکنه ؟ بزار فکر کنم آهان ! قبول ! ، خوب مگه نگفتی حلقه دوم اینجوری میشمارد : ۱ بعد ۲ بعد ۴ بعد ۸ بعد ۱۶ و الی آخر ؟ بله گفتم ، خوب پس حلقه سوم به ازای هر مقداری که j میگیرد دستور زیرش رو اجرا میکنه ، یعنی : وقتی j یک است یکبار اجرا میکنه و وقتی j دو است دوبار اجرا میکنه و الی آخر ، یعنی : ۱+۲+۴+۸+۱۶+... اوکی ؟ اوکی ! خوب به نظرت تا کجا این سری ادامه پیدا میکنه ؟ فکر کنم تا جایی که j به n برسه درست گفتی ! آفرین پس قبول داری حلقه دوم اینجوری تغییر میکنه : ۱و۲و۴و۸و۱۶و...وn بله قبول دارم ، حالا که قبول داری ، بیا یه فرضی بکنیم ، چه فرضی ؟ بیا فرض کنیم n توانی از دو باشه ، به چه درد میخوره ؟ تو چه کار داری ؟ فقط گوش بده ! باشه گوش میدم ، پس فرض کردیم n=2^k ، قبول ؟ قبول، خوب حالا بیا به این جلمه دقیق تر نگاه کنیم : ۱و۲و۴و۸و۱۶و...وn ، میتونم به جای یک بنویسم دو به توان صفر ؟ بله ، میتونم به جای دو بنویسم دو به توان یک ؟ بله میتونم به جای چهار بنویسم دو به توان دو ؟ بله ، و همینطور الی آخر و آیا میتوانم به جای n بنویسم دو به توان k (بر طبق فرضی که کردیم) ؟ بله میشه نوشت، اگه میشه پس باز نویسی کنم این جوری میشه : ۰^۲ و ۱^۲ و ۲^۲ و .... و تا دو به توان k به نظرت چند تا عدد هست ؟ نمیدونم ، بترکی اللهی ! خوب توان های دو از چند هستند تا چند ؟ از صفر شروع میشن تا k آفرین ! خوب پس چند تا عدد داریم ؟ k تا عدد ، بمیری ! k+1 عدد چون از صفر داریم تا k اوکی ؟ اوکی ! خوب بیا از فرضمون الگاریتم بگیریم، حتما الگاریتم رو هم بلد نیستی ! ؟ نه دیگه استاد اینقدر ها بلدم، خوبه ، پس چی میشه ؟ چی چی میشه ؟ اگه از فرضمون الگاریتم بگیریم دیگه ! آهان ، خوب میشه : k=log n ، خوبه پس قبول داری به اندازه log n تا عدد حلقه دوم درست میکنه ؟ بله قبول دارم ، پس باید اینم قبول داشته باشی که حلقه پایینی به اندازه مقدار هر یک از این اعدادی که حلقه دومی میسازه دستور آخر رو اجرا میکنه،قبول ؟ قبول ، خوب پس حلقه سومی داره به اندازه مجموع یه تعداد عدد که همشون هم توان های دو هستند اجرا میشه ، قبول ؟ قبول ، چند تا عدد ؟ الگاریتم n تا عدد ، آهان ، خوبه ، پس قبول داری تعداد اجراهای حلقه سوم اینجوری میشه ؟ ۱+۲+۴+۸+۱۶+۳۲+... ؟ بله ! اینو قبلآ هم که گفته بودین بله گفته بودم ولی دو ساعت فک زدم تا بهت حالی کنم تعداد این اعداد لگاریتم n هست. و اگه یکم سواد ریاضی داشته باشی، میفهمی که این سری میشه مجموع اعداد توان دو که چند تا هستن ؟ لگاریتم n ، خوب حالا حاصلش چند میشه استاد ؟ میشه : ۲n-1 چرا ؟ چرا نداره ! چرا رو تو یه داستان دیگه کلی توضیح میدم، همینجوری فعلآ ازم قبول کن ، باشه استاد ، خوب حالا بعد از کلی حرف و توضیح فهمیدیم که دو تا حلقه پایینی به اندازه ۲n-1 اجرا میشه و حالا حلقه اول رو بیار تو کار، چون تعداد تکرار حلقه اول از مرتبه الگاریتم n است و چون این حلقه با این دو تا حلقه کاری نداره (مستقله) باید تعداد اجراهای این حلقه رو در تعداد تکرار دو تا حلقه دیگه ضرب کنیم : یعنی : ۲n-1 * log n که مرتبش میشه : nlogn چرا رو در ضمیمه آوردم |