Program "odpowiednie słowa"

Question

Witam programistów 

Mam do zrobienia na zaliczenie z Programowania program i nie wiem zabardzo jak się za niego zabrać.

Program ten po wpisaniu do niego pewnej ilości znaków i wpisaniu jak długi jest wyraz powinien dopasować pasujące słowo z pliku .

np:

ilość liter=3
litery : k,t

Pasujące słowa to : kot,kat, itd..

Proszę o jakieś wskazówki,pomoc.

Z góry dziękuje.

Answer 1

Dziel i rządź, słyszałeś?

Ja podzieliłbym to najpierw na podstawie ilości liter. Tablica/wektor i w każdym polu przechowujesz strukturę słów danej długości. Jeden problem z głowy.

Słowa z liter. Osobiście użyłbym grafu. rozbijałbym słowa na litery, a następnie umieszczał w grafie. Pozwoliło by to zmniejszyć złożoność algorytmu, unikając iterowania całego słownika.

W najprostszej wersji (wybacz, nie chce mi się w święta nadto główkować, to zadanie domowe nie mil-wan :P ), każdy węzeł składa się z mapy 32 węzłów (jeden na literę alfabetu), wskaźników na słowa i własnej reprezentacji literowej. słowa dodajesz składając kolejne nazwy węzłów.

Słowa są przechowywane gdzieś obok. Klasa węzła ma tylko wskaźniki na nie. Wyobraź to sobie jako piramidę. Każdy obiekt reprezentuje litere i ma w sobie alfabet. Jeżeli w pierwszym piętrze wybrałeś literę a w drugim literę b, to obiekt w którym się znajdujesz będzie zawierał wskaźniki na słowa zawierające oba te znaki.

Zeby to rozjaśnić, na przykładzie który podałeś. 3 litery, 'k' i 't'. Lecimy do szufladki 3 naszego wektora/tablicy, interesują nas tylko wyrazy 3 literowe. Szufladka ta zawiera 0-32 elementy. Załóżmy że masz dużo słów i każda litera alfabetu występuje chociaż raz, więc masz 32 obiekty węzła.  Szukasz obiektów reprezentujących 'k' i 't'. Następnie w obiekcie 'k' szukasz 't' a w 't' szukasz 'k'. Słowa w tych obiektach będą spełniały wszystkie trzy wymagania.

Kodu nie skrobnę bo sporo tego, ale jeżeli potrzebujesz jaśniej to wieczorem mogę Ci to jakoś rozrysować :P. Jeżeli profesorek nie jest uparty to takie rozwiązanie przejdzie, niestety może zjadać sporo ramu i dodawanie kolejnych wyrazów słownika trochę trwa.

Comments

Byłbym wdzięczny za to rozrysowanie musze to sobie poukładać w głowie :p Nie jest to dla mnie takie łatwe amator jeszcze ze mnie jak widać :D

---

Uhhh. wybacz, nie mam talentu plastycznego ani pedagogicznego :P

http://i.imgur.com/Jz414JU.jpg

Jest tam pseudokod i zasada działania. W bardzo podobny sposób zaimplementowany jest SceneGraph w tuturialu tworzenia gier pod SFML. Nie musisz raczej znać tej biblioteki żeby go zrozumieć :

https://github.com/SFML/SFML-Game-Development-Book/tree/master/04_Input

Patrz na wszystko z Graph i Node w nazwie :)

W razie wszelkich pytań służę pomocą!

Answer 2

Plik pewnie tekstowy, więc pobierasz linie, wpisujesz do stringa oraz sprawdzasz ich długość. Jeśli długość równa jest wyrazowi podanemu przez użytkownika, wpisujesz wyraz do dynamicznej tablicy. Po przejściu przez cały plik, wyświetlasz wyniki z tablicy. Będziesz potrzebował biblioteki fstream.

Comments

Trzeba jeszcze użyć std::string::find(char) do sprawdzenia występowania liter. Najlepsza odpowiedź powinna być wydajniejsza, ale... żre ogromne ilości RAM jak na taką błachostkę.