尾遞迴

10611014 2021-08-09 15:09:23 ‧ 922 瀏覽

分享至

#include<iostream>
#include<string>
using namespace std;
int f(int,int);
int f(int m,int n)
{
   if(m==0||n==0)
   return 1;
   else
   return f(m-1,n)+f(m,n-1);
}
int main()
{   
    int m,n;
    cin>>m>>n;
    if(m>=1&&n<=35)
    cout<<f(m,n)<<endl;
    
    system("pause");
    return 0;
 }

石頭 iT邦高手 1 級 ‧ 2021-08-09 15:22:30 檢舉

雖然我不清楚你的需求但你的時間複雜度是階乘非常吃效能
這邊給你個方向你可以嘗試使用Cache Mapping來存放計算過後的值這樣可以減少很多計算效能

登入發表討論

直播研討會

{{ item.channelVendor }} {{ item.webinarstarted }} |

直播中

3 個回答

wrxue

iT邦好手 1 級 ‧ 2021-08-09 15:33:22

#include<iostream>
#include<string>
using namespace std;
int main()
{   
    int m,n;
    cin>>m>>n;
    long int arr[m + 1][n + 1];
    if(m>=1&&n<=35) {
        for (int i = 0; i <= m; i++) {
            for (int j = 0; j <= n; j++) {
                if (i == 0 || j == 0) {
                    arr[i][j] = 1;
                    continue;
                }
                arr[i][j] = arr[i - 1][j] + arr[i][j - 1];
            }
        }
        cout<<arr[m][n]<<endl;
    }
    
    system("pause");
    return 0;
}

用遞迴的資源都消耗在 stack 上，不要說 當m和n的值越大，程式跑出答案速度較慢，m/n 大到一個程度還讓你 stack overflow 算不下去。
改用陣列存值會輕鬆許多，該陣列還能重複使用，邊際成本遞減明顯