首页 > 试题广场 >

编程题:输入一个正整数,若该数能用几个连续正整数之和表示,则

[问答题]
编程题:输入一个正整数,若该数能用几个连续正整数之和表示,则输出所有可能的正整数序列。
    /*
     * 假设正整数 n 能表示为 i 个连续正整数之和且其第一个数为 x,则 n = x * i + (i - 1) * i/2,其中 n, x, i
     * 都为正整数, 所以如果 x = (n - (i-1)*i/2) / i 为正整数(即分子对i取模等于0),则 n 就能表示为i个连续正整数之和。
     * i 的取值范围为[2,1+sqrt(1+8n)/2],可通过一元二次不等式求得)或者简单地认为i的取值范围为[2,n/2+1]
     */
    public static void GetNumSequence(int n) {
        for (int i = 2; (2 * i - 1) * (2 * i - 1) - 1 < 8 * n; i++)// 将求根转化为平方。例如 i<sqrt(x)-->i*i<n
        {
            if ((n - i * (i - 1) / 2) % i == 0) {
                int x = (n - i * (i - 1) / 2) / i;
                int j = 0;
                while (j < i) {
                    System.out.print(x + " ");
                    x++;
                    j++;
                }
                System.out.println("");
            }
        }
    }

发表于 2015-04-22 10:24:20 回复(0)
写了个简单的,大概根据的是等差数列和的公式 n*(2*a1 + n - 1)/2 = num,可能效率上不够高
public class ConsecutiveIntegerSum {

    public static void main(String[] args) {
        devideIntoConsecutiveIntegerSum(10000);
    }
    
    public static void devideIntoConsecutiveIntegerSum(int num){
        int a1 = 1;
        int n = 2;
        for(n = 2 ; n < num ;n++){
            for(a1 = 1; a1 < num ;a1++){
                if((n*n + (2*a1 - 1)*n )  == 2 *num){
                    for(int i=1;i<=n;i++){
                        System.out.print((a1 + (i-1)) + ",");
                    }
                    System.out.println();
                }
            }
        }
    }
}

发表于 2015-04-21 21:44:40 回复(0)
mlc头像 mlc
public static void  f(int n) {
        
        
        boolean isExist = false;
        
        if(n<=2) {
            isExist = false;
        }
        
        for(int begin = 1 ; begin < (n+1)/2; begin ++) {
            for(int end = begin +1; end < n; end ++) {
                if ((begin + end)*(end + 1 - begin)== n*2) {
                    isExist = true;
                    System.out.print(begin);
                    for(int i = begin+1;i<=end;i++) {
                        System.out.print(i);
                    }
                    System.out.println();
                }
            }
            
        }
        
        if(isExist == false) {
            System.out.println("null");
        }
    }
    
发表于 2015-04-20 10:27:11 回复(0)
分割数?
分治法,将待分割数num分割出1,2,...,num后,将余数作为子问题继续计算。

devide函数处理待分割数为num,分割数为thr的情况,该函数借助一个数组arr,arr[num]用来记录该数分割出去多少,然后调用devide_rec函数处理余数。 最后当num为0时,说明一种分割方式已经完成。
#include <stdio.h>
#include <malloc.h>

void devide (int *arr, int len, int num, int thr);
void devide_rec (int *arr, int len, int num, int thr);

void printArr (int *arr, int len) {
    int i = len-1;
    while (arr[i]) {
        printf ("%d ", arr[i]);
        i -= arr[i];
    }
    printf ("\n");
}

void devide (int *arr, int len, int num, int thr) {
    arr[num] = thr;
    num -= thr;
    if (!num) {
        printArr (arr, len);
        return;
    }
    devide_rec (arr, len, num, thr);
}

void devide_rec (int *arr, int len, int num, int thr) {
    int i;
    if (thr > num) {
        thr = num;
    }
    for (i = 1; i <= thr; ++i) {
        devide(arr, len, num, i);
    }
}

int main () {
    int num = 6;
    int *arr = (int*)malloc(sizeof(int)*(num+1));
    arr[0] = 0;
    devide_rec (arr, num+1, num, num);
    free(arr);
    return 0;
}

