[wiskunde] Doolhof in MatLab

EpicDnS

Problem 1.40.

(8.0) A labyrinth is given as an n £n array A in which each element

can be either 0 (white) or 1 (black). A knight in the labyrinth is at an initial

position (i , j ) which is given. The numbers i , j satisfy 1 Ç i Ç n, 1 Ç j Ç n, n È 4.

He may move to a neighbouring cell (i §1, j ) or (i , j §1) if such a cell is open

(white). The knight is out once he has reached a cell on the boundary.

a) Write an algorithm that finds a way out (if possible). You can assume that

the knight can look globally at his labyrinth (which is of course not true in

real life).

b) Write a code that determines the minimum length of this path. If the path does not exist this length should be 0.

c) Write also a code that determines such a path of minimal length.

d) Find a strategy for the knight such that he finds a way out in case he does

not have a global view. The knight has n2 pieces of paper with the numbers

1, . . . ,n2 written on them. You also have n2 black cards to your disposal. Argue

why you think your method is correct.

e) Implement the pseudo-code form the algorithm in

Hand in a function that solves

item b) and item c):

function [N, z] = labyrinth1(A, i, j)

This function has as input

A, which is a n £n matrix of 0s and 1s (0: white,

1: black), and

i , j , which is the initial position.

If there is a way out

z should be a shortest path, N its length. So z must be

a

N £2 array. If there is no way out, N should be -1 and z empty.

Hand in a function that solves

item e):

function [N, z] = labyrinth2(A, i, j)

with the same IO as before, only now the path should be a solution that the

knight would be able to find himself; so we do not care how long the path

is.

Bovenstaande is de opgave die wij hebben gekregen om te programmeren met het programma MatLab. Met MatLab heb ik echter het probleem dat ik precies weet wat ik wil invullen (een begaanbaar vakje geef ik waarde '0', onbegaanbaar waarde '1' etc.) Ik krijg het echter nooit voor elkaar dat te vertalen naar MatLab taal en dat is natuurlijk erg jammer.

Gezien bovenstaande opdracht een echte beginnersopdracht is, hoop ik dat deze voor jullie zeer eenvoudig is en iemand mij daarbij zou willen helpen. Ik weet namelijk niet goed hoe te beginnen.

Wat weet ik wel?

Een doolhof zal moeten worden geconstrueerd als een matrix, gebruik maken van waarden 0 en 1 en zodra er dreigt een vakje met 1 betreden te worden moet het programma de ingeving krijgen om zich om te draaien (1 betreden is immers niet mogelijk). Op die manier volgt het programma uiteindelijk alle nullen, naar de uitgang van de matrix (het doolhof). Hoe ik dit omzet in MatLab taal is echter voor mij een groot raadsel.

Alvast bedankt,

Dennis.

EvilBro

Beschrijf eerst eens duidelijk het algoritme dat je wilt implementeren. Als je dat hebt dan kunnen we eens kijken hoe het dan in Matlab moet.

EpicDnS

Oké, op de volgende manier zag ik het voor mij:

Er wordt een willekeurige n x n matrix gegeneerd. Deze bestaat uit input waarden 0 en 1 (willekeurig).
Vervolgens moet er aan MatLab worden vertelt dat een veld met de coördinaten (i,j) niet begaanbaar is als er een waarde 1 in staat en wel begaanbaar is als er een waarde 0 in staat.
De laatste stap is dat zodra ik een input geef (bijvoorbeeld ik 'begin' in vak (i,j)) dat MatLab gaat proberen om zich richting de uitgang (buitenste rand) te verplaatsen. Mocht hij op een vak met waarde 0 komen, dan is er niets aan de hand, mocht er een vak met waarde 1 zijn, dan wordt dit vak 'afgesloten (of gekenmerkt) dat het niet begaanbaar is, en zoekt hij verder.

Natuurlijk bestaat er de mogelijkheid dat er geen oplossing is, in dat geval zou ik de output '0' willen krijgen. In alle andere gevallen wil ik de output krijgen met het aantal stappen dat MatLab nodig heeft gehad om de uitgang te bereiken.

Dat is hoe ik het voor mij zie. Eerst matrix generen met nullen en enen, vervolgens de spelregels ingeven en daarna de oplossing verkrijgen.

EvilBro

Maar Matlab gaat niks doen als jij niet vertelt wat ie moet doen. Je zal dus moeten vertellen hoe je bij de oplossing kan komen. De vraag is dus: hoe zou jij dat doen? Ofwel: welk stappenplan zou jij systematisch doorlopen om tot een oplossing te komen?

Wetenschapsforum

Laatste berichten

Nieuwsberichten

[wiskunde] Doolhof in MatLab

[wiskunde] Doolhof in MatLab

Re: Doolhof in MatLab

Re: Doolhof in MatLab

Re: Doolhof in MatLab