سلام . با کمی تاخیر نسبت به شروع تاپیک....
دوستمان در خصوص راه حل بازگشتی مساله پرسیده بودند . من کد این حل به همراه توضیحاتش را برای شما میگذارم . خواستید به سایت ما هم سری بزنید .
نمک 88 (سایت دانشجویان مهندسی نرم افزار کامیپوتر فردوسی مشهد ورودی 88) . آنجا تا دلتان بخواهد در انجمن ها صحبت سر این جور چیزهاست.
راه حلی که در زیر می آید ، زیباترین شیوه حل تا کنون است . الگوریتم آن به این صورت است :
R <- []
L <- [ e1, e2 ... en ]
c <- 0
function: powerSet(L, c)
R <- R union L
for e in L starting at c
powerSet(L\{e}, c)
end
return R
end
پیاده سازی این الگوریتم در جاوا به صورت زیر است: publicstaticvoid powerSet(List<String> list, int count)
{
result.add(list);
for(int i = count; i < list.size(); i++)
{
List<String> temp = new ArrayList<String>(list);
temp.remove(i);
powerSet(temp, i);
} }
توضیح الگوریتم : اگر ما بتوانیم مجموعه را به دو زیر مجموعه ای که در یکی یک عضو خاص آمده باشد و در دیگری نیامده باشد ، افراز کنیم ، توانسته ایم یک گام بزرگ در حل بازگشتی مساله برداریم . در این الگوریتم ابتدا لیست شامل اعضا مجموعه گرفته میشود . سپس powerSetدر هر مرحله یک عضو خاص را از مجموعه حذف میکند و تمام زیر مجموعه های بدون عضو خاص را به result اضافه میکند.
مشخص شدن عضوی که در هر مرحله باید حذف شود ، توسط اندیس ارسال شده به powerSet انجام میشود و عمل حذف در کد جاوا در خط temp.remove(i)صورت میگیرد. سپس دوباره تابع فراخوانی میشود . برای فهم بهتر یک بار تابع را با A={a,b,c} دنبال کنید.
اشکال این الگوریتم تنها مرتبه زمانی بالای آن (2^n) است.