Algoritme i form av pseudokode

[Zhai]

Her har jeg en algoritme oppgave som jeg føler meg veldig svak på. Nå vet jeg ikke hvor mye folk her kan om algoritme og slikt, men forhåpentligvis så er det sikkert noen her som har litt peiling.

Selve oppgaven ligger under, og det eneste jeg skjønner er at jeg må starte med "Input" av de symbolene(nevnt under). Videre så er jeg sikker på at jeg skal bruke såkalte "If-then" setninger, men vet ikke helt hvordan jeg skal formulere dette i oppgaven. Noen som kan komme med forslag til løsning her kanskje?

Oppgaven:
Finn en algoritme, formulert som en pseudokode, slik at hvis input er
et uttrykk med symbolene p, q, r, ¬, ∨, ∧, (og), så vil algoritmen gi svaret JA om:

¬ bare forekommer rett til venstre for en utsagnsvariabel

parentessettingen er korrekt

det står alltid et av symbolene ), p, q eller r rett til venstre for en
∧ eller en ∨

det står alltid et av symbolene (, p, q eller r rett til høyre for en
∧ eller en ∨

Algoritmen skal gi svaret NEI hvis et av strekpunktene over ikke
holder.

[Markonan]

Har du lov å henvise til et og et tegn i inputet?

F.eks, hvis du har input som listen c, kan du da skrive det første tegnet i inputet som c[0]?

Da blir i så fall den første testen din noe sånt som

IF c[0] == "¬" THEN print("JA")

For å sjekke om parentessettingen er korrekt regner jeg med betyr at alle (-parentesene skal ha en tilsvarende )?
Da er spørsmålet mitt om du har lov til å traversere hele listen med f.eks en for-løkke?

Venter på svar før jeg prøver mer på denne.

[Zhai]

Takk for svar,
jeg skjønner godt at du stiller spørsmål til oppgaven, for selv jeg syns dette var litt udetaljert beskrivelse av oppgaven.

Angående det om man kan henvise til et og et tegn i inputet er jeg litt usikker på, for det at du skriver et tegn som fks. c[0], har jeg ikke vært borti verken i læreboka eller i forelesningene. Det kan godt hende det er lov, men det fins vel en alternativ mulighet for input her hvis jeg skjønner riktig?

Jeg skjønner det med parentessetting på samme måte som deg, så jeg antar at det skal være rett det du sier. For-løkke og eventuelt andre setninger, eller løkker skal vel være veldig sentralt her, så det er fullt mulig å ta i bruk av for-løkker.

Håper virkelig at dette åpner opp litt for deg slik at du kan hjelpe til. Jeg har gitt denne oppgaven et par flere forsøk nå i natt, men sitter fremdeles fast nesten helt på begynnelsen av oppgaven.

[Markonan]

Hele poenget med pseudokode er at man skal kunne legge frem en algoritme på en forståelig måte for alle som kan programmere, uavhengig av hvilket programmeringsspråk de har lært seg. Det eneste som er viktig er at det er klart hva man gjør i algoritmen.

Sånn sett så er jeg helt sikker på at det er lov å hente ut et og et element i inputet ditt, siden det typisk hadde vært en såkalt streng, og det er mulig å hente ut hvert tegn i en streng i alle programmeringsspråk jeg noen gang har vært borti.

Algoritmen du skal skrive her er ikke spesielt vanskelig, men jeg blir litt usikker med en gang det ikke er lov å ta et og et tegn (dvs ikke har blitt lært). Da vet jeg faktisk ikke helt hvordan den skal løses.

Hvilket kurs er dette i forbindelse med? Er det diskret matematikk?

[Zhai]

Stemmer det, dette er diskret matematikk. Når du sier at man tar et og et tegn som input, kan dette forstås som om man for eksempel tar:
1. Input p
2. Input q
3. Input r
eller noe lignende...osv....
Dette er i så fall fullt lovlig. Er det noe lignende du mener når du skriver c[0] og lister videre ned som et eksempel? Jeg ble bare litt forvirret når du bruker disse parentesene og tall inni, siden akkurat den formen du nevner har ikke jeg brukt.

[Markonan]

Ser nå at jeg leste litt feil i oppgaven din. Trodde du bare skulle sjekke at det første tegnet i inputet var en negasjon. Da er det ikke så nøye med å hente ut et og et element!

P,Q og R er utsagnsvariablene, og du må sjekke at det bare er de som kommer rett til høyre for negasjonen ¬. Da må du traversere inputet, og hver gang du finner en negasjon må du sjekke at tegnet som følger er P,Q eller R. I litt pseudoaktig kode.

Code: Select all

FOR EACH ELEMENT IN INPUT
  IF ELEMENT == '¬' THEN
     IF NEXT ELEMENT == 'P' OR 'Q' OR 'R' THEN PRINT "JA"

Jeg kan forklare hvordan jeg hadde løst oppgaven med parentesene også. Da hadde jeg satt en telle-variabel, f.eks TELLER = 0, og så hadde jeg traversert inputet med en for-løkke. Kan vise med litt semi-pseudokode.

Code: Select all

TELLER = 0
FOR EACH ELEMENT IN INPUT
  IF ELEMENT == '(' THEN TELLER++
  IF ELEMENT == ')' THEN TELLER--

IF TELLER == 0 THEN PRINT "JA"

Du går altså gjennom alle elemenetene i inputet, og for hver '(' legger du til 1 til TELLER, og for hver ')' trekker du fra en. Hvis du har en positiv TELLER eller negativ TELLER når du har gått gjennom hele listen har du ubalanse i parentesene!

Håper dette er forståelig og til hjelp!

Bør også nevnes at du ikke kan bruke de løsningene jeg har her siden du skal skal skrive ut "JA" før alle betingelsene er sjekket. Da må du endre litt og passe på at den bare skriver ut "JA" eller "NEI" helt til slutt. I min første løsning vil den nå skrive ut "JA" hver gang den finner en utsagnsvariabel rett etter en negasjon, som ikke er helt det de spør om.

[Zhai]

Dette hjalp en god del. Jeg har brukt det jeg har lært om algoritme og pseudokode for å omformulere svaret ditt litt, men betydningen av svaret mitt skal være lik din.

Nå har du løst to av del oppgavene, men jeg antar at de siste to del oppgavene kan løses på en lik måte som den første del oppgaven? Jeg mener altså disse:

det står alltid et av symbolene ), p, q eller r rett til venstre for en
∧ eller en ∨

det står alltid et av symbolene (, p, q eller r rett til høyre for en
∧ eller en ∨