صفحه‌ها: ۱ ۲
(۲۰ دى ۱۳۹۰ ۱۱:۰۷ ب.ظ)sasanlive نوشته شده توسط: من هر چی از روش شما میرم به حالتهای نقض برمیخورم.خودم که گفتم روش من غلطه. در صورتی که ماتریس مرتب کامل باشه بدیهیه که با ۲logn میشه حلش کرد. در واقع اگه اون‌طوری مرتب باشه فرقی با حالت مرتب ساده نداره. توی فرض مساله تنها ذکر کرده که سطرها و ستون‌ها مرتب هستند. و ماتریس مثال من با این فرض تناقضی نداره. همه سطرها مرتب و همه ستون‌ها مرتب هستند. در ضمن در فرض مساله یه چیز باحال هم نیست و اون هم یکتایی هر مقدار است.
(۲۱ دى ۱۳۹۰ ۰۲:۱۴ ق.ظ)admin نوشته شده توسط:(20 دى ۱۳۹۰ ۱۱:۰۷ ب.ظ)sasanlive نوشته شده توسط: من هر چی از روش شما میرم به حالتهای نقض برمیخورم.خودم که گفتم روش من غلطه. در صورتی که ماتریس مرتب کامل باشه بدیهیه که با ۲logn میشه حلش کرد. در واقع اگه اون‌طوری مرتب باشه فرقی با حالت مرتب ساده نداره. توی فرض مساله تنها ذکر کرده که سطرها و ستون‌ها مرتب هستند. و ماتریس مثال من با این فرض تناقضی نداره. همه سطرها مرتب و همه ستون‌ها مرتب هستند. در ضمن در فرض مساله یه چیز باحال هم نیست و اون هم یکتایی هر مقدار است.
اما دکتر جان من هنوز میگم روش اول من درسته و اگه جواب شما اونو نقض میکنه به این خاطره که روش پر کردن ماتریس شما با روش پر کردن ماتریس من فرق میکنه.
ما باید یه روش پر کردن ماتریسو بعد از مرتب سازی اتخاذ کنیم. یا سطری ماتریسو پر کنبم و یا ستونی پرش کنیم.
اگه شما هم بعد مرتب سازی ماتریستونو به شکل ماتریس من به صورت ستونی پر کنین به شکل زیر در میاد.
۱۳ ۹ ۵ ۱
۱۴ ۱۰ ۶ ۲
۱۵ ۱۱ ۷ ۳
۱۶ ۱۲ ۸ ۴
و حالا دوباره مثل حالت اولی که شرح دادم اول اونو به شکل سطری جستجو میکنیم و بعد به شکل ستونی.که با این روش عدد ۱۵ با کمتر از ۲n بدست میاد.
یعنی اگه اعدادو بعد از مرتب سازی معمولی به شکل ستون به ستون وارد ماتریس کردیم , اول اونو به شکل سطری جستجو میکنیم.
واگه بعد از مرتب سازی اونو به شکل سطر به سطر وارد ماتریس کردیم اول اونو به شکل ستونی جستجو میکنیم.
یعنی یه سیاست پر کردن ماتریس رو بعد از مرتب سازی به شکل ثابت انتخاب میکنیم. و همیشه ماتریسو به همون شکل پر میکنیم. اونوقت دیگه یه روش جستجو رو هم بعد از اتخاذ سیاست پر کردن ماتریس به شکل ثابت در نظر میگیریم.
(۲۱ دى ۱۳۹۰ ۰۹:۴۵ ق.ظ)sasanlive نوشته شده توسط: اگه شما هم بعد مرتب سازی ماتریستونو به شکل ماتریس من به صورت ستونی پر کنین به شکل زیر در میاد.اگه ماتریس رو بخوایم خودمون پر کنیم پیچیدگی ار درجه n^2 میشه. لطفاً به فرض مساله دقت کنید. ما فقط می‌دونیم که سطرها و ستون‌ها مرتب هستند. ما مرتب سازی رو انجام نمی‌دیم که بتونیم شیوه مرتب کردن رو تعیین کنیم.
در صورتی که مرتبسازی به شکلی که شما می‌گین باشه که الگوریتم بهتر وجود داره (۲logn).
ماتریس زیر رو در نظر بگیر
به روش خودت مرتب شده)۰۱ ۰۱ ۰۱ ۰۱
۰۱ ۰۱ ۰۱ ۰۱
۰۴ ۰۱ ۰۱ ۰۱
۰۵ ۰۱ ۰۱ ۰۱
حالا فرض کن که می‌خوایم ۴ رو پیدا کنیم. الگوریتم شما تو چه زمانی جواب میده؟
خوب اگه منظور شما اینه که فقط دستمون تو جستجو بازه و نمیدونیم با چه روشی ماتریس مرتب هست میشه از یه روش جستجوی دیگه استفاده کرد.
اول x رو با قطر اصلی ماتریس مقایسه میکنیم.
اگه با یکی از اعداد روی قطر برابر بود که تمومه.
اگه روی قطر اصلی به عددی رسیدیم که از x بزرگتره به عدد قبلی روی قطر اصلی ماتریس برمیگردیم.حالا عدد روی قطر اصلی رو با عدد سمت راستش مقایسه میکنیم. دو حالت پیش میاد:
۱-اگه عدد سمت راست از x کوچکتر بود ادامه ماتریسو به شکل سطری میگردیم تا x پیدا بشه.که اینکارو با اصافه کردن اندیس به i,j انجام میدیم.
۲-اگه عدد سمت راست از x بزرگتر بود ادامه ماتریسو به شکل ستونی میگردیم تا x پیدا بشه.که اینکارو با اصافه کردن اندیس به i,j انجام میدیم.
عدد ۱۴ رو در دو ماتریس خودم و شما پیدا میکنم.
در ماتریس شما به شکل سطری پر شده:
۰۴ ۰۳ ۰۲ ۰۱
۰۸ ۰۷ ۰۶ ۰۵
۱۲ ۱۱ ۱۰ ۰۹
۱۶ ۱۵ ۱۴ ۱۳
ترتیب مقایسه: با ۱ سپس با ۶ سپس با ۱۱ سپس با ۱۶ حالا x کوچکتر از ۱۶ هست به ۱۱ برمیگردم و با سمت راستش که ۱۲ مقایسه میکنم.چون x بزرگتر از ۱۲ بقیه مقایسه به شکل سطری انجام میدم که اینکارو با اضافه کردن اندیسها انجام میدیم . میشه ۱۲ بعد ۱۳ بعد ۱۴ که مقدار بدست اومده با کمتر از ۲n بدست اومد.
در ماتریس خودم که به شکل ستونی پر شده:
۱۳ ۹ ۵ ۱
۱۴ ۱۰ ۶ ۲
۱۵ ۱۱ ۷ ۳
۱۶ ۱۲ ۸ ۴
ترتیب مقایسه: با ۱ سپس با ۶ سپس با ۱۱ سپس با ۱۶ حالا x کوچکتر از ۱۶ هست به ۱۱ برمیگردم با سمت راستش مقایسه میکنم. عدد ۱۵ هست که از x بزرگتره پس بقیه جستجو رو به شکل ستونی ادامه میدم تا x پیدا بشه که اینکارو با اضافه کردن اندیسها انجام میدیم. میشه ۱۲ بعد ۱۳ بعد ۱۴ که مقداره x در زمان کمتر از ۲n بدست اومده.
همینطور در ماتریس جدیدتون با اعداد یکسان هم جواب میده.
۰۱ ۰۱ ۰۱ ۰۱
۰۱ ۰۱ ۰۱ ۰۱
۰۴ ۰۱ ۰۱ ۰۱
۰۵ ۰۱ ۰۱ ۰۱
البته این روش جستجو به شرطی برقراره که ماتریس بعد از مرتب سازی طبق قواعد پر شدن ماتریسها , به روش سطری یا ستونی پر شده باشه.
.
تو این ماتریس
۰۴ ۰۳ ۰۲ ۰۱
۱۳ ۱۰ ۰۶ ۰۲
۱۵ ۱۱ ۱۰ ۰۳
۱۶ ۱۵ ۱۴ ۰۴
۱۳ رو چطوری پیدا میکنه؟
(۲۱ دى ۱۳۹۰ ۰۷:۱۵ ب.ظ)admin نوشته شده توسط: تو این ماتریس
۰۴ ۰۳ ۰۲ ۰۱
۱۳ ۱۰ ۰۶ ۰۲
۱۵ ۱۱ ۱۰ ۰۳
۱۶ ۱۵ ۱۴ ۰۴
۱۳ رو چطوری پیدا میکنه؟
گفتم اخرش که در صورتی درسته که از قانون پر شدن ماتریسها پیروی کنه یعنی یا ستونی یا سطری.
بعد از اینکه اعداد مرتب سازی میشن یا به شکل سطری در ماتریس قرار میگیرن یا ستونی. حالت دیگه ای نمیشه پر کرد.
ماتریس شما نه سطری پر شده نه ستونی.
اعداد بعد از مرتب سازی به شکل زیر در میان.
۱,۲,۲,۳,۳,۴,۴,۶,۱۰,۱۰,۱۱,۱۳,۱۴,۱۵,۱۵,۱۶
و مثلا سطری به شکل زیر وارد ماتریس میشه.
۰۳ ۰۲ ۰۲ ۰۱
۰۶ ۰۴ ۰۴ ۰۳
۱۳ ۱۱ ۱۰ ۱۰
۱۶ ۱۵ ۱۵ ۱۴
ستونی هم رسم کنین جواب بدست میاد.
وبه اون شکلی که شما وارد ماتریس کردین نه سطری نه ستونی.
درون ماتریس که مرتب سازی انجام نمیشه. بیرون ماتریس انجام میشه بعد به شکل سطری یا ستونی وارد ماتریس میشه.
شما میاین داخل ماتریس اعدادو مرتب میکنین که این اشتباهه. باید بیرون ماتریس با یک الگوریتمی مرتب شده باشن و بعد ستونی یا سطری وارد ماتریس یشن.
تو مساله گفته از چپ به راست و از بالا به پایین به صورت غیر نزولی مرتبه یعنی بیرون ماتریس به شکل غیر نزولی و نه غیر صعودی مرتب شده و بعد به شکل سطری یا ستونی وارد ماتریس میشن.
وگرنه من هر نوع جستجویی ارایه بدم میشه نقض کرد مثلا تو شکل زیر من ۱۴ پایینو پیدا کنم شما میگی نه بالایی رو میخواستم.
۱۴ ۰۳ ۰۲ ۰۱
۱۵ ۰۸ ۰۷ ۰۶
۱۶ ۱۲ ۱۱ ۱۰
۱۷ ۱۶ ۱۵ ۱۴
میشه توضیح بدین به چه شکلی شما اعدادو مرتب کردین. داخل ماتریس و بصورت دستی مرتب کردین؟
و اگه بیرون ماتریس مرتب کردین با چه اصول و یا الگوریتمی میشه به این شکل اعدادو وارد ماتریس کرد؟
.
(۲۱ دى ۱۳۹۰ ۰۷:۳۳ ب.ظ)Ali-B نوشته شده توسط: من که هر چی به خودم فشار آورم، نتونستم حلش کنم، آخرش رفتم جوابش تو کتاب تستم نگاه کردم و خلاص، البته تا یه جایی درست رفته بودم (جستجو روی قطر ماتریس). اگه دوست دارید جوابش بنویسم؟
اگه اونم ۲n بدست آورده اول ببین طبق حالاتی که گفتیم نقض نمیشه. اگه نشد لطف کنی عکسشو بذاری خیلی خوبه.
(۲۱ دى ۱۳۹۰ ۰۸:۳۱ ب.ظ)sasanlive نوشته شده توسط: بعد از اینکه اعداد مرتب سازی میشن یا به شکل سطری در ماتریس قرار میگیرن یا ستونی. حالت دیگه ای نمیشه پر کرد.
ماتریس شما نه سطری پر شده نه ستونی.
اعداد بعد از مرتب سازی به شکل زیر در میان.
۱,۲,۲,۳,۳,۴,۴,۶,۱۰,۱۰,۱۱,۱۳,۱۴,۱۵,۱۵,۱۶
و مثلا سطری به شکل زیر وارد ماتریس میشه.
۰۳ ۰۲ ۰۲ ۰۱
۰۶ ۰۴ ۰۴ ۰۳
۱۳ ۱۱ ۱۰ ۱۰
۱۶ ۱۵ ۱۵ ۱۴
ستونی هم رسم کنین جواب بدست میاد.
وبه اون شکلی که شما وارد ماتریس کردین نه سطری نه ستونی.
درون ماتریس که مرتب سازی انجام نمیشه. بیرون ماتریس انجام میشه بعد به شکل سطری یا ستونی وارد ماتریس میشه.
فکر میکنم محدودیتی که شما میگید با توجه به صورت سوال وجود نداره و اعداد در خود ماتریس مرتب میشن، مهم اینه که چه در سطر و چه در ستون اعضا مرتب باشن و اینکه اعداد این سطر باید از سطر بعدی کوچکتر باشن یا ... مهم نیست.
راه حل کتاب سنجش:
[attachment=2364]
(۲۱ دى ۱۳۹۰ ۱۰:۵۴ ب.ظ)Ali-B نوشته شده توسط: فکر میکنم محدودیتی که شما میگید با توجه به صورت سوال وجود نداره و اعداد در خود ماتریس مرتب میشن، مهم اینه که چه در سطر و چه در ستون اعضا مرتب باشن و اینکه اعداد این سطر باید از سطر بعدی کوچکتر باشن یا ... مهم نیست.
راه حل کتاب سنجش:
ممنون بابت عکس.
اولین نقیضش اینه که فرض کرده اعضا رو قطر مرتب شدن.
پس یک نوع خاص از مرتبسازی رو درنظر گرفته.
و با گفته های قبلیمون تناقض داره.
باید روش کار بشه.
(۲۱ دى ۱۳۹۰ ۱۱:۰۷ ب.ظ)sasanlive نوشته شده توسط:(21 دى ۱۳۹۰ ۱۰:۵۴ ب.ظ)Ali-B نوشته شده توسط: فکر میکنم محدودیتی که شما میگید با توجه به صورت سوال وجود نداره و اعداد در خود ماتریس مرتب میشن، مهم اینه که چه در سطر و چه در ستون اعضا مرتب باشن و اینکه اعداد این سطر باید از سطر بعدی کوچکتر باشن یا ... مهم نیست.
راه حل کتاب سنجش:
ممنون بابت عکس.
اولین نقیضش اینه که فرض کرده اعضا رو قطر مرتب شدن.
پس یک نوع خاص از مرتبسازی رو درنظر گرفته.
و با گفته های قبلیمون تناقض داره.
باید روش کار بشه.
خب ماتریسی با این شرایط خود به خود روی قطرش هم مرتب میشه. هر مثالی که بیاریم، روی قطرش هم مرتب خواهد بود.
(۲۱ دى ۱۳۹۰ ۱۱:۵۷ ب.ظ)sasanlive نوشته شده توسط: خب ماتریسی با این شرایط خود به خود روی قطرش هم مرتب میشه. هر مثالی که بیاریم، روی قطرش هم مرتب خواهد بود.درسته مرتب میشه.
عددی حل کن ببین جستجو کلی صادقه.
جستجو رو از کدوم قطر شروع میکنه.
در مورد داده های تکراریم درسته یا نه.
باید بررسی بشه متاسفانه من وقتم کمه دیرتر از همه شروع کردم هنوز یه دورم کتابا تموم نشده.هیچ تستی هم نزدم. واسه همین نمیتونم زیاد دیگه وقت بذارم سره این مسئله.
از زحمتت بابت عکس هم خیلی ممنون.