//****************************************************************************************************
//
// 求和为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-5
4-6
7-8
Totally 3 sequences found.
*/
分享到:
相关推荐
1. 初级程序员注重算法和数据结构 2. 事先做好准备,对工作有热情 3. 面试过程放松。不要急于写代码,了解清楚所要解决的问题,多和面试官沟通,然后开始做一些整体的设计和规划。不要急于提交,自己测试几个用例避免错误...
数据结构与算法--面向对象的C++设计 数据结构与算法--面向对象的C++设计 数据结构与算法--面向对象的C++设计 数据结构与算法--面向对象的C++设计 数据结构与算法--面向对象的C++设计 数据结构与算法--面向对象的C++...
算法-求正整数2和n之间的完全数(信息学奥赛一本通-T1150).rar
c++算法-图算法(第三版)一书的pdf版
考虑设A为 (PQ) ,并且删除掉的是数字P%10,得到B=((P/10)Q)...所以,若N为奇数,Q必为空,检查是否可以得到A使得i即可。 若N为偶数,应当进行一次循环,求出假设i在每一位上时的A和B。注意Q*2有进位和不进位两种情形。
基于延迟-求和的麦克风阵列语音增强算法研究.pdf 延迟-求和 麦克风阵列 语音增强
C++算法-图算法(第三版),网上下载。
对于给定的n位正整数a 和正整数k,设计一个算法找出剩下数字组成的新数 最小的删数方案。 «编程任务: 对于给定的正整数a,编程计算删去k个数字后得到的最小数。 Input 由文件input.txt提供输入数据。文件的第1...
加密算法模块(VC++)-算法源码吧-加密解密算法- C_C++ 加密算法必备,开拓视野和了解相关算法
C++基于 Retinex 的图像增强算法-Opencv-C++。 一种常见图像增强算法,基于Retinex理论。本代码通过vs2015编译通过,Opencv3.1.0,C++ opencv c++ Retinex 图像增强
给定一个整数n,求出所有连续的且和为n正整数。比如对于整数27,结果为2~7、8~10、13和14,因为这些数之间的整数的和都是27。注意:并不是所有的整数都有结果,例如不存在连续的整数和为16。为了提高计算的效率,...
设计一个程序,随机产生n个1~3999的正整数序列,分别采用直接插入排序、折半插入排序、希尔排序、冒泡排序、快速排序、直接选择排序、堆排序和二路归并排序算法对其递增排序,求出每种排序方法所需的绝对时间。
图形学-种子填充算法-C++
将正整数n表示成一系列正整数之和:n=n1+n2+…+nk,其中n1≥n2≥…≥nk≥1,k≥1。 正整数n的这种表示称为正整数n的划分。求正整数n的不同划分个数。 例如正整数6有如下11种不同的划分: 6; 5+1; 4+2,4+1+1...
大数据-算法-切平面在混合整数非线性规划中.pdf
数据结构与算法---C++版(Adam Drozdek)书中的源代码
C++算法-图算法(第三版)
C++算法-图算法(第三版)
C++算法-图算法(第三版)