Backtrack یکی از ایده های مهم حل مسایل

[erfan_a2a]

بسم الله الرحمن الرحیم​

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

برنامه ای بنویسید که از ورودی n را خوانده و تمام اعداد باینری n رقمی را کع تعداد آنها 2 به توان n تا میاشد را چاپ کند.برای مثال برای n=2 جواب میشود:
00 و 01 و 10 و 11​

کدآنرا در زیر قرار میدهم و توضیحاتی نیز بر آن میدهم در صورتی که سوالی داشتین حتما بپرسین​

[LIST=1]
[*]#include<iostream>
[*]using namespace std;
[*]const int N=1000 + 10;
[*]int arr[N];
[*]int n;
[*]void bt(int cnt){
[*]      if(cnt==n){
[*]              for(int i=0;i<n;i++)
[*]                      cout<<arr[i];
[*]              cout<<endl;
[*]              return;
[*]      }
[*]      arr[cnt]=0;
[*]      bt(cnt+1);
[*]      arr[cnt]=1;
[*]      bt(cnt+1);
[*]      arr[cnt]=0;
[*]}
[*]int main(){
[*]      cin>>n;
[*]      bt(0);
[*]}
[/LIST]

در این مثال بسیار ساده ما برای اینکه تمام حالت های ممکن را به دست آوریم از یک تابع کمکی bt استفاده کردیم که در هر مرحله در خانه ی cnt یک بار مقدار خانه یarr[cnt]a را برابر صفر قرار داده و bt را برای cnt+1صدا میزند و یکبار آنرا یک قرار داده و خانه ی بعدی را صدا میزند بدین طریق تمام حالات ممکن تحت پوشش قرار میگیرند .

برای تمرین شما برنامه ای بنویسید که n را از ورودی بگیرد و تعداد حالات قرار دادن n رخ را در صفحه n*n شطرنج به طریقی که این n رخ همدیگر را تهدید نکنند را در خروجی چاپ کند ، در دفعه بعد ان شا الله جواب این مساله را خواهم گذاشت

 

[erfankh]

پاسخ : Backtrack یکی از ایده های مهم حل مسایل

#include<iostream>
using namespace std;
int n,ans;
bool sotoon[1000];
void R(int s){
    if(s==n){ans++;return;}
    for(int i=0;i<n;i++){
     if(!sotoon[i]){
     sotoon[i]=1;
     R(s+1);
     sotoon[i]=0;
    }}}
int main(){
      cin>>n;
      for(int i=0;i<n;i++)sotoon[i]=0;
      R(0);
      cout<<ans<<endl;
      cin>>n;
      return 0;
     }

رخ ها با بک ترک

 

[erfan_a2a]

پاسخ : Backtrack یکی از ایده های مهم حل مسایل

سلام

عرفان عزیز که هم نام خودم هم هستی کاملا درسته

من دیگه کد رو چون درسته نمیگذارم فقط یک توضیح کوچک میدهم:

ببینید در هر مرحله ما برای اینکه بدونیم چه ستون هایی در آن ها رخ قرار داده شده یک آرایه تعریف کردیم و در هر ستون که رخ قرار دادیم مثلا ستون i مقدار خانه i ام آرایه را true میکنیم که دیگر در مراحل بعدی در آن چیزی قرار ندهیم . بعد در هر مرحله ما یک رخ در را در تمام خانه های سطر i ام که مقدار آرایه ستون آن false است قرار میدهیم و مقدار آرایه را برای آن ستون true میکنیم و تابع را برای سطر بعد صدامیزنیم .
توصیه میکنم برای درک خیلی خوب برای n = 4 که جواب آن هم 24 است و زیاد نیست برنامه ی بالا را روی کاغذ اجرا کنید.

و اما سوال بعد:
یک جدول n * n داریم و در لحظه ی اول در خانه ی بالا سمت چپ قرار داریم در هر مرحله میتوانیم یا به راست یا به پایین رویم ، در این حین امکان دارد چند حرکت متوالی راست و یا پایین باشد به قطعه هایی از مسیر که مسیر حرکت ما از راست به پایین یا از پایین به راست تغییر میکند پیچ میگویند به چند طریق میتوان از خانه ی بالا سمت چپ به خانه ی پایین سمت راست رفت که دقیقا k پیچ داشته باشیم؟
ورودی : n , k

 

[erfankh]

پاسخ : Backtrack یکی از ایده های مهم حل مسایل

