请编写程序,根据输入的任何一个正整数,找出符合这种要求的所有连续正整数序列。输入数据:一个正整数,以命令行参数的形式提供给程序。输出数据:在标准输出上打印出符合题目描述的全部正整数序列,每行一个序列,每个序列都从该序列的最小正整数开始、以从小到大的顺序打印。如果结果有多个序列,按各序列的最小正整数的大小从小到大打印各序列。此外,序列不允许重复,序列内的整数用一个空格分隔。如果没有符合要求的序列,输出“NONE”。例如,对于15,其输d出结果是:
1 2 3 4 5
4 5 6
7 8对于16,其输出结果是:
NONE求各路高手贴代码,记得写注释!
1 2 3 4 5
4 5 6
7 8对于16,其输出结果是:
NONE求各路高手贴代码,记得写注释!
假设输入值为 x,用for循环i从1开始循环,到x-1, 每次循环就干一件事:
从i开始一个一个加起来: M=i+(i+1)+(i+2)+....,
如果比X小,继续往下加,
如果相等,恭喜你,答对了,
如果比X大,不用试了,没可能了; 从2开始再循环吧。。解法2:其实这个是连续数列相加,可以有:
1. 设输入为X,有解是从n开始的m个自然数
2. 有 X=1/2×(n+n+m-1)*(m) [ 首项加末项乘项数除2 ]
3. n最大不超过X/2
根据以上,推导一下,得到个 n = (2*X/m-m+1)/2
这下循环简单了,
for (m = 2 to X/2){
if ((2*X/m-m+1)/2) 是个自然数,打印从n开始的m个数
else 继续
}
public static void main(String[] args) {
int sum = 0;
for (int i = 1; i <= 15; i++) {
for (int j = i; j <= 15; j++) {
sum = sum + j;
if (sum == 15) {
for (int k = i; k <= j; k++) {
System.out.print(" " + k);
}
System.out.println();
}
}
sum = 0;
}
}
import java.util.List;public class Hello {
public static void main(String[] args) {
int value = 159; for (int count = 2; count < value / 2; ++count) {
float mid = value / ((float) count); int min = (int) Math.ceil(mid - count / 2);
int max = min + count - 1; if (min == 0) { break; }
List<Integer> ns = new LinkedList<Integer>();
int sum = 0; for (int i = min; i <= max; ++i) {
sum += i;
ns.add(i);
} if (sum == value) {
System.out.println(ns);
}
}
}
}
1. 例如count是奇数时,如果 value % count != 0可以不做这个循环
2. 求和,因为是一个等差数列求和,可以直接使用求和公式
3. 那个List根本不需要
int num = scanner.nextInt(); int mid = num / 2;// 最大的那个数
// 枚举
for (int i = 1; i <= mid; i++)
f(num, i);// 递归
if (!flag)
System.out.println("NONE"); } private static void f(int num, int start) { if (num == 0)// 如果已经全部减完了就打印
{
for (int i = 0; i < js; i++)
System.out.print(rec[i] + " ");
System.out.println("\n");
flag = true;
} if (num < start)
return;// 退出条件 如果已经完全不能剪了 rec[js++] = start;// 保存数据
f(num - start, start + 1);// 递归检测下一个数能不能被减
js--;// 删掉保存的数 return;
}}
很简单 就一个简单的递归外面套一层如果数过大会出现栈蹦了
* @param args
*/
public static void main(String[] args) {
Scanner input = new Scanner(System.in);
System.out.println("请输入:");
int n = input.nextInt();
m3(n);
} /**
* 单纯循环实现
*
* @param n
*/
static void m1(int n) {
boolean hasNo = true;
for (int i = 1; i < n; i++) {
int sum = 0;
int j = i;
for (; sum < n; j++) {
sum += j;
} if (sum == n) {
hasNo = false;
for (int k = i; k < j; k++) {
System.out.print(k + "\t");
}
System.out.println();
}
}
if (hasNo) {
System.out.println("NONE");
}
} /**
* 二维数组实现
*
* @param n
*/
static void m2(int n) {
int[][] arr = new int[n][];
int l = 0;
for (int i = 1; i < n; i++) {
int sum = 0;
arr[l] = new int[n];
for (int j = i; sum < n; j++) {
sum += j;
arr[l][j - i] = j;
}
if (sum == n) {
l++;
} }
if (l == 0) {
System.out.println("NONE");
} else {
for (int i = 0; i < l; i++) {
if (arr[i][0] == 0) {
break;
}
for (int j = 0; j < n; j++) {
if (arr[i][j] == 0) {
break;
}
System.out.print(arr[i][j] + "\t");
}
System.out.println();
}
}
} /**
* 字符串实现
*
* @param n
*/
static void m3(int n) {
boolean hasNo = true;
for (int i = 1; i < n; i++) {
int sum = 0;
StringBuffer sb = new StringBuffer();
for (int j = i; sum < n; j++) {
sum += j;
sb.append(j + "\t");
}
if (sum == n) {
hasNo = false;
System.out.println(sb.toString());
}
}
if (hasNo) {
System.out.println("NONE");
}
}
}
楼主给你三种方法,都测试了哦记得给分。。
1、从begin开始连加,加到和inputNum相等,则输出;
2、begin的连加大于inputNum,则begin++,再重复第1步;
3、循环begin++,直到begin > (inputNum/2)结束;
4、设置一个记录是否存在连加的flag,如果为false,则结束时输出“None”
------------------------------------------代码实现类似2楼,只是修正了几个地方:
1、封装起来,易于扩展;
2、begin循环到whole/2就结束,而2楼全部循环了;
3、2楼没有判断“没有连加”的情况,没有输出“None”
/**
* 从begin开始逐个增加,直到whole/2为止
*/
public static void getPlus_2(int whole, int begin) {
boolean isNotExist = true;
for (int i = begin; i <= (whole / 2); i++) { // 从begin开始逐个增加,直到whole/2为止
int sum = 0;
for (int j = i; sum < whole; j++) {
sum += j;
if (sum == whole) { // 刚好相等,则中断循环,并输出序列
System.out.println(getStr(i, j));
isNotExist = false;
}
}
}
if (isNotExist) { // 如果没有找到,输出None
System.out.println("None");
}
}
/**
* 从begin到end,打印序列
*/
public static String getStr(int begin, int end) {
StringBuffer sb = new StringBuffer();
for (int i = begin; i <= end; i++) {
sb.append(i + " ");
}
return sb.toString();
}
public static void main(String[] args) {
int inputNum = 21;
getPlus_2(inputNum, 1); // 输入正整数,和开始计算的begin
}
思路:
1、上面所述,通过组合数量count来遍历;
2、那count什么时候结束呢?原来是【count> value/2】。但试想,每次都是从value/2从两边分别找元素,所以,只要【value/2 - count/2 = 0】,证明小的那边已经到头了。
所以结束条件可以写成:【value/count - (count/2) >= 0】,这样能减少30%的遍历次数。
3、对连加的组合,value/count为中间值,value*2/count为组合一头一尾的和,而且为正整数。
所以,符合要求的都有【value*2 % count == 0】,就是说两头加起来的和为正整数。
这样能快速定位哪些组合符合要求,原是每个组合都for求和。
4、由于value*2/count为两头和,所以-count+1后再除以2,就是组合中的最小值min 。具体见下面代码: (已经很简洁了吧) public static void main(String[] args) {
int inputNum = 21;
getPlus_3();
}
/**
* 通过数学方法来提高效率
*/
public static void getPlus_3() {
int value = 21;
for (int count = 2; value / count - (count / 2) >= 0; count++) {
if (value * 2 % count == 0) {
int min = (value * 2 / count - count + 1) / 2;
if (min > 0) {
int max = min + count - 1;
System.out.println(getStr(min, max));
}
}
}
}
/**
* 从begin到end,打印序列
*/
public static String getStr(int begin, int end) {
StringBuffer sb = new StringBuffer();
for (int i = begin; i <= end; i++) {
sb.append(i + " ");
}
return sb.toString();
}
从 1 + 2 + 3 开始,已 3 递增的等差数列中任意一个正整数 n 可以表示为 3 个连续数相加 ……
从 1 + 2 + 3 + 4 开始, ………………
static void sf(int sum, List<Integer> indexs, List<Integer> lens)
{
for (int startPost = 1; startPost < sum / 2; startPost++)
{
double tem = 1.0 * (2 * startPost - 1) * (2 * startPost - 1)+8*sum;
double len = 1-2*startPost + Math.Sqrt(tem);
len = len / 2;
if (((int)len) == len)
{
indexs.Add(startPost);
lens.Add((int)len);
}
}
}
import java.util.Map.Entry;
import java.util.TreeMap;public class Game1Main { /**
* <method description>
*
* @param args
*/ public static void main(String[] args) {
for(int X = 15; X <20; X++){
Map<Integer, Integer> result = getList(X);
showResult(X, result);
}
} private static void showResult(int val, Map<Integer, Integer> result) {
System.out.println(val + "===>");
if (result.isEmpty()) {
System.out.println("NONE");
} else {
for (Entry<Integer, Integer> entry : result.entrySet()) {
for (int i = entry.getKey(); i < entry.getKey() + entry.getValue(); i++) {
System.out.print(i + " ");
}
System.out.println();
}
}
System.out.println();
} private static Map<Integer, Integer> getList(int X) {
Map<Integer, Integer> result = new TreeMap<Integer, Integer>();
for (int m = 2; m < X / 2; m++) {
int n = (2 * X / m - m + 1) / 2;
if (((n + n + m - 1) * (m) / 2 == X) && n >= 1) {
result.put(n, m);
}
}
return result;
}}
我写了个解法2的代码, 试着运行了15~19, 结果如下
15===>
1 2 3 4 5
4 5 6
7 8 16===>
NONE17===>
8 9 18===>
3 4 5 6
5 6 7 19===>
9 10
Map<Integer, Integer> result = new TreeMap<Integer, Integer>();
for (int m = 2; m < Math.sqrt(X+X); m++) {
int n = (2 * X / m - m + 1) / 2;
if ((n + n + m - 1) * (m) / 2 == X) {
result.put(n, m);
}
}
return result;
}
算法循环部分优化了一下
private static void solveBySingleLoop(int max) {
int threshold = max/2+1;
int i = 1;
int j = 2;
boolean match = false;
int sum = i+j;
while (i<threshold && j<=threshold) {
if (sum==max) {
match = true;
for (int k=i; k<=j; k++) {
System.out.printf("%d ", k);
}
System.out.println();
sum-=i++;
} else if (sum<max) {
sum+=++j;
} else {
sum-=i++;
}
}
if (!match) {
System.out.println("none");
}
}
#include<iostream>
using namespace std;
void function(int n)
{
for(int i=2;;i++)
{
if(n/i-(i+2)/2+1<=0)//结束条件
break;
if(i%2==0&&n%i*2==i)//商为偶数,也就是要拆解成偶数个相邻的数字
{
for(int k=0;k<i;k++)
cout<<n/i-(i/2)+1+k<<"\t";
cout<<endl;
}
if(i%2==1&&n%i==0)//商为奇数,也就是要拆解成奇数个相邻的数字
{
for(int k=0;k<i;k++)
cout<<n/i-(i+1)/3+k<<"\t";
cout<<endl;
}
}
}
int main()
{
function(15);
function(16);
function(5);
function(18);
return 0;
}
思路:
1.结束条件是什么?
2.除数是奇数时,求余结果为0。
3.除数是偶数时,求余结果为除数的一半。这样商会出现0.5,商加减0.5就成了两个相邻的数字。
叙述的也许不太清楚,见谅~~~~
则满足条件的序列为:s, s+1, s+2 …… s+(k-1),其中s>0,k>1
由题意得:s+(s+1)+(s+2)……(s+(k-1)) = n
化简:s*k + (k-1)*K/2 = n
求得:s = (n - (k-1)*K/2)/k, 当(n - (k-1)*K/2)%k==0时,s有整数解
求得此二元方程的整数解就得到这个问题的答案了#include <stdlib.h>
#include <stdio.h>void printNum(unsigned int s, unsigned int k)
{
while(k-->0)
printf("%u ", s++);
printf("\n");
}void function(unsigned int n)
{
unsigned int s=0;
unsigned int k=2;
unsigned int count=0; for(k=2; ;k++)
{
int tmp = n - (k-1)*k/2; if(tmp<1)
break; if(tmp%k==0)
{
s=tmp/k;
printNum(s,k);
count++;
}
} if(s==0)
printf("NONE\n");
}int main(int argc, char *argv[])
{ if(argc!=2)
{
printf("invalid arg!!!\nusage:%s <number>\n", argv[0]);
return -1;
}
function(atoi(argv[1])); return 0;
}
1、更正笔误;
2、删除没用的临时变量count。设输入的数字为n,满足条件的序列的起始数字为s,长度为k,
则满足条件的序列为:s, s+1, s+2 …… s+(k-1),其中s>0,k>1
由题意得:s+(s+1)+(s+2)……(s+(k-1)) = n
化简:s*k + (k-1)*k/2 = n
求得:s = (n - (k-1)*k/2)/k, 当(n - (k-1)*k/2)%k==0时,s有整数解
求得此二元方程的整数解就得到这个问题的答案了#include <stdlib.h>
#include <stdio.h>void printNum(unsigned int s, unsigned int k)
{
while(k-->0)
printf("%u ", s++);
printf("\n");
}void function(unsigned int n)
{
unsigned int s=0;
unsigned int k=2; for(k=2; ;k++)
{
int tmp = n - (k-1)*k/2; if(tmp<1)
break;
if(tmp%k==0)
{
s=tmp/k;
printNum(s,k);
}
} if(s==0)
printf("NONE\n");
}int main(int argc, char *argv[])
{ if(argc!=2)
{
printf("invalid arg!!!\nusage:%s <number>\n", argv[0]);
return -1;
}
function(atoi(argv[1])); return 0;
}
现在阔以了,楼主试试!
------------------------------------------------
这次改良了一下sum相等的判断条件:
符合连加=value的组合,有一个规律:组合个数如果是单数,那么中间值是个整数;组合个数如果是双数,那么中间值的小数为0.5。即:
单数,整除:count % 2 == 1 && value % count == 0
双数,除后小数为0.5,即不能整除,且2*val可以整除: count % 2 == 0 && value % count != 0 && value * 2 % count == 0 public static void main(String[] args) {
int value = 101;
for (int count = 2; count <= value / 2; count++) {
if ((count % 2 == 0 && value % count != 0 && value * 2 % count == 0)
|| (count % 2 == 1 && value % count == 0)){
int min = (value * 2 / count - count + 1) / 2;
if (min <= 0) { break; }
int max = min + count - 1;
System.out.println(getStr(min, max));
}
}
}
public static String getStr(int begin, int end) {
StringBuffer sb = new StringBuffer((end - begin + 1) * 2);
for (int i = begin; i <= end; i++) {
sb.append(i + " ");
}
return sb.toString();
}