编辑于 2015-04-18 22:06:15 回复(0)
/*
设初始值为x,有m个数,因为是连续的数字,那么求和为mx + m*(m-1)/2 = n。
因为x至少为1,那么代入可推出m<=√(2*n),而且m>=2。然后枚举m,由等式可求出x,
如果x为整数,那么x就满足题意,可输出。效率可达到o(√n)
*/

#include<iostream>
#include<cmath>

using namespace std;

void main()
{
    int n;

    cin >> n;

    for(int m = sqrt(2*n); m >=2 ; m --)
    {
        double fx = (double)(2*n - m*(m-1)) / (2*m);
        int dx = (int)fx;

        if(dx == fx)
        {
            for(int i = dx; i < dx+m; i ++)
            {
                cout << i << " ";
            }
            cout << endl;
        }
    }
}

发表于 2015-04-23 12:16:14 回复(1)
#include<iostream>
#include<math.h>
using namespace std;
//mx+m(m-1)/2=n
//x=(2*n-m*m+m)/(2*m)
void process(int n){
    int m=2;
    double x=0;
    int first=0;
    int i=0;
    for(;m<=sqrt(2*n);m++){
        x=(2.0*n-m*m+m)/(2*m);
        first=(int)x;
        if(x==(float)first){
            for(i=first;i<first+m;i++)
                cout<<i<<" ";
            cout<<endl;
        }//if
    }//for
}//fun
int main(){
    int n=0;
    while(cin>>n){
       process(n);
    }//while
    return 0;
}//main
发表于 2017-07-04 15:31:34 回复(0)
int Fun(int n) {
    int m = (n+1)/2;
    for ( int i=2;i<=m;++i ) {
        if ( 0==(n-(i-1)*i/2)%i ) {
            return (n-(i-1)*i/2)/i);
        }
    }
    return -1;
}
发表于 2015-05-13 15:41:59 回复(0)
请问一下为什么我n输入15是对的,其它数据就是错的??
发表于 2015-04-28 20:15:59 回复(0)
比较笨的方法:
思路:1.起始数字不可能大于输入数字的一半,但是不排除终止数字为输入数字的一半,所以采用输入数字/2向上取整的方式,作为循环的阀值。
   2.1~(ceil(输入数字/2)-1)这个区域内的所有数字都有可能成为起始数字,所以对这个区域进行2层循环遍历。当和大于等于输入数字时终止循环,并判断和是否等于输入数字,标记然后退出。
根据标记打印数字串.
    public static void integerBreak1(long target){
        boolean have = false;
        System.out.println("###########BEGIN##################");
        for(long i=0 ; i< Math.ceil((double)target/2);i++){
            long count = 0;
            long start = i;
            for(long j=i+1 ; j<=target ; j++){
                if(start < target){
                    count++;
                    start = start + j;
                }else{
                    if(start == target){
                        have = true;
                    }else{
                        have = false;
                    }
                         break;
                }
            }
            if(have){
                for(long k=0 ; k<=count; k++){
                    if(k==0){
                        System.out.print("{"+(i));
                    }else if(k==count){
                        System.out.println(","+(i+k)+"}");
                    }else{
                        System.out.print(","+(i+k));
                    }
                }
                
            }
        }
        System.out.println("###########END##################");
    }



发表于 2015-04-23 11:38:46 回复(0)
import java.util.Scanner;

public class GetSum {
    public static void main(String[] argv){
        Scanner scanner = new Scanner(System.in);
        
        int n = scanner.nextInt();
        
        for(int i=1, startNum=1, sum=0;i<=n/2;i++){
            sum += i;
            System.out.println("i :" + i + " startNum :" + startNum + " sum :" + sum);
            if(sum > n){
                sum = 0;
                i = startNum;
                startNum+=1;
                
                continue;
            }
            
            if(sum == n){
                for(int j=startNum;j<=i;j++){
                    System.out.print(j + " ");
                }
                System.out.println();
                
                sum = 0;
                i = startNum;
                startNum += 1;
            }
        }
    }
}

