[C++] Woordzoeker

[Verwijderd]

Ik heb eigenlijk hulp nodig met het volgende probleem.

Voor mijn elektro opleiding hebben we als opdracht gekregen om een woordzoeker te maken in C++.
De bedoeling van deze woordzoeker is dat we van de leraar 2 .txt bestanden krijgen met in 1 bestand de woorden die opgezocht moet worden, en in het andere bestand alle letters waar de woorden in opgezocht dient te worden.
De woorden kunnen in alle vormen in dit bestand verstopt kunnen worden: horizontaal, verticaal, diagornaal.

Als output moeten we kunnen laten zien bij welke coördinaten het gezochte woord begint en bij welke coördinaat hij eindigd. En dit dan dus voor alle gezochte woorden.

Nu heb ik na veel zoeken op internet weinig informatie gevonden over dit soort programma, en kom zelf niet veel verder meer, dus dacht ik probeer het hier.

txt bestanden inlezen lukt mij, maar ik neem aan dat bij dit programma deze ingelezen moet wroden in een array.

Maar de vergelijking waar de woorden staan in de letterbrei is voor mij een probleem, en hoe ik deze op het scherm kan tonen met de juiste coördinaten.

Ik hoop dat ik mijn probleem zo duidelijk mogelijk heb opgesteld

[.oisyn]

Wat is er zo lastig aan het maken van een array van strings, wat in feite dus gewoon een 2d array is waarin je kunt zoeken? Vervolgens pak je het eerste teken van een te zoeken woord en zoek je die op in de 2d array. Als je een positie gevonden hebt ga je de 8 tekens eromheen controleren of dat misschien het volgende teken is, en vervolgens trek je dat door in dezelfde richting voor de rest van de tekens.

[ Voor 54% gewijzigd door .oisyn op 26-01-2006 12:19 ]

[Soultaker]

Je moet in ieder geval enig benul hebben van wat een twee-dimensionale array is (of hoe je die op een een-dimensionale kunt afbeelden, wat hetzelfde is). Ik ga er vanuit dat je dat weet of op kunt zoeken.

Dan kun je ofwel doen wat .oisyn zegt (de gevraagde woorden zoeken) of juist omgekeerd te werk gaan; van elke geldige positie kijken of je er een woord mee kunt maken. Elke gevonden woord wordt immers bepaald door een beginpositie, een richting (naar rechts, naar rechtsonder, of naar onder) en een lengte (de lengte van het woord!).

Zo kun je dus alle oplossingen afgaan. Bijvoorbeeld:

A	B	C	D
E	F	G	H
I	J	K	L

Beginnend bij de A, kun je horizontaal kijken: AB? ABC? ABCD? En diagonaal: AF? AFK? En verticaal: AE? AEI? Vervolgens neem je de volgende positie, zeg, B, en kijk je weer horizontaal: BC? BCD? enzovoorts. Zodra een woord in je woordenlijst staat noteer je de begin- en eindpositie.

Efficiënt zijn geen van beide methoden, maar voor simpele grids werkt het wel. Merk ook op dat je kunt stoppen met kijken als er geen woord is dat begint met de gevonden text; als je bijvoorbeeld horizontaal bij 'AB' bent aangekomen maar er beginnen geen woorden met AB, dan is het zinloos om nog verder naar rechts te kijken (ABC, ABCD). Als er geen woorden met een A beginnen, kun je ook de hele letter overslaan.

Er zijn nog talloze andere optimalisaties, maar ga eerst maar een simpel algoritme werkend krijgen.

[ Voor 3% gewijzigd door Soultaker op 26-01-2006 13:05 ]