Трябва да си направя алгоритъм за една задача.

Известна е стойността A = (a*b)/(c*d). Също така, знае се, че a, b, c и d са цели положителни числа и принадлежат на някакъв ограничен брой от 30-ина стойности(може и да се повтарят, но не е желателно).

1. При зададено A трябва да намеря всички възможни комбинации на a, b, c и d.

2. С предимство е тази комбинация на a, b, c и d, в която те имат минимални стойности спрямо останалите комбинации, т. е. стойността на най-голямото число в комбинацията е най-малка в сравнение с останалите комбинации.

Как най-удачно мога да направя алгоритъм?

Понеже още ме мързи да мисля, може да се вземе най-очеизвадния вариант:
1. Въртят се всички вариации a,b,c,d. Ако комбинацията е печеливша, записва се в масив V=[a,b,c,d,m], където m=max (a,b,c,d)
2. Масива V се сортира възходящо по m

Има варианти да се избегне сортирането като още в 1 може да се записват сортирано - дали в масив, опашка и т.н. зависи от въображението на марсианеца и от тайните страсти на преподавателя

Съдържаниет е скрито
Влезте за да го видите

ми начин е да пробваш с всички или част от възможните комбинации подредени в таблица и с sql да търсиш отговорите на въпросите си...
за бг може да ползваш аксес или каквото имаш под ръка

исках да кажа че таблицата може да се държи в каквато база данни имаш под ръка ms access или др

Съдържаниет е скрито
Влезте за да го видите

Ако търсиш някаква оптимизация, това което ми идва на първо четене е следното:правиш 2 сортирани списъка, като в единя слагаш всички възможни стойности на a*b(Списък X) а във втория всички целочислени възможни стойности на a*b*A(Списък Y), където а и b са ти от множеството положителни (хубаво е за всяка стойност от списъка да помниш как се е получила). Нулираш си един брояч "p", след това вземаш единя от тези 2 списъка (без значение кой примерно X), и започваш да циклиш от първото число на X, катo за всяко число x на X, започваш от "p" -тото число на Y да въртиш по числата (y) и докато x>y, увеличаваш брояча "p"(т.е. да е равен на индекса на y). Ако в някой момент x=y, значи си стигнал до решение и блъскаш в списъка на принципа на commercial. в такъв момент слагаш брояча "p" да ти е = индекса на y и спираш да го увеличаваш. След това ако в някой момент стигнеш до x<y, тогава преминаваш към следващото в X списъка. Ако за някое x, x>y до края на списъка на Y, спираш работа. може да има и по-добро решение, но това свежда проверките от 810 000 до под 3000 при 30 възможности

Значи така да разбирам:
имаш (примерно за 30 елемента) множество (сортирано) {a1, a2, ... a30} = K &#8712; N

Решение:

правиме множество {b1, b2, ... b450} = L &#8712; N, където b1 = a1*a2, b2 = a1*a3, ... , b450 = a29*a30

сортираме L и проверяваме дали има повтарящи се елементи. Ако има, то махаме всички освен този (примерно b_i, където b_i = (a_i * a_j)) при който max(a_i, a_j) е най-малък.

След това правиме класове 1/b1, 1/b2, .. 1/b_max. За всеки клас намираме най-малък и най-голям елемент, който са съответно (за класа b_i) b1/b_i и b_max/b_i

При дадено A минаваме през всички класове 1/b1 до 1/b_max и проверяваме дали за текущия клас 1/b_i : b1/b_i <= A <= b_max/b_i

Ако да, то намираме дали съществува в множеството елемента b_x, така че b_x/b_i = A. Първо проверка дали A*b_i е цяло число и след това търсиме дали го има в стойностите с бинарно търсене или хеш-таблица примерно, както си прецениш си го имплементирай.

За всеки клас 1/b_i има най-много едно решение. И така въртиш през всички класове и пазиш само b_x/b_i с най-нискaтa стойност на max(a_j, a_k, a_l, a_m) (като приемаме, че b_x = a_j*a_k, b_i = a_l*a_m).

Ами това е, мисля! Надявам се, че ме разбра :)

Това е ясно, но аз търся по-елегантно решение. Задачата е практическа, не е изпитна.

Acces е смешно да се споменава в подобен форум, тук работата опира до създаване на истинска, самостоятелно работеща програма. В случая търся решение само на определен фрагмент от нея.

Сега съм малко уморен, после ще разгледам по-внимателно предложението!

Днес малко съм гроги, пък и не съм професионалист, като повечето пишещи тук. Просто за лични нужди си правя една програмка на Java. Ще помисля върху това предложение.