一本通——分解因数

1001-高同学

发表文章数:265

热门标签

首页 » LeetCode » 正文

思路:对当前的数进行分析,如果是因数并且小于等于下一个因数,则进行递归。

#include <bits/stdc++.h>
using namespace std;

#define MAXN 300
int visited[MAXN];
int cnt;
bool flag=true;

void tracback(int x,int n)
{
    int i;

    for(i=x; i<=n; i++)
    {
        if(n%i==0&&i<=n/i)
        {
            cnt++;
            tracback(i,n/i);
        }
    }
}
int main()
{
    int t,n;
    cin>>t;
    while(t--)
    {
        cnt=1;
        cin>>n;
        tracback(2,n);
        cout<<cnt<<endl;
    }
    return 0;
}

另附一道与本题思路相似的题目:

链接:http://ybt.ssoier.cn:8088/problem_show.php?pid=1318

 

1、对当前的数与和进行递归

2、用visited数组存放的是其数值

代码:

#include <bits/stdc++.h>
using namespace std;
int n;
#define MAXN 300
int visited[MAXN];
int cnt;
bool flag=true;

void tracback(int x,int m,int step)
{
    int i;

    for(i=x; i<=n-m; i++)
    {
        if(i==n)
            return ;
        if((i+m)<n)
        {
            visited[step]=i;
            tracback(i,m+i,step+1);
        }
        if((i+m)==n)
        {
            visited[step]=i;
            cout<<n<<"=";
            flag=true;
            for(int j=1; j<=step; j++)
            {
                if(flag)
                    flag=false;
                else
                    cout<<"+";
                cout<<visited[j];
            }
            cout<<endl;
            return ;
        }
    }
}
int main()
{
    cin>>n;

    tracback(1,0,1);

    return 0;
}

 

标签:

拜师教育学员文章:作者:1001-高同学, 转载或复制请以 超链接形式 并注明出处 拜师资源博客
原文地址:《一本通——分解因数》 发布于2020-02-12

分享到:
赞(0) 打赏

评论 抢沙发

评论前必须登录!

  注册



长按图片转发给朋友

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

微信扫一扫打赏

Vieu3.3主题
专业打造轻量级个人企业风格博客主题!专注于前端开发,全站响应式布局自适应模板。

登录

忘记密码 ?

您也可以使用第三方帐号快捷登录

Q Q 登 录
微 博 登 录