算法 – 求和为n的连续正整数序列(C++)

算法 – 求和为n的连续正整数序列(C++)

大家好,又见面了,我是全栈君。

//****************************************************************************************************
//
//  求和为n的连续正整数序列 - C++ - by Chimomo
//
//  题目: 输入一个正整数n,输出全部和为n的连续正整数序列。比如:输入15,因为1+2+3+4+5=4+5+6=7+8=15,所以输出3个连续序列1-5、4-6和7-8。

//// Answer: Suppose n = i+(i+1)+...+(j-1)+j, then n = (i+j)(j-i+1)/2 = (j*j-i*i+i+j)/2 => j^2+j+(i-i^2-2n) = 0 => j = (sqrt(1-4(i-i^2-2n))-1)/2 => j = (sqrt(4i^2+8n-4i+1)-1)/2.// We know 1 <= i < j <= n/2+1, so for each i in [1,n/2], do this arithmetic to check if there is a integer answer.//// Note: 二次函数 ax^2+bx+c=0 的求根公式为: x = (-b±sqrt(b^2-4ac)) / 2a。////****************************************************************************************************#include <iostream>#include <cassert>#include <stack>#include <math.h>using namespace std ;int FindConsecutiveSequence(int n){ int count = 0; for (int i = 1; i <= n/2; i++) { double sqroot = sqrt(4*i*i + 8*n - 4*i + 1); int floor = sqroot; if(sqroot == floor) { cout << i << "-" << (sqroot - 1) / 2 << endl; count++; } } return count;}int main(){ int count = FindConsecutiveSequence(15); cout << "Totally " << count << " sequences found." << endl; return 0;}// Output:/*1-54-67-8Totally 3 sequences found.*/

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/115523.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号