(۲۰ دى ۱۳۹۰ ۰۲:۳۱ ب.ظ)vijay نوشته شده توسط:  
گزینه درست ۲nشده حداکثر مقایسه برای پیدا کردن xچون در صورت وجود گفته nهست ضریب ۲ برای چی؟؟؟؟

ماتریس زیرو فرض کن. که تقریبا به اون ترتیبی که گفته مرتب شده.

۴۰ ۳۰ ۲۰ ۱۰
۴۱ ۳۱ ۲۱ ۱۱
۴۲ ۳۲ ۲۲ ۱۲
۴۳ ۳۳ ۲۳ ۱۳

میخوایم عدد ۴۳ پیدا کنیم که حداکثر مقایسه هست.
با n=4 مقایسه در سطر میفهمیم در سطر آخره و با n=4 مقایسه در ستون میفهمیم در ستون آخره.
پس کلا شد n+n=2n

یعنی الگورریتم ما عدد xرا بااعداد اول و آخر هرسطر مقایسه میکنه بین آنها نبود میره سطر بعد همینطور تا آخر.بعد اگه در سطری با این روش پیدا شد میره سراغ ستونش که همون nتا ستون میشه حداکثر و میشه ۲n.
استدلال من اینه از جواب شما دوست عزیز درسته؟؟؟

(۲۰ دى ۱۳۹۰ ۰۷:۱۳ ب.ظ)vijay نوشته شده توسط:  یعنی الگورریتم ما عدد xرا بااعداد اول و آخر هرسطر مقایسه میکنه بین آنها نبود میره سطر بعد همینطور تا آخر.بعد اگه در سطری با این روش پیدا شد میره سراغ ستونش که همون nتا ستون میشه حداکثر و میشه ۲n.
استدلال من اینه از جواب شما دوست عزیز درسته؟؟؟

در این مثال ابتدا میاد سطر اولو میبینه و با تک تکشون مقایسه میکنه. میبینه که ۴۳ از ۴۰ هم بزرگتره پس میفهمه جواب تو ستون آخره. اینکارو حداکثر با n=4 مقایسه انجام داد.
حالا میاد تو ستون آخر مقایسه رو انجام میده و میبینه جواب تو سطر آخره که میتونه حداکثر با n=4 مقایسه پیدا کنه.
پس در کل با n=2n مقایسه جواب پیدا میشه.
مثلا برای پیدا کردن ۳۲ بعد از مقایسه در سطر اول میفهمه که ۳۲ کوچکتر از ۴۰ هست و جواب در ستون سوم قرار داره و فقط این ستونو میگرده و ...

البته بدترین حالت به صورت زیر هست:
۰۴ ۰۳ ۰۲ ۰۱
۰۸ ۰۷ ۰۶ ۰۵
۱۲ ۱۱ ۱۰ ۰۹
۱۶ ۱۵ ۱۴ ۱۳

حالا فرض کنید که می‌خوایم ۱۵ رو پیدا کنیم.
الگوریتم درست توی این مساله به صورت اریب حرکت می‌کنه. اگه گفتین چه شکلی؟
با الگوریتم قبلی ۳n زمان می‌بره!

(۲۰ دى ۱۳۹۰ ۰۸:۵۵ ب.ظ)admin نوشته شده توسط:  البته بدترین حالت به صورت زیر هست:
۰۴ ۰۳ ۰۲ ۰۱
۰۸ ۰۷ ۰۶ ۰۵
۱۲ ۱۱ ۱۰ ۰۹
۱۶ ۱۵ ۱۴ ۱۳

حالا فرض کنید که می‌خوایم ۱۵ رو پیدا کنیم.
الگوریتم درست توی این مساله به صورت اریب حرکت می‌کنه. اگه گفتین چه شکلی؟
با الگوریتم قبلی ۳n زمان می‌بره!

اگه تو ماتریس شما اول ستونو بگرده بعد سطرو باز جواب کمتر از ۲n میشه.

