任意整数有⼏种分解⽅法java_整数的分解⽅法腾讯 2017春招真题
题⽬
如下⽰例:
1:共0种分解⽅法;
2:共0种分解⽅法;
3:3=2+1 共1种分解⽅法;
4:4=3+1=2+1+1 共2种分解⽅法;
5:5=4+1=3+2=3+1+1=2+2+1=2+1+1+1 共5种分解⽅法
6:6=5+1=4+2=4+1+1=3+2+1=3+1+1+1=2+2+1+1=2+1+1+1+1 共7种分解⽅法
以此类推,求⼀任意整数num有⼏种分解⽅法?
输⼊⼀个数字(1到90),输出该整数的分解⽅法个数
如:
输⼊:2——输出:0
输⼊:3——输出:1
输⼊:5——输出:5
分析
为保证输出的唯⼀性,保持降序排列
列表分析3~7的分解情况:
当前数
分解情况以1结尾
分解情况以2结尾
分解情况以3结尾
分解情况总数
3
① 2+1
---
nextint()方法
---
1
4
① 3+1
② 2+1+1
(②是将3进⼀步分解)
---
(2+2不算,分解出来的数不能都相等)
---
2
5
① 4+1
② 2+2+1
③ 3+1+1
④ 2+1+1+1
(②--④是将4进⼀步分解,此时4=2+2也算)① 3+2
---
5
6
① 5+1
② 4+1+1
③ 2+2+1+1
④ 3+1+1+1
⑤ 2+1+1+1+1
⑥ 3+2+1
(②--⑥是将5进⼀步分解)
① 4+2
---
(3+3不算)
7
7
① 6+1
② 3+3+1
③ 5+1+1
④ 4+1+1+1
⑤ 2+2+1+1+1
⑥ 3+1+1+1+1
⑦ 2+1+1+1+1+1
⑧ 3+2+1+1
⑨ 4+2+1
(②--⑨是将5进⼀步分解)
① 5+2
② 3+2+2
(②是将5进⼀步分解,且只取5的分解情况中结尾数>=2的,才能保证降序排列)
① 4+3
12
总结分解⽅法:
对于数num,按照分解情况的结尾数字考虑:以1结尾,以2结尾,...,以Math.floor((num - 1) / 2)结尾,每种结尾都先进⾏⼀次分解(以7为例,以1结尾时分解成6+1,以2结尾分解成5+2,以3结尾分解成4+3)
对于第⼀次分解出的两个数(num1,num2),进⼀步分解num1,且只在num1 > 2*num2 时分解num1(否则⽆法保证降序,例:
5=3+2,3继续分解出2+1,则5=2+1+2不是降序)
若num1是偶数,计算分解情况时+1(例:5=4+1,进⼀步分解4时,要考虑4=2+2)
保证num1进⼀步分解的结尾的数>=num2(例:7=5+2,进⼀步分解5时,只能将5分解成3+2,若分解成任意以1结尾的情况,如4+1,则7=4+1+2不是降序)
因此,我们运⽤动态规划的⽅法,从3开始往⼤数分析,构造⼆维数组,横坐标表⽰当前分析的数,纵坐标表⽰当前分解情况结尾的数
解答
解法1:(我)
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
while (sc.hasNext()){
int num = sc.nextInt();
int result = 0;
int[][] arr = new int[num+1][];
for(int i = 3; i <= num; i++){
int columnNum = (int)Math.floor((i-1)/2d);
arr[i] = new int[columnNum];
for(int j = 0; j < columnNum; j++){
arr[i][j] = 1;
int num2 = j + 1;
int num1 = i - num2;
if(num1 > 2 * num2){//只有这种情况才分解
if(num1 % 2 == 0){//num1是偶数,计算分解情况时+1
arr[i][j]++;
}
//计算数1的分解情况
for (int k = j; k < arr[num1].length; k++){
arr[i][j] += arr[num1][k];
}
}
}
}
/
/ 输出整个⼆维数组的情况
// for(int i = 3; i <= num; i++){
// for(int j = 0; j < arr[i].length;j++){
// System.out.println("arr["+i+"]["+j+"] is: "+arr[i][j]); // }
// }
if(num == 1 || num == 2) result = 0;
else{
for(int i = 0; i < arr[num].length;i++){
result += arr[num][i];
}
}
System.out.println(result);
}
}
}

版权声明:本站内容均来自互联网,仅供演示用,请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198,我们将在24小时内删除。