一道有趣的题目,把一个整数num拆分成n个整数的合,要求这n个整数各不相同,不能有重复,如num为10,则有以下几种情况:
1 9
2 8
3 7
4 6
1 2 7
1 3 6
1 4 5
1 2 3 4
我想了一个算法,不知正确与否,希望各位大牛来拍砖。
分析:
首先,把10拆分成两个数,因为各个数不能相同,所以只当第一个数为4时为止,即
1 9
2 8
3 7
4 6
其次,再把10拆分1和9,对9采用上面的拆法,9会被拆成如下:
1 8
2 7
3 6
4 5
因为各数字不能重复出现,所以把1 8这对去掉,所以10被拆成如下:
1 2 7
1 3 6
1 4 5
再次,再把10拆分成1、2和7,对7采用上面的拆法,7会被拆成如下:
1 6
2 5
3 4
1 2 4
因为拆分出的数字中不能含有1、2所以只留下3 4这对数字,所以10被拆成如下:
1 2 3 4
最后,再把10拆分成1、2、3和4,由于4拆分出的两个数字必须大于3,这是不可能的,所以已经无法继续拆分。至此10的拆分结束。
从上面的分析可以看出,最后一步都是把经过前面拆分后剩下的数值拆分成两个数,而前面的拆分则是拆分出1或1、2或1、2、3……,由此写出了第一个程序:
package calc.printsum;
import junit.framework.TestCase;
/**
* 打印和为num的所有情况,并且每行中不能有重复数字
*/
public class PrintResult1 extends TestCase {
public void test() {
int num = 10;
// i <= Math.ceil(num / 2)
//因为i再大就会打出重复数字了
for (int i = 1; i <= Math.ceil(num / 2); i++) {
splitNum(i, num - sumToN(i));
// System.out.println("------------");
}
}
/**
* @param start
* @param num
*/
private void splitNum(int start, int num) {
if (start > num) {
return;
}
for (int i = start; i <= Math.ceil(num / 2) && i != (num - i); i++) {
// 打出从1到start的数字
printSerial(start);
// 把剩下的num分成两半
System.out.print(i + " ");
System.out.println(num - i);
}
}
/**
* 顺序打印1到n
* @param n
*/
private void printSerial(int n) {
for (int i = 1; i < n; i++) {
System.out.print(i + " ");
}
}
/**
* 计算1到n的总和
* @param n
* @return
*/
private int sumToN(int n) {
int sum = 0;
for (int i = 1; i < n; i++) {
sum += i;
}
return sum;
}
}
函数printSerial由于是i<n所以当i=1时是不会打印任何东西的,所以splitNum的for循环中当start是1时实际上只执行了“把剩下的num分成两半”的两句打印语句,这正是我们想要的。
分析此类可以发现存在两个问题:
1、sumToN实际上是不需要的,我们完全可以充分利用先计算过的结果,从而无须每次都从头到尾计算前n个数的和;
2、如果把System.out.println("------------");这一句的注释打开,可以看到在最后一组数字后面还打多了两次------------,如下:
1 2 3 4
------------
------------
------------
于是有了修改后的PrintResult2:
package calc.printsum;
import junit.framework.TestCase;
/**
* 打印和为num的所有情况,并且每行中不能有重复数字
*/
public class PrintResult2 extends TestCase {
public void test() {
int num = 10;
int sum = 0;
// i <= Math.ceil(num / 2)
//因为i再大就会打出重复数字了
for (int i = 1; i <= Math.ceil(num / 2); i++) {
// sum利用了上次计算的结果
sum += (i - 1);
// 由i > (num - sum) / 2演变而来,当i再增大时num-sum的值已经无法继续拆分成两个不同于前i个数字的数字之合了
if (2 * i > (num - sum)) {
break;
}
splitNum(i, num - sum);
// System.out.println("------------i:" + i + " sum:" + sum
// + " (num - sum) / 2:" + (num - sum) / 2);
}
}
/**
* 把num按从start开始分离成两个不同的数相加
* @param start
* @param num
*/
private void splitNum(int start, int num) {
if (start >= num) {
return;
}
for (int i = start; i <= Math.ceil(num / 2) && i != (num - i); i++) {
// 打出从1到start的数字
printSerial(start);
// 把剩下的num分成两半
System.out.print(i + " ");
System.out.println(num - i);
}
}
/**
* 顺序打印1到n
*
* @param n
*/
private void printSerial(int n) {
for (int i = 1; i < n; i++) {
System.out.print(i + " ");
}
}
}
这是我对这个题目的思考过程,有错误的地方欢迎大牛批评指出。
分享到:
相关推荐
java 字母数字分离 字母大小写互换 将数字排在字母的后面
给定一个整数n(1≤n≤100000000),要求从个位开始分离出它的每一位数字。从个位开始按照从低位到高位的顺序依次输出每一位数字。 【输入】 输入一个整数,整数在1到100000000之间。 【输出】 从个位开始按照从低位...
可以分离EXCEL中的数字和文字,很难得的用法。
用汇编语言将字符串中的字母和数字分开存储
能够在电子表格中快速提取分离汉字、字母、数字
测试matlab分离字符串和数字的测试数据,可用来测试matlab分离数字和字符串的代码
易语言正则表达式分离汉字英文数字源码,正则表达式分离汉字英文数字,子程序,子程序1
1.将文件data1的内容读出; 2.去除掉杂质(不是构成数字的符号),将这些字符转换为数字; 3.将整型数据输出并求和; 4.将浮点型数据输出并求和
课程设计基于Java实现前后端分离的数字图像检索系统源码(前端+后端).tar课程设计基于Java实现前后端分离的数字图像检索系统源码(前端+后端).tar课程设计基于Java实现前后端分离的数字图像检索系统源码(前端+后端)....
数字放大器分离光电传感器 (激光型)pdf,数字放大器分离光电传感器 (激光型) E3C-LDA
23GUI设计+图像处理基于数字图像处理,设计实现一个自然场景下公路交通限速标志分割和识别的程序。要求系统具有界面,并实现以下功能:1)读入自然场景下包含交通标志的图像;2)对图像进行预处理;3)限速交通标志...
word分离文本和数值,是excel中回用到的一个常用函数,学习他很有用哦,希望大家能学会,谢谢大家的支持
foremost是一个 控制台程序,用于根据页眉,页脚和内部数据结构 恢复文件。 Foremost可以处理图像文件,例如由 dd, Safeback, Encase等生成的图像文件,或直接在驱动器上。页眉和页脚可以由配置文件指定,也可以...
java 作业 数字加密器 文字母转化 整数分离 水仙花数 计算器 韩信点兵 累加和 猜数字
用 Python 实现一组手写数字识别。使用keras+opencv进行简单的实现。首先进行图像中数字的目标检测与分割,将图片中的数字分离出来然后进行单独识别。使用的数据集为mnist手写数字识别库,采用卷积神经网络进行识别
数字图像处理,高斯滤波,通过可分离性进行加速,。。。
信息时代下图书馆的数字化和“形神分离”.pdf
分离数字字母汉字符号-易语言.zip
只是一个简单的函数,将单个数字(也是小数)与其组成数字分开。 例如,如果号码是 4328.76, 该模型将此数字分隔为 6 位数字/输出信号: '4' 、 '3' 、 '2' 、 '8' 、 '7' 和 '6'。
行业资料-电子功用-数字电视的彩色分离器