Outrun algorithm

Outrun algorithms

8 March 2014

Въведение

Много полезно е понякога вместо да се изпробват всички възможни варианти да се надбягват стойностите

При догонващия алгоритъм броят на итерациите които ще направим не надвишава сбора на стойностите на двата списъка. Така например ако всеки списък има по 100 стойности, то няма да надвиши 200 итерации. Докато ако се правят проверки на всички възможни ще бъде 10 000. Разликата е 50 пъти.

При първоначалното настигане няма извършване на проверки. Също след задминаване на края, също няма проверки, дори не се итерира там. Така примерно от тези 200 може в началото да няма проверки. Примерно за първите 50. И ако се задмине края на 150, то последните 50 въобще да не се итерират. Което ще бъде 100 итерации с проверки, и 50 итерации без проверки.

Примерно имаме поредица от стойности 1, 10, 25, 50
И друга поредица 5, 15, 20, 30, 40
Как бихме ги проследили как нарастват
Вземаме първите стойности на двете поредици и гледаме коя е по-голяма
Ако са еднакви значи ще има застъпване
Ако първата поредица започва с по-малко число от втората, част от първата няма да има застъпване с втората.
И съответно обратното
В нашия случай 1 < 5, което ще рече, че от 1 до 5 няма да има застъпване.
Ако първата поредица завърши преди 5 то въобще няма да има застъпване между двете поредици.
If (endValue1 < startValue2)
Return;
If (endValue2 < startValue1)
Return;

Value1 := startValue1;
Value2 := startValue2;
If (value1 < value2) {

} else {

}

Но може да има няколко числа от първата поредица, които да са преди първото число от втората поредица. Примерно 1,3,4, 6 и 5,7,9. Така 1,3,4 ще бъдат преди първото число от втората поредица.

Програмиране

В програмирането надбягващия се алгоритъм може да се изнесе в отделен клас. Който да си има първоначално догонване, проверки. Да си прави всичко. Да си взема стойности за двата списъка. Да вика за проверка. Може да ползва и компаратор. И да му се подават стандартни списъци и да ги надбягва.

Back to main menu