Przetwarzanie zbioru
Z Baza wiedzy Sokaris
Spis treści
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:
- 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
- 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.
- 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
- 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
- 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
- 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
- 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
- znak "^" obrazuje, że element przekształcany został dopisany do górnego łańcucha
- 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:
- 3;
- 2;
- +-
- ^v
- Wyniki dla 5:
- 5;
- 3,2;
- -++
- ^vv
- Wyniki dla 7:
- 7,2;
- 5,3;
- -++-
- ^vv^