1 Тема від mazurkevych

  • mazurkevych
  • Користувач
  • Поза форумом
  • Звідки: Львів
  • Дата реєстрації: 28.11.2013
  • Повідомлень: 8
    • Репутація: 0

Тема: Підкажіть алгоритм.

Задача:
Дано список цін деяких товарів , що задається масивом і дано номінал купюри(їх є необмежена кількість).
Вивесті кожні 2 товари, які можна купити за будь-яку кількість цих купюр БЕЗ  ЗДАЧІ.
____________________________________________________________________________
Підкажіть алгоритм, який би був оптимальним для великої кількості товарів.?

2 Відповідь від koala Востаннє редагувалося koala (15.05.2014 21:50:57)

  • koala
  • koala
  • Лінива тваринка
  • Поза форумом
  • Дата реєстрації: 01.05.2013
  • Повідомлень: 15 292
    • Репутація: 13031

Re: Підкажіть алгоритм.

Відсортувати за залишком і вивести всі пари, що нам підходять. Хай є масив Prices[ GoodsCount ] та змінна Nominal. Розбиваємо масив на Nominal підмасивів за залишками ( Prices[ i ] % Nominal ), тобто якщо Prices[ i ] % Nominal == k, то Prices[ i ] йде в k-й підмасив. Будь-яка пара з цих підмасивів під номерами n, Nominal - n буде давати суму, що ділится на Nominal без залишку, що нам і було потрібно. Звісно, для підмасиву з номером 0 парний - він сам.

Подякували: Chemist-i1

koala вебсайт