Przetwarzanie zbioru: Różnice pomiędzy wersjami
Z Baza wiedzy Sokaris
| Linia 6: | Linia 6: | ||
===Przekształcenie=== | ===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 | ||
Wersja z 16:59, 22 lis 2018
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
