1

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

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

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

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

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

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

3

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

koala написав:

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

велике спасибі)