روش مرتب سازی ماتریس شما فرق میکنه با روش مرتب سازی شده در ماتریس من.
در ماتریس که من نوشتم ستونها رو برحسب دهگانی که دارن متمایز کرده و سطرها رو بر حسب یکانی که دارن متمایز کرده. ولی در ماتریس شما چون این ترتیب وجود نداره این حالت پیش اومده.
میتونیم الگوریتمی جوری بنویسیم که طبق روش مرتب سازی ما ماترسیو جستجو کنه. و مثلا اگر مثله ماتریس شما نشه ستونها رو بر حسب دهگان متمایز کرد و اعداد شبیه هم در دهگان بوجود بیاد اونوقت اول ستونها رو جستجو کنه.

همون روش قبلی که گفتیم ولی این بار فکر کنم یه برگشت به عقب داریم یعنی از۱۶ به ۱۳

(۲۰ دى ۱۳۹۰ ۰۹:۲۹ ب.ظ)sasanlive نوشته شده توسط:  روش مرتب سازی ماتریس شما فرق میکنه با روش مرتب سازی شده در ماتریس من.
در ماتریس که من نوشتم ستونها رو برحسب دهگانی که دارن متمایز کرده و سطرها رو بر حسب یکانی که دارن متمایز کرده. ولی در ماتریس شما چون این ترتیب وجود نداره این حالت پیش اومده.
میتونیم الگوریتمی جوری بنویسیم که طبق روش مرتب سازی ما ماترسیو جستجو کنه. و مثلا اگر مثله ماتریس شما نشه ستونها رو بر حسب دهگان متمایز کرد و اعداد شبیه هم در دهگان بوجود بیاد اونوقت اول ستونها رو جستجو کنه.

خوب چطوری می‌نویسی آخر سر؟ اول ستون یا اول سطر؟ الگوریتم شما در بدترین شرایط پیچیدگیش ۳n-1 است.
چطوری می‌خوای بفهمی که شکل ماتریس چجوریه؟
الگوریتم دقیق اینطوریه:
به صورت اریب از بالا شروع می‌کنیم به مقایسه. اگه برابر بود که حله اگه نبود چی؟ اولین مقدار بیشتر از x این کار رو می‌کنیم: همه ستون‌های بالای اون جا و سطهای سمت چپش رو بررسی می‌کنیم.
پیچیدگی الگوریتم: حداکثر به اندازه قطر ماتریس که می‌شه n + تعداد اعداد ستون بالای اون مکان + تعداد اعداد سطر چپش که در مجموع این تعداد برابر n + n می‌شه

(۲۰ دى ۱۳۹۰ ۰۹:۴۹ ب.ظ)admin نوشته شده توسط:  خوب چطوری می‌نویسی آخر سر؟ اول ستون یا اول سطر؟ الگوریتم شما در بدترین شرایط پیچیدگیش ۳n-1 است.
چطوری می‌خوای بفهمی که شکل ماتریس چجوریه؟
الگوریتم دقیق اینطوریه:
به صورت اریب از بالا شروع می‌کنیم به مقایسه. اگه برابر بود که حله اگه نبود چی؟ اولین مقدار بیشتر از x این کار رو می‌کنیم: همه ستون‌های بالای اون جا و سطهای سمت چپش رو بررسی می‌کنیم.
پیچیدگی الگوریتم: حداکثر به اندازه قطر ماتریس که می‌شه n + تعداد اعداد ستون بالای اون مکان + تعداد اعداد سطر چپش که در مجموع این تعداد برابر n + n می‌شه

الگوریتم مرتب سازی به شکل بهینه نوشته میشه.
ما زمان جستجو رو تو این مسئله میخوایم.
شما ماتریسو فقط پشت سره هم نوشتین و الگوریتم مرتب سازی خاصی روش پیاده سازی نشده. باید هم در ستون و هم در سطر الگوریتمی برای مرتب سازی نوشته شده باشه. چون مسئله گفته هم در ستون و هم در سطر مرتب سازی صورت گرفته.

اگه میشه با اعداد در ماتریسه خودتون یا من روند جستجوتونو شرح بدین تا ما متوجه بشیم به چه شکلی الگوریتم شما جستجو میکنه.

(۲۰ دى ۱۳۹۰ ۱۰:۱۵ ب.ظ)sasanlive نوشته شده توسط:  باید هم در ستون و هم در سطر الگوریتمی برای مرتب سازی نوشته شده باشه.

