CODEWITHSUNDEEP
c++vectorstaticdynamic-programmingmemoization
Soumadeep Saha
Soumadeep Saha

Reputation: 335

How to reset a static vector inside a function?

I am trying to solve a certain problem on an online judge using the Dynamic Programming paradigm. I have written a function which memoizes the results of smaller subproblems. But this function will be called t times in a single run. So when the function calls itself I want its "Memory" to be preserved, but when it is called from the driver I wan't the vector to be reset. How do I do that? I think having a global vector and reseting it after each call from the driver is possible, but as I have learnt from books and stack overflow that is "bad programming style". So what is a good sollution to this problem? Heres the code :

class mem{
public:    
        bool mike_win;
    bool written;

};
bool calc(int a){
    static vector<mem> memory(a);
    if( a == 1){
            return false;
    }
    if(memory[a-1].written == true){
        return (!(memory[a-1].mike_win))
    }
    vector<int> div_list = divis(a);
        //^^ divis is a function which takes a number and returns 
        //all its divisors in descending order in a vector<int>

    for(vector<int>::iterator i = div_list.begin();i != div_list.end();i++){
        if ( ! ( calc( a / (*i) ))){
            memory[a-1].written = true;
            memory[a-1].mike_win = true;
            return true;
        }
    }
    if(calc(a-1 ) == false){
        memory[a-1].written = true;
        memory[a-1].mike_win = true;
        return true;
    }
    else{
        memory[a-1].written = false;
        memory[a-1].mike_win = false;
        return false;
    }

}

Heres a link to the question. And heres the function divis :

vector<int> divis(int a){

    vector<int> div_list(int a )
        if(a==2){
                return div_list;
        }
        int k = sqrt(a);
        for(int i=2;i<=k;i++){
            if(!(a%i)){
                    div_list.push_back(i);
                    div_list.push_back(a/i);
            }
        }
        sort(div_list.rbegin(),div_list.rend());
        div_list.erase(unique(div_list.begin(),div_list.end()),div_list.end());
        return div_list;
}

Upvotes: 2

Views: 595

Answers (1)

chbaker0
chbaker0

Reputation: 1808

I think the way I would do it is to create two overloads of calc: on that takes just int as a parameter, and another that takes an int and a reference to vector<int>. That way, a user will call the first overload, which will create the temporary vector for memorization, and pass it to the second function, which passes the reference upon recursion. Kinda like this:

bool calc(int a, vector<int>& memory)
{
    // Do your stuff here
    // Instead of calling it as calc( a / (*i) ), just call
    // it as calc( a / (*i) , memory )
}

bool calc(int a)
{
    vector<int> memory(a);
    calc(a, memory);
}

That way, you avoid having to do any sort of book-keeping in the heart of your algorithm to determine whether to clear the vector or not; it will be done automatically after the first call returns.

Upvotes: 3

Related Questions