Как сбросить статический вектор внутри функции?
Я пытаюсь решить определенную проблему в онлайн-судье, используя Динамическое программирование парадигма. Я написал функцию, которая запоминает результаты небольших подзадач. Но эта функция будет называться т раз за один раз. Поэтому, когда функция вызывает себя, я хочу, чтобы ее «Объем памяти» чтобы сохранить, но когда он вызывается из драйвера, я не хочу сбрасывать вектор. Как я могу это сделать? Я думаю, что иметь глобальный вектор и переустанавливать его после каждого вызова драйвера возможно, но, как я узнал из книг и переполнения стека, это «плохой стиль программирования». Так что же является хорошим решением этой проблемы? Вот код:
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;
}
}
Вот ссылка на вопрос. И вот функция деления:
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;
}
Решение
Я думаю, что способ сделать это состоит в том, чтобы создать две перегрузки calc: на что требуется всего лишь int в качестве параметра, а другой, который принимает int и ссылка на vector<int>, Таким образом, пользователь вызовет первую перегрузку, которая создаст временный вектор для запоминания, и передаст его второй функции, которая передает ссылку при рекурсии. Вроде как:
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);
}
Таким образом, вы избегаете необходимости какого-либо бухгалтерского учета в основе вашего алгоритма, чтобы определить, очищать вектор или нет; это будет сделано автоматически после первого звонка.
Другие решения