#include<iostream>
using namespace std;
int n,k,ans;
void T_p(int x,int y,int k,bool p){
 if(x==1&&y==1&&k==0)ans++;
 if(x>1){
  if(p)T_p(x-1,y,k-1,0);
  else T_p(x-1,y,k,0);
 }
 if(y>1){
  if(p)T_p(x,y-1,k,1);
  else T_p(x,y-1,k-1,1);
 }
}
int main(){
 cin>>n>>k;
 T_p(n-1,n,k,0);
 T_p(n,n-1,k,1);
 cout<<ans<<endl;
 cin>>n;
 return 0;
}

درست هست؟

 

[erfankh]

پاسخ : Backtrack یکی از ایده های مهم حل مسایل

آقای عبدی نگفتید که درست هست یا خیر؟
با تشکر:53:
​

 

[erfan_a2a]

پاسخ : Backtrack یکی از ایده های مهم حل مسایل

سلام
ببخشید یه مقدار با تاخیر دارم جواب میدم
جواب شما کاملا درسته . بسیار تشویق و تحسین
من خودم هم یدونه زدم که البته زیاد فرقی* با شما نمی*کنه ولی* حالا چون یکم توضیحات داره اونو هم میزارم.

#include<iostream>
using namespace std;

int n,k;

int bt(int x,int y,int num_of_turn,bool jahat){
    // motaghayere jahat ra be in dalil gereftim ke dar har marhale
    // be ma neshan dahad marhale ye ghabl che jahti dashtim
    // agar jahat barabare 0 bashad yani dafe pish be samte 
    // payin miraftim va agar 1 bashad yani dafe pish be samte 
    // rast miraftim
    if(num_of_turn>k)
        return 0;
    if(x==n && y == n && num_of_turn==k){
        return 1;
    }
    int sum=0;
    if(x==1 && y==1)
        return bt(x+1,y,num_of_turn,1)+bt(x,y+1,num_of_turn,0);
    if(x!=n){
        if(jahat == 1)
            sum+=bt(x+1,y,num_of_turn,1);
        if(jahat == 0)
            sum+=bt(x+1,y,num_of_turn+1,1);
    }
    if(y!=n){
        if(jahat == 0)
            sum+=bt(x,y+1,num_of_turn,0);
        if(jahat == 1)
            sum+=bt(x,y+1,num_of_turn+1,0);
    }
    return sum;
}

int main(){
    cin>>n>>k;
    cout<<bt(1,1,0,0)<<endl;
    return 0;
}

​

 

[erfan_a2a]

پاسخ : Backtrack یکی از ایده های مهم حل مسایل

و اما سوال بعدی:

n تا عدید داریم که شاید بعضی از آنها با هم برابر باشند میخواهیم ببینیم آیا میشود با جمع چند تا از آنها به عدد k رسید؟
در سطر اول ورودی n ، در خط بعد n عدد و در خط سوم عدد k
اگر میتوان اینکار را کرد اعداد مورد نظر را چاپ و در غیر این صورت no answer چاپ کنید

مثال :
ورودی :
3
1 10 22
11
جواب :
1 10

مثال 2:
ورودی:
2
2 5
4
خروجی:
no answer​

 

[navidjalalmanesh]

پاسخ : Backtrack یکی از ایده های مهم حل مسایل

چون مرحله ی بعدی المپیاد کامپیوتر در پیشه و احتمالا سوال هایی که در این مرحله داده خواهد شد اکثرا به backtrack احتیاج خواهند داشت...
​

سوال هایی که تو مرحله 2.5 بهتون می دن اکثرا ایده خور و با یه بار برنامه نویسی معمولی (نه خیلی سخت نه خیلی آسون) هستن. به نظر من بلد بودن بک ترک در حد مقدماتی خوبه (همین دو سه تا سوال که حل کردین) , اما بیشتر از این به کارتون نمی یاد توی این مرحله . حل سوالات project Euler اولویتتون باشه .

توضیحاتی که کمیته پارسال راجع به مرحله 2.5 داده بود


این هم سوالات مرحله 2.5 سال 1389 :

آزمون آزمایشی

روز اول

روز دوم

 

[erfankh]

پاسخ : Backtrack یکی از ایده های مهم حل مسایل

#include<iostream>
#include<vector>
using namespace std;
int n,k,a[1000],l[1000];
vector<int> ans;
bool p=0;
void Bi(int x,int h,int t){
 if(h==n){
  if(x==k){
   p=1;
   for(int i=0;i<t;i++)ans.push_back(l[i]);
  }
  return;
 }
 l[t]=a[h];
 Bi(x+a[h],h+1,t+1);
 Bi(x,h+1,t);
}
int main(){
 cin>>n;
 for(int i=0;i<n;i++)cin>>a[i];
 cin>>k;
 Bi(0,0,0);
 if(p){
  for(int i=0;i<ans.size();i++){
   cout<<ans[i];
   if(i<ans.size()-1)cout<<" ";
  }}
  else  cout<<"no answer";
  cout<<endl;
  cin>>n;
  return 0;
 }