发表于 2015-04-22 17:14:17 回复(0)
int input;    //开始时输入的正整数,设定为全局变量

int main()
{
    int i;
    input = 9;    //赋值9,答案:4,5和2,3,4

    for (i = 1; i < input; i++)    //起始值设定为1开始往上升,直到input-1结束
         calResult(0, i);

    return 0;
}

int calResult(int sum, int num)
{
    int num_t;
    int sum_t;
    int ret=0;
    if (sum + num == input)    //如果跟input一致就判断找到连续和跟input一致的结果
    {
        printf("number: %d",num);
        return 1;
    }
    else if (sum + num > input)    //如果大于input返回-1终止递归
        return -1;
    else
    {
        sum_t = sum + num;
        num_t = num + 1;
        ret = calResult(sum_t, num_t);    //使用递归查看连续累加的数值跟input比较

        if (ret == 1)
            printf(",%d",num);
        return ret;
    }
}
             

发表于 2015-04-21 21:17:37 回复(0)
从1开始,当sum小于目标数时,逐个往上加;当大于目标数时,首先去掉一次头部元素,仍然大于目标数时,需要检查是否为最后一个元素导致不正确,试着减去最后一个元素(只有减去最后一个元素之后等于目标数时才从序列中删除)

import java.util.List;
import java.util.ArrayList;
import java.util.Iterator;

public class test1 {
    public static void main(String[] args) {
        if(args.length != 1) {
            System.out.println("please input one number!");
        }
        
        int num = Integer.parseInt(args[0]);
        System.out.println(num);
        if(num <= 0) {
            System.out.println("please input a positive number!");
        }
        
        boolean flag = false; //标识是否找到正确序列
        boolean isPop = false; //是否尾部已经弹出过了
        int sum = 0;
        int i = 1;
        int temp = 0;
        List<Integer> list = new ArrayList<Integer>();
        while(!flag) {
            if(sum == num) {
                flag = true;
                break;
            }
            if(sum < num) {
                sum += i; //向序列中添加元素,并加到sum中
                list.add(i);
                i++;
                System.out.println("add   " + i);
            } else {
                if(list.size() > 0) {
                    if(!isPop) {
                        temp = list.remove(0);
                        sum -= temp; //删除头部最小元素
                        System.out.println("remove  " + temp);
                    } else {
                        //删除过头部元素后试着删除尾部元素,看是否等于sum
                        if(sum - list.indexOf(list.size()) == num) {
                            list.remove(list.size());
                            flag = true;
                            break;
                        } else {
                            isPop = false;
                        }
                    }
                    
                } else {
                    break;
                }
            }
        }
        //如果找到正确序列就进行输出
        if(flag) {
            System.out.println("the correct line is :");
            for(Iterator<Integer> iter = list.iterator(); iter.hasNext(); ) {
                System.out.println(iter.next());
            }
        } else {
            System.out.println("not found the correct line!");
        }
    }
}

编辑于 2015-04-19 21:44:36 回复(0)
//穷举法 比如输入1个正整数n
int i=0,j=0,sum=0,nstart,nend;
bool flag = false;
for(i=1;i<n/2;i++)
{
    sum = 0;
    nsart = i;
    for(j=1;i<=i;j++)
        {
            sum+=j;
            if(sum == targert)
            {
                nstart = j;
                bool = true;
                break;
            }
        }
}
         

发表于 2015-04-19 20:30:50 回复(0)
#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;  
}
发表于 2015-04-19 19:17:31 回复(0)
思路:从1到z穷举连续整数个数 i,计算从x,x+1, x+2.....x+i-1的和,既(x+x+i-1)* i / 2,如果等于z就输出。
借来代码如下:

#include<stdio.h>

int main()

{

    int i,z,x,y,j;

    printf("please input z:");

    scanf("%d",&z);

    for(i=1;i<=z;i++)

        for(x=1;x<=z;x++)

        {

            y=x+i-1;

            if((y+x)*i==2*z)

            {

                for(j=x;j<=y;j++)

                    printf("%3d ",j);

                printf("\n"); 

            }

        }

}


发表于 2015-01-06 23:28:48 回复(0)