首页 > 试题广场 >

序列和

[编程题]序列和
  • 热度指数:104043 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 32M,其他语言64M
  • 算法知识视频讲解
给出一个正整数 N 和长度 L ,找出一段长度大于等于 L 的连续非负整数,他们的和恰好为 N 。答案可能有多个,我我们需要找出长度最小的那个。
例如 N = 18 L = 2:
5 + 6 + 7 = 18
3 + 4 + 5 + 6 = 18
都是满足要求的,但是我们输出更短的 5 6 7

数据范围:

输入描述:
输入数据包括一行: 两个正整数N(1 ≤ N ≤ 1000000000),L(2 ≤ L ≤ 100)


输出描述:
从小到大输出这段连续非负整数,以空格分隔,行末无空格。如果没有这样的序列或者找出的序列长度大于100,则输出No
示例1

输入

18 2

输出

5 6 7
示例2

输入

30 13

输出

No

说明

无法由非负整数构成 
from sys import stdin
def check(N, L):
    if N*2 % L == 0:
        if (N*2/L+1-L)%2 == 0:
            return (N*2/L+1-L)/2
    return -1
if __name__ == "__main__":
    ip_list = stdin.readline().rstrip().split(" ")
    N = int(ip_list[0])
    L = int(ip_list[1])
    k = L
    while k <=100:
        x = check(N,k)
        if x != -1:
            break
        k += 1
    if x == -1:
        print('No')
    else:
        res = ''
        for i in range(k):
            res += str(int(x+i))
            if i < k-1:
                res +=' '
        print(res)

发表于 2020-03-25 15:07:26 回复(1)
python3 解题思路




a=[]
result=input().split(' ')
N=int(result[0])
L=int(result[1])
b=''
if 1<=N and N<=1000000000 or 2<=L and L<=100:
for i in range(L,101):
if len(a)==0 and len(a)<=L:
if i%2!=0:
if N%i==0:
a.extend(range(int((N/i))-int((i-1)/2),int((N/i))+int((i-1)/2)+1))
elif i%2==0 :
if N%i==0.5*i:
a.extend(range(int(N/i)-int(i/2)+1,int(N/i)+int(i/2)+1))
strings = [str(inte) for inte in a]
b=" ".join(strings)
if len(b)>0:

print(b)
else:
print('No')
else:
print("No")
编辑于 2020-03-21 01:52:21 回复(0)
importjava.util.Scanner;
publicclassMain{
    publicstaticvoidmain(String args[]){
        Scanner sc=newScanner(System.in);
        intn=sc.nextInt();
        intl=sc.nextInt();
        intmid=n/l;
        intnum=0;
        while(mid>=(l-1)/2&&l<=100){
            num=0;
            for(inti=-(l-1)/2;i<=l/2;i++){
                num+=mid+i;
            }
            if(num>n)
                mid--;
            elseif(num<n)
                l++;
            elseif(num==n)
                break;
        }
        //System.out.print(num);
        if(l>100||num!=n){
            System.out.print("No");
        }
        elseif(num==n){
            for(inti=-(l-1)/2;i<=(l/2);i++){
                if(i==(l/2))
                    System.out.print(mid+i);
                else
                    System.out.print((mid+i)+" ");
            }
        }
    }
}
发表于 2020-03-20 21:45:15 回复(0)

Go语言实现一个

基本思路

1 2 3 4 5 6 7
前 n 个的和是:
1 : 1
2 : 3
3 : 6
4 : 10
...
例如: 对于给出的样例 18 2
长度应为 3
// sum(n) 表示从 1 开始前n个数的和
于是 18 - sum(3)(6) = 12 % 3 (0) 12 / 3 = 4
所以结果 为 1 2 3 全部加 4
5 6 7
基于这个思路可以得到下面的代码:

package main

import "fmt"

func main() {
    var N, L int
    var find = true
    _, _ = fmt.Scanf("%d %d", &N, &L)

    for find {
        if move := (N - getSum(L)) / L; (N-getSum(L))%L == 0 {
            for i := 1 + move; i < move+L; i++ {
                fmt.Printf("%d ", i)
            }
            fmt.Print(move + L)
            find = false
        } else {
            L++
        }
        if L > 100 {
            fmt.Print("No")
            find = false
        }
    }
}

