• 设为首页
  • 点击收藏
  • 手机版
    手机扫一扫访问
    迪恩网络手机版
  • 关注官方公众号
    微信扫一扫关注
    迪恩网络公众号

将一个正整数表示为连续自然数的和(附C实现源码)(原创)

原作者: [db:作者] 来自: [db:来源] 收藏 邀请

问题描述:将一个正整数表示为两个或这个两个以上的连续自然数的和。给定一个数,输出所有的可能的结果。
例如:
3=1+2;
9=4+5;
9=2+3+4;
解决方法:
对于给定的整数n,求解基本思路如下,
1)用两个变量slow和fast分别表示连续自然数的最小数和最大数;
2)首先令slow=1,fast=2,他们是可能表示为n的初始集合。
3)while(slow < fast)
当slow到fast的和大于n时,令slow++,相当于从集合中删掉较小的元素;
当slow到fast的和小于n时,令fast++,相当于添加新元素到集合
当slow到fast的和等于n时,输出slow到fast之间(包括slow和fast)的整数,即要求的连续自然数;并且令slow++(求下一组)
C语言实现的的源码如下(VC编译器)


#include 
#include 
//将一个整数表示为连续自然数的和,例如:
//3=1+2
//9=4+5
//9=2+3+4


void pnt(int n, int low, int fast)
{
    printf("%d=",n);
    int i;
    for(i = low; i < fast; ++i)
        printf("%d+", i);
    printf("%d", fast);
    printf("\n");
}

//时间复杂度O(N)

//找到结果集返回1

//否则返回0
int gen(int n)
{
    int ret = 0;//·µ»ØÖµ
    int slow = 1;
    int fast = 2;
    int sum = 3;
    while(slow < fast)
    {
        if(sum > n)
        {
            sum -= slow;
            slow++;
        }
        else if(sum < n)
        {
            fast++;
            sum += fast;
        }
        else
        {
            ret = 1;
            pnt(n, slow, fast);
            sum -= slow;
            slow++;
        }
    }
    return ret;
}

//testing
int main()
{
    int i;
    for(i = 1; i <= 20; ++i)
    {
        if(gen(i) == 0)
        {
            printf("%d=N/A\n", i);
        }
        printf("-----------------------------------\n");
    }
    system("pause");
    return 0;
}

运行结果如下:


鲜花

握手

雷人

路过

鸡蛋
专题导读
上一篇:
LIBSVM使用教程发布时间:2022-05-14
下一篇:
使用PBM文件图形化显示随机数组(原创)发布时间:2022-05-14
热门推荐
阅读排行榜

扫描微信二维码

查看手机版网站

随时了解更新最新资讯

139-2527-9053

在线客服(服务时间 9:00~18:00)

在线QQ客服
地址:深圳市南山区西丽大学城创智工业园
电邮:jeky_zhao#qq.com
移动电话:139-2527-9053

Powered by 互联科技 X3.4© 2001-2213 极客世界.|Sitemap