Wrocław 08.06.2006r.

autor:		Mirosław Łysakowski 

kierunek:	ARS

nr indeksu:     127991

1. Treść problemu
2. Algorytm działania
3. Implementacja programowa
4. Wyniki i wnioski
5. Źródła



1. Treść problemu

Zadanie polega na napisaniu programu, który będzie rozwiązywał proste łamigłówki matematyczne. Jest to problem dosyć złożony we względu na dużą różnorodność zadań. Zadania rozwiązywane przez mój program to zadania, w których wszystkie dane są podane liczbowo i nie ma w nich żadnych ważnych nieliczbowych informacji. Program na podstawie napisanej w pliku tekstowym treści zadania będzie potrafił takie zadanie rozwiać i poprawnie udzielić odpowiedzi na zadane w treści pytanie.

2. Algorytm działania

Generalnie działanie programu można podzielić na dwa etapy. Pierwszy z nich dotyczy nalezienia w treści zadania słów kluczowych oraz wartości liczbowych. Polega to na tym, że program czyta wszystkie słowa w zadaniu. Najpierw sprawdza i ewentualnie zamienia wszystkie duże litery na małe a następnie sprawdza czy do wyrazów nie są "doczepione" znaki typu ","".""?" itd. Jeśli takie znaki znajdzie wtedy usuwa je z wyrazu. Dopiero wtedy wyrazy wpisywane są do tablicy na której wykonywane będą kolejne kroki algorytmu. Drugi etap to udzielenie poprawnej odpowiedzi w zależności od postawionego w treści pytania. Ponieważ w zadaniu może się zmieniać kilka wartości, program powinien zwrócić tylko tę wartość o którą pytamy. Zdania powinny być napisane czytelnie, poprawnie gramatycznie i w bez polskich znaków. Odmiana wyrazów w języku polskim jest niestety problemem, gdyż zdarza się ze program jest zmuszony do porównywania kilku pierwszych liter wyrazów i może się zdarzyć sytuacja kiedy program porówna całkowicie inny wyraz mający tylko wspólny początek. Klasy zadań (a co z tym idzie, sposób jego rozwiązania) są rozróżniane na podstawie słów kluczowych występujących w treści zadania. Na tej podstawie wykonywane są kolejne kroki algorytmu.

Klasy zadań:

Treść zadania:
" ania ma 6 bulek a krzys ma 7 bulek. krzys zabral ani 3 bulki. ile bulek ma krzys a ile ma ania? "

Odpowiedź na wyjściu:
"krzys ma teraz 10
ania ma teraz 3"

Program szuka słów kluczowych zawartych w kodzie programu. Przykładowo w powyższym zdaniu takim słowem kluczowym jest „zabrał”. Przeszukując trzy kolejne wyrazy znaleziona zostaje wartość, która będzie dodawana lub odejmowana do zmiennych. Na tej podstawie program wie jaką operacje (dodawanie lub odejmowanie) ma wykonywać i ile wynosi ta wartość. Następnie sprawdza wyraz wcześniejszy („krzys”) i porównuje go z wszystkimi wyrazami. W związku z odmianą słów przez przypadki porównywane są tylko trzy pierwsze znaki wyrazu. Jeśli znaleziony zostanie taki wyraz, wtedy program szuka liczby całkowitej znajdującej się za nim, przeszukując tym razem tylko trzy kolejne wyrazy („ma” oraz „7”). Wiadomo wtedy ze krzys = 7. Podobnie w przypadku drugiej zmiennej, z tym tylko wyjątkiem, że tym razem program rozpoczyna poszukiwania od następnego wyrazu po słowie kluczowym „zabrał”. W tym wypadku słowem tym jest „ani”. Po skończeniu tych operacji wiemy że krzys = 7, ania = 6 oraz że należy odjąć liczbę 3 od wartości która jest przypisana zmiennej występującej za słowem kluczowym „zabrał”. Krótko mówiąc, od zmiennej „ania” odejmowana jest wartość 3, a do zmiennej „krzys” dodawana jest wartość 3. Formułując odpowiedź program szuka w treści słowa pytającego (w tym przypadku „ile”). Jeśli znajdzie, wtedy przeszukuje trzy kolejne wyrazy (za słowem „ile”) jednocześnie porównując je z wyrazami znajdującymi się przed lub za słowem kluczowym „zabrał”. Na tej podstawie generowana jest odpowiedź na zadane w treści pytanie.

b) Zadanie z dwiema danymi wartościami, w którym suma oraz iloczyn dwóch niewiadomych jest równy odpowiednio danym dwóm wartościom.

Treść zadania:
" Marysia ma 25 roz . Roz czerwonych jest 4 razy wiecej niz roz zoltych . Ile jest roz zoltych ,a ile jest roz czerwonych ? "

odpowiedź na wyjściu:
"czerwonych roz jest 5
 zoltych roz jest 20"