func getSum(n int) int {
    var res int
    for i := 1; i <= n; i++ {
        res += i
    }
    return res
}

/* input case
18 2
*/
发表于 2020-03-19 12:07:14 回复(2)
"""
5 + 6 + 7 = 18 转化为
3*5 + 0 + 1 + 2 = 18

"""


def factorial(n):
    if n < 2:
        return 1
    else:
        return n + factorial(n-1)


def show_ans(n, length):
    ans = [str(x) for x in range(n, n+length)]
    print ' '.join(ans)

if __name__ == "__main__":
    N, L = [int(x) for x in raw_input().split()]
    get_ans = False

    for i in range(L, 101):
        fac = factorial(i-1)

        if N - fac < 0:
            print 'No'
            break

        if ((N - fac) % i) == 0:
            start = (N - fac) / i
            show_ans(start, i)
            get_ans = True
            break

    if not get_ans:
        print 'No'

编辑于 2018-02-05 16:44:09 回复(0)
#include<iostream>
using namespace std;

int main(){
	int N, L;
	cin >> N >> L;
	int j, firstNum;
	int minValue;
	for (j = L; j <= 100; j++){
		minValue = (j - 1) * j / 2;
		if (N >= minValue && (N - minValue) % j == 0){
			firstNum = (N - minValue) / j;
			cout << firstNum;
			for (int i = 1; i < j; i++)
				cout << " " << firstNum + i;
			return 0;
		}
	}
	cout << "No";
	return 0;
}
//换一种思维,自下而上,不用判奇偶

发表于 2017-03-09 18:49:31 回复(0)
importjava.util.Scanner; 
publicclassMain{
    publicstaticvoidmain(String[] args){
        Scanner scan = newScanner(System.in);
        intN = scan.nextInt();
        intL = scan.nextInt();
        intbegin = 0;
        doublek = 0;
        doublen = (double)N;
        doublei = (double)L;
        for(;i <= 100; i++){
            k = (n-(i-1)*i/2)/i;//因为N = i*k+(i-1)+(i-2)+...+1;故
            if(k == Math.floor(k)){//若k为整数,则符合条件
                L = (int)i;
                begin = (int) k;
                break;
            }
        }
        if(i > 100){
            System.out.print("No");
        }else{
            for(intj = 0; j < L; j++){
                if(j == (L-1)){
                    System.out.print((begin + j));
                    break;
                }
                System.out.print((begin + j) + " ");
            }
        } 
    }
}

编辑于 2017-03-08 19:19:12 回复(0)
import java.util.*;
public class Main{
    public static void main(String args[]){
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int L = sc.nextInt();
      	for(int i = L; i <= 100; i++) {
        	if((2*N+i-i*i)%(2*i) == 0) {
            	int start = (2*N+i-i*i)/(2*i);
            	for(int j = 0; j < i-1; j++) {
                	System.out.print(start+j+" ");
            	}
            	System.out.print(start+i-1);
            	return;
        	}
    	}
        System.out.print("No");
    }
}

发表于 2017-03-19 21:08:11 回复(2)

图片说明

#include<iostream>
using namespace std;
int main() {
    int N, L;
    cin>>N>>L;
    for(int i = L; i <= 100; i++) {
        if((2*N+i-i*i)%(2*i) == 0) {
            int start = (2*N+i-i*i)/(2*i);
            for(int j = 0; j < i-1; j++) {
                cout<<start+j<<" ";
            }
            cout<<start+i-1;
            return 0;
        }
    }
    cout<<"No"<<endl;
}
发表于 2017-03-08 17:26:34 回复(17)
借用回答区中或赞最高的答案的分析图,我给出了Python版实现


发表于 2018-05-04 21:27:34 回复(1)
import java.util.Scanner;
/*
 * 题目需要找出一段长度大于等于L的连续非负整数,使得其和等于N。L要尽可能小。
 * 考虑是连续非负整数,所以其和我们能用中位数来表示,分两种情况:
 * 情况一,长度为奇数的情况:
 *   此时中位数一定是整数,N = 中位数 x L
 * 情况二,长度为偶数的情况:
 *   此时中位数肯定是xx.5的形式,N = xx.5 * L
 * 所以我们从长度L开始枚举,至100为止,分奇偶讨论。
 */