الان که دوباره جواب خودم رو دیدم فهمیدم یه مشکلی هست توش. مثلا برای پیدا کردن ۴ جواب نمی‌ده.
مساله خیلی جالب شد ماتریس زیر رو در نظر بگیرید:
۰۴ ۰۳ ۰۲ ۰۱
۱۳ ۱۰ ۰۶ ۰۲
۱۵ ۱۱ ۱۰ ۰۳
۱۶ ۱۵ ۱۴ ۰۴

حالا فرض کنید که می‌خواید ۱۴ رو پیدا کنید. چطوری پیدا می‌کنید؟
الگوریتم برای ۱۱ چطوری جواب می‌ده؟
برای یافتن ۱۲ چه کار می‌کنید؟

فکر کنم از جستجوی باینری باید یه بهره‌ای ببریم

(۲۰ دى ۱۳۹۰ ۱۰:۲۸ ب.ظ)admin نوشته شده توسط:  ماتریس من هم تو سطر و هم تو ستون مرتبه.

نمیگم مرتب نیست.
میگم از ابتدا روش الگوریتم مرتب سازی خاصی بکار برده نشده و چون پشت سره هم نوشتین مرتبه.
در سوال گفته سطر و ستون مرتب شدن یعنی بر اساس یه الگوریتمی. شما بر چه اساسی سطرو جدا و ستونو جدا مرتب کردین؟

---

(۲۰ دى ۱۳۹۰ ۱۰:۲۸ ب.ظ)admin نوشته شده توسط:  الگوریتم دقیق اینطوریه:
به صورت اریب(قطری) از بالا شروع می‌کنیم به مقایسه. اگه برابر بود که حله اگه نبود چی؟ اولین مقدار بیشتر از x این کار رو می‌کنیم: همه ستون‌های بالای اون جا و سطهای سمت چپش رو بررسی می‌کنیم.
پیچیدگی الگوریتم: حداکثر به اندازه قطر ماتریس که می‌شه n + تعداد اعداد ستون بالای اون مکان + تعداد اعداد سطر چپش که در مجموع این تعداد برابر n + n می‌شه

اگه میشه با عدد شرح بدین من فکر میکنم الگوریتم جستجوتون ایراد داره.
لطف کنین با عدد در ماتریس خودتون یا من روش جستجو رو توضیح بدین.

نمیشه با مقایسه آخرین عنصر هر سطر، ابتدا هر سطر را پیدا کنیم (همان مرتبه n) و بعد که سر پیدا شد با مرتبه Logn عنصر مورد نظر را پیدا کنیم. اسم این جستجویی که Logn بود یادم رفت.

البته برای جستجو سطر بالا و ستون چپ باید از روش‌های باینری استفاده کنید.

(۲۰ دى ۱۳۹۰ ۱۰:۱۵ ب.ظ)sasanlive نوشته شده توسط:  شما ماتریسو فقط پشت سره هم نوشتین و الگوریتم مرتب سازی خاصی روش پیاده سازی نشده. باید هم در ستون و هم در سطر الگوریتمی برای مرتب سازی نوشته شده باشه. چون مسئله گفته هم در ستون و هم در سطر مرتب سازی صورت گرفته.

ماتریس‌های مثال من هر دو تا هم در سطر و هم در ستون مرتب هستند

(۲۰ دى ۱۳۹۰ ۱۰:۵۵ ب.ظ)admin نوشته شده توسط:  ماتریس‌های مثال من هر دو تا هم در سطر و هم در ستون مرتب هستند

میدونم مرتب هستن ولی وقتی یه تعداد عدد میدن بدون ترتیب خاص الگوریتم مرتب سازی اول سطرو جدا و ستونو جدا بر اساس الگوریتم خاصی مرتب میکنه.و فرض میکنیم اعدادو به شکلی در ماتریس مرتب میکنه که جستجوی ما بهینه بشه و بعد حداکثر زمان جستجو رو توش پیدا میکنیم.ولی شما فقط اعدادو معمولی مرتب کردین و بصورت ترتیبی در ماتریس قرار دادین. مرتب میشه ولی جستجو رو بهینه نمیکنه.

هنوز مثال عددی نزدین. من هر چی از روش شما میرم به حالتهای نقض برمیخورم.

