Определить минимальное число пирамид которое требуется сложить

viktoriua97 · Регистрация: 28.01.2016

Author24 — интернет-сервис помощи студентам

Капитан Вася всегда держит на своем корабле запас пушечных ядер для борьбы с пира-
тами. Так как он привык во всем поддерживать порядок, он хранит ядра в виде пирамид.
Каждый из слоев одной пирамиды является равносторонним заполненным ядрами треуголь-
ником, сторона которого содержит ровно k ядер. Сторона основания пирамиды состоит из
n ядер, в следующем слое сторона состоит из n − 1 ядра, и т.д., пока на вершину не будет
положено одно ядро (которое является равносторонним треугольником со стороной 1).
Например, пирамида размера 3 состоит из трех уровней, выглядящих так (сверху вниз):

C++

X
 
 X
X X
 
  X
 X X
X X X

Ясно, что каждый из треугольников может содержать только 1, 3, 6, 10 и т.д. ядер. Таким
образом, пирамида может содержать только 1, 4, 10, 20, и т.д. ядер.
Вася отправляется в плавание и берет с собой ровно m ядер. Какое минимальное число
пирамид требуется ему сложить из них на своем корабле?

C++

Входные данные 
5
1
5
9
15
91

C++

Выходные данные
1
2
3
3
2

ФедосеевПавел · 11.02.2017, 19:17

Я бы реализовал и сверил два подхода:
1. Условно говоря "тетраэдрическая система счисления".
2. Динамическое программирование.

Тетраэдрические числа:
https://ru.wikipedia.org/wiki/... ские_числа
1, 4, 10, 20, 35, 56, 84, 120, 165, 220, 286, 364, 455, 560, 680, 816, 969, … (последовательность A000292 в OEIS).

Решение по 1-му варианту отпадает, т.к. даже в примере для 91 результат 2. А при переводе в "тетраэдрическую систему счисления" получили бы 91=84+4+1+1+1, хотя решением является 91=35+56.

Значит остаётся динамическое программирование. Алгоритм будет напоминать и алгоритм Дейкстры и решение задачи "калькулятор на 3 действия" - Определите, какое наименьшее число операций необходимо, чтобы получить из числа 1 число N
1. Пусть определён массив T[300000+1], каждый элемент которого T[i] в конце вычислений будет хранить минимальное количество пирамид.
2. Инициализируем T[]
- заполняем все элементы значением MAX_INT - подобие бесконечности.
- последовательно вычисляя тетраэдрические числа i, заполняем соответствующие T[i] единицами
3. Начиная с максимального тетраэдрического числа, входящего в массив T[] выполняем следующее
- пусть CurrTetrahedral - текущее тетраэдрическое число (для него T[CurrTetrahedral]==1)
- пусть CurrMin - текущее минимальное количество пирамид. В момент рассмотрения числа i==CurrTetrahedral, значение CurrMin равно 1.
- рассмотрим число i=i+CurrTetrahedral. Для него CurrMin=CurrMin+1. Но ведь в T[i] уже что-то хранится. Тогда, для обеспечения минимального числа пирамид T[i]=min(T[i], CurrMin). Ну и т.к. T[i] возможно изменилось - пересчитаем и CurrMin=T[i].
- перейдём к следующему i, пока не переберём все индексы массива T[]
- после рассмотрения всех вариантов для CurrTetrahedral, возьмём предыдущее тетраэдрическое число - обновим CurrTetrahedral (будем искать в T[j] вниз, пока не найдём T[j]==1)

После всего этого, получим массив T[i], из которого и будем брать ответы.

Можно прикрутить рекурсию в инициализацию для вычисления следующего тетраэдрического числа, а при выходе из рекурсии - выполнять перебор индексов для него. Это сократит перебор при поиске предыдущего числа.

Новичок · 12.02.2017, 19:43

Когда-то давно писал, вот готовый код.

C++

#include <iostream>
#include <vector>
#include <algorithm>
 
using namespace std;
 
