Przetwarzanie zbioru
Z Baza wiedzy Sokaris
Wersja z dnia 16:59, 22 lis 2018 autorstwa P. Mondzelewski (dyskusja | edycje)
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
- Łańcuch obrazujący wybór