(۳۰ فروردین ۱۳۹۶ ۰۱:۰۳ ق.ظ)msour44 نوشته شده توسط:  سلام
n عدد صحیح داریم ولی ۱۵ عدد متمایز از ۱ تا ۱۵ که این n عدد به صورت مرتب شده هستند(مثلا یک ارایه مرتب)
سوال گفته به کمک جستجویی دودویی ابتدا و انتهای تکرار عدد ۸ را پیدا می کنیم یعنی محل اولین و اخرین رخداد عدد ۸ که این کار به این صورت انجام می شود مثلا یکبار$7.9$ را جستجو میکنیم که جستجو بین اولین رخداد ۸ و اخرین رخداد ۷ متوقف می شود ویکبار هم $8.1$ را جستجو می کنیم تا محل اخرین عدد ۸ را بیابیم توجه شود که n عدد صحیح است و ارایه هم مرتب. پس با دو مقایسه محل اولین و اخرین رخداد عدد ۸ را پیدا کردیم(کار با اندیس ها) با انجام یک تفاضل ساده روی اندیس محل های پیدا شده تعداد تکرار عدد ۸ بدست می اید حالا همین کار را برای عدد ۴ در بازه قبل از محل اولین رخداد ۸ تا ابتدای ارایه انجام می دهیم و همچنین عدد ۱۲ در بازه راستی در واقع برای یافتن تعداد تکرار هر عدد در بدترین حالت ۲ بار جستجویی دودویی را انجام میدهیم ۱۵ عدد داشتیم پس در بدترین حالت ۳۰ بار البته احتمالا می توانیم با هر بار جستجو دو محل برای دو عدد پیدا کنیم ولی خوب زیاد تاثیری روی مرتبه ندارد و باز تعداد تکرار ثابت است پس هزینه کلی این الگوریتم همان هزینه جستجو یعنی $O(\lg n)$ است گزینه ۲

دوست عزیز
خیلی لطف کردید، مثل همیشه کامل و جامع
موفق و پیروز باشید انشاالله

---

(۳۰ فروردین ۱۳۹۶ ۱۲:۲۴ ق.ظ)*tarannom* نوشته شده توسط:  

(29 فروردین ۱۳۹۶ ۰۷:۵۴ ب.ظ)alimamala نوشته شده توسط:  با عرض سلام
دوستان یه راهنمایی در مورد سوال زیر می فرمایید لطفا ؟
با سپاس و قدر دانی

اگه میشه پاسخشو بذارید....

این پاسخ کتاب هست دوست من، ولی فکر نمی کنم با توضیحات دوستمون نیازی بهش باشه

(۳۰ فروردین ۱۳۹۶ ۰۱:۰۳ ق.ظ)msour44 نوشته شده توسط:  سلام
n عدد صحیح داریم ولی ۱۵ عدد متمایز از ۱ تا ۱۵ که این n عدد به صورت مرتب شده هستند(مثلا یک ارایه مرتب)
سوال گفته به کمک جستجویی دودویی ابتدا و انتهای تکرار عدد ۸ را پیدا می کنیم یعنی محل اولین و اخرین رخداد عدد ۸ که این کار به این صورت انجام می شود مثلا یکبار$7.9$ را جستجو میکنیم که جستجو بین اولین رخداد ۸ و اخرین رخداد ۷ متوقف می شود ویکبار هم $8.1$ را جستجو می کنیم تا محل اخرین عدد ۸ را بیابیم توجه شود که n عدد صحیح است و ارایه هم مرتب. پس با دو مقایسه محل اولین و اخرین رخداد عدد ۸ را پیدا کردیم(کار با اندیس ها) با انجام یک تفاضل ساده روی اندیس محل های پیدا شده تعداد تکرار عدد ۸ بدست می اید حالا همین کار را برای عدد ۴ در بازه قبل از محل اولین رخداد ۸ تا ابتدای ارایه انجام می دهیم و همچنین عدد ۱۲ در بازه راستی در واقع برای یافتن تعداد تکرار هر عدد در بدترین حالت ۲ بار جستجویی دودویی را انجام میدهیم ۱۵ عدد داشتیم پس در بدترین حالت ۳۰ بار البته احتمالا می توانیم با هر بار جستجو دو محل برای دو عدد پیدا کنیم ولی خوب زیاد تاثیری روی مرتبه ندارد و باز تعداد تکرار ثابت است پس هزینه کلی این الگوریتم همان هزینه جستجو یعنی $O(\lg n)$ است گزینه ۲

اگه میشه رابطه بازگشتیشم بگید رو اونم یه توضیح مختصری بدید.....ممنون...

(۳۰ فروردین ۱۳۹۶ ۰۹:۳۶ ق.ظ)*tarannom* نوشته شده توسط:  