درست هست؟

 

[erfan_a2a]

پاسخ : Backtrack یکی از ایده های مهم حل مسایل

سوال هایی که تو مرحله 2.5 بهتون می دن اکثرا ایده خور و با یه بار برنامه نویسی معمولی (نه خیلی سخت نه خیلی آسون) هستن. به نظر من بلد بودن بک ترک در حد مقدماتی خوبه (همین دو سه تا سوال که حل کردین) , اما بیشتر از این به کارتون نمی یاد توی این مرحله . حل سوالات project euler اولویتتون باشه .

شما سوال ها رو نگاه کردین؟
مثلا تو آزمون آزمایشی سوال ماهی و خیلی دیگه از سوال ها

 

[erfankh]

پاسخ : Backtrack یکی از ایده های مهم حل مسایل

درست هست آقای عبدی؟؟

 

[navidjalalmanesh]

پاسخ : Backtrack یکی از ایده های مهم حل مسایل

شما سوال ها رو نگاه کردین؟
مثلا تو آزمون آزمایشی سوال ماهی و خیلی دیگه از سوال ها

راه حل سوال ماهی بدون بک ترک بود (می شد با بک ترک هم پیاده سازی کرد اون قسمت ایجاد کردن حالت های مختلف رو اما بدون بک ترک هم می شد) [Solution هاش توی همون لینکی که توی پست قبلی دادم هست , می تونید کد سوال 5 رو نگاه کنید] .

من نمی گم بک ترک بلد نباشید , می گم دغدغه اصلی تون باید تسلط بر سوال های مثل سوال های Project Euler باشه.

 

[erfankh]

پاسخ : Backtrack یکی از ایده های مهم حل مسایل

ببخشید
این سوال ماهی دقیقا کدوم سواله؟

 

[navidjalalmanesh]

پاسخ : Backtrack یکی از ایده های مهم حل مسایل

ببخشید
این سوال ماهی دقیقا کدوم سواله؟

سوال 5 ام این امتحانه : Final Bahman

 

[erfankh]

پاسخ : Backtrack یکی از ایده های مهم حل مسایل

آقای عبدی درست هست؟
:53

 

[erfan_a2a]

پاسخ : Backtrack یکی از ایده های مهم حل مسایل

سلام
من چند روز پیش خوندم کد شما رو درست بود ولی دیگه چیزی ننوشتم ببخشید
ان شا الله به زودی یک سول دیگه میگذارم

 

[erfan_a2a]

پاسخ : Backtrack یکی از ایده های مهم حل مسایل

سلام

ببخشید من امتحانام شروع شده یک مقدار حضورم کم رنگ شده .

خوب یک سوال در زیر نوشتم :
در ورودی عدد n داده شده است. یک جدول n*1 را خوب مینامیم اگر با دو رنگ سفید و سیاه رنگ شده باشد و اگر خانه ای سیاه رنگ شده بود حد اقل یکی از دو خانه ی جلویی آن سیاه رنگ باشد . برای دو خانه آخر که دو خانه ی جلویی ندارند شما فرض کنید هر حالتی میتوانند داشته باشند یعنی هم میتوانند سیاه باشند هم سفید
چند جدول خوب n*1 داریم؟

 

[erfankh]

پاسخ : Backtrack یکی از ایده های مهم حل مسایل

کد:
جدول خوب

 

[erfankh]

پاسخ : Backtrack یکی از ایده های مهم حل مسایل

درست هست کدم؟؟

 

[erfan_a2a]

پاسخ : Backtrack یکی از ایده های مهم حل مسایل

سلام

نه متاسفانه درست نیست زیرا مثلا برای n=2 جواب میده 3 در حالی که جواب میشه 4

ببین این که گفتم برای دو خانه ی آخر میتوانیم هر حالتی داشته باشیم یعنی چهار حالت داره میتونه سفید یا سیاه هر چی بخواد باشه من کد درست رو میگذارم :

#include<iostream>
using namespace std;
 
int bt(int x,int n1,int n2){
 if(x==0)
  return 1;
 if(n1 || n2)
  return bt(x-1,1,n1) + bt(x-1,0,n1);
 return bt(x-1,0,n1);  
}
int main(){
 int n;
 cin>>n;
 cout<<bt(n,1,1)<<endl;
}