فرض کن دو مهره قرمز و دو مهره آبی داری. باید این 4 مهره را کنار هم قرار بدی. تنها…
- User
فرض کن دو مهره قرمز و دو مهره آبی داری. باید این 4 مهره را کنار هم قرار بدی. تنها محدودیت این است که مهره های همرنگ حتما باید کنار هم باشند. مثلا دو ترکیب مجاز و غیر مجاز میتواند به صورت زیر باشد. مجاز:آبی1، آبی2،قرمز1، قرمز2 غیر مجاز:آبی1،قرمز2، قرمز1،آبی2 یک الگوریتم بازگشت به عقب بنویس که تمام ترکیبهای مجاز برای کنار هم قرار گرفتن مهره ها را چاپ کند.
- Assistant
رویهی بازگشتی:
- اگر تمام مهرهها را قرار داده باشیم، یک یا چند ترکیب مجاز حاصل شده است و آنها را چاپ کن.
- اگر هنوز مهرهای باقی مانده باشد، برای هر یک از مهرههای باقی مانده:
- اگر مهره رنگش با آخرین مهره قرار داده شده متفاوت باشد، مهره را با آخرین مهره قرار داده شده جایگزین کن و باقی مانده را به تابع فراخوانی کن.
- اگر مهره رنگش با آخرین مهره قرار داده شده یکی باشد، مشابه مهره را پیدا کرده و آن را به عنوان آخرین مهره قرار داده شده در نظر بگیر و مرحله قبلی را تکرار کن.
- اگر هیچ مهرهای باقی نمانده باشد، تمام مهرهها را قرار دادهایم و یک ترکیب مجاز حاصل شده است.
- بازگشت از تابع.
کد الگوریتم بازگشتی:
def backtrack(last_color, red_left, blue_left): if red_left == 0 and blue_left == 0: print(last_color) return if red_left > 0 and last_color[-1] != 'r': backtrack(last_color + 'r', red_left - 1, blue_left) if blue_left > 0 and last_color[-1] != 'b': backtrack(last_color + 'b', red_left, blue_left - 1) for i in range(1, len(last_color)+1): if last_color[-i] == 'r' and blue_left > 0: backtrack(last_color[:len(last_color)-i] + 'b', red_left, blue_left - 1) elif last_color[-i] == 'b' and red_left > 0: backtrack(last_color[:len(last_color)-i] + 'r', red_left - 1, blue_left)
backtrack('', 2, 2)
- User
الگوریتم بالا رو به زبان سی شارپ بنویس
- Assistant
این کد برای الگوریتم بازگشتی مد نظر شما به زبان سی شارپ است:
using System; class BacktrackingExample { static void Main(string[] args) { Backtrack("", 2, 2); } static void Backtrack(string lastColor, int redLeft, int blueLeft) { if (redLeft == 0 && blueLeft == 0) { Console.WriteLine(lastColor); return; } if (redLeft > 0 && lastColor.Length == 0 || lastColor[lastColor.Length - 1] != 'r') { Backtrack(lastColor + "r", redLeft - 1, blueLeft); } if (blueLeft > 0 && lastColor.Length == 0 || lastColor[lastColor.Length - 1] != 'b') { Backtrack(lastColor + "b", redLeft, blueLeft - 1); } for (int i = 1; i <= lastColor.Length; i++) { if (lastColor[lastColor.Length - i] == 'r' && blueLeft > 0) { Backtrack(lastColor.Remove(lastColor.Length - i) + "b", redLeft, blueLeft - 1); } else if (lastColor[lastColor.Length - i] == 'b' && redLeft > 0) { Backtrack(lastColor.Remove(lastColor.Length - i) + "r", redLeft - 1, blueLeft); } } } }