(30 فروردین ۱۳۹۶ ۰۱:۰۳ ق.ظ)msour44 نوشته شده توسط:  سلام
n عدد صحیح داریم ولی ۱۵ عدد متمایز از ۱ تا ۱۵ که این n عدد به صورت مرتب شده هستند(مثلا یک ارایه مرتب)
سوال گفته به کمک جستجویی دودویی ابتدا و انتهای تکرار عدد ۸ را پیدا می کنیم یعنی محل اولین و اخرین رخداد عدد ۸ که این کار به این صورت انجام می شود مثلا یکبار$7.9$ را جستجو میکنیم که جستجو بین اولین رخداد ۸ و اخرین رخداد ۷ متوقف می شود ویکبار هم $8.1$ را جستجو می کنیم تا محل اخرین عدد ۸ را بیابیم توجه شود که n عدد صحیح است و ارایه هم مرتب. پس با دو مقایسه محل اولین و اخرین رخداد عدد ۸ را پیدا کردیم(کار با اندیس ها) با انجام یک تفاضل ساده روی اندیس محل های پیدا شده تعداد تکرار عدد ۸ بدست می اید حالا همین کار را برای عدد ۴ در بازه قبل از محل اولین رخداد ۸ تا ابتدای ارایه انجام می دهیم و همچنین عدد ۱۲ در بازه راستی در واقع برای یافتن تعداد تکرار هر عدد در بدترین حالت ۲ بار جستجویی دودویی را انجام میدهیم ۱۵ عدد داشتیم پس در بدترین حالت ۳۰ بار البته احتمالا می توانیم با هر بار جستجو دو محل برای دو عدد پیدا کنیم ولی خوب زیاد تاثیری روی مرتبه ندارد و باز تعداد تکرار ثابت است پس هزینه کلی این الگوریتم همان هزینه جستجو یعنی $O(\lg n)$ است گزینه ۲

اگه میشه رابطه بازگشتیشم بگید رو اونم یه توضیح مختصری بدید.....ممنون...

به نظر میرسیه رابطه بازگشتی دو پارامتری نیاز داریم یک n همان تعداد عدد صحیح و دیگری بازه ۱ تا ۱۵ همان محدوده اعداد متمایز پس برای این سوال رابطه بازگشتی می تونه به شکل زیر باشه
$T(n,[1..15])=T(n_1,[1..7])+T(n_2,[9..15])+O(\lg n)$
که $n_1$ تعداد اعداد صحیح بازه چپی و دیگری هم راستی است که بستگی به تعداد عدد مورد جستجو در هر مرحله دارد(بازه ها هم تغییر می کنند می توانیم از میانگین هر بار استفاده کنیم). مثلا در همان گام اول در بهترین حالت تعداد عدد ۸ برابر n-14 است و سایر اعداد هر کدام فقط یک بار تکرار شده اند پس داریم
$T(n,[1..15])=T(7,[1..7])+T(7,[9..15])+O(\lg n)=O(1)+O(1)+O(\lg n)=O(\lg n)$
که $T(7,[1..7])$ یعنی ۷ تا عدد داریم که اعداد متمایز از ۱ تا ۷ است و چون هر عدد یکبار جداقل طبق سوال تکرار شده پس تعداد تکرار هر عدد برابر یک است و نیاز به محاسبه ندارد در واقع نوعی شرط پایان بازگشتی است.البته در حالت های دیگر هم با توجه به ثابت بودن تعداد اعداد متمایز زیاد بر تعداد تکرار روابط اضافه نمی شود ولی اگر محدوده اعداد متمایز ثابت نباشد مثلا$[1..\sqrt{n}]$ موضوع کمی پیچیده می شودو در این مورد باید حالت های مختلف بررسی و میانگین گیری انجام داده تا به نتیجه برسیم که مثل بعضی از نویسندگان کتاب ها که هر وقت موضوع پیچیده میشه میگن بدلیل پیچیدگی زیاد از گفتن ان صرف نظر می شود ویا به عنوان تمرین به دانشجو واگذار می شود.اینجا هم این موضوع به عنوان تمرین به شما دوست گرامی واگذار می شود تا شما باشین دیگه ازاین سوالات نپرسین.(البته باسه بعد ارشد)
البته ممکن است رابطه بهتری وجود داشته باشد به هر حال این رابطه در یک بررسی اولیه حاصل شد

حاج اقا مرسی واقعا خیلی خوب میگید
یه سوال! با توجه به اینکه تو سوال گفته ارایه رو دو قسمت میکنیم و با تقسیم غلبه میریم :چه وقت باز گشتیو براساس (T(n/2 مینویسیم اینجا؟! اگه بازه ی اعداد صحیحو به ما نداده بود؟ یا اگه نگفته بود اعداد مرتبن؟
نمیدونم منظورمو متوجه میشید یا نه؟میخوام بگم چه زمای با دوتا ( T(n/2 به اضافه ی log n بازگشت میریم که مرتبه بشه تتای n؟
الان تو این رابطه که گفتید چون یه بازه ی مشخص داریم مرتبه ی هر بازگشتی شد تتای ۱؟

(۳۰ فروردین ۱۳۹۶ ۰۲:۱۱ ب.ظ)*tarannom* نوشته شده توسط:  حاج اقا مرسی واقعا خیلی خوب میگید
یه سوال! با توجه به اینکه تو سوال گفته ارایه رو دو قسمت میکنیم و با تقسیم غلبه میریم :چه وقت باز گشتیو براساس (T(n/2 مینویسیم اینجا؟! اگه بازه ی اعداد صحیحو به ما نداده بود؟ یا اگه نگفته بود اعداد مرتبن؟
نمیدونم منظورمو متوجه میشید یا نه؟میخوام بگم چه زمای با دوتا ( T(n/2 به اضافه ی log n بازگشت میریم که مرتبه بشه تتای n؟
الان تو این رابطه که گفتید چون یه بازه ی مشخص داریم مرتبه ی هر بازگشتی شد تتای ۱؟

اول دقت کنید که بازگشتی ما دو پارامتری است پارامتر اول تعداد کل اعداد و پارامتر دوم مشخص کننده اعداد متمایز
اینکه چه زمانی دوتا رابطه با n/2 به اضافه lgn داریم که مرتبش بشه تتای n ? با توجه به شیوه مطرح شده در سوال چنین چیزی اتفاق نمی افتد همان طوری که محاسبه کردیم مر تبه در بدترین حالت lgn میشه ولی ممکن است الگوریتم دیگری مطرح بود در سوال که باعث ایجاد چنین وضعیتی بشود.
اینکه چون بازه مشخصی داریم مرتبه هر بازگشتی شد تتای ۱// دقت کنید بازه مشخص نه چون بازه ثابت است میشه تتای ۱ یعنی تعداد تکرار در رابطه بازگشتی کمه یه به عبارتی ارتفاع درخت بازگشتی کمه. گفتیم که هزینه در بدترین حالت رو می توانیم ۳۲ تا lgn بگیریم.
فرض کنید تعداد تکرار عدد ۸ یک باشه پس در چپ و راست ۸ تقریبا n/2 باقی می ماند ولی باید به دو پارامتری بودن دقت کردو حالت های مختلف را جداگانه محاسبه کرد و مرتبه میانگین را بدست اورد.
رابطه بازگشتی مرتب سازی سریع را بیاد اورید$T(n)=T(k)+T(n-k-1)+n-1$ برای یافتن حالت میانگین به k مقادیر مختلف می دادیم در این سوال هم تعداد تکرار در هر گام روی تعداد باقی مانده محدود چپ و راست مرحله بعدی تاثیر گذار است.
اینکه اعداد مرتب نباشند انوقت دیگر نمی توانیم از مرتب سازی دودویی استفاده کنیم در واقع شرایط مطرح شده در تست برقرار نیست در این حالت می توانیم از ایده مرتب سازی شمارشی برابر شمارش تعداد اعداد استفاده کنیم که البته مرتبه n میشه و اینکه بازه نداشته باشم هم احتمالا باعث افزایش مرتبه می شود ولی ممکن است روشی با مرتبه n هم باشه (با استفاده از درهم سازی) البته نیاز به بررسی بیشتر دارد.
نمی دونم منطورمو می تونم برسونم یا نه .
یک ارایه در نظر بگیرد میدونیم که با داشتن یک اندیس به راحتی به مقدار ذخیره شده در ان میتوان دست یاقت حالا الگوریتمی داریم که حداکثر به ۳۲
مقدار ذخیره شده در این ارایه n نیاز دارد هزینه دستیا بی هم ثابت است و لی هزینه یافتن اندیس ها log n حالا الگوریتم ما هر تابع بازگشتی با پارامتر های مختلف(مقادیر مختلف n) را صدا کند در کل چون بیشتر از ۳۲ بار با هزینه log اجرا نمیشه پس مرتبه logn میشه. بیشتر بحث روی بازه ی غیر ثابت بود (که قرار بود شما تحقیق کنید که با طرح سوال جدید توپ انداختین تو زمین من. از بس طولانی شد یادم رفت اولش چی گفتم. ممکنه ضریب اشتباه بره بالا)

آخراش دیگه سرگیجه گرفتم
میگم فرقی داشت اگه نمیگفت مثلا از ۸ شروع کنید؟! میومدیم واسه عدد ۱ تا ۱۵ دودویی جستجو میکردیم.اونوقت چی؟
فکر کنم اگه دم دست بودم زندم نمیذاشتید

(۳۰ فروردین ۱۳۹۶ ۰۴:۵۹ ب.ظ)*tarannom* نوشته شده توسط:  آخراش دیگه سرگیجه گرفتم
میگم فرقی داشت اگه نمیگفت مثلا از ۸ شروع کنید؟! میومدیم واسه عدد ۱ تا ۱۵ دودویی جستجو میکردیم.اونوقت چی؟
فکر کنم اگه دم دست بودم زندم نمیذاشتید

خواهش می کنم دوست گرامی
اگر خوب موضوع را درک نکردید دلیلش توضیحات بد و دانش ناچیز منه و مطمئنا خالی از اشکال نیست.
برای ۱ تا ۱۵ نه زیاد فرقی نمیکنه مثلا اگر به ترتیب ۱ تا ۱۵ رو تعداد تکرارشو پیدا کنیم تو همون رابطه بازگشتی مقدار $n_1$ صفر می شود و مقدار $n_2$ بستگی به تعداد عدد جستجو در گام قبلی دارد. و روی مرتبه تاثیری ندارد ولی اگر بجای ۱۵ مقدار $\sqrt{n}$ یا $\log n$ بوداین روش تقسیم و غلبه کارایی را نسبت به ترتیب های دیگر افزایش میداد حداقل تو ضریب. ویا اگر عدد بزرگی بود این روش با توجه به پارامتر دوم (بازه) شرط پایان بهتری داشت مثل $T(7,[1..7])$ که نیاز به محاسبه نداشت و مشخص بود تعداد تکرار هر عدد از ۱ تا ۷ برابر یک است در واقع طراح با توجه به وقت کنکور مسئله رو با ثابت کردن تعداد اعداد متمایز ساده کرده و هدف درک استفاده از جستجویی دودویی در یافتن تعداد تکرار اعداد است.

(۳۰ فروردین ۱۳۹۶ ۰۷:۲۰ ب.ظ)msour44 نوشته شده توسط:  

(30 فروردین ۱۳۹۶ ۰۴:۵۹ ب.ظ)*tarannom* نوشته شده توسط:  آخراش دیگه سرگیجه گرفتم
میگم فرقی داشت اگه نمیگفت مثلا از ۸ شروع کنید؟! میومدیم واسه عدد ۱ تا ۱۵ دودویی جستجو میکردیم.اونوقت چی؟
فکر کنم اگه دم دست بودم زندم نمیذاشتید

خواهش می کنم دوست گرامی
اگر خوب موضوع را درک نکردید دلیلش توضیحات بد و دانش ناچیز منه و مطمئنا خالی از اشکال نیست.
برای ۱ تا ۱۵ نه زیاد فرقی نمیکنه مثلا اگر به ترتیب ۱ تا ۱۵ رو تعداد تکرارشو پیدا کنیم تو همون رابطه بازگشتی مقدار $n_1$ صفر می شود و مقدار $n_2$ بستگی به تعداد عدد جستجو در گام قبلی دارد. و روی مرتبه تاثیری ندارد ولی اگر بجای ۱۵ مقدار $\sqrt{n}$ یا $\log n$ بوداین روش تقسیم و غلبه کارایی را نسبت به ترتیب های دیگر افزایش میداد حداقل تو ضریب. ویا اگر عدد بزرگی بود این روش با توجه به پارامتر دوم (بازه) شرط پایان بهتری داشت مثل $T(7,[1..7])$ که نیاز به محاسبه نداشت و مشخص بود تعداد تکرار هر عدد از ۱ تا ۷ برابر یک است در واقع طراح با توجه به وقت کنکور مسئله رو با ثابت کردن تعداد اعداد متمایز ساده کرده و هدف درک استفاده از جستجویی دودویی در یافتن تعداد تکرار اعداد است.

خیلیییییی مرسیییییی

(۲۹ فروردین ۱۳۹۶ ۰۷:۵۴ ب.ظ)alimamala نوشته شده توسط:  با عرض سلام
دوستان یه راهنمایی در مورد سوال زیر می فرمایید لطفا ؟
با سپاس و قدر دانی

اگه میشه پاسخشو بذارید....

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

(۳۰ فروردین ۱۳۹۶ ۰۸:۳۵ ق.ظ)*tarannom* نوشته شده توسط:  گزینشو بذارید کافیه نمیخواد عکس بگیرید همونوقت میخوام ببینم راه حلم درسته یا نه.

چشم، حتما از این به بعد جواب رو هم می ذارم ان شاالله