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

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

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

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

C++
1
2
3
4
5
6
7
8
X
 
 X
X X
 
  X
 X X
X X X

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

C++
1
2
3
4
5
6
7
Входные данные 
5
1
5
9
15
91

C++
1
2
3
4
5
6
Выходные данные
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++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#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. Сообщения и темы, а также другой контент, размещаемый на форуме, по просьбам пользователей не удаляется и не закрывается.

Новые блоги и статьи Все статьи Все блоги /
SDL3 для Web (WebAssembly): Реализация движения на Box2D v3 - трение и коллизии с повёрнутыми стенами 8Observer8 20.02.2026 Содержание блога Box2D позволяет легко создать главного героя, который не проходит сквозь стены и перемещается с заданным трением о препятствия, которые можно располагать под углом, как верхнее. . .	Конвертировать закладки radiotray-ng в m3u-плейлист damix 19.02.2026 Это можно сделать скриптом для PowerShell. Использование . \СonvertRadiotrayToM3U. ps1 <path_to_bookmarks. json> Рядом с файлом bookmarks. json появится файл bookmarks. m3u с результатом. # Check if. . .	Семь CDC на одном интерфейсе: 5 U[S]ARTов, 1 CAN и 1 SSI Eddy_Em 18.02.2026 Постепенно допиливаю свою "многоинтерфейсную плату". Выглядит вот так: https:/ / www. cyberforum. ru/ blog_attachment. php?attachmentid=11617&stc=1&d=1771445347 Основана на STM32F303RBT6. На борту пять. . .	Камера Toupcam IUA500KMA Eddy_Em 12.02.2026 Т. к. у всяких "хикроботов" слишком уж мелкий пиксель, для подсмотра в ESPriF они вообще плохо годятся: уже 14 величину можно рассмотреть еле-еле лишь на экспозициях под 3 секунды (а то и больше),. . .
И ясному Солнцу zbw 12.02.2026 И ясному Солнцу, и светлой Луне. В мире покоя нет и люди не могут жить в тишине. А жить им немного лет.	«Знание-Сила» zbw 12.02.2026 «Знание-Сила» «Время-Деньги» «Деньги -Пуля»	SDL3 для Web (WebAssembly): Подключение Box2D v3, физика и отрисовка коллайдеров 8Observer8 12.02.2026 Содержание блога Box2D - это библиотека для 2D физики для анимаций и игр. С её помощью можно определять были ли коллизии между конкретными объектами и вызывать обработчики событий столкновения. . . .	SDL3 для Web (WebAssembly): Загрузка PNG с прозрачным фоном с помощью SDL_LoadPNG (без SDL3_image) 8Observer8 11.02.2026 Содержание блога Библиотека SDL3 содержит встроенные инструменты для базовой работы с изображениями - без использования библиотеки SDL3_image. Пошагово создадим проект для загрузки изображения. . .

ФедосеевПавел Модератор 8659 / 4494 / 1669 Регистрация: 01.02.2015 Сообщений: 13,905 Записей в блоге: 12
	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], из которого и будем брать ответы. Можно прикрутить рекурсию в инициализацию для вычисления следующего тетраэдрического числа, а при выходе из рекурсии - выполнять перебор индексов для него. Это сократит перебор при поиске предыдущего числа. 1

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