qiyadeng

专注于Java示例及教程
posts - 84, comments - 152, trackbacks - 0, articles - 34

表正整数n为连续整数的条件和方法

Posted on 2009-01-19 16:37 qiyadeng 阅读(1898) 评论(3)  编辑  收藏

今天看到关于一个整数表示为n个连续整数和的问题。搜索了下找到如下文章:

表为连续正整数
View SlideShare document or Upload your own.

还搜索到程序的实现:http://blog.csdn.net/Solstice/archive/2006/09/13/1217700.aspx

http://squall.cs.ntou.edu.tw/cprog/Assignments/99Fall/FindGivenSum.html

http://blog.chinaunix.net/u2/76292/showart_1359876.html(这个是不正确的)

 

我也简单的实现了下:(g++编译,主要思路是利用等差数列求和公式n=(a+a+k)*(k+2)/2列举k,找到合适的a)

#include <iostream>
#include <math.h>
using namespace std;

int main(){

    int n;
    cout<<"input n:"<<endl;
    cin>>n;

    int maxk=(int)sqrt((double)n*2);

    int flag = 0;

    //cout<<"maxk="<<maxk<<endl;

    //for(int i=1;i<maxk+1;i++){
    for(int i=maxk+1;i>0;i--){
         double a = n/(double)(i+1)-i/(double)2;
        //cout<<"a="<<a<<endl;
    
        if(a>0&&a-(int)a==0){
            //cout<<i<<endl;
            for(int j=0;j<i+1;j++){
                cout<<a+j<<" ";
            }
            cout<<endl;
            flag=1;
        }

    }
    if(flag==0){
        cout<<"NONE"<<endl;
    }
    return 0;

}

Feedback

# re: 表正整数n为连续整数的条件和方法  回复  更多评论   

2009-01-19 23:51 by 墙头草
不错哦~~~~~




=================================================================
Struts2的零配置
Struts2利用stream直接输出Excel
Struts2结合dhtmlx tree
Struts2中ZeroConfig和CodeBehind下的Stream类型返回
struts中html:select标签和html:options 的使用

更多Struts

# re: 表正整数n为连续整数的条件和方法  回复  更多评论   

2009-01-22 10:45 by appu
good.
实现倒是不难, 关键是怎么样让它执行次数最少,至少是比较少。

# re: 表正整数n为连续整数的条件和方法  回复  更多评论   

2010-08-11 10:59 by glq2000
网上讲连续整数和问题的博文很多,但博主这篇最讲的最明白,赞一个~~~

我按照楼主论文提供的方法写了一个,代码如下,其循环次数为O(n/4),相比之下还是楼主的方法更快些,循环次数为O(sqrt(2n)),
void ContinueInt(int n)
{
int i, k, m, num=0;
for(i=3; i<n/2+1; i +=2) //以步长为2从3开始到n/2为止,求n的所有奇数因子
{
if(n%i == 0)
{
++num;
m = n/i;
k = (i-1)/2;
for(int j=(m-k>0)?(m-k):(k-m+1); j<=m+k; ++j) //利用论文中的结论
cout<<j<<" "; //即n=(2k+1)*m=(2k+1)*2m/2=(2k+1)(m-k+m+k)/2
cout<<endl;
}
}
if(n%2)//n本身是奇数
{
++num;
cout<<(n-1)/2<<" "<<(n-1)/2+1<<endl;
}
cout<<"in all, num="<<num<<endl;
}

只有注册用户登录后才能发表评论。


网站导航: