خوارزمية سياج الطلاء  


مستوى الصعوبة الثابت
كثيرا ما يطلب في CodeNation فيس بوك جوجل يستشعر JP مورغان مورجان ستانلي
مجموعة البرمجة الديناميكية LeetCode

المشكلة بيان  

تنص "خوارزمية دهان السياج" على أنه تم إعطاؤك سياجًا به بعض الدعامات (بعض القطع الخشبية أو بعض القطع الأخرى) وبعض الألوان. تعرف على عدد الطرق لطلاء السياج بحيث لا يكون هناك سوى سياجين متجاورين لهما نفس اللون. نظرًا لأن هذا الرقم يمكن أن يكون كبيرًا ، قم بإرجاع وحدة الإجابة 2.

مثال  

خوارزمية سياج الطلاءدبوس

Number of posts/wooden sticks = 2
Number of colors = 2
4

تفسير
يمكنك رسم كلا المنشورين بألوان مختلفة بطريقتين. ولديك طريقتان لرسم المنشورات بنفس اللون. حتى المجموع لديك 2 طرق.

نهج لطلاء السياج الخوارزمية  

لنبدأ بنهج ساذج. لقد علمنا أن لدينا مشاركات n وألوان k. نحتاج الآن إلى إيجاد عدد طرق تلوين المنشورات بحيث لا يوجد على الأكثر سوى منشورين متجاورين لهما نفس اللون. يمكن أن يكون نهج واحد ساذج إذا كنا تولد كل التسلسلات للدلالة على اللون الذي حصلت عليه كل مشاركة. لكن هذا النهج غير فعال للغاية وسيؤدي بالتأكيد إلى تجاوز الحد الزمني.

إذن ، ما الذي يمكن أن يكون نهجًا أفضل؟ واحد نهج يمكن أن يكون إذا قسمنا المشكلة إلى مشاكل أصغر. ضع في اعتبارك أننا نعرف الإجابة عن عدد المشاركات = n-2 و n-1. دعونا نشير إلى هذه القيم باستخدام F (n-2) و F (n-1) على التوالي. لذلك نحن نعلم أن F (n-1) تمثل عدد الطرق التي يمكن من خلالها أن يكون لعمودين متجاورين فقط نفس اللون ونفس الشيء ينطبق على F (n-2). الآن نعتبر أنه إذا قمنا بتلوين المنشورات في الموضعين (n-2) و nth بنفس اللون ، فإننا نطلب أن (n-1) لا يجب أن يكون لها نفس لون المنشور (n-1) nd. يتم الإشارة إلى هذه القيمة باستخدام F (n-2). لذلك درسنا حالة يكون فيها المنشور رقم n له نفس لون المشاركة الأخيرة. يجب أن نفكر أيضًا في الطرق التي لا يجب أن يكون فيها المنشور الحالي وآخر آخر نفس اللون. يتم الإشارة إلى هذه القيمة باستخدام F (n-2). الآن لدينا طرق (k-1) لتلوين المنشور التاسع. وبالتالي فإن إجمالي عدد الطرق يساوي (F (n-1) + F (n-1)) * (k-2).

انظر أيضا
طرق فك

رمز  

كود C ++ لخوارزمية السياج

#include <bits/stdc++.h>
using namespace std;

int main(){
  // number of posts
  int n;cin>>n;
  // number of available colors
  int k;cin>>k;
  int mod = 1000000007;
  int ways = 0;
  if(n == 1)cout<<k;
  else if(n == 2)cout<<k*k;
  else {
    int last = k*k; int lastTolast = k;
    for(int i=3;i<=n;i++){
      ways = ((last + lastTolast)*(k-1))%mod;
      lastTolast = last;
      last = ways;
    }
    cout<<ways;
  }
}
4 2
10

كود جافا لخوارزمية السياج

import java.util.*;
class Main{
    public static void main(String[] args){
    	Scanner sc = new Scanner(System.in);
    	// number of posts
    int n = sc.nextInt();
    // number of available colors
    int k = sc.nextInt();
    int mod = 1000000007;
    int ways = 0;
    if(n == 1)System.out.print(k);
    else if(n == 2)System.out.print(k*k);
    else {
      int last = k*k; int lastTolast = k;
      for(int i=3;i<=n;i++){
        ways = ((last + lastTolast)*(k-1))%mod;
        lastTolast = last;
        last = ways;
      }
      System.out.print(ways);
    }
    }
}
4 2
10

تحليل التعقيد  

تعقيد الوقت

O (N) كما نرى من الخوارزمية. لقد استخدمنا حلقة واحدة تستمر حتى i يساوي n. وبالتالي إجراء تكرارات n ، مما يعني أن لدينا تعقيدًا زمنيًا خطيًا.

تعقيد الفضاء

يا (1) ،  لأننا استخدمنا عددًا ثابتًا من المتغيرات بدلاً من إنشاء مصفوفة DP. هذا النهج أكثر قابلية للتطبيق لأن حل المشكلة يعتمد فقط على آخر مشكلتين صغيرتين.