码蹄集MT2042硬币塔

Question

问题描述

我在马蹄集上做题目，答案给的是C++版本，然后我用Java写的就有runtime error

代码

这是答案的

这是我的

import java.util.Scanner;
import java.util.*;

class Main {
    // coin保存每一级硬币塔硬币总数的数组
    // gold保存每一级硬币塔金币总数的数组
    static long[] coin = new long[45];
    static long[] gold = new long[45];

    public static void main(String[] args) {

        Scanner input = new Scanner(System.in);
        // code here
        int n = input.nextInt();
        int i = input.nextInt();

        coin[0] = 1;
        gold[0] = 1;

        for (int k = 1; k <= n; k++) {
            coin[k] = coin[k-1] * 2 + k + 2;
            gold[k] = gold[k-1] * 2 + k;
        }

        long result = find(n,i);

        System.out.println(result);

        input.close();
    }


    /**
     * 求出在k级硬币塔中从下往上数i个硬币，一共有多少个金币
     *
     * @param k    硬币塔的级别
     * @param i    从下往上数i个硬币
     * @return 包含的金币的个数
     */
    public static long find(long k, long i) {
        if (0 == i) return 0;
        if (0 == k) return 1;
        if (1 == i) return 0;
        if (i <= coin[(int) (k - 1)] + 1) return find(k - 1, i - 1);
        if (i <= coin[(int) (k - 1)] + 1 + k) return gold[(int) (k - 1)] + i - (coin[(int) (k - 1)] + 1);
        if (i <= 2 * coin[(int) (k - 1)] + 1 + k)
            return gold[(int) (k - 1)] + k + find(k - 1, i - k - 1 - coin[(int) (k - 1)]);
        return gold[(int) k];
    }
}

这是运行结果

想请教一下大家哪里出了问题，感激不尽

Answer 1

这段Java代码的语法是正确的，但是有一些细节需要注意。

首先，在输入时，应该使用nextLong()方法来读取long类型的数据，而不是nextInt()方法。因为硬币塔的级别和从下往上数的硬币数量可能会非常大，超出了int类型的范围。

其次，由于硬币塔问题是一个递归问题，可能会导致栈溢出的问题。因此，在使用递归求解硬币塔问题时，需要注意设置递归深度的限制，以避免栈溢出的情况发生。

最后，需要注意的是，硬币塔问题的解法有多种，不同的解法可能会存在一些细节上的差异。因此，在实际应用中，需要根据具体情况选择合适的解法和实现方式。