Przetwarzanie zbioru

Z Baza wiedzy Sokaris

Przetwarzanie zbioru danych

Dane wejściowe

Danymi wejściowymi jest ciąg liczb

Przekształcenie

Dane wejściowe dzielimy na dwa wyjściowe łańcuchy liczb w ten sposób, że:

  • Ustawiamy znacznik bieżący na drugiem elemencie ciągu, tak, aby już pierwsze przekształcenie dało w wyniku dwa wyjściowe łańcuchy liczb
  • Aż do osiągnięcia końca ciągu:
  1. poddajemy przekształceniu wszystkie elementy ciągu poczynając od znacznika bieżącego i cofając się po jednej pozycji aż do pierwszego elementu ciągu
  2. przesuwamy znacznik bieżący o jeden element ciągu naprzód

Algorytm przekształcenia

  • Element przekształcany dopisujemy na początek jednego z wyjściowych łańcuchów liczb, przesuwając, jeśli istnieją, dotychczasowe elementy tego łańcucha w prawo
  • Wyboru łańcucha do którego dopisujemy element przekształcany dokonujemy sumując elementy dopisane już do obu łańcuchów.
  1. Jeśli suma elementów górny łańcucha jest mniejsza bądź równa sumie elementów dolnego łańcucha - element przekształcany dopisujemy do łańcucha górnego
  2. Jeśli suma elementów górny łańcucha jest większa od sumy elementów dolnego łańcucha - element przekształcany dopisujemy do łańcucha dolnego

Obrazowanie wyniku działania algorytmu

W wyniku działania algorytmu otrzymujemy:

  • Oba wynikowe łańcuchy liczb
  • Łańcuch obrazujący porównanie sumy elementów łańcuchów wynikowych
  1. znak "+" obrazuje, że w chwili dopisywania elementu przekształcanego suma elementów górnego łańcucha jest większa od sumy elementów dolnego łańcucha
  2. znak "-" obrazuje, że w chwili dopisywania elementu przekształcanego suma elementów górnego łańcucha jest mniejsza od sumy elementów dolnego łańcucha
  3. znak "=" obrazuje, że w chwili dopisywania elementu przekształcanego suma elementów górnego łańcucha jest równa sumie elementów dolnego łańcucha (łańcuchy są w równowadze)
  • Łańcuch obrazujący decyzję wyboru łańcucha do dopisania elementu przekształcanego
  1. znak "^" obrazuje, że element przekształcany został dopisany do górnego łańcucha
  2. znak "v" obrazuje, że element przekształcany został dopisany do dolnego łańcucha


Przykład działania

  • Liczby wejściowe: 3, 5, 7
  • Wyniki dla 3:
  1. 3;
  2. 2;
  3. +-
  4. ^v
  • Wyniki dla 5:
  1. 5;
  2. 3,2;
  3. -++
  4. ^vv
  • Wyniki dla 7:
  1. 7,2;
  2. 5,3;
  3. -++-
  4. ^vv^