用三角数之和表示自然数

Question

三角数是事物可以排列成三角形的数。

例如，1、3、6、10、15...都是三角数。

o

o o

o o o

o o o o

是n=4三角形数

的形状

what I have to do is A natural number N is given and I have to print N expressed by sum of triangular numbers.

如果 N = 4

输出应该是

1 1 1 1

1 3

3 1

否则如果 N = 6

输出应该是

1 1 1 1 1 1

1 1 1 3

1 1 3 1

1 3 1 1

3 1 1 1

3 3

6

我已经搜索了几个小时，但找不到答案...

请帮忙

（我不确定这是否有帮助，但我发现

如果当 n 为 k 时我说 T(k) 是三角数，那么

T(k) = T(k-1) + T(k-3) + T(k-6) + .... + T(k-p) 而 (k-p) > 0

p 是三角数 )

这是 k=-1 的代码（阅读下面的评论）

#include <iostream>
#include <vector>

using namespace std;

long TriangleNumber(int index);
void PrintTriangles(int index);

vector<long> triangleNumList(450); //(450 power raised by 2 is about 200,000)
vector<long> storage(100001);

int main() {
    int n, p;

    for (int i = 0; i < 450; i++) {
        triangleNumList[i] = i * (i + 1) / 2;
    }
    cin >> n >> p;
    cout << TriangleNumber(n);
    if (p == 1) {
        //PrintTriangles();
    }

    return 0;
}

long TriangleNumber(int index) {
    int iter = 1, out = 0;
    if (index == 1 || index == 0) {
        return 1;
    }
    else {
        if (storage[index] != 0) {
            return storage[index];
        }
        else {
            while (triangleNumList[iter] <= index) {
                storage[index] = ( storage[index] + TriangleNumber(index - triangleNumList[iter]) ) % 1000000;
                iter++;
            }
        }
    }
    return storage[index];
}
void PrintTriangles(int index) {
    // What Algorithm?
}

Answer 1

这里是一些递归的 Python 3.6 代码，它打印输入目标的三角数之和。在这个版本中，我优先考虑代码的简单性。您可能希望对输入值添加错误检查、计算总和、存储列表而不只是打印它们，并将整个例程包装到一个函数中。设置三角数列表也可以用更少的代码行来完成。

您的代码节省了时间，但由于 "memoizing" 三角数（存储和重复使用它们而不是总是在需要时计算它们）而恶化了内存使用。如果愿意，您可以对总和列表执行相同的操作。也可以在动态编程风格中更多地做到这一点：找到 n=1 然后 n=2 等的总和列表。我将把所有这些留给你。

""" Given a positive integer n, print all the ways n can be expressed as
the sum of triangular numbers.
"""
def print_sums_of_triangular_numbers(prefix, target):
    """Print sums totalling to target, each after printing the prefix."""
    if target == 0:
        print(*prefix)
        return
    for tri in triangle_num_list:
        if tri > target:
            return
        print_sums_of_triangular_numbers(prefix + [tri], target - tri)

n = int(input('Value of n ? '))

# Set up list of triangular numbers not greater than n
triangle_num_list = []
index = 1
tri_sum = 1
while tri_sum <= n:
    triangle_num_list.append(tri_sum)
    index += 1
    tri_sum += index

# Print the sums totalling to n
print_sums_of_triangular_numbers([], n)

以下是此代码两次运行的打印输出：

Value of n ? 4
1 1 1 1
1 3
3 1

Value of n ? 6
1 1 1 1 1 1
1 1 1 3
1 1 3 1
1 3 1 1
3 1 1 1
3 3
6

用三角数之和表示自然数

Expressing Natural Number by sum of Triangular numbers

math

triangular