۰
subtitle
ارسال: #۱
الگویتم به روش تفسیم و حل برای پیدا کردن دو عدد مجاور دریک آرایه
الگویتم به روش تفسیم و حل برای پیدا کردن دو عدد مجاور دریک آرایه از اعداد صحیح، که بزرگترین مقسوم علیه مشترک آنها از هر دو عدد مجاور دیگری دراین آرایه بزرگتر باشد. الگوریتم خود را تحلیل کنید.
دوستان ایده خاصی ندارید؟ من هر چی فکر کردم نشد.چون وقتی آرایه رو تقسیم کنیم. باز به خانه آرایه بعدی نیاز پیدا میشه. Huh
دوستان ایده خاصی ندارید؟ من هر چی فکر کردم نشد.چون وقتی آرایه رو تقسیم کنیم. باز به خانه آرایه بعدی نیاز پیدا میشه. Huh
۰
ارسال: #۲
RE: دو عدد مجاور در آرایه
سلام ببخش دیر شد خیلی وقت نکردم روش فکر کنم اما این راه حل به ذهنم رسید حالا برنامه نوشتن با خودت :
همون طور که قبلا براتون نوشتم میشه از الگوریتم روش Mergsort استفاده کرد همونطور که در شکل هم قرار دادم با این تفاوت که از low تا Mid رو داریم و از Mid تا High یعنی عنصر وسط رو حساب میکنیم و به دو بخش تقسیم میکنیم و در هر دو حالت عنصر Mid رو در نظر میگیریم . به حالتی که در تصویر قرار دادم میرسیم . حالا تمام جفت عناصر مجاور هم رو داریم . هر جفت را در تابع BMM قرار میدهیم تا بزرگترین مقسوم الیه را به ما بدهد و آن را مساوی با x قرار ئمیدهیم . حال x را با تمام عناصر داخل آرایه توسط دستور for مقایسه میکنیم و با دستور if شرطی قرار میدهیم که اگه x کوچکتر از عناصر داخل آرایه بود ادامه دهیم در غیر این صورت اگه بزرگتر بود خوب اون دو عدد رو چاپ کنیم .تابع BMM رو داشتم برات قرار میدم .
همون طور که قبلا براتون نوشتم میشه از الگوریتم روش Mergsort استفاده کرد همونطور که در شکل هم قرار دادم با این تفاوت که از low تا Mid رو داریم و از Mid تا High یعنی عنصر وسط رو حساب میکنیم و به دو بخش تقسیم میکنیم و در هر دو حالت عنصر Mid رو در نظر میگیریم . به حالتی که در تصویر قرار دادم میرسیم . حالا تمام جفت عناصر مجاور هم رو داریم . هر جفت را در تابع BMM قرار میدهیم تا بزرگترین مقسوم الیه را به ما بدهد و آن را مساوی با x قرار ئمیدهیم . حال x را با تمام عناصر داخل آرایه توسط دستور for مقایسه میکنیم و با دستور if شرطی قرار میدهیم که اگه x کوچکتر از عناصر داخل آرایه بود ادامه دهیم در غیر این صورت اگه بزرگتر بود خوب اون دو عدد رو چاپ کنیم .تابع BMM رو داشتم برات قرار میدم .
کد:
int BMM(int a , int b)
{
if(b==0)
return a;
else
return BMM(b,a%b);
}
۰
ارسال: #۳
دو عدد مجاور در آرایه
سلام دوستان من
در مورد تقسیم و غلبه یک مثال می زنم.
ببین شما می خواهی از شهر A به شهر C بری. و مجبوری در این مسیر حتما از شهر B عبور کنی.
پس شما خیلی راحت می تونی مساله رو به دو قسمت جداگانه تقسیم ، هر دو را حل و سپس جواب ها را با توجه به نوع مساله پیوند بزنی. این میشه کلیات مساله. و اگه از A به B باید از شهر M عبور کنیم خوب چرا تقسیم نکنیم؟
با یه بار شکستن هرچند یه بار از تقسیم وغلبه استفاده شده اما از نظر Order زمانی چیزه خاصی بدست نمی آریم. همون جور که داخل شکل دوستم یاسر پیداست این نمودار درختی هست که هدف تقسیم وغلبه بوده که Order رو کم کنه و اساتید همین رو ازت می خوان.
در مورد تقسیم و غلبه یک مثال می زنم.
ببین شما می خواهی از شهر A به شهر C بری. و مجبوری در این مسیر حتما از شهر B عبور کنی.
پس شما خیلی راحت می تونی مساله رو به دو قسمت جداگانه تقسیم ، هر دو را حل و سپس جواب ها را با توجه به نوع مساله پیوند بزنی. این میشه کلیات مساله. و اگه از A به B باید از شهر M عبور کنیم خوب چرا تقسیم نکنیم؟
با یه بار شکستن هرچند یه بار از تقسیم وغلبه استفاده شده اما از نظر Order زمانی چیزه خاصی بدست نمی آریم. همون جور که داخل شکل دوستم یاسر پیداست این نمودار درختی هست که هدف تقسیم وغلبه بوده که Order رو کم کنه و اساتید همین رو ازت می خوان.
۰
ارسال: #۴
دو عدد مجاور در آرایه
روشی که yaser_ilam_com گفته به نظرم درست میاد. شکستن باید تا زمانی ادامه پیدا کنه که به آرایه های دو خونه ای برسیم و این شکستن باید طوری باشه که تو سطح آخر درخت ایجاد شده تمام حالات عناصر مجاور رو داشته باشیم. وقتی با این حالت رسیدیم(یعنی سطح آخر درخت) باید برای هر جفت از اعداد BMM رو حساب بکنیم و همین طور که در درخت به سمت ریشه حرکت می کنیم BMMهای به دست آمده رو به هم مقایسه کنیم تا در هرلحظه بزرگترین BMM رو داشته باشیم
۰
ارسال: #۵
دو عدد مجاور در آرایه
بهتر نیست. آرایه رو به ۲ قسمت بشکنیم و سپس مقایسه رو انجام دهیم؟
سپس هر عنصر را با عنصر کناری مقایسه کنیم.
و برای اون ۲ نقاط مرزی(آخرین عنصر آرایه اول و اولین عنصر آرایه دوم) هم یک مقایسه انجام دهیم و کار تمام شود؟
سپس هر عنصر را با عنصر کناری مقایسه کنیم.
و برای اون ۲ نقاط مرزی(آخرین عنصر آرایه اول و اولین عنصر آرایه دوم) هم یک مقایسه انجام دهیم و کار تمام شود؟
ارسال: #۶
RE: دو عدد مجاور در آرایه
(۱۵ خرداد ۱۳۹۱ ۱۰:۲۴ ب.ظ)H-Arshad نوشته شده توسط: بهتر نیست. آرایه رو به ۲ قسمت بشکنیم و سپس مقایسه رو انجام دهیم؟تقسیم و غلبه همینه که میگه بشکن تا بجواب برسی حالا فکر کنم شما میگی فقط یکبار بشکنیم و دو آرایه ایجاد کنیم .بعد مقایسه عناصر آرایه چپ و بعد مقایسه عناصر راست و بعد عنصری که در مرز مشترک بین دو آرایه هست درسته؟؟
سپس هر عنصر را با عنصر کناری مقایسه کنیم.
و برای اون ۲ نقاط مرزی(آخرین عنصر آرایه اول و اولین عنصر آرایه دوم) هم یک مقایسه انجام دهیم و کار تمام شود؟
من این روش رو قبول ندارم چون این دیگه تقسیم و غلبه نیست یکبار میشکنیم که نمیشه تقسیم و غلبه من همون راه اول رو تاکید دارم.
۰
ارسال: #۷
دو عدد مجاور در آرایه
در علوم کامپیوتر, الگوریتم تقسیم و حل (چیرگی) (Divide and conquer/D&C) الگو ی طراحیِ الگوریتمِ مهمی بر اساس بازگشت چندانشعابی می‌باشد. یک الگوریتم تقسیم و حل از طریق تفکیک یک مسئله به دو یا چند زیرمسئله از یک نوع (یا انواع وابسته به هم)، به صورت بازگشتی، کار می‌کند. این تفکیک تا زمانی ادامه می‌یابد که زیرمسئله‌های حاصله به میزان کافی ساده شده باشند تا بتوان آنها را مستقیماً حل کرد. جواب مسئلهٔ اصلی از ترکیب جواب‌های به دست آمده برای زیر مسئله‌ها به دست می‌آید.
مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.
مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.
ارسال: #۸
RE: دو عدد مجاور در آرایه
(۱۵ خرداد ۱۳۹۱ ۱۰:۴۳ ب.ظ)H-Arshad نوشته شده توسط:شما خودت جواب سوال رو دادی این تفکیک تا زمانی ادامه می‌یابد که زیرمسئله‌های حاصله به میزان کافی ساده شده باشند حالا بحث اینه که با شکستن به مقدار یک بار مسئله به اندازه کافی ساده شده ؟؟ قطعا خیر درسته با یکبار شکستن هم میشه عملیات تقسیم و غلبه رو انجام داد اما این خیلی کم پیش میاد عموما به بیش از یکبار نیاز داره(15 خرداد ۱۳۹۱ ۱۰:۳۲ ب.ظ)yaser_ilam_com نوشته شده توسط:در علوم کامپیوتر, الگوریتم تقسیم و حل (چیرگی) (Divide and conquer/D&C) الگو ی طراحیِ الگوریتمِ مهمی بر اساس بازگشت چندانشعابی می‌باشد. یک الگوریتم تقسیم و حل از طریق تفکیک یک مسئله به دو یا چند زیرمسئله از یک نوع (یا انواع وابسته به هم)، به صورت بازگشتی، کار می‌کند. این تفکیک تا زمانی ادامه می‌یابد که زیرمسئله‌های حاصله به میزان کافی ساده شده باشند تا بتوان آنها را مستقیماً حل کرد. جواب مسئلهٔ اصلی از ترکیب جواب‌های به دست آمده برای زیر مسئله‌ها به دست می‌آید.
۰
۰
ارسال: #۱۰
دو عدد مجاور در آرایه
بهتر نیست . بشکونیم آرایه را تا تک عنصر شدن؟ بعد عنصر اول با دوم بزرگترین مقسوم و علیه مشترک را بدست میآریم. سپس عنصر اول و دوم را به ارایه اضافه میکنیم
بعد عنصر سوم با دوم مقایسه میکنیم و عنصر سوم را به آرایه اضافه میکنیم و الا آخر.
این طوری عنصر تکراری نداریم.
بعد عنصر سوم با دوم مقایسه میکنیم و عنصر سوم را به آرایه اضافه میکنیم و الا آخر.
این طوری عنصر تکراری نداریم.
۰
۰
ارسال: #۱۲
دو عدد مجاور در آرایه
۰
ارسال: #۱۳
دو عدد مجاور در آرایه
(۱۶ خرداد ۱۳۹۱ ۰۶:۰۱ ب.ظ)mfXpert نوشته شده توسط:بحث BMM نیست.(16 خرداد ۱۳۹۱ ۱۲:۳۵ ب.ظ)H-Arshad نوشته شده توسط: درسته اما حالت اضافی ما زیاد داریم اینجا.ما برای هر جفت از اعداد مجاور فقط یکبار BMM رو حساب می کنیم پس حالت اضافه ای وجود نداره!
منظور این اعدادی است که چند بار اضافی کپی کردیم.برای اینکه عدد هم با سمت چپ و هم راست خودش چک بشه.
۰
ارسال: #۱۴
دو عدد مجاور در آرایه
Can I see some ID?
Feeling left out?
نگران نباش، فقط روی این لینک برای ثبت نام کلیک کن. رمزت رو فراموش کردی؟ اینجا به یادت میاریم! close