【编程练习】正整数分解为几个连续自然数之和

题目:输入一个正整数,若该数能用几个连续正整数之和表示,则输出所有可能的正整数序列。

一个正整数有可能可以被表示为n(n>=2)个连续正整数之和,如:
15=1+2+3+4+5
15=4+5+6
15=7+8

有些数可以写成连续N(>1)个自然数之和,比如14=2+3+4+5;有些不能,比如8.那么如何判断一个数是否可以写成连续N个自然数之和呢?

一个数M若可以写成以a开头的连续n个自然数之和,则M=a+(a+1)+(a+2)+…+(a+n-1)=n*a+n*(n-1)/2,要求a!=0,否则就是以a+1开头的连续n-1个整数了,也就是要求(M-n*(n-1)/2)%n==0,这样就很容易判断一个数可不可以写成连续n个自然数的形式了,遍历n=2…sqrt(M)*2,还可以输出所有解。

void divide(int num)
{
    int i,j,a;
    for(i=2; i<=sqrt((float)num)*2; ++i)
    {
        if((num-i*(i-1)/2)%i==0)
        {
            a=(num-i*(i-1)/2)/i;
            if(a>0)
            {
                for(j=0; j<i; ++j)
                    cout<<a+j<<" ";
            }
            cout<<endl;
        }
    }
}  

第二个问题是什么样的数可以写成连续n个自然数之和,什么样的数不能?

通过编程实验发现,除了2^n以外,其余所有数都可以写成该形式。下面说明为什么。
若数M符合条件,则有M=a+(a+1)+(a+2)+…+(a+n-1)=(2*a+n-1)*n/2,而2*a+n-1与n肯定一个为奇数一个为偶数,即M一定要有一个奇数因子,而所有2^n都没有奇数因子,因此肯定不符合条件。
再证明只有M有一个奇数因子,即M!=2^n,M就可以写成连续n个自然数之和。假设M有一个奇数因子a,则M=a*b。

  1. 若b也是奇数,只要b-(a-1)/2>0,M就可以写成以b-(a-1)/2开头的连续a个自然数;将这条结论里的a和b调换,仍然成立。15=3*5=1+2+3+4+5=4+5+6.
  2. 若b是偶数,则我们有一个奇数a和一个偶数b。
  • 2.1 若b-(a-1)/2>0,M就可以写成以b-(a-1)/2开头的连续a个自然数。24=3*8=7+8+9.
  • 2.2 若(a+1)/2-b>0,M就可以写成以(a+1)/2-b开头的连续2*b个自然数。38=19*2=8+9+10+11.

上述两个不等式必然至少有一个成立,所以可以证明,只要M有一个奇数因子,就一定可以写成连续n个自然数之和。

另一个正整数分解的算法:
sum(i,j)为i累加到j的和 
令 i=1 j=2 
if sum(i,j)>N i++ 
else if sum(i,j)<N j++ 
else cout i...j

参考代码:

#include <iostream>
using namespace std;  

int add(int m,int n)
{
    int sum=0;
    for(int i=m;i<=n;i++)
        sum+=i;
    return sum;
}  

void divide(int num)
{
    int i=1,j=2,flag;
    int sum=0;
    while(i<=num/2)
    {
     sum=add(i,j);
     while(sum!=num)
     {
        if(sum>num)
            i++;
        else
            j++;
        sum=add(i,j);
     }
     for(int k=i;k<=j;k++)
        cout<<k<<" ";
     ++i;
     cout<<endl;
    }
}  

int main()
{
    int num;
    cout<<"Please input your number:"<<endl;
    cin>>num;
    divide(num);
    return 0;
}  

时间: 2024-10-24 14:11:57

【编程练习】正整数分解为几个连续自然数之和的相关文章

正整数分解为几个连续自然数之和

题目:输入一个正整数,若该数能用几个连续正整数之和表示,则输出所有可能的正整数序列. 一个正整数有可能可以被表示为n(n>=2)个连续正整数之和,如: 15=1+2+3+4+5 15=4+5+6 15=7+8 有些数可以写成连续N(>1)个自然数之和,比如14=2+3+4+5:有些不能,比如8.那么如何判断一个数是否可以写成连续N个自然数之和呢? 一个数M若可以写成以a开头的连续n个自然数之和,则M=a+(a+1)+(a+2)+-+(a+n-1)=n*a+n*(n-1)/2,要求a!=0,否则

自然数M拆分为连续自然数之和