(۲۰ دى ۱۳۹۰ ۱۰:۳۵ ب.ظ)pos نوشته شده توسط:  نمیشه با مقایسه آخرین عنصر هر سطر، ابتدا هر سطر را پیدا کنیم (همان مرتبه n) و بعد که سر پیدا شد با مرتبه Logn عنصر مورد نظر را پیدا کنیم. اسم این جستجویی که Logn بود یادم رفت.

نه
مثال:
۰۴ ۰۳ ۰۲ ۰۱
۱۳ ۱۰ ۰۶ ۰۲
۱۵ ۱۱ ۱۰ ۰۳
۱۶ ۱۵ ۱۴ ۰۴

حالا فرض کنید که می‌خواید ۱۴ رو پیدا کنید. چطوری پیدا می‌کنید؟
الگوریتم برای ۱۱ چطوری جواب می‌ده؟
برای یافتن ۱۲ چه کار می‌کنید؟

فکر کنم از جستجوی باینری باید یه بهره‌ای ببریم

خوب اگه منظور شما اینه که فقط دستمون تو جستجو بازه و نمیدونیم با چه روشی ماتریس مرتب هست میشه از یه روش جستجوی دیگه استفاده کرد.


اول x رو با قطر اصلی ماتریس مقایسه میکنیم.
اگه با یکی از اعداد روی قطر برابر بود که تمومه.
اگه روی قطر اصلی به عددی رسیدیم که از x بزرگتره به عدد قبلی روی قطر اصلی ماتریس برمیگردیم.حالا عدد روی قطر اصلی رو با عدد سمت راستش مقایسه میکنیم. دو حالت پیش میاد:
۱-اگه عدد سمت راست از x کوچکتر بود ادامه ماتریسو به شکل سطری میگردیم تا x پیدا بشه.که اینکارو با اصافه کردن اندیس به i,j انجام میدیم.
۲-اگه عدد سمت راست از x بزرگتر بود ادامه ماتریسو به شکل ستونی میگردیم تا x پیدا بشه.که اینکارو با اصافه کردن اندیس به i,j انجام میدیم.

عدد ۱۴ رو در دو ماتریس خودم و شما پیدا میکنم.

در ماتریس شما به شکل سطری پر شده:

۰۴ ۰۳ ۰۲ ۰۱
۰۸ ۰۷ ۰۶ ۰۵
۱۲ ۱۱ ۱۰ ۰۹
۱۶ ۱۵ ۱۴ ۱۳

ترتیب مقایسه: با ۱ سپس با ۶ سپس با ۱۱ سپس با ۱۶ حالا x کوچکتر از ۱۶ هست به ۱۱ برمیگردم و با سمت راستش که ۱۲ مقایسه میکنم.چون x بزرگتر از ۱۲ بقیه مقایسه به شکل سطری انجام میدم که اینکارو با اضافه کردن اندیسها انجام میدیم . میشه ۱۲ بعد ۱۳ بعد ۱۴ که مقدار بدست اومده با کمتر از ۲n بدست اومد.


در ماتریس خودم که به شکل ستونی پر شده:

۱۳ ۹ ۵ ۱
۱۴ ۱۰ ۶ ۲
۱۵ ۱۱ ۷ ۳
۱۶ ۱۲ ۸ ۴

ترتیب مقایسه: با ۱ سپس با ۶ سپس با ۱۱ سپس با ۱۶ حالا x کوچکتر از ۱۶ هست به ۱۱ برمیگردم با سمت راستش مقایسه میکنم. عدد ۱۵ هست که از x بزرگتره پس بقیه جستجو رو به شکل ستونی ادامه میدم تا x پیدا بشه که اینکارو با اضافه کردن اندیسها انجام میدیم. میشه ۱۲ بعد ۱۳ بعد ۱۴ که مقداره x در زمان کمتر از ۲n بدست اومده.


همینطور در ماتریس جدیدتون با اعداد یکسان هم جواب میده.
۰۱ ۰۱ ۰۱ ۰۱
۰۱ ۰۱ ۰۱ ۰۱
۰۴ ۰۱ ۰۱ ۰۱
۰۵ ۰۱ ۰۱ ۰۱


البته این روش جستجو به شرطی برقراره که ماتریس بعد از مرتب سازی طبق قواعد پر شدن ماتریسها , به روش سطری یا ستونی پر شده باشه.
.