public class Main {
	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		int n = in.nextInt(), l = in.nextInt();
		in.close();
		int bg = -1, ed = -1;
		for (int i = l; i <= 100; ++i) {
			// 奇数,中位数一定是整数
			if (i % 2 == 1 && n % i == 0) {
				int mid = n / i;
				bg = mid - (i - 1) / 2;
				ed = mid + (i - 1) / 2;
				if (bg >= 0) // 答案要合法,即需要是非负整数
					break;
			}
			// 偶数,中位数一定是0.5形式
			if (i % 2 == 0 && (double)n / i - n / i == 0.5f) {
				int mid = n / i;
				bg = mid - i / 2 + 1;
				ed = mid + i / 2;
				if (bg >= 0)
					break;
			}
		}
		if (bg >= 0) {
			for (int i = bg; i < ed; ++i) {
				System.out.print(i + " ");
			}
			System.out.println(ed);
		}
		else {
			System.out.println("No");
		}
	}
}

发表于 2017-03-08 16:26:25 回复(2)
根据楼上lencha的思路,写的java版本
发表于 2017-03-09 10:17:29 回复(1)
import java.util.*;
public class Main{
    public static void main(String[] args){
        Scanner scan=new Scanner(System.in);
        int N=scan.nextInt();
        int L=scan.nextInt();
        int first;
        int last;
        
        for(;L<=100;L++){
            first=((2*N/L)-L+1)/2;
            last=first+L-1;
            if(((first+last)*L)/2==N){
                for(int i=0;i<L-1;i++){
                    System.out.print(first+" ");
                    first++;
                }
                System.out.print(last);
                return;
            }
        }
        System.out.print("No");
        return;
    }  
}
java版本
发表于 2020-07-31 14:28:28 回复(0)

「Python详细解题思路」

一开始不要被题目描述吓到,仔细品一下“找出一段长度大于等于L连续非负整数,他们的恰好为N”, 你细细品,其实不就是找到一个从某个数字开始以1为差长度为L的等差数列的和嘛。
复习一下从a1开始以d为差长度为n的等差数列的和为:
所以我们只要能找到一个整数a1作为起始数值就好,整理一下得:

N为已知,只需要根据l来求得a那么在代码实现时,我们可以从L开始,依次遍历所有l的可能(从L100),并检查相应求得的数值是否为整数即可。
详细代码如下:
## Python 3.*
## Written by CheesePrawn on 25th May 2020
if __name__ == '__main__':
    N, L = map(int, input().split(' '))
    ## 设定标签值,如果在接下来的程序中没有找到所需结果,最终输出No
    not_find = True
    ## 根据题意 2<=L<=100, 界定循环次数
    for l in range(L, 101):
        ## 根据公式进行计算
        a_start = (2 * N - (l - 1) * l) / (2 * l)
        ## 如果所得结果为整数,即为我们所要找的起始值
        if int(a_start) == a_start:
            not_find = False
            a_start = int(a_start)
            ## 依次输出,并以空格隔开,注意题意要求,最后一位结尾不需要空格,所以单独输出
            for i in range(l - 1):
                print(a_start + i, end=' ')
            print(a_start + l - 1)
            ## 根据题意只需要找到最短的,l是从小到大,所以最先找到的即为所求,不用再进行循环了
            break
    ## 如果没有找到,输出No
    if not_find:
        print("No")
参考lencha的解题思路
编辑于 2020-05-25 18:10:16 回复(1)

其实这题不需要等差公式。

考虑任意连续整数,假设是答案,长度为 K 。

去掉所有K个n以后必定是 1 + 2 + 3 + ... 的形式。

所以先求出 1 + 2 + 3 + ... + 100 的前缀和,从小到大试着减去对应长度的前缀和。检查剩下的数是否是长度的整数倍就可以了。

