الگوریتم تقسیم وحل

[19216810047]

با سلام
دوستان من می خوام برای مسیله ی زیر الگوریتمی از روش تقسیم و حل ارایه بدم.می خواستم منو راهنمایی کنید.
مسیله:الگوریتمی طراحی کنید که مشخص کند آیا دو عضو در یک مجموعهnعنصری وجود دارند که جمع آنها مساوی مقدار x شود یا خیر و اندیس آن دو عنصر را برگرداند

[the king]

با سلام
دوستان من می خوام برای مسیله ی زیر الگوریتمی از روش تقسیم و حل ارایه بدم.می خواستم منو راهنمایی کنید.
مسیله:الگوریتمی طراحی کنید که مشخص کند آیا دو عضو در یک مجموعهnعنصری وجود دارند که جمع آنها مساوی مقدار x شود یا خیر و اندیس آن دو عنصر را برگرداند

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


a¹ a¹
a² a²
a³ a³
. .
. .
. .
. .
aⁿ aⁿ


حالا در روش تقسیم و حل سعی می کنیم که مقایسه های بی مورد کمتری انجام بشه. فرضا اگر مقدار یک عنصر از x بیشتر باشه فقط زمانی جمع کردنش
با عنصر دیگه ای می تونه x بشه که با عنصر دیگه ای جمع بشه که از 0 کوچکتره. همچنین زمانی که مقدار یک عنصر کوچکتر یا مساوی x باشه، فقط زمانی
جمع کردنش با عنصر دیگه ای می تونه x بشه که با عنصر دیگه ای جمع بشه که یا 0 ئه و یا از 0 بزرگتره.

پس می توانید مساله را به دو بخش مجزا تقسیم کنید، در بخش اول در یک طرف مقادیر بزرگتر از x رو قرار بدهید و در طرف دیگه مقادیر کوچکتر از 0
و عناصر این دو مجموعه رو یکی یکی با هم مقایسه کنید :


a¹ > x b¹ < 0
a² > x b² < 0
a³ > x b³ < 0
. .
. .
. .
. .
aⁿ > x bⁿ < 0


و در بخش دیگر در یک طرف مقادیر کوچکتر یا مساوی x رو قرار بدهید و در طرف دیگه مقادیر بزرگتر یا مساوی 0
و عناصر این دو مجموعه رو یکی یکی با هم مقایسه کنید :


a¹ ≤ x b¹ ≥ 0
a² ≤ x b² ≥ 0
a³ ≤ x b³ ≥ 0
. .
. .
. .
. .
aⁿ ≤ x bⁿ ≥ 0

[19216810047]

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

[the king]

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

باید چهار تا مجموعه بسازید، دو مجموعه A و B برای بخش اول و دو مجموعه C و D برای بخش دوم
اینطوری که از اولین عنصر تا آخرین عنصر رو در یک حلقه پیمایش می کنید و دو تا شرط رو چک می کنید :
شرط اول - اگر از x بزرگتر بود به مجموعه A و اگر نبود به مجموعه C اضافه اش می کنید.
شرط دوم - اگر از صفر کوچکتر بود به مجموعه B و اگر نبود به مجموعه D اضافه اش می کنید.

این دو تا شرط ربطی به هم ندارند، مثلا ممکنه یک عنصر هم در مجموعه A باشه و هم مجموعه B

پیمایش این حلقه که تمام بشه عناصر تفکیک شده اند و دو مساله کوچکتر دارید :
آیا در مجموعه A و B دو عنصر متناظری هست که مجموع شان x باشد؟
آیا در مجموعه C و D دو عنصر متناظری هست که مجموع شان x باشد؟