0

Всем привет есть задача! Я её решил перебором, но эту задачу нужно решить жадным алгоритмом. Пожалуйста помогите мне решить эту задачу! И также вы можете подкинуть мне, где я могу прочитать про жадный алгоритм и на каких сайтах могу решить?

Вот задача:

Задано натуральное число x. Найдите число способов представить его в виде суммы четырех натуральных чисел: x = a + b + c + d, где a <= b <= c <= d.

Входной файл INPUT.TXT содержит целое число x (1 <= x <= 1500).
В выходной файл OUTPUT.TXT выведите ответ на задачу.

Примеры

Входные данные: 3
Ответ: 0

Входные данные: 5
Ответ: 1

3
  • Что-то не похоже, чтобы эта задача решалась жадно. Или перебор, или динамика же?
    – Qwertiy
    Commented 20 мар. 2017 в 16:20
  • Это считается аналитически (без программирования). Более жадный алгоритм придумать трудно.
    – user239133
    Commented 20 мар. 2017 в 17:22
  • попробуй упростить перебор до нескольких строк Commented 29 апр. 2020 в 17:31

3 ответа 3

4

Самое жадное - в смысле вычислительных ресурсов и времени - вычисление выглядит так:

long long count(long long n)
{
    return (((n+3)*n-9*(n%2))*n+72)/144;
}

См. Кнут, "Искусство программирования", т.4А, задача 7.2.1.4-31.

Сравнивал со своим решением

long long count(long n, long k = 4, long min = 1)
{
    if (n < min*k) return 0;
    if (k == 1) return 1;
    long long sum = 0;
    for(long long i = min; i <= n/k; ++i)
        sum += count(n-i,k-1,i);
    return sum;
}

Дает то же значение.

1

Если чисто N необходимо разложить на K слагаемых, то "разумный" алгоритм решения такой задачи будет основан на том факте, что для того, чтобы последовательность слагаемых была неубывающей, необходимо, чтобы первое слагаемое не превосходило [N / K] (более того, это еще и достаточное условие существования последовательности с таким первым слагаемым).

Отсюда получаем очевидный алгоритм: перебираем все возможные первые слагаемые S в диапазоне от 1 до [N / K], после чего применяем ту же самую логику для N - S и K - 1.

Будет ли такой алгоритм "жадным" в вашем определении - трудно сказать. Традиционная идея "жадного" алгоритма состоит в градиентной ("жадной") оптимизации некоей целевой функции. Я в данном случае не вижу никакой оптимизируемой целевой функции.

5
  • А что вы подразумеваете под N и K ? Commented 20 мар. 2017 в 16:57
  • @futuretourist: Я подправил первое предложение, чтобы ввести N и K. K в вашем случае - 4, а N - это ваш x. Commented 20 мар. 2017 в 17:00
  • Спасибо @AnT попробую! Commented 20 мар. 2017 в 17:02
  • Ваш код можно оптимизировать - ведь поскольку следующее значение в разложении не может быть меньше предыдущего, нужно начинать цикл с i = 1 только для первого вызова, но не для последующих. Кстати, он, похоже, вообще будет неверно работать из-за этого... Да, работает неверно.
    – Harry
    Commented 20 мар. 2017 в 17:17
  • Решение @Harry прошло! А вашем коде есть ошибки.Согласен с Harry Commented 20 мар. 2017 в 17:21
0

Задача больше математическая. Представим х как сумму единичек: х = 1 + 1 + 1 + ... + 1. Чтобы представить х как сумму 4 слагаемых, нужно разбить эту сумму единиц на 4 (как бы скобки расставить). Ну вот так, возможно, нагляднее даже будет: представим х как сумму счётных палочек: х = |.|.|.|....| Точки назовём "дырками", тогда для того, чтобы поделить это на 4 части, нужно "занять" 3 дырки. Это можно сделать С(3,х) (число сочетаний из Х по 4) способами. Но здесь только будут все варианты, поэтому результат надо еще поделить на 4!, чтобы отсортировать по возрастанию.

UPD: Делить не на 4!, а на меньшее число, нужно учитывать, что числа могут оказаться равны и тогда делить надо на меньшее число. Сходу так не придумал, а думать дольше сейчас нет времени, увы(

4
  • спасибо ,попробую! Но мне также интересен вариант с жадным алгоритмом,так как я сейчас его изучаю. Commented 20 мар. 2017 в 16:43
  • Ну и что будет, например, для 17? 17!/(3!*14!*4!) - дробное...
    – Harry
    Commented 20 мар. 2017 в 16:44
  • вы что предлагаете @Harry ? Commented 20 мар. 2017 в 16:45
  • @Harry исправил ответ, не учел, что если слагаемые одинаковые (а такое точно будет), то нужно этот момент прибавить обратно Commented 20 мар. 2017 в 16:45

Ваш ответ

Нажимая «Отправить ответ», вы соглашаетесь с условиями пользования и подтверждаете, что прочитали политику конфиденциальности.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.