math - 用三角数之和表示自然数
问题描述
三角形数是事物可以排列成三角形时的数字。
例如,1、3、6、10、15... 是三角形数。
○
哦
哦哦
哦哦
是 n=4 三角形数的形状
我要做的是给定一个自然数 N,我必须打印由三角形数之和表示的 N。
如果 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(kp) 而 (kp) > 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?
}
解决方案
这是一些递归 Python 3.6 代码,它打印三角数的总和,这些总和是输入目标的总和。在这个版本中,我优先考虑代码的简单性。您可能希望对输入值添加错误检查、计算总和、存储列表而不是仅仅打印它们,并将整个例程包装到一个函数中。建立三角数列表也可以用更少的代码行来完成。
您的代码通过“记忆”三角数(存储和重用它们而不是在需要时总是计算它们)节省了时间,但恶化了内存使用。如果你愿意,你可以对总和列表做同样的事情。也可以在动态编程风格中进行更多操作:找到n=1
then forn=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
推荐阅读
- php - 在使用 Php 之间使用冒号 (:) 访问变量的 Json 值
- uwp - 在 C++/WinRT 项目中使用 CoreDispatcher::RunAsync 时获取“在定义之前无法使用返回‘auto’的函数”
- php - PHP将此时间戳转换为纪元/unix时间(int)
- c - 通过调用无意返回的函数来退出 switch 语句是一种好的编码习惯吗
- mysql - 触发器检查两个表上的多个值是否相等,然后更新表
- c# - 如何在 xamarin 表单中创建具有两种布局的页面
- c++ - 在 C++ 中使用取决于函数的大小初始化数组
- sql - 将数据从一个表迁移到另一个表
- java - 信件计数应用程序
- mongodb - 使用 mongodb 和 kafka 消费者的并发更新问题