题目:输入一个正数n,输出所有和为n连续正整数序列。
例如输入15,由于1+2+3+4+5=4+5+6=7+8=15,所以输出3个连续序列1-5、4-6和7-8。
解法1
因为整数序列是有序的,可以设立两个游标begin和end,通过判区间[begin,end]的和是否为N来得到这个序列。如果区间和大于n,begin往前移动,如果小于n,end往前移动,等于就输出这个区间。时间复杂度是0(n)。
public void find(int n) {
if (n > 0 && ((n & n-1) == 0)) {
System.out.println("no way");
return;
}
int begin = 1;
int end = 2;
int sum = begin + end;
while (begin < end && begin < (n+1)/2) {
if (sum < n) {
end++;
sum += end;
} else if (sum > n) {
sum -= begin;
begin++;
} else {
System.out.println(n + " can be divided from " + begin + " to " + end);
sum -= begin;
begin++;
}
}
}
解法2
假设自然数n可以拆分成:m, m+1, …, m+k-1 (m >= 1, k >= 2),则 n = (m + m+k-1)*k/2 即 2*n = (2*m+k-1)*k。
由于(2*m+k-1)与k的奇偶性是相反的,因此,可以先将n的所有质因子2提取出来,得到:2 * n = 2^t * a * b,由于(2*m+k-1)与k的奇偶性相反,且(2*m+k-1) > k,当确定了a,b时,可得到2*n的两组拆分(2^t * a, b) 和 (a, 2^t * b)(当a等于b时,这两组拆分是一样的),对每组拆分,k是较小的数。
public void find2(int n) {
if (n <= 0)
return;
int count = 1;
int i;
int j;
while(n % 2 == 0) {
n /= 2;
count++;
}
for (i = 1; ; i += 2) {
if (n % i != 0)
continue;
j = n / i;
if (i > j)
break;
if ((i << count) < j)
print(j, i << count);
else
print(i << count, j);
if (i == j) break;
if (i == 1) continue;
if ((j << count) < i)
print(i, j << count);
else
print(j << count, i);
}
}
private void print(int i, int j) {
int k = j;
int m = (i-j+1) / 2;
System.out.println("from " + m + " to " + (m+k-1));
}
分享到:
相关推荐
给出一个正整数N和长度L,找出一段长度大于等于L的连续非负整数,他们的和恰好为N。答案可能有多个,我我们需要找出长度最小的那个。 例如 N = 18 L = 2: 5 + 6 + 7 = 18 3 + 4 + 5 + 6 = 18 都是满足要求的,但是...
丢失的最小正整数leetcode LeetCode leetcode 题目(共 65 题) 1 两数之和 2 两数相加 3 无重复字符的最长子串 4 寻找两个正序数组的中位数 7 整数反转 9 回文数 13 罗马数字转整数 14 最长公共前缀 15 三数之和 16 ...
119 超长正整数的加法 第四部分 图形篇 120 绘制直线 121 绘制圆 122 绘制圆弧 123 绘制椭圆 124 设置背景色和前景色 125 设置线条类型 126 设置填充类型和填充颜色 127 图形文本的输出 128 金刚石图案 129 飘带图案...
119 超长正整数的加法 第四部分 图形篇 120 绘制直线 121 绘制圆 122 绘制圆弧 123 绘制椭圆 124 设置背景色和前景色 125 设置线条类型 126 设置填充类型和填充颜色 127 图形文本的输出 ...
阶乘:非负整数n的阶乘是所有小于或等于n的正整数的乘积。 找到5! 递归地斐波那契数列:斐波那契数列中的前两个数字是0和1,每个后续数字是前两个数字的和。 递归产生序列。 范围序列:递归地产生一个3到9且互斥的...
} 【例4.14】编程序,输入正整数N,计算r1!+r2!+...+rn! 并输出。其中,N=r1r2...rn 。 解:该程序是一个计算若干数据项之和的程序。本章已经编写过多个求和的程序, 现在总结一下求和程序模式。所有计算和的程序都...
} 【例4.14】编程序,输入正整数N,计算r12! 并输出。其中,1r2 。 解:该程序是一个计算若干数据项之和的程序。本章已经编写过多个求和的程序, 现在总结一下求和程序模式。所有计算和的程序都使用一个和单元,有...
题目:给一个不多于5位的正整数,要求:一、求它是几位数,二、逆序打印出各位数字。 【程序21】 题目:一个5位数,判断它是不是回文数。即12321是回文数,个位与万位相同,十位与千位相同。 【程序22】 ...
输出第一个不见的正整数 Medium 矩阵旋转90° Easy 最大子序列和 Medium 判断能否跳到最后 Easy vector East 爬楼梯 Easy 单链表节点删除 Easy 合并数组 Medium 二叉树中序遍历 Easy 二叉树是否相等 Easy 二叉树最大...
119 超长正整数的加法 第四部分 图形篇 120 绘制直线 121 绘制圆 122 绘制圆弧 123 绘制椭圆 124 设置背景色和前景色 125 设置线条类型 126 设置填充类型和填充颜色 127 图形文本的输出 128 金刚石图案 ...
4、有一个分数序列:1/2,1/3,1/4,1/5,1/6,1/7,……,编写函数求序列前n项之和,要求在主程序中提示用户输入整数n,并判断所输入数是否合法(大于1为合法),如果合法则调用求和函数并输出结果。 5、计算两个日期之间...
119 超长正整数的加法 第四部分 图形篇 120 绘制直线 121 绘制圆 122 绘制圆弧 123 绘制椭圆 124 设置背景色和前景色 125 设置线条类型 126 设置填充类型和填充颜色 127 图形文本的输出 128 金刚石图案 ...
119 超长正整数的加法 第四部分 图形篇 120 绘制直线 121 绘制圆 122 绘制圆弧 123 绘制椭圆 124 设置背景色和前景色 125 设置线条类型 126 设置填充类型和填充颜色 127 图形文本的输出 128 金刚石图案 ...
119 超长正整数的加法 第四部分 图形篇 120 绘制直线 121 绘制圆 122 绘制圆弧 123 绘制椭圆 124 设置背景色和前景色 125 设置线条类型 126 设置填充类型和填充颜色 127 图形文本的输出 128 金刚石图案 ...
119 超长正整数的加法 第四部分 图形篇 120 绘制直线 121 绘制圆 122 绘制圆弧 123 绘制椭圆 124 设置背景色和前景色 125 设置线条类型 126 设置填充类型和填充颜色 127 图形文本的输出 128 金刚石图案 ...
119 超长正整数的加法 第四部分 图形篇 120 绘制直线 121 绘制圆 122 绘制圆弧 123 绘制椭圆 124 设置背景色和前景色 125 设置线条类型 126 设置填充类型和填充颜色 127 图形文本的输出 128 金刚石图案 ...
119 超长正整数的加法 第四部分 图形篇 120 绘制直线 121 绘制圆 122 绘制圆弧 123 绘制椭圆 124 设置背景色和前景色 125 设置线条类型 126 设置填充类型和填充颜色 127 图形文本的输出 128 金刚石图案 ...
119 超长正整数的加法 第四部分 图形篇 120 绘制直线 121 绘制圆 122 绘制圆弧 123 绘制椭圆 124 设置背景色和前景色 125 设置线条类型 126 设置填充类型和填充颜色 127 图形文本的输出 128 金刚石图案 ...
119 超长正整数的加法 第四部分 图形篇 120 绘制直线 121 绘制圆 122 绘制圆弧 123 绘制椭圆 124 设置背景色和前景色 125 设置线条类型 126 设置填充类型和填充颜色 127 图形文本的输出 128 金刚石图案 ...
119 超长正整数的加法 第四部分 图形篇 120 绘制直线 121 绘制圆 122 绘制圆弧 123 绘制椭圆 124 设置背景色和前景色 125 设置线条类型 126 设置填充类型和填充颜色 127 图形文本的输出 128 金刚石图案 ...