优化递归函数

-2

对于n = 18，我的代码在1GHz机器上花费的时间超过0.5秒。我认为这是由于我使用递归函数，但我并不真正知道如何优化此代码，因为它实际上只是“打印”数字...... 因此，也许问题来自这样一个事实：我正在使用递归函数。优化递归函数

这里是我的代码：

#include<iostream> 

void singleSquareRemove (int s) 
{ 
    if (s == 1) 
    { 
     std::cout << 1 << std::endl; 
     return; 
    } 
    else 
    { 
     for (int i = s-1; i >=1; --i) 
    singleSquareRemove(i); 
     std::cout << s << std::endl; 
    } 
} 
void whenSquareisFull (int v) 
{ 
    if (v == 1) 
    { 
     std::cout << 1 << std::endl; 
     return; 
    } 
    else if (v == 2) 
    { 
     std::cout << 2 << std::endl; 
     return; 
    } 
    else if (v == 3) 
    { 
     std::cout << 1 << std::endl; 
     std::cout << 3 << std::endl; 
     return; 
    } 
    else 
    { 
     whenSquareisFull(v-2); 
     for (int i = v-3; i > 0; --i) 
    singleSquareRemove(i); 
     std::cout << v << std::endl; 
    } 
} 
int main() 
{ 

    unsigned int n {0}; 
    std::cin >> n; 

    whenSquareisFull(n); 
    for (int i = n-1; i > 0; --i) 
    { 
     singleSquareRemove(i); 
     } 

}

来源

2017-10-17 Salutsalut1

简介，评估和优化热点，重复。 – crashmstr

通常情况下，你必须进行基准测试等，但是'std :: endl'可能会占用很多时间。 – Rakete1111

我认为这可能会有所帮助，如果您将递归调用作为尾调用，以便可以通过编译器进行优化。 –

的时间接收器是在您打印的价值和冲洗输出（std::endl）。

您可以通过使用“缓冲区”类型（如std::vector）然后迭代打印来避免该时间陷入。通过这种方式，时间花在了实际的“计算”上，然后您可以进行分析，而不是花时间打印输出。使用

示例代码：

#include <iostream> 
#include <vector> 

static std::vector<int> values; 

void singleSquareRemove (int s) 
{ 
    for (int i = s - 1; i >= 1; --i) 
     singleSquareRemove(i); 
    values.push_back(s); 
} 

void whenSquareisFull (int v) 
{ 
    switch (v) { 
     case 1: case 2: 
      values.push_back(v); 
     break; 
     case 3: { 
      values.push_back(1); 
      values.push_back(v); 
     } break; 
     default: { 
      whenSquareisFull(v - 2); 
      for (int i = v - 3; i > 0; --i) singleSquareRemove(i); 
      values.push_back(v); 
     } break; 
    } 
} 

int main() 
{ 
    unsigned int n {0}; 
    std::cin >> n; 
    // start timing here 
    whenSquareisFull(n); 
    while (--n > 0) singleSquareRemove(n); 
    // stop timing here 
    for (auto itr = values.begin(); itr != values.end(); ++itr) 
     std::cout << *itr << std::endl; 
    return 0; 
}

希望帮助！

来源

2017-10-17 20:22:45 txtechhelp

优化递归函数

回答

相关问题