[C语言]连续因子—–穷举 | 祭夜の咖啡馆
  • 今天,还是不知道如何正确地处理事件。

  • 充值系统已开放,修复了一些BUG

  • 各项服务恢复正常

  • 修复在线人数的显示

  • 修复了Baidu与Github登陆的小Bug

  • 优化网站整体代码布局,提高速度

[C语言]连续因子—–穷举

C语言 祭夜ゐ 3周前 (11-01) 43次浏览 已收录 0个评论 扫描二维码
文章目录[隐藏]

前言

额,这个题好像有点问题(同学指出的,我也同意这个问题),详见题目中的修改部分
 

题目

一个正整数  的因子中可能存在若干连续的数字。例如 630 可以分解为 3567,其中 5、6、7 就是 3 个连续的数字。给定任一正整数 ,要求编写程序求出最长连续因子的个数,并输出最的连续因子序列。

输入格式:

输入在一行中给出一个正整数 )。

输出格式:

首先在第 1 行输出最长连续因子的个数;然后在第 2 行中按 因子1*因子2*……*因子k 的格式输出最的连续因子序列,其中因子按递增顺序输出,1 不算在内。

输入样例:

630

输出样例:

3
5*6*7

 

为什么有问题 #(疑问)

对于630可以分解成2*3*3*5*73*5*6*7

很明显根据输出判断,结果要的是最长的具有连续性的因子(前者最长连续为2*3,相较于后者的最长连续为5*6*7显然短了)

因此,判断题目描述不正确。

思路

根据上面的分析,可以知道输出的这一串连续因子的乘积输入值的因子,

那么可以制造一个比较长的连续因子的乘积(越长意味着这个积的因子起始值较小),比如2*3*4*5*6*7*8*9

并且这个积开始要大于甚至等于输入值。

为什么要靠近?

因为,存在一些这样的数:2*3*4*5*6 = 720,懂了吧 #(滑稽)

然后用输入值对其进行取余操作,如果取余结果是0就输出,否则就改变积的组成

如何改变积的组成?

像这样:

[C语言]连续因子-----穷举

从最长长度开始,每次都把某一固定长度的所有可能情况都过一遍。

如何判断最长长度?

题目给出了输入值的范围: 

而我们判断最长长度的因子乘积大小为n!(假设最长长度为n-1)

因为,2³¹ = 2 147 483 648,13! = 6 227 020 800,12! = 479 001 600

12! < 2³¹ <13! ,由此可以设定长度为12,即最长长度的因子的乘积大小为13!

 正式处理

1.由于是在固定因子长度的情况下穷举所有连续可能性,因此第一层循环为因子长度(即数量)

2.确定长度后,要执行的操作是从2开始依次往后移动起始值,于是,第二层循环为因子起始值的改变(为什么用循环?这不是废话吗 #(受虐滑稽)

3.确定长度与起始值后,根据这两个来计算“因子”的乘积(累乘,不过存储的容器最好大点 #(流汗滑稽) ),

4.用输入值对得到的积进行取余,为0就说明就是它了,别找了,输出一下就跑了 #(cos滑稽)

不是0就让起始值后移,不能后移就减小长度。。。。。

注意:起始值的确定

如果a*b = c(a<b),那么当a增加到b时,b也相应的减少到a。

因此,当a=b=√c 时a就算是到达最大值了。

对于本题若起始值是a,同时我们默认b>a总是成立(因为后面的值至少比a大1),

所以一旦a超过√c(这里的c是输入值),连续因子的积必然大于输入值;

所以,后面的操作都是无意义的

贴代码

还是那样,代码并非最优,仅供参考。你可以将累乘写成函数,那样程序将具有模块化风格。
/**
 * 一个正整数 N 的因子中可能存在若干连续的数字。例如 630 可以分解为 3×5×6×7,其中 5、6、7 就是 3 个连续的数字。给定任一正整数 N,要求编写程序求出最长连续因子的个数,并输出最小的连续因子序列。
 * 输入在一行中给出一个正整数 N(1<N<2的31次方 )。
*/

#include <stdio.h>
#include <math.h>

int main(void)
{
    int N;
    int m;
    int len;
    int i,j,t;
    int max;
    long long int sum;
    scanf("%d", &N);
    max = sqrt(N);

    //定长度
    for (len = 11; len >= 1; len--)
    {
        //定起始值
        for (j = 2; j <= max; j++)
        {
            //初始化
            sum = 1;
            m = len;
            t = j;

            //累乘
            while (m--)
            {
                sum *= t++;
                if (sum > N)
                {
                    break;
                }
                
            }

            //取余
            if (N % sum == 0)
            {
                printf("%d\n%d", len, j);
                for (i = j+1; i < t; i++)
                {
                    printf("*%d", i);
                }
                return 0;
            }
            
        }
    }

    printf("1\n%d\n", N);
    return 0;
}

 

总结

做题时注意审题,并且尽量观察程序输出结果,并以输出结果为参考标准,因为出题人一般都不是什么好东西,不会检查描述问题。
随便写写,不要当真。 #(受虐滑稽)


祭夜blog , 版权所有丨如未注明 , 均为原创丨本网站采用BY-NC-SA协议进行授权
转载请注明原文链接:[C语言]连续因子—–穷举
喜欢 (0)
[1690127128@qq.com]
分享 (0)
发表我的评论
取消评论
表情 贴图 加粗 删除线 居中 斜体 签到

Hi,您需要填写昵称和邮箱!

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址