Giải thích code đệ quy c++

[hockotg (Moon Cactus)]

Một máy ATM hiện có n < = 20 tờ tiền có giá t1, t2.t3…tn. Hãy đưa ra mộtcách trả với số tiền đúng bằng s. Dữ liệu vào từ file “ATM.INP” có dạng:

• Dòng đầu là 2 số n và s.
• Dòng thứ 2 gồm ’ số t1, t2…tn.
  Kết quả ra file “ATM.OUT” có dạng: Nếu có thể trả đúng thì đưa ra cách trả, nếu không ghi -1.
  ATM.INP

10 390
200 10 20 20 50 50 50 50 100 100

ATM.OUT

20 20 50 50 50 100 100

#include<bits/stdc++.h>

#define nmax 100100
#define ll long long
using namespace std;
ll atm[nmax];
ll rut[nmax];
ll danhdau[nmax];
ll n,sn;
ll s,sum;
void inkq()
{
    for(int i=1; i<=n; i++)
    {
       //cout << danhdau[i]<<" ";
    }
}
void backtrack(ll index)
{
    if(sn)
    {
        return ;
    }
    for(int j=0; j<=1; j++)
    {
        danhdau[index]=j;
        sum+=j*atm[index];
        if(index==n)
        {
            if(sum==s)
            {   sn++;
                inkq();
            }
        }
        else
        {
            backtrack(index+1);
        }
        sum=sum-j*atm[index];

    }
     cout << index <<endl;
}
int main()
{   sn=0;
    cin>>n>>s;
    for(int i=1; i<=n; i++)
    {
        cin>>atm[i];
    }
    backtrack(1);
}

Đây là bài máy rút tiền atm. Cho em hỏi là tại sao khi index==n ấy tức là index==10 ấy thì tại sao nó lại quay về bằng 9 ạ?

[Reborn (David Martin)]

Ko thể hiểu bạn đang code cái gì so với cái đề có ăn nhập gì với nhau? càng ko hiểu câu hỏi của bạn.

[hockotg (Moon Cactus)]

ui sorry mình dùng quay lùi để giải quyết bài này , trong quá trình gọi đệ quy thì mình thử in ra chỉ số của phần tử trong mảng , lúc nó duyệt đến chỉ số cuối cùng của mảng thì nó in ra chỉ số lần đầu tiên là 10 , sau đó là 10 một lần nữa. nhưng cái mình ko hiểu đây là tại sao trong chương trình mình không viết lệnh giảm đi giá trị của chỉ số mà nó vãn tiếp tục giảm đi một đơn vị xuống 9 rồi nó lại quay lại 10 …

[library (La biblioteca)]

@hockotg

for(int j=0; j<=1; j++)
{
    danhdau[index]=j;
    sum+=j*atm[index];
    if(index==n)
    {
        if(sum==s)
        {   sn++;
            inkq();
        }
    }
    else
    {
        backtrack(index+1);
    }
    sum=sum-j*atm[index];

}
 cout << index <<endl;

Thử suy nghĩ TH này nhé cậu, tại thời điểm index của cậu bằng 9 (khi gọi backtrack(9)):

1. Khi thực hiện backtrack(9), vòng lặp đầu tiên, index == n (10) trả về false, chúng ta gọi backtrack(10)
2. Khi thực hiện backtrack(10), index == n (10) trả về true ở cả 2 vòng lặp, cout << index <<endl sẽ in ra 10, backtrack(10) kết thúc và quay lại backtrack(9).
3. Ở backtrack(9), vòng lặp thứ 2, bước (1), (2) thực hiện lại 1 lần nữa => cậu sẽ có thêm 1 lần in ra số 10 nữa.
4. Kết thúc vòng lặp trong backtrack(9), cout << index <<endl; in 9 ra màn hình.

Hi vọng nó giúp cậu giải thích được hoạt động của code.

[hockotg (Moon Cactus)]

cho mình hỏi xíu nữa tại sao nó lại quay về backtrack(9) hả bạn trong khi mình ko có câu lệnh nào để giảm giá trị của index từ 10 xuống 9 cả

[hockotg (Moon Cactus)]

à mình hiểu rồi bạn mình cảm ơn bạn nha