(۲۰ دى ۱۳۹۰ ۱۱:۰۷ ب.ظ)sasanlive نوشته شده توسط:  من هر چی از روش شما میرم به حالتهای نقض برمیخورم.

خودم که گفتم روش من غلطه. در صورتی که ماتریس مرتب کامل باشه بدیهیه که با ۲logn می‌شه حلش کرد. در واقع اگه اون‌طوری مرتب باشه فرقی با حالت مرتب ساده نداره. توی فرض مساله تنها ذکر کرده که سطرها و ستون‌ها مرتب هستند. و ماتریس مثال من با این فرض تناقضی نداره. همه سطرها مرتب و همه ستون‌ها مرتب هستند. در ضمن در فرض مساله یه چیز باحال هم نیست و اون هم یکتایی هر مقدار است.

(۲۱ دى ۱۳۹۰ ۰۲:۱۴ ق.ظ)admin نوشته شده توسط:  

(20 دى ۱۳۹۰ ۱۱:۰۷ ب.ظ)sasanlive نوشته شده توسط:  من هر چی از روش شما میرم به حالتهای نقض برمیخورم.

خودم که گفتم روش من غلطه. در صورتی که ماتریس مرتب کامل باشه بدیهیه که با ۲logn می‌شه حلش کرد. در واقع اگه اون‌طوری مرتب باشه فرقی با حالت مرتب ساده نداره. توی فرض مساله تنها ذکر کرده که سطرها و ستون‌ها مرتب هستند. و ماتریس مثال من با این فرض تناقضی نداره. همه سطرها مرتب و همه ستون‌ها مرتب هستند. در ضمن در فرض مساله یه چیز باحال هم نیست و اون هم یکتایی هر مقدار است.

اما دکتر جان من هنوز میگم روش اول من درسته و اگه جواب شما اونو نقض میکنه به این خاطره که روش پر کردن ماتریس شما با روش پر کردن ماتریس من فرق میکنه.
ما باید یه روش پر کردن ماتریسو بعد از مرتب سازی اتخاذ کنیم. یا سطری ماتریسو پر کنبم و یا ستونی پرش کنیم.
اگه شما هم بعد مرتب سازی ماتریستونو به شکل ماتریس من به صورت ستونی پر کنین به شکل زیر در میاد.

۱۳ ۹ ۵ ۱
۱۴ ۱۰ ۶ ۲
۱۵ ۱۱ ۷ ۳
۱۶ ۱۲ ۸ ۴

و حالا دوباره مثل حالت اولی که شرح دادم اول اونو به شکل سطری جستجو میکنیم و بعد به شکل ستونی.که با این روش عدد ۱۵ با کمتر از ۲n بدست میاد.

یعنی اگه اعدادو بعد از مرتب سازی معمولی به شکل ستون به ستون وارد ماتریس کردیم , اول اونو به شکل سطری جستجو میکنیم.
واگه بعد از مرتب سازی اونو به شکل سطر به سطر وارد ماتریس کردیم اول اونو به شکل ستونی جستجو میکنیم.
یعنی یه سیاست پر کردن ماتریس رو بعد از مرتب سازی به شکل ثابت انتخاب میکنیم. و همیشه ماتریسو به همون شکل پر میکنیم. اونوقت دیگه یه روش جستجو رو هم بعد از اتخاذ سیاست پر کردن ماتریس به شکل ثابت در نظر میگیریم.

(۲۱ دى ۱۳۹۰ ۰۹:۴۵ ق.ظ)sasanlive نوشته شده توسط:  اگه شما هم بعد مرتب سازی ماتریستونو به شکل ماتریس من به صورت ستونی پر کنین به شکل زیر در میاد.

اگه ماتریس رو بخوایم خودمون پر کنیم پیچیدگی ار درجه n^2 می‌شه. لطفاً به فرض مساله دقت کنید. ما فقط می‌دونیم که سطرها و ستون‌ها مرتب هستند. ما مرتب سازی رو انجام نمی‌دیم که بتونیم شیوه مرتب کردن رو تعیین کنیم.
در صورتی که مرتبسازی به شکلی که شما می‌گین باشه که الگوریتم بهتر وجود داره (۲logn).