Program wyszukuje w zdaniu słowa kluczowego "razy". Jeśli znajdzie takie słowo wiadomo, że wykonywanymi operacjami będą w zadaniu albo mnożenie albo dzielenie. W kolejnym kroku sprawdzany jest wyraz występujący za słowem „razy”. Oczekiwanymi słowami są „mniej” lub „więcej”. Wiedza ta jest później potrzebna do wybrania odpowiedniego wzoru przy podstawieniach liczbowych. Następnie sprawdza się czy wyraz występujący przed słowem kluczowym „razy” jest liczba całkowitą. Jeśli nie jest liczbą lub jeśli wcześniej nie znaleziono słów „mniej” lub „więcej” pojawia się komunikat o błędzie w treści zadania. Następnie program szuka w treści miejsc wystąpienia słów typu „ma”, „posiada” itp. oraz sprawdza czy występujące po nim słowo jest liczba całkowitą. Jeśli zdanie jest poprawnie sformułowane, w tym momencie przypisane już mamy dwie dane wartości, czyli sumę = 25 i iloczyn = 4 dwóch niewiadomych. Dodatkowo zapamiętywane jest słowo które występuje po słowie „ma” oraz następującej po niej liczbie „7”. Tym słowem jest „roz”. Na podstawie tych danych układany jest układ równań i wyliczane są niewiadome. Formułując odpowiedź program szuka w treści słowa pytającego (w tym przypadku „ile”). Jeśli znajdzie, wtedy przeszukuje trzy kolejne wyrazy (za słowem „ile”) jednocześnie porównując je z wyrazami znajdującymi się do czterech wyrazów przed (lub za) słowem kluczowym „razy” oraz za słowem „roz”. Poszukiwanymi słowami w tym zadaniu są „zoltych” i „czerwonych”. Ważne jest aby w treści zadania nie pierwszy występował rzeczownik („roz”) a po nim przymiotnik („zółtych”), gdyż w przeciwnym razie program wyświetli komunikat o błędzie. Jeśli jednak zadanie jest sformułowane prawidłowo program jest w stanie generować prawidłową odpowiedź na zadane w treści pytanie.

c) Zadania w których suma/różnica/iloczyn/iloraz dwóch niewiadomych tworzą układ dwóch równań z dwiema nie wiadomymi.

Treść zadania:
" suma dwóch liczb wynosi 11, a iloczyn liczb wynosi 18 ,jakie, to liczby ? "

odpowiedź na wyjściu:
"pierwsza liczba: 9
 druga liczba: 2"

Program wyszukuje w tekście kluczowych słów "iloczyn", "iloraz", "różnica" lub "suma". Jeśli w zadaniu znajdzie co najmniej dwa różne słowa kluczowe wtedy wiadomo, że do rozwiązania tego zadania potrzebny będzie układ dwóch równań z dwiema niewiadomymi. Następnie od miejsca gdzie zostały znalezione słowa kluczowe („suma”, „iloczyn”) program sprawdza, do pięciu wyrazów do przodu, czy występują liczby całkowite. Na tej podstawie program przypisuje operacjom matematycznym odpowiednie wartości liczbowe. W przypadku „sumy” cyfrą tą jest ”11”, a w przypadku „iloczynu” znalezioną liczbą jest „18”. Wiedząc, że suma dwóch liczb wynosi 11, a ich iloczyn wynosi 18 tworzony jest układ dwóch równań z dwiema niewiadomymi.  Rozwiązaniem takiego zadania są dwie wartości liczbowe spełniające założenia podane w zadaniu. Jeśli się okaże, że znalezione niewidome nie należą do zbioru liczb całkowitych wyświetla się komunikat o błędzie w treści zadania powodowanym złym dobraniem wartości liczbowych. Formułowanie odpowiedzi dla tej klasy zadań jest najprostsze, gdyż za każdym razem wyświetlane są obie wyliczone niewiadome.

3. Implementacja programowa

Program został napisany w języku C++ w środowisku Builder 6. Program uruchamiany jest pod konsola. Intersfejs użytkownika jest bardzo prymitywny i ogranicza się do wpisania nazwy pliku tekstowego w którym zamieszczone jest zadanie. Wyjście ogranicza się pokazania treści tego zadania oraz wyświetlenia rozwiązania (udzieleniu poprawnej odpowiedzi) lub komunikatu o błędzie.

4. Wnioski

Zaproponowany przeze mnie algorytm jest dosyć restrykcyjny jeśli chodzi o sposób formułowania zadania. Nie można nim rozwiązywać zadań nietypowych lub bardziej złożonych w których ważna role spełniają także dane "nieliczbowe". Jeśli jednak zadanie zostanie poprawnie sformułowane, program jest w stanie udzielić prawidłowej odpowiedzi lub wyświetli komunikat o błędzie w danych( np. liczba nie jest całkowita). Wystarczy niestety, ze w pytaniu zostanie zamieniony miejscami podmiot z orzeczeniem (np. "ile jest Roz zoltych" na "ile jest zoltych roz") i algorytm przestaje poprawnie działać. Innym lecz nie mniej ważnym problemem jest polska gramatyka, która wymaga odmiany slow przez przypadki. Skutkiem tego dwa takie same wyrazy, lecz występujące w innych przypadkach będą interpretowane przez program jako dwa różne wyrazy. Problem ten jest tutaj częściowo rozwiązany. Algorytm porównując kolejne wyrazy sprawdza tylko 3 lub 4 pierwsze znaki wyrazu i na tej podstawie ocenia czy wyrazy są identyczne. Rozwiązanie takie ma jednak swoje plusy i minusy. Plusem jest fakt ze pomijamy w tym momencie odmianę wyrazów przez przypadki, minusem natomiast jest fakt, ze może się zdarzyć sytuacja kiedy dwa zupełnie inne wyrazy mające podobny początek ( np. "administracja" oraz "admiral") zostaną uznane za te same. Zakładam jednak, ze taka sytuacja jest rzadka podczas gdy odmiana wyrazów przez przypadki występuje na każdym kroku.

Podsumowując algorytm najlepiej działa gdy zadanie jest sformułowane według pewnego "szablonu" a wszystkie wymagane wartości liczbowe potrzebne do rozwiązania zadania są zawarte w treści. Wartości te powinny również należeć do zbioru liczb całkowitych gdyż tylko takie są brane pod uwagę przez algorytm w treści zadania.

5. Źródła

Przy pisaniu programu korzystałem z przykładów zadań zamieszczonym na poniższej stronie.

http://www.jezusek.friko.pl/prace.html