Skip to content
The Chat Archive
gpt-3.5-turbo-0301· OpenAI WildChat-4.8M (AI2)

فرض کن دو مهره قرمز و دو مهره آبی داری. باید این 4 مهره را کنار هم قرار بدی. تنها…

  1. User

    فرض کن دو مهره قرمز و دو مهره آبی داری. باید این 4 مهره را کنار هم قرار بدی. تنها محدودیت این است که مهره های همرنگ حتما باید کنار هم باشند. مثلا دو ترکیب مجاز و غیر مجاز میتواند به صورت زیر باشد. مجاز:آبی1، آبی2،قرمز1، قرمز2 غیر مجاز:آبی1،قرمز2، قرمز1،آبی2 یک الگوریتم بازگشت به عقب بنویس که تمام ترکیبهای مجاز برای کنار هم قرار گرفتن مهره ها را چاپ کند.

  2. Assistant

    رویه‌ی بازگشتی:

    1. اگر تمام مهره‌ها را قرار داده باشیم، یک یا چند ترکیب مجاز حاصل شده است و آن‌ها را چاپ کن.
    2. اگر هنوز مهره‌ای باقی مانده باشد، برای هر یک از مهره‌های باقی مانده:
    • اگر مهره رنگش با آخرین مهره قرار داده شده متفاوت باشد، مهره را با آخرین مهره قرار داده شده جایگزین کن و باقی مانده را به تابع فراخوانی کن.
    • اگر مهره رنگش با آخرین مهره قرار داده شده یکی باشد، مشابه مهره را پیدا کرده و آن را به عنوان آخرین مهره قرار داده شده در نظر بگیر و مرحله قبلی را تکرار کن.
    • اگر هیچ مهره‌ای باقی نمانده باشد، تمام مهره‌ها را قرار داده‌ایم و یک ترکیب مجاز حاصل شده است.
    • بازگشت از تابع.

    کد الگوریتم بازگشتی:

    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)

  3. User

    الگوریتم بالا رو به زبان سی شارپ بنویس

  4. 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);
                }
            }
        }
    }