PS：这是我人生中写的第一篇博客，当时发表在CSDN上。
递归里面还有递归 ， 三个递归嵌套解决奥数题 :
在下面的数中间填上“+”，“-”，使计算结果为100：123456789=100。
解题思路： 我们可以在9个数字（1、2、3、4、5、6、7、8、9）之间插入的符号个数最多为8个，符号放置的位置只能从一取到八。
| 1 | 一 | 2 | 二 | 3 | 三 | 4 | 四 | 5 | 五 | 6 | 六 | 7 | 七 | 8 | 八 | 9 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
第一步，先考虑符号的个数，有多少个运算符号，以符号个数=2为例。
第二步，考虑符号的放置位置，2个符号所有可能放置的位置如下：
（一二），（一三），（一四），（一五），（一六），（一七），（一八）
（二三），（二四），（二五），（二六），（二七），（二八），
（三四），（三五），（三六），（三七），（三八），
……
第三步，再考虑符号为加或为减：
以符号位置为（一二）的情况举例，可能的结果就有：
- 1+2+3456789
- 1+2-3456789
- 1-2+3456789
- 1-2-3456789
总共三步探测结果，每一个步骤一个递归算法。
代码实现：
public class aoShuJiaJian_QiuHe {
// 输出
public static void print(int[] oi, int[] sub_array, int[] xy, int jieguo) {
System.out.print(sub_array[0]);
for (int i = 1; i < sub_array.length; i++) {
if (oi[i - 1] == 0) {
System.out.print("+" + sub_array[i]);
} else {
System.out.print("-" + sub_array[i]);
}
}
System.out.print("=" + jieguo);
System.out.println();
// 输出符号的位置
// for (int i = 0; i < xy.length; i++) {
// System.out.print(xy[i] + " ");
// }
// System.out.println();
}
// 计算结果
public static void jiSuan_jieguo(int n, int[] oi, int[] sub_array, int[] xy) {
int qiuhe = sub_array[0];
for (int i = 1; i < sub_array.length; i++) {
//0为加，1为减
if (oi[i - 1] == 0) {
qiuhe = qiuhe + sub_array[i];
} else {
qiuhe = qiuhe - sub_array[i];
}
}
if (qiuhe == 100) {
print(oi, sub_array, xy, qiuhe); //结果等于100输出
}
}
// 计算被符号分割的各各数
// 例如符号个数为3 符号位为3，5，7 则被符号分割的数为123，45，67，89
// array 要计算的数组
// n为符号个数
// xy保存的是符号的位置
// oi保存的是加减符号
public static void jiSuan_even(int[] array, int n, int[] xy, int[] oi) {
// 保存被符号分割的数
// 符号若为N个，则被符号分割的数的个数为N+1个
int[] sub_array = new int[n + 1];
for (int i = 0; i < n + 1; i++) {
if (i == 0) {
// 例如xy[i]=3，则sub_array[i]=1*100+2*10+3*1
for (int j = 0; j < xy[i]; j++) {
int temp = 1;
// cifang意为 次方
for (int cifang = xy[i] - j; cifang > 1; cifang--) {
temp = temp * 10;
}
sub_array[i] = sub_array[i] + array[j] * temp;
}
} else if (i > 0 && i < n) {
for (int j = xy[i - 1]; j < xy[i]; j++) {
int temp = 1;
for (int cifang = xy[i] - j; cifang > 1; cifang--) {
temp = temp * 10;
}
sub_array[i] = sub_array[i] + array[j] * temp;
}
} else {
for (int j = xy[i - 1]; j < array.length; j++) {
int temp = 1;
for (int cifang = array.length - j; cifang > 1; cifang--) {
temp = temp * 10;
}
sub_array[i] = sub_array[i] + array[j] * temp;
}
}
}
// 计算结果
jiSuan_jieguo(n, oi, sub_array, xy);
}
//////////////////////////////////////////////////////////////
// 第三个递归 用来确定加减号
public static void fuhao_oi_(int[] array, int n, int[] xy, int[] oi, int i) {
if (i == n) {
jiSuan_even(array, n, xy, oi);
return;
}
for (int k = 0; k <= 1; k++) //二叉树 0为加 1为减
{
oi[i] = k;
fuhao_oi_(array, n, xy, oi, i + 1);
}
}
/////////////////////////////////////////////////////////////////////
// 第二个递归 确定符号位置
public static void fuhaoxy(int[] array, int n, int[] xy, int index) {
if (index == n) {
if (n == 1 && xy[index - 1] > 8) {
return;
}
// 符号位置不能重合 不要出现重复
for (int j = n - 1; j >= 1; j--) {
if (xy[j] - xy[j - 1] <= 0) {
return;
}
}
int[] oi = new int[n]; // oi数组 保存符号
fuhao_oi_(array, n, xy, oi, 0);
return;
}
for (int i = 1; i <= 8; i++) {
xy[index] = i;
fuhaoxy(array, n, xy, index + 1);
}
}
/////////////////////////////////////////////////////////////////////
// 第一个递归 确定符号的个数。
public static void fuhaosum(int[] array, int n) {
if (n > 8) {
return;
}
int[] xy = new int[n];
for (int i = 1; i <= n; i++) {
xy[i - 1] = i;
fuhaoxy(array, n, xy, 0);
}
fuhaosum(array, n + 1);
}
public static void main(String[] args) {
int[] array = new int[9];
for (int i = 1; i <= 9; i++) {
array[i - 1] = i;
}
fuhaosum(array, 1);
}
}
运行结果如下：
123-45-67+89=100
123-45-67+89=100
123-45-67+89=100
123+4-5+67-89=100
123+45-67+8-9=100
123+4-5+67-89=100
123+45-67+8-9=100
123+4-5+67-89=100
123+45-67+8-9=100
123+4-5+67-89=100
123+45-67+8-9=100
1+2+34-5+67-8+9=100
1+23-4+5+6+78-9=100
1+23-4+56+7+8+9=100
12+3+4+5-6-7+89=100
12-3-4+5-6+7+89=100
12+3-4+5+67+8+9=100
123-4-5-6-7+8-9=100
1+2+34-5+67-8+9=100
1+23-4+5+6+78-9=100
1+23-4+56+7+8+9=100
12+3+4+5-6-7+89=100
12-3-4+5-6+7+89=100
12+3-4+5+67+8+9=100
123-4-5-6-7+8-9=100
1+2+34-5+67-8+9=100
1+23-4+5+6+78-9=100
1+23-4+56+7+8+9=100
12+3+4+5-6-7+89=100
12-3-4+5-6+7+89=100
12+3-4+5+67+8+9=100
123-4-5-6-7+8-9=100
1+2+34-5+67-8+9=100
1+23-4+5+6+78-9=100
1+23-4+56+7+8+9=100
12+3+4+5-6-7+89=100
12-3-4+5-6+7+89=100
12+3-4+5+67+8+9=100
123-4-5-6-7+8-9=100
1+2+34-5+67-8+9=100
1+23-4+5+6+78-9=100
1+23-4+56+7+8+9=100
12+3+4+5-6-7+89=100
12-3-4+5-6+7+89=100
12+3-4+5+67+8+9=100
123-4-5-6-7+8-9=100
1+2+34-5+67-8+9=100
1+23-4+5+6+78-9=100
1+23-4+56+7+8+9=100
12+3+4+5-6-7+89=100
12-3-4+5-6+7+89=100
12+3-4+5+67+8+9=100
123-4-5-6-7+8-9=100
1+2+3-4+5+6+78+9=100
1+2+3-4+5+6+78+9=100
1+2+3-4+5+6+78+9=100
1+2+3-4+5+6+78+9=100
1+2+3-4+5+6+78+9=100
1+2+3-4+5+6+78+9=100
1+2+3-4+5+6+78+9=100