有些数可以写成连续N(>1)个自然数之和,比如14=2+3+4+5:有些不能,比如8.那么如何判断一个数是否可以写成连续N个自然数之和呢?这是这一节的基本问题. 一个数M若可以写成以a开头的连续n个自然数之和,则M=a+(a+1)+(a+2)+-+(a+n-1)=n*a+n*(n-1)/2,要求a!=0,否则就是以a+1开头的连续n-1个整数了,也就是要求(M-(n+n*(n-1)/2))%n==0,即(M-(n*(n+1)/2))%n==0,这样就很容易判断一个数可不可以写成连续n个自然数的形

将一个正整数分解质因数

查看全套"c语言习题集" 题目: 将一个正整数分解质因数.例如:输入90,打印出90=2*3*3*5. 程序分析:对n进行分解质因数,应先找到一个最小的质数k,然后按下述步骤完成: (1)如果这个质数恰等于n,则说明分解质因数的过程已经结束,打印出即可. (2)如果n<>k,但n能被k整除,则应打印出k的值,并用n除以k的商,作为新的正整数你n,重复执行第一步. (3)如果n不能被k整除,则用k+1作为k的值,重复执行第一步. 2.程序源代码: #include "

算法题-把一个正整数分解为几个不同的正整数之和,打印出所有组合。

问题描述 把一个正整数分解为几个不同的正整数之和,打印出所有组合. 笔试遇到的一个题,不会做.从网上搜,只搜到求积最大的一个组合.有会的帮忙解决下,多谢,最好说下算法思路,能有c源码最好

Java实现将一个正整数分解质因数

* 题目:将一个正整数分解质因数.例如:输入90,打印出90=2*3*3*5. * 分析:对n进行分解质因数,应先找到一个最小的质数k,然后按下述步骤完成: *(1)如果这个质数恰等于n,则说明分解质因数的过程已经结束,打印出即可. *(2)如果n>k,但n能被k整除,则应打印出k的值,并用n除以k的商,作为新的正整数你n,重复执行第一步. *(3)如果n不能被k整除,则用k+1作为k的值,重复执行第一步. *这个题目很明显是要用递归算法来实现的,打印"*"有些技巧,但也很容易解

iostream-将一个正整数分解质因数。例如:输入 90, 打印出 90=2*3*3*5

问题描述 将一个正整数分解质因数.例如:输入 90, 打印出 90=2*3*3*5 #include using namespace std; void fnabs(int n) { int i; for(i=2;i<=n;i++) { while(n%i==0) {n/=i; cout<<"*"<<i;} } } int main() { int n; n=90; cout<<n<<"="; fnabs(n);

将一个正整数表示为连续自然数的和

原文:将一个正整数表示为连续自然数的和 将一个正整数表示为连续自然数的和,比如给定整数15,那么根据题意,需要输出的连续自然数为1+2+3+4+5=4+5+6=7+8=15.题目中的连续自然数序列可以看做一个升序的有序数组,取数组前两个数为起始的区间的左右两个端点.对区间中的值进行累加,如果累加值小于给定的整数时,那么右端点向右移动,添加下一个数字,如果累加值大于给定的整数时,那么左端点向右移动,表示去掉最左端的最小值,如果值与给定整数相等,那么输出后,需要重新对定区间左右两个端点赋值,直到左端

求完美数

一个数如果恰好等于它的因子之和,这个数就称为"完美数"或"完数".例如6=1+2+3.(6的因子是1,2,3) 完美数的一些性质: 欧几里德证明了:一个偶数是完数,当且仅当它具有如下形式:2(p-1)×(2p-1) 其中p和(2p-1)是素数. 尽管没有发现奇完数,但是当代数学家奥斯丁·欧尔(Oystein Ore)证明,若有奇完全数,则其形状必然是12p+1或36p+9的形式,其中p是素数.在1018以下的自然数中奇完数是不存在的. 除6以外的偶完数,把它的各位数

《从问题到程序:用Python学编程和计算》——3.5 练习

3.5 练习 概念和理解 1. 复习下面概念:数值积分,区间分割法,舍入误差,简单重复,累积,累积变量,生成和筛选,递推,递推变量,素数(质数),因子和真因子,哥德巴赫猜想,输入循环,输入控制的循环,递归定义,递归函数,循环定义,无穷递归,循环和递归,斐波那契数列,二路递归,计时,循环不变式,计算复杂性,最大公约数,欧几里得算法(辗转相除法),河内塔问题,自递归,相互递归,程序终止性,不可判定,Collatz猜想,唯一定义原则,自下而上,自顶向下,逐步求精,形式参数(形参),文档串,实际参数(实