int main() {
    const size_t inf = 3e5;
    vector <size_t> a(inf + 1, inf);
    a[0] = 0;
    for (size_t i = 1; i < a.size(); i++) {
        size_t s1 = 0, s2 = 0;
        for (size_t j = 1; ; j++) {
            s1 += j;
            s2 += s1;
            if (i >= s2) a[i] = min(a[i], a[i - s2] + 1);
            else break;
        }
    }
    size_t t;
    cin >> t;
    for (size_t i = 0; i < t; i++) {
        size_t m;
        cin >> m;
        cout << a[m] << "\n";
    }
}

viktoriua97 · 18.02.2017, 08:14 **[ТС]**

ФедосеевПавел, Удалите пожалуйста тему "Определить минимальное число пирамид которое требуется сложить" - C++

ФедосеевПавел · 18.02.2017, 21:17

viktoriua97, это неподвластный мне раздел, в этом разделе у меня равные с вами права и обязанности.
Но кроме моего бессилия, ещё есть правила форума, согласно которым

2.2. Сообщения и темы, а также другой контент, размещаемый на форуме, по просьбам пользователей не удаляется и не закрывается.

ФедосеевПавел Модератор 8541 / 4393 / 1651 Регистрация: 01.02.2015 Сообщений: 13,650 Записей в блоге: 9
	11.02.2017, 19:17	2
	Я бы реализовал и сверил два подхода: 1. Условно говоря "тетраэдрическая система счисления". 2. Динамическое программирование. Тетраэдрические числа: https://ru.wikipedia.org/wiki/... ские_числа 1, 4, 10, 20, 35, 56, 84, 120, 165, 220, 286, 364, 455, 560, 680, 816, 969, … (последовательность A000292 в OEIS). Решение по 1-му варианту отпадает, т.к. даже в примере для 91 результат 2. А при переводе в "тетраэдрическую систему счисления" получили бы 91=84+4+1+1+1, хотя решением является 91=35+56. Значит остаётся динамическое программирование. Алгоритм будет напоминать и алгоритм Дейкстры и решение задачи "калькулятор на 3 действия" - Определите, какое наименьшее число операций необходимо, чтобы получить из числа 1 число N 1. Пусть определён массив T[300000+1], каждый элемент которого T[i] в конце вычислений будет хранить минимальное количество пирамид. 2. Инициализируем T[] - заполняем все элементы значением MAX_INT - подобие бесконечности. - последовательно вычисляя тетраэдрические числа i, заполняем соответствующие T[i] единицами 3. Начиная с максимального тетраэдрического числа, входящего в массив T[] выполняем следующее - пусть CurrTetrahedral - текущее тетраэдрическое число (для него T[CurrTetrahedral]==1) - пусть CurrMin - текущее минимальное количество пирамид. В момент рассмотрения числа i==CurrTetrahedral, значение CurrMin равно 1. - рассмотрим число i=i+CurrTetrahedral. Для него CurrMin=CurrMin+1. Но ведь в T[i] уже что-то хранится. Тогда, для обеспечения минимального числа пирамид T[i]=min(T[i], CurrMin). Ну и т.к. T[i] возможно изменилось - пересчитаем и CurrMin=T[i]. - перейдём к следующему i, пока не переберём все индексы массива T[] - после рассмотрения всех вариантов для CurrTetrahedral, возьмём предыдущее тетраэдрическое число - обновим CurrTetrahedral (будем искать в T[j] вниз, пока не найдём T[j]==1) После всего этого, получим массив T[i], из которого и будем брать ответы. Можно прикрутить рекурсию в инициализацию для вычисления следующего тетраэдрического числа, а при выходе из рекурсии - выполнять перебор индексов для него. Это сократит перебор при поиске предыдущего числа. 1

viktoriua97 0 / 0 / 0 Регистрация: 28.01.2016 Сообщений: 7
	18.02.2017, 08:14 [ТС]	4
	ФедосеевПавел, Удалите пожалуйста тему "Определить минимальное число пирамид которое требуется сложить" - C++ 0

ФедосеевПавел Модератор 8541 / 4393 / 1651 Регистрация: 01.02.2015 Сообщений: 13,650 Записей в блоге: 9
	18.02.2017, 21:17	5
	viktoriua97, это неподвластный мне раздел, в этом разделе у меня равные с вами права и обязанности. Но кроме моего бессилия, ещё есть правила форума, согласно которым 2.2. Сообщения и темы, а также другой контент, размещаемый на форуме, по просьбам пользователей не удаляется и не закрывается. 0