Выражение натурального числа суммой треугольных чисел - PullRequest
Новая
       21

Выражение натурального числа суммой треугольных чисел

0 голосов
/ 07 октября 2018

Треугольные числа - это числа, которые представляют собой число вещей, когда вещи могут быть расположены в треугольной форме.

Например, 1, 3, 6, 10, 15 ... являются треугольными числами.

o

oo

ooo

oooo

- это форма 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 31

1 3 1 1

3 1 1 1

3 3

6

Я искал несколько часов и не мог найти ответы ...

, пожалуйста, помогите.

(Я не уверен, что это могло бы помочь, но я обнаружил, что Если я говорю, что T (k) - Треугольное число, когда n - 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?
}

1 Ответ

0 голосов
/ 08 октября 2018

Вот некоторый рекурсивный код Python 3.6, который печатает суммы треугольных чисел, которые составляют введенную цель.Я расставил приоритеты в простоте кода в этой версии.Возможно, вы захотите добавить проверку ошибок для входного значения, считая суммы, сохраняя списки, а не просто печатая их, и оборачивая всю подпрограмму в функцию.Настройка списка треугольных чисел может также выполняться в меньшем количестве строк кода.

Ваш код сэкономил время, но уменьшил использование памяти, «запоминая» треугольные числа (сохраняя и повторно используя их, а не всегда вычисляя их при необходимости).).Вы можете сделать то же самое со списками сумм, если хотите.Это также можно сделать в стиле динамического программирования: найдите списки сумм для 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
...