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 ще бъдат преди първото число от втората поредица.

Условия за край

Във всеки момент един от двата пътя догонва другия. Когато един път догонва друг, то може да не успее да го догони. Тогава последния елемент от пътя, който достига до края, му се присвоява следващ елемент, този който догонва. След което останалите елементи от другия път си запазват подредбата. Може да не се проверяват до края елементите. Последния елемент ще си има Nil за следващ елемент. Така приключването на алгоритъма се проверява за достигане на края на пътя, който догонва.

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

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

Код

					
function TDSClipper.order2(runner1, runner2: TRunMarker): TRunMarker;
var
  prev: TRunMarker;
begin

  if (runner1.Point1.X <= runner2.Point1.X) then begin
    Result := runner1;
  end
  else begin
    Result := runner2;

    prev := runner2;
    runner2 := runner2.Next;

    if (runner2 = nil) then begin
      prev.Next := runner1;
      exit;
    end;

    while runner2.Point1.X < runner1.Point1.X do begin
      prev := runner2;
      runner2 := runner2.Next;
      if (runner2 = nil) then begin
        prev.Next := runner1;
        exit;
      end;
    end;

    prev.Next := runner1;
  end;

  while true do begin
    prev := runner1;
    runner1 := runner1.Next;

    if (runner1 = nil) then begin
      // there is only one element in the first linked list
      prev.Next := runner2;
      exit;
    end;

    while runner1.Point1.X <= runner2.Point1.X do begin
      prev := runner1;
      runner1 := runner1.Next;
      if (runner1 = nil) then begin
        prev.Next := runner2;
        exit;
      end;
    end;

    prev.Next := runner2;

    prev := runner2;
    runner2 := runner2.Next;

    if (runner2 = nil) then begin
      prev.Next := runner1;
      exit;
    end;

    while runner2.Point1.X < runner1.Point1.X do begin
      prev := runner2;
      runner2 := runner2.Next;
      if (runner2 = nil) then begin
        prev.Next := runner1;
        exit;
      end;
    end;

    prev.Next := runner1;
  end;

end;

Back to main menu