矩形中分出正方形，递归优化

科技前沿 • 2025-01-26 09:50 • 阅读 63

大家好，我是讯享网，很高兴认识大家。

1103: 地盘划分
最少可以划分多少个正方形，1个？NO，是指充分划分,也就是
剩下的部分不能再划分了，所以每次割正方形都要割一个最大的正方形
//3 * 4的矩形，依次可以分隔成3 * 4->3 * 3, 3 * 1，

1、要对递归进行优化呀，不管是否超时都要追求好的算法
2、本来想用一个数组来记录已经找过的状态，以便下次查询，不仅想法不靠谱
//const int MAX=1e5+2;
//int a[MAX][MAX];只是定义了一个这样大的数组在New Online Judge上就报错

讯享网

/usr/bin/ld: failed to convert GOTPCREL relocation; relink with
–no-relax collect2: error: ld returned 1 exit status
网上对这个报错说法不一，有一个说到是全局变量中开了一个过大的数组，把定义数组的语句注释掉，果然不再编译错误
/usr/bin/ld: failed to convert GOTPCREL relocation; relink with --no-relax
collect2: error: ld returned 1 exit status

#include<iostream> #include<algorithm> using namespace std; //const int MAX=1e5+2; //int a[MAX][MAX];只是定义了一个这样大的数组在New Online Judge上就报错 int fun(int m,int n){ 
    if(m==n)return 1; else if(m>n)swap(m,n); // return fun(n-m,m)+1;//简单这样会超时 if(n%m==0)return n/m; else return fun(m,n%m)+n/m;//3 4  } int main(){ 
    int n,m; while(cin>>n>>m){ 
    cout<<fun(m,n)<<endl; } return 0; }

讯享网

矩形中分出正方形，递归优化

相关推荐