MENU

第六届蓝桥杯Java A——加法变乘法

March 11, 2019 • Read: 2699 • 算法阅读设置

我们都知道:1+2+3+ ... + 49 = 1225
现在要求你把其中两个不相邻的加号变成乘号,使得结果为2015

比如:
1+2+3+...+10*11+12+...+27*28+29+...+49 = 2015就是符合要求的答案。

请你寻找另外一个可能的答案,并把位置靠前的那个乘号左边的数字提交(对于示例,就是提交10)

答案:16

public class Main {
    static int[] book = new int[49];
    static int[] res = new int[2];

    public static void main(String[] args) {
        dfs(0);
    }

    static void dfs(int idx) {
        if (idx == 2) {
            if (check())
                System.out.println(res[0] + " " + res[1]);
            return;
        }
        for (int i = 1; i <= 48; i++) { // * 放在i这个数字的右边
            if (book[i] == 0) {
                if (idx == 1 && Math.abs(i - res[0]) != 1) {
                    book[i] = 1;
                    res[idx] = i;
                    dfs(idx + 1);
                    book[i] = 0;
                } else {
                    book[i] = 1;
                    res[idx] = i;
                    dfs(idx + 1);
                    book[i] = 0;
                }
            }
        }
    }

    static boolean check() {
        int ans = 0;
        for (int i = 1; i <= 49; i++)
            if (res[0] == i || res[1] == i)
                    ans += (i * (i + 1));
        
        for (int i = 1; i <= 49; i++) {
            if (res[0] == i || res[1] == i || res[0] + 1 == i || res[1] + 1 == i)
                continue;
            ans += i;
        }
        return ans == 2015;
    }
}

解法二:

public class Main {

    public static void main(String[] args) {
        for (int i = 1; i <= 46; i++) 
            for (int j = i + 2; j <= 48; j++)
                if (i * (i + 1) - ((i << 1) | 1) + j * (j + 1) - ((j << 1) | 1) == 2015-1225)
                    System.out.println(i + " " + j);
    }
}
Archives Tip
QR Code for this page
Tipping QR Code