ماتریس زیر رو در نظر بگیر به روش خودت مرتب شده)
۰۱ ۰۱ ۰۱ ۰۱
۰۱ ۰۱ ۰۱ ۰۱
۰۴ ۰۱ ۰۱ ۰۱
۰۵ ۰۱ ۰۱ ۰۱

حالا فرض کن که می‌خوایم ۴ رو پیدا کنیم. الگوریتم شما تو چه زمانی جواب می‌ده؟

تو این ماتریس
۰۴ ۰۳ ۰۲ ۰۱
۱۳ ۱۰ ۰۶ ۰۲
۱۵ ۱۱ ۱۰ ۰۳
۱۶ ۱۵ ۱۴ ۰۴

۱۳ رو چطوری پیدا می‌کنه؟

(۲۱ دى ۱۳۹۰ ۰۷:۱۵ ب.ظ)admin نوشته شده توسط:  تو این ماتریس
۰۴ ۰۳ ۰۲ ۰۱
۱۳ ۱۰ ۰۶ ۰۲
۱۵ ۱۱ ۱۰ ۰۳
۱۶ ۱۵ ۱۴ ۰۴

۱۳ رو چطوری پیدا می‌کنه؟

گفتم اخرش که در صورتی درسته که از قانون پر شدن ماتریسها پیروی کنه یعنی یا ستونی یا سطری.

بعد از اینکه اعداد مرتب سازی میشن یا به شکل سطری در ماتریس قرار میگیرن یا ستونی. حالت دیگه ای نمیشه پر کرد.
ماتریس شما نه سطری پر شده نه ستونی.
اعداد بعد از مرتب سازی به شکل زیر در میان.
۱,۲,۲,۳,۳,۴,۴,۶,۱۰,۱۰,۱۱,۱۳,۱۴,۱۵,۱۵,۱۶

و مثلا سطری به شکل زیر وارد ماتریس میشه.
۰۳ ۰۲ ۰۲ ۰۱
۰۶ ۰۴ ۰۴ ۰۳
۱۳ ۱۱ ۱۰ ۱۰
۱۶ ۱۵ ۱۵ ۱۴

ستونی هم رسم کنین جواب بدست میاد.

وبه اون شکلی که شما وارد ماتریس کردین نه سطری نه ستونی.
درون ماتریس که مرتب سازی انجام نمیشه. بیرون ماتریس انجام میشه بعد به شکل سطری یا ستونی وارد ماتریس میشه.

شما میاین داخل ماتریس اعدادو مرتب میکنین که این اشتباهه. باید بیرون ماتریس با یک الگوریتمی مرتب شده باشن و بعد ستونی یا سطری وارد ماتریس یشن.
تو مساله گفته از چپ به راست و از بالا به پایین به صورت غیر نزولی مرتبه یعنی بیرون ماتریس به شکل غیر نزولی و نه غیر صعودی مرتب شده و بعد به شکل سطری یا ستونی وارد ماتریس میشن.

وگرنه من هر نوع جستجویی ارایه بدم میشه نقض کرد مثلا تو شکل زیر من ۱۴ پایینو پیدا کنم شما میگی نه بالایی رو میخواستم.
۱۴ ۰۳ ۰۲ ۰۱
۱۵ ۰۸ ۰۷ ۰۶
۱۶ ۱۲ ۱۱ ۱۰
۱۷ ۱۶ ۱۵ ۱۴

میشه توضیح بدین به چه شکلی شما اعدادو مرتب کردین. داخل ماتریس و بصورت دستی مرتب کردین؟
و اگه بیرون ماتریس مرتب کردین با چه اصول و یا الگوریتمی میشه به این شکل اعدادو وارد ماتریس کرد؟
.

---

(۲۱ دى ۱۳۹۰ ۰۷:۳۳ ب.ظ)Ali-B نوشته شده توسط:  من که هر چی به خودم فشار آورم، نتونستم حلش کنم، آخرش رفتم جوابش تو کتاب تستم نگاه کردم و خلاص، البته تا یه جایی درست رفته بودم (جستجو روی قطر ماتریس). اگه دوست دارید جوابش بنویسم؟

اگه اونم ۲n بدست آورده اول ببین طبق حالاتی که گفتیم نقض نمیشه. اگه نشد لطف کنی عکسشو بذاری خیلی خوبه.