این سوال رو توی جزوه کلاس دکتر یوسفی دیدم.
متوجه راه حلش نشدم، چرا توانی از دو حساب کرده مراحل رو؟
[attachment=17650]
(۱۷ دى ۱۳۹۳ ۰۶:۱۳ ب.ظ)Ametrine نوشته شده توسط: این سوال رو توی جزوه کلاس دکتر یوسفی دیدم.در ابتدا آرایه خالی است یک درج انجام میدیم و طول آرایه یک میشه.(هزینه درج عنصر ۱ =۱)
متوجه راه حلش نشدم، چرا توانی از دو حساب کرده مراحل رو؟
آرایه پر شد : آرایه جدیدی به طول ۲ می سازیم و این عنصر را در آن کپی می کنیم.( هزینه کپی=۱)
حال آرایه ای به طول دو و با یک عنصر خالی داریم بنابر این عنصر دوم را هم در آن درج می کنیم (هزینه درج عنصر ۲ =۱)
آرایه پر شد: آرایه جدیدی به طول ۴ می سازیم و دو عنصر قبلی را در آن کپی می کنیم ( هزینه کپی =۲)
حال آرایه ای به طول چهار و با دو عنصر خالی داریم بنابر این عنصر سوم و چهارم را هم در آن درج می کنیم (هزینه درج عنصر ۳ و ۴ =۲)
آرایه پر شد: آرایه جدیدی به طول ۸ می سازیم و چهار عنصر قبلی را در آن کپی می کنیم ( هزینه کپی =۴)
.
.
.
و الی آخر....
در کل هر عنصری یک بار درج شد و هزینه درج برابر ۱۰۰۰ خواهد بود ( ۱۰۰۰ عنصر داریم)
هزینه کپی هم همانطوری که در بالا دیدیم به صورت جمع ۱+۲+۴+... خواهد بود.انتهای این دنباله نیز ۵۱۲ است زیرا وقتی نیازمند کپی ۵۱۲ عنصر شدیم یعنی ارایه جدید مان ۱۰۲۴ تایی خواهد بود و دیگر مشکل جا وجود نخواهد داشت....
(۱۸ دى ۱۳۹۳ ۰۷:۵۸ ق.ظ)Ametrine نوشته شده توسط: ممنون از توضیحات کاملتون.دو تا دو تا اضافه نکردیم. طبق صورت سوال در هر مرحله که آرایه پر شد سایز آرایه رو دو برابر کردیم.شاید منظورتون رو درست نفهمیدم..
چرا دوتا دوتا خونه اضافه میکنیم؟
چرا مثلاً اینطوری نمیگیم:
یک خونه داریم ۱ درج انجام میدیم، پر میشه، پس ۱ خونه دیگه به این اضافه میکنیم.
میشه ۲ خونه، حالا قبلی رو کپی میکنیم یه مقدار جدید دیگه هم درج میکنیم. دوباره آرایه پر میشه.
پس یه خونه دیگه اضافه میکنیم، میشه ۳ خونه، دوتای قبلی رو کپی میکنیم و تو خونه ی جدید ۱ درج انجام میدیم ....
(۱۸ دى ۱۳۹۳ ۰۸:۱۸ ب.ظ)codin نوشته شده توسط: دو تا دو تا اضافه نکردیم. طبق صورت سوال در هر مرحله که آرایه پر شد سایز آرایه رو دو برابر کردیم.شاید منظورتون رو درست نفهمیدم..چه بد! صورت سوال رو درست نخوندم!
من عذرمیخوام