#include
using namespace std;
const int N = 110;
int q[N];
int main()
{
    int n, l; cin >> n >> l;
    for(int i = 1; i <= 100; i++) q[i] = i, q[i] += q[i - 1];
    for(int i = l; i <= 100; i++)
    {
        int k = n - q[i];
        if(k % i == 0)
        {
            for(int j = 1; j <= i; j++) cout << j + k / i << " \n"[j == i];
            return 0;
        }
    }
    cout << "No\n";
}
发表于 2021-03-05 16:30:22 回复(0)
Java版本
根据本题思路,假设有L个数组成N,那么即有L*a1+((L-1)*L)/2)*d=N,因为该题求的是连续函数,所以d为1,那么即可以根据L和N求出a1,且a1必须为整数,且L不大于100。那么可得a1 = (2N - (L-1)L) / (2 * L),切记最后输出的行末不能带有空格。
import java.util.Scanner;
public class Main {
    public static void main(String[] args){
        Scanner input =  new Scanner(System.in);
        int N = input.nextInt();
        int L = input.nextInt();
        show(N,L);
    }
    public static int show(int N,int L){
        int i = L;
        while(i <= 100){
            int a = (2*N - i*(i-1))/(2*i);
            if((2*N - i*(i-1))%(2*i) == 0 && a >= 0){
                for(int j = 0;j < i-1;j++){
                    System.out.print(a + " ");
                    a = a + 1;
                }
                System.out.print(a);
                return 0;
            }
            i = i + 1;
        }
        if(i > 100){
             System.out.print("No");
             return 0;
        }
        return 0;
    }
}


编辑于 2020-04-27 17:53:30 回复(1)
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int L = sc.nextInt();
        for (int i = L; i <= 100; i ++) {
            if ((2 * N + i - i * i) % (2 * i) == 0) {
                int a1 = (2 * N + i - i * i) / (2 * i);
                for (int j = 0; j < i-1; j ++) {
                    System.out.print(a1 + j + " ");
                }
                System.out.println(a1 + i - 1);
                return;
            }
        }
        System.out.println("No");
    }
}


发表于 2017-03-12 21:24:44 回复(1)

模拟法

解题思路:设长度minlen,从L开始遍历100, 求出等差为1、长度为minlen、和为N的等差数列的首项a1,如果a1为整数且minlen<=100, 则成功
时间复杂度:O(100 - L) = O(1)
#include<iostream>
(720)#include<cmath>
using namespace std;
int main(){
    int n, l;
    int minlen;
    int k;
    while(cin >> n >> l){
        minlen = l;
        while(minlen <= 100){
            double a = (2 * n +  minlen * (1 -  minlen)) / double((2 * minlen));
            if(ceil(a) == a){
                for(k = a; k < a + minlen - 1; k++){
                    cout << k << " ";
                }
                cout << k;
                break;
            }
            minlen++ ;
        }
        if(minlen == 101) cout << "No";
    }
    return 0;
}


发表于 2020-04-13 16:01:41 回复(0)
到80一直ac不了
后来发现ac的关键在于最后一个空格
多年不打acm手生的厉害
N, L = map(int,input().split())
while L <= 100:
    s=(2*N-L*(L-1))/2/L
    if int(s)==s:
        s=int(s)
        for i in range(s,s+L-1):
            print(i,end=' ')
        print(s+L-1)
        break
    L=L+1
if L >= 101:
    print("No")


发表于 2020-03-26 21:32:22 回复(1)
# 用异常方式跳出循环输出No
# 等差数列求和首先想到等差数列求和公式
import sys

lines = []
try:
    while True:
        line = sys.stdin.readline().strip()
        if line == "":
            break
        lines.append(line.split())
    N, L = int(lines[0][0]), int(lines[0][1])
    List = []
    l = L
    while l <= 100:
        a1 = (2 * N - l * (l - 1)) / (2 * l)    # 等差数列之和公式
        if int(a1)==a1 and a1>=0:   # 判断是否为整数且为非负
            for i in range(l - 1):
                print(int(a1 + i), end=" ")
            print(int(a1 + l - 1))
            break
        l = l + 1
    else:
        raise
except:
    print("No")

发表于 2023-04-21 14:06:36 回复(0)