zadanie z grupowaniem pionków Opcje

[marcus753]

Witam was od tygodnia męczę z piekielnie trudnym zadaniem może ktoś z was mi trochę pomoże...

Zadanie ma taką treść

Jasiu zdenerwowany że przegrał w warcaby wziął n pionków i rzucił nimi na planszę tak że każdy pionek upadł tylko na jedno pole. Jasiu chce teraz pogrupować pionki które leżą obok siebie (czyli ustalić że pionki ułożyły się np. w 5 grup 1 grupa składa się z 3 pionków druga z 2 itd...)

2 pionki zalicza się do tej samej grupy jeśli lezą obok siebie.

mam teraz taki plik wejściowy z współrzędnymi każdego pionka
rząd/kolumna
1:1
2:2
3:3
4:4

czyli pionki ułożyły się na ukos
wynikiem takiego rozłożenia pionków powinno być 1:4 (grupa 1 , składa się z 4 pionków)

gdyby było np
1:1
1:2
2:2
5:5
5:6
wynikiem takiego rozłożenia pionków powinno być 1:3, 2:2 (grupa 1 , składa się z 3 pionków ,grupa 2 , składa się z 2 pionków)

napisałem 2 skyrpty razem z jakies 200 linijek oczywiście nie zadziałały poprawnie dochodzę do momentu w którym zaczynam pisać na nowo ale sam już nie wiem jak to wszystko zrobić ;(

bedę wdzięczny za każdą pomoc sugestie itp. (skrypt nie jest na żaden konkurs gdzie wymagana jest praca indywidualna itp) żeby nie było że wyręczam się tym forum jak chcecie moge zamieścić moje dotychczasowe skrypty ale ja sam już zaczynam się w nich gubić więc nie wiem czy wam by coś dały

POZDRAWIAM (IMG:style_emoticons/default/sciana.gif) (IMG:style_emoticons/default/sciana.gif)

pomysł miałem taki żeby porównać każdy rekord do rekordów leżących obok niego w odległości 1rzedu czyli np. dla danych
1:1
1:2
2:2
5:5
5:6

porównuje 1:1 do 1:2 jeśli leżą obok siebie do nowego pliku zapisuje 1:1:1,1:2:1 (ostatnia cyfra to grupa) następnie porównuje 1:1 do 2:2 w efekcie czego do poprzedniego pliku dopisuje 1:1:1 2:2:1
nastepnie 1:1 do 5:5 jako że 5:5 leży poza najbliższym żędem pobieram kolejną zmienną do porównania czyli 1:2 porownuje do 2:2 i tu już zaczynają się schody teraz przydało by się żeby sprawdzał czy 1:2 ma już jakąś grupe a to oznacza że najpierw musiał bym otworzyć plik aby pobrać dane i na otwartym pliku otwierać go jeszcze raz aby aktualizować nie mam pojecia jak to zrobić albo ominąć...

drugi skrypt miał ignorować takie same rekordy które występują więcej niż jeden raz i zliczać ile rekordów ma tą samą grupe

[thek]

Niekoniecznie (IMG:style_emoticons/default/smile.gif) Zależy czy masz je posortowane czy nie. Jeśli tak, to masz rację i olewamy wszystkie mające mniejszą pierwszą współrzędną oraz równą pierwszą i mniejszą drugą na zasadzie:
olej olej olej
olej baza może
może może może
Brak sortowania wymusza na Tobie sprawdzenie wszelkich możliwości.

PS: Posortowana PULA to zawsze szukanie i tak od pierwszego elementu, gdyż nigdy nie trafisz na element mniejszy (IMG:style_emoticons/default/winksmiley.jpg) Stąd posortowanie puli na samym początku według pierwszego elementu, a jeśli jest kilka takich samych to wedle drugiego, może być dobrym pomysłem na optymalizację algorytmu, gdyż przerywasz szukanie po osiągnięciu przez skrypt w puli wolnych określonej wartości współrzędnych większej niż (baza +1, baza+1).

EDIT: Ciekawostką jest fakt, że takie rozwiązanie problemu pozwala na uznanie za grupę także pionków stojących na tym samym polu w wyniku rzucenia. Kto powiedział, że na jednym polu może stać tylko jeden? W wyniku rzutu może się okazać normą, że na jedno pole spadnie więcej niż jeden pion.
A na przyszłość zanim zaczniesz robić coś "z biegu" zastanów się nad założeniami bazowymi bo jak widzisz dobre przemyślenie sprawy ułatwia proces ze stopnia "nie wiem co dalej" do "to trywialne". Tutaj jednak najlepsze wyniki mają osoby myślące bardzo abstrakcyjnie i praktycy, bo to oni najszybciej wynajdują algorytm. Ja zacząłem od definicji "sąsiada". Gdy to już miałem reszta poszła gładko.

Ten post edytował thek 20.01.2010, 12:54:07