时间戳

首页 > 解决方案 > 如何在立方体图案中找到立方体的数量，其中中心的立方体沿着手臂有 4 个立方体

algorithm - 如何在立方体图案中找到立方体的数量，其中中心的立方体沿着手臂有 4 个立方体

问题描述

从早上开始，我一直在努力解决以下hackerEarth 问题，并且不知道出了什么问题。你能指出代码中的错误吗？

在立方体模式中，最下层和最上层包含 1 个立方体。接下来的内层包含 5 个立方体，每个立方体中心有一个立方体，4 个立方体沿着手臂覆盖中央的立方体。以类似的方式，内层包含 13 个立方体，依此类推。连续层中立方体的数量首先增加到第 ((n+1)/2) 级，然后开始减少，以相同的方式，即形状是对称的。

对于给定的整数 N（奇数），求立方体。 在此处输入图像描述

例如：设N = 7，那么立方体层的顺序如下：1、5、13、25、13、5、1。所以对于N = 7，答案是1 + 5 + 13 + 5 + 1 = 63 .

我编写的以下代码似乎不适用于所有测试用例，并且显然花费的时间比预期的要多。

    static ulong FindCubes(long N)
    {
       if (N == 1)
            return 1;
        if (N == 2)
            return 5;

        ulong factor = 4, sum = 1, lastNum =1;

        for (int i = 1; i < (N / 2 + 1); i++)
        {                
            lastNum += factor;
            sum += lastNum;                
            factor += 4;
        }
        return sum * 2 - lastNum; ;
    }

标签： algorithm

解决方案

有一些方法可以做到这一点，实际上正如评论中提到的那样，最有效的方法（在我看来）是为Arithmetic Progressions系列中的每个数字执行并找到一个公式 - 根据维基百科，它是：

n^2 + (n-1)^2

但不要停在那里！现在您可以使用相同的方法找到该系列中的一般元素：

和 n^2 + (n-1)^2, n=1 到 k

根据wolfram alpha是

1/3 * (k + 2 * k^3)

所以现在你可以编写一个简单的python代码：

n = 7
# Calculate number of layers to sum
layers = (n - 1) / 2
# Sum the layers using the new formula
sum_of_layers = 1/3 * (layers + 2 * layers ** 3)
# Adding the middle item (for N=7 it would be 25)
middle_index = layers + 1
# Using the formula from the Arithmetic Progressions
middle_item = middle_index ** 2 + (middle_index-1) ** 2
# Printing the result
print(int(sum_of_layers * 2 + middle_item))

导致：

63

推荐阅读