Przetwarzanie zbioru: Różnice pomiędzy wersjami
Z Baza wiedzy Sokaris
(Nie pokazano 3 pośrednich wersji utworzonych przez tego samego użytkownika) | |||
Linia 1: | Linia 1: | ||
− | + | ==Przetwarzanie zbioru danych== | |
− | + | ===Dane wejściowe=== | |
Danymi wejściowymi jest ciąg liczb | 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^ |
Aktualna wersja na dzień 17:02, 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
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^