1. Если вы только начинаете программировать на ассемблере и не знаете с чего начать, тогда попробуйте среду разработки ASM Visual IDE
    (c) на правах рекламы
    Скрыть объявление

Совсем детский вопрос или "Задача о сдаче"

Тема в разделе "WASM.A&O", создана пользователем Enchantner, 18 дек 2010.

  1. Enchantner

    Enchantner New Member

    Публикаций:
    0
    Регистрация:
    29 июл 2008
    Сообщения:
    23
    KeSqueer
    Ага, и скорость полного перебора будет O(2^n). Не пойдет.
     
  2. n0name

    n0name New Member

    Публикаций:
    0
    Регистрация:
    5 июн 2004
    Сообщения:
    4.336
    Адрес:
    Russia
    динамическое программирование подойдет только если нужная сумма ограничена сверху вменяемым числом (1кк вполне нормально).
    ну и нет там никаких собственно трудностей.
    для i+1 элемента пробуем пробегаться k=0..i и находим минимальное значение coins[k] + coins[i - k]
    сложность - n^2, где n - значение сдачи.
     
  3. gorodon

    gorodon New Member

    Публикаций:
    0
    Регистрация:
    19 окт 2009
    Сообщения:
    301
    n0name,Enchantner

    Сумма "сдачи" может быть любой, т.к. данную сумму можно свести к значению S < 2*B(n)
    (где B(n) - самая большая "монета" или другими словами максимальный элемент базиса
    {B(n) B(n-1) ...B(1)}) просто вычитая из заданного значение сдачи значение, кратное B(n).
    Надеюсь, с этим вы спорить не будете...

    После этого нужно выполнить всего n итераций 'жадного' алгоритма (#8) для всех базисов:

    {B(n) B(n-1) ...B(1)}
    {B(n-1) B(n-2) ...B(1)}
    ...
    {B(2) B(1)}
    {B(1)}

    и выбрать то решение, где количество монет будет наименьшим.

    Например, для примера 425 - {1,125,300,400}
    Решение будет таковым:
    {1,125,300,400} - 400*1+1*25 = 26м
    {1,125,300} - 300*1+125*1 = 2м
    {1,125} - 125*3 + 1*50 = 53м
    {1} - 1*425 = 425v

    Мин число монет - 2 (300+125)

    Для числа 825 - сначала 825-400=425 (<2*400) - далее - вышеприведенные расчеты.