تو سوال گفته حداقل تعداد مقایسه ها نگفته حداکثر اگر می گفت حداکثر میشد n-1
ولی با استدلال زیر n/2 میشه
اگر فرض کنیم تعداد کل گوی ها ۲N+1 باشه n تا منفی و N+1 تا مثبت هست روش کار به این صورت هست که اولین عنصر رو میگیرم و تک تک با تمام عناصر مقایسه میکنیم اگر دفع بشه جزء گروه موافقه ولی اگر جذب بشه گروه مخالف
حالا بهترین حالت برای زمانی هست که n/2 عنصری که اول با آنها مقایسه می شود همگی مربوط به یک گروه باشند که در اینصورت نیازی به مقایسه با بقیه n/2 عناصر که اونها هم جزء دسته دیگری هستند نیست
(۲۳ بهمن ۱۳۹۱ ۰۲:۱۸ ق.ظ)k_111 نوشته شده توسط: تو سوال گفته حداقل تعداد مقایسه ها نگفته حداکثر اگر می گفت حداکثر میشد n-1
ولی با استدلال زیر n/2 میشه
اگر فرض کنیم تعداد کل گوی ها ۲N+1 باشه n تا منفی و N+1 تا مثبت هست روش کار به این صورت هست که اولین عنصر رو میگیرم و تک تک با تمام عناصر مقایسه میکنیم اگر دفع بشه جزء گروه موافقه ولی اگر جذب بشه گروه مخالف
حالا بهترین حالت برای زمانی هست که n/2 عنصری که اول با آنها مقایسه می شود همگی مربوط به یک گروه باشند که در اینصورت نیازی به مقایسه با بقیه n/2 عناصر که اونها هم جزء دسته دیگری هستند نیست
خیلی جالبه بچه ها میان نظر میدن بدون اینکه به خودشون زحمت بدن یکی از کامنتای قبلی رو بخونن.
عزیز کجای سوال گفته n+1 مثبت و n تا منفی. در کامنتای قبلی هم توضیح داده شده که تعداد مثبت زوج و منفی فرده. پس می تونه تمام گویها منفی باشه. یعنی برای ۵ حتما لازم نیست ۲و۳ باشه می تونه ۴و۱ یا ۵و۰ باشه.
لطفا قبل کامنت نوشتن یه نگاهی هم به کامنتای قبلی بندازین.
(۲۳ بهمن ۱۳۹۱ ۰۲:۱۸ ق.ظ)k_111 نوشته شده توسط: تو سوال گفته حداقل تعداد مقایسه ها نگفته حداکثر اگر می گفت حداکثر میشد n-1خیلی دلم میخواد چیزی که شما میگی درست باشه چون خودم n/2 زدم ولی نمیشه، چون نمیتونیم این پیش فرض تقسیم گوی ها به n منفی و n+1 تا مثبت بپذیریم ما فقط میدونیم تعداد گوی های مثبت زوج است و درهمین مثال خودتون هر عددی از صفر تا ۲n می تونه باشه پس نمیشه آزمایشو تا نیمه انجام داد.
ولی با استدلال زیر n/2 میشه
اگر فرض کنیم تعداد کل گوی ها ۲N+1 باشه n تا منفی و N+1 تا مثبت هست روش کار به این صورت هست که اولین عنصر رو میگیرم و تک تک با تمام عناصر مقایسه میکنیم اگر دفع بشه جزء گروه موافقه ولی اگر جذب بشه گروه مخالف
حالا بهترین حالت برای زمانی هست که n/2 عنصری که اول با آنها مقایسه می شود همگی مربوط به یک گروه باشند که در اینصورت نیازی به مقایسه با بقیه n/2 عناصر که اونها هم جزء دسته دیگری هستند نیست
بچه ها به یه موضوعی اگر دقت کنید اینه که گفته دست کم ، این یعنی خوشبینانه ترین حالت ممکن رو باید در نظر بگیریم ، اگر هر دوتایی که برمیداریم همدیگرو دفع کنند تقریبا با تست کردن نصف گوی ها میشه به نتیجه رسید، من فکر میکنم n/2 درست باشه . با توجه به اینکه گفته دست کم خیلی بعید به نظر میرسه گزینه n-1 صحیح باشه، یعنی اگر دستی هم چند تا نمونه تست کنید همین نتیجه رو میده
البته باز هم باید منتظر کلید سنجش بود
من هم n-1 زدم. اما چون برای بعضی حالات n/2 میشه و گفته دست کم همون n/2 درسته!!!
متاسفانه سر امتحان موقع تحلیل خوب بودم اما موقع انتخاب گزینه ...
یه سوال رو سر نیست و است اشتباه کردم...
خدایـــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــا....
من برای این تست n-1 زدم نمیدونم چند درصد این گزینه درسته.
اما یه چیزی که در پستهای دوستان ندیدم (یا شاید دقت نکردم) این بود که سوال گفته مثبت‌ها زوج است. از یک سری گوی‌های سه‌تایی ممکنه هیچ‌کدامشون مثبت نباشند (صفر مثبت) ==> باید همچنان برای سه گوی دو مقایسه را دست کم انجام داد تا قطعی بتوان گفت مثبت است یا منفی. در تحلیل بدترین حالت، دو گوی از سه گوی را برمیداریم و به هم نزدیک میکنیم و همدیگر را دفع میکنند. نیمشه نتیجه گرفت آیا مثبت است یا منفی (فقط میدانیم این دو همنام‌ند) یکی از این دو را با گوی سوم آزمایش میکنیم، همدیگر را دفع کردند پس نتیجه میگیریم همه‌ی گویها منفی هستند و صفر مثبت وجود دارد. اما اگر در آزمایش دوم همدیگر را جذب کردند نتیجه میگیریم دو گوی آزمایش اول مثبت بودند و یک منفی وجود دارد.
این آزمایش برای سه نمونه بود... ولی ممکنه کلید تست چز دیگری باشه.
سوال ۴۲ هم از الگوریتم میانه گیری حل میشه. برای مورد ب فکر میکنم رابطه بازگشتی‌اش مشابه این باشه: [tex]T(n)=T(\frac{n}{2}) n[/tex]
(۲۳ بهمن ۱۳۹۱ ۰۱:۰۲ ب.ظ)mohammad-a نوشته شده توسط: من برای این تست n-1 زدم نمیدونم چند درصد این گزینه درسته.پس دقیقا همون میشه ، در بهترین حالت با n/2 مقایسه میتونیم گوی ها رو به دو گروه تقسیم کنیم و چون گفته مثبت ها زوج هستند و تعداد کل رو هم گفته که فرد هست پس میشه به راحتی نتیجه گرفت گروهی که تعدادش زوجه مثبت و گروهی که تعدادش فرده منفی میشه.
اما یه چیزی که در پستهای دوستان ندیدم (یا شاید دقت نکردم) این بود که سوال گفته مثبت‌ها زوج است.
نقل قول: در تحلیل بدترین حالت، دو گوی از سه گوی را برمیداریم و به هم نزدیک میکنیم و همدیگر را دفع میکنند. نیمشه نتیجه گرفت آیا مثبت است یا منفی (فقط میدانیم این دو همنام‌ند) یکی از این دو را با گوی سوم آزمایش میکنیم، همدیگر را دفع کردند پس نتیجه میگیریم همه‌ی گویها منفی هستند و صفر مثبت وجود دارد. اما اگر در آزمایش دوم همدیگر را جذب کردند نتیجه میگیریم دو گوی آزمایش اول مثبت بودند و یک منفی وجود دارد.به نظر من وقتی میگه دست کم یا بهترین حالت دیگه لزومی نداره بدترین حالت یا حالت های معمول رو چک کرد ، مسئله رو باید در بهترین حالت ممکن چک کرد تا کمترین تعداد مقایسه بدست بیاد. بهترین حالت ممکن هم اینه که نصف گوی ها رو که برمیداریم همگی همدیگر رو دفع کنند پس شاید در حالت عادی بگیم اگر دفع کرد اینطوری میشه اگر دفع نکرد اون طوری! ولی در بهترین حالت فقط یک حالت داریم اونم اینکه تا نصفه گوی ها همه همدیگرو دفع کنند.
(۲۳ بهمن ۱۳۹۱ ۰۱:۰۲ ب.ظ)mohammad-a نوشته شده توسط: من برای این تست n-1 زدم نمیدونم چند درصد این گزینه درسته.
اما یه چیزی که در پستهای دوستان ندیدم (یا شاید دقت نکردم) این بود که سوال گفته مثبت‌ها زوج است. از یک سری گوی‌های سه‌تایی ممکنه هیچ‌کدامشون مثبت نباشند (صفر مثبت) ==> باید همچنان برای سه گوی دو مقایسه را دست کم انجام داد تا قطعی بتوان گفت مثبت است یا منفی. در تحلیل بدترین حالت، دو گوی از سه گوی را برمیداریم و به هم نزدیک میکنیم و همدیگر را دفع میکنند. نیمشه نتیجه گرفت آیا مثبت است یا منفی (فقط میدانیم این دو همنام‌ند) یکی از این دو را با گوی سوم آزمایش میکنیم، همدیگر را دفع کردند پس نتیجه میگیریم همه‌ی گویها منفی هستند و صفر مثبت وجود دارد. اما اگر در آزمایش دوم همدیگر را جذب کردند نتیجه میگیریم دو گوی آزمایش اول مثبت بودند و یک منفی وجود دارد.
این آزمایش برای سه نمونه بود... ولی ممکنه کلید تست چز دیگری باشه.
سوال ۴۲ هم از الگوریتم میانه گیری حل میشه. برای مورد ب فکر میکنم رابطه بازگشتی‌اش مشابه این باشه: [tex]T(n)=T(\frac{n}{2}) n[/tex]
سه پست قبلی بحث شده بود. بازم با این همه دلیل دوستان می گند میشه n/2. بابا یه تست کنیم با این حرفایی که دوستان می زنند ما که برای هر مثالی شما بگید n-1 در میاریم. جالبه فقط هی می نویسن دست کم خوشبینانه؟!!!!!!!!!
دوستان لطفا در مورد ۳۹ کسی نظری نداره l
(۲۳ بهمن ۱۳۹۱ ۰۱:۳۴ ب.ظ)mohammad-a نوشته شده توسط: من البته با توجه به تجربه سال گذشته علاقه ندارم زیاد وارد بحث درباره‌ی سوالات بشم.دست کم یعنی حداقل تعداد مقایسه ، اینطور نیست؟! حداقل تعداد مقایسه هم یعنی خوشبینانه ترین حالت که ممکنه اصلا هم اتفاق نیفته ولی بهرحال خوشبینانه ترین حالت ،حتی اگر احتمال اتفاق افتادنش خیلی خیلی کم باشه. آخه دوست عزیز جواب کلی رو که نخواسته حتی متوسط هم نخواسته گفته دست کم چه تعدادی عمل مقایسه ضروریه.
ولی شما یک چیزی نوشتید، نوشتید در بهترین حالت... شاید تحلیل شما درست باشه، اما به نظرم ازعبارت "دست کم" نمیشه این برداشت رو داشت که ما میتونیم در بهترین حالت تحلیل کنیم. گزینه مربوط به شما به نظرم میتونه در بهترین حالت این نتیجه رو داشته باشه که بله اما این بهترین حالت بود. .
در بدترین حالت نمیشه این نتیجه‌گیری رو بسط داد. (یک مسأله وقتیکه جواب کلی رو خواسته نمیشه فرض بهترین حالت رو داشت... مثلا بهترین حالت مرتب‌سازی یک فاصله ضریب nتایی هست، میشه این رو همیشه نتیجه گرفت؟)
نقل قول: مثلاً ما ۱۰۰۱ گوی داریم که ۵۰۰ تای اینها مثبت هستند و ۵۰۱ عدد دیگه منفی، و به دو دسته N/2 تقسیم کردیم. در نهایت میشه گفت با n/2+1 مقایسه میتونیم در این وضعیتی که بهترین حالت معرفی شد، جواب رو پیدا کنیمچرا +۱ ؟ وقتی تعداد زوج و فرد مشخص شده از طریق تعدادشون میشه بارش رو مشخص کرد اصلا نیازی به مقایسه اضافی نیست
نقل قول: یک فرض دیگه هم باید در نظر بگیریم. برای همین مورد، وقتیکه به ۵۰۰ گروه دوتایی تقسیم کردیم، این فرض رو هم در نظر گرفتیم که در هر گروه یک مثبت و یک منفی هست درحالیکه ما اصلا اطلاعی درباره بار گویها نداریم و صرفا با مقایسه میخواهیم این رو پیدا کنیم. بیشتر که فکر میکنم حتی در همین مثال هم نمیشه با N/2 مقایسه به طور دقیق گفت چه گویهایی مثبت و چه گوی هایی منفی هستنداون کلمه دست کم خیلی تعیید کنندست از نظر من ، فکر میکنم اختلاف نظر ما به خاطر همین باشه که از نظر شما اون کلمه اهمیتی نداره ، در صورت مسئله گفته شده n فرد است پس نمیشه ۵۰۰ در نظرش بگیریم ولی اگر مثلا ۵۰۱ هم در نظر گرفته بشه و شما ۲۵۰ تا گوی رو دوتا ، دوتا مقایسه کنید و همدیگر رو دفع کنند(باتوجه به اینکه داریم حداقل حالات ممکن رو در نظر میگیریم) و از اونجاییکه تعداد گوی های با بار مثبت زوج هستند این ۲۵۰ گوی بارشون مثبت است و ۲۵۱ باقیمانده بارشون منفی (اگر برعکس باشه باید تو مقایسه n ام اون دوتا همدیگر رو جذب کنند که باز هم اینجا بین این دو ایدهآل ترین رو در نظر میگیریم) من سر جلسه این گزینه رو با شک انتخاب کردم ولی الان تقریبا مطمئنم، به نظر خیلی روشن و واضحه حالا اگر کلید سنجش چیز دیگه ای باشه باید دید علت چیه.
(۲۳ بهمن ۱۳۹۱ ۰۳:۳۰ ب.ظ)mohammad-a نوشته شده توسط: به هر حال، این نظر بنده بود. در بالا هم عرض کردم که ۱۰۰۱ گوی در نظر بگیرید (نقضی در صورت مساله نیست)آره بیخیال من که قبولیم با یکی دو تا سئوال حل نمیشه ایشاله جواب شما درست باشه به کارتون بیاد ولی کل سئوالات کنکور یه طرف این یه دونه سئوال یه طرف! این یکی از باحالترین و در عین حال مزخرفترین سئوال هایی بود که تو زندگیم دیدم همین که انقدر چالش ایجاد کرده خیلی جالبه به نظر من بیشتر سئوال هوش بود تا ساختمان داده!
بیخیال یه مدت از این کنکور لعنتی دور بشیم بهتره.
یعنی کلیدا که بیاد اول از همه میرم سراغ جواب این! 
سلام عزیزان
در مورد سوال ۴۴ باید بگم که قبلا سوال المپیاد بوده و جوابش n-1 هست.
اینو تو اینترنت دیدم گفتم بزارم واستون.
n تا گوی باردار داریم که بار آنها را نمی‌دانیم. در هر مرحله می‌توانیم دو گوی را به هم نزدیک کنیم و تشخیص دهیم که آیا بار آنها یکسان می‌باشد یا نه.
اگر n فرد باشد و زوجیت تعداد بارهای منفی را بدانیم، n-1 بار مقایسه‌ی گلوله‌ها برای تشخیص بار گویها لازم و کافی است
با سلام
توضیحاتی راجع به سوال ۴۷ ساختمان و الگوریتم آی تی
با توجه به توضیحاتی که دکتر قدسی دادن قضیه به این صورته
۱-اگه عنصری بخواد در عمق یک قرار بگیره و طول کد نویسه اش به طول یک باشه باید فراوانیش بیشتر از ۲/۵ باشه ولی عکس این قضیه لزوماً برقرار نیست. یعنی اگه عنصری فراوانیش بیشتر از ۲/۵ باشه لزوماً در عمق ۱ قرار نمی گیره.
مثالش رو سهیل جان اوردن
رشته ای به طول ۱۰۰
۴۱ کاراکتر A
۴۱ کاراکتر B
۱۸ کاراکتر C
A و B فراوانیشون هر دو از ۲/۵ بیشتره ولی یکیشون ۱ بیت میشه یکی دیگه ۲ بیت!
۲- اگه فراوانی همه عناصر کمتر از ۱/۳ باشه هیچ عنصری تو عمق یک قرار نمیگیره و عنصری با طول کد یک نویسه ای نخواهیم داشت و همگی بیش از ۱ خواهند بود.
پس قسمت اول نادرست و قسمت دوم درست خواهد بود که گزینه ۴ جواب صحیحه.
بچه ها یکی لطف کنه بگه سوال ۴۰ توی دفترچه B ترتیب گزینه هاش مثل همین دفترچه D هست؟؟؟؟؟؟؟؟؟؟
راستی پس باقی سوالا چی حلشون نصفه موند؟؟؟؟؟؟؟؟؟؟؟؟؟
در مورد سوال ۴۵ باید توجه کنید که زیردنباله ی [متوالی] خواسته شده و این با مسائل مشابهی که قبلا دیدین مثل طولانی ترین زیردنباله صعودی فرق می کنه.
این مسئله longest increasing contiguous sub-sequence هست.
الگوریتم برای این مسئله از تتای n هست. البته تتای logn هم حافظه مصرف میکنه. یعنی گزینه ۴ صحیحه. توضیحات بیشتر رو میتونید در لینک زیر پیدا کنید.
کتاب how to think about algorithms صفحه ۲۲۳-۲۲۴ فصل ۱۶ (برنامه ریزی پویا)
لینک کتاب :
مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.