Tävlingsprogrammering/Uppgifter/Mångtydig morse

Mångtydig morse - Uppgift 4 - Onlinekvalet till PO 2007

Tabellen ovan visar Morsealfabetet. Punkter och streck används för att beteckna korta respektive långa signaler. Normalt lämnas morsemeddelanden med ett uppehåll mellan varje bokstav, till exempel --. . - som står för ordet GET. Men av en obestämd anledning kommer det just nu in meddelanden i en oavbruten följd av långa och korta signaler, alltså utan uppehåll mellan bokstäverna. GET-signalen blir då --..- och kan därför stå för många andra bokstavssekvenser, t.ex. MU. Skriv ett program som tar emot en följd av streck och punkter, och som sedan skriver ut varje möjlig kombination av bokstäver som svarar mot den givna indatasträngen

Indata

På första raden står signalsträngen, som består av högst 15 tecken. Därefter följer 26 rader som beskriver Morse-alfabetet. Denna information är samma i alla testfall och motsvarar precis tabellen ovan. Den första av dessa rader ger signalen för A, den andra för B o.s.v.

Utdata

Programmet ska skriva ut alla möjliga bokstavssekvenser som svarar mot den givna indatasträngen. Sekvenserna ska skrivas ut i alfabetisk ordning med en per rad. Endast versalerna A-Z får förekomma.

Exempel: Indata

--..-

.-

-...

-.-.

-..

.

..-.

--.

....

..

.---

-.-

.-..

--

-.

---

.--.

--.-

.-.

...

-

..-

...-

.--

-..-

-.--

--..

Exempel: Utdata

GA

GET

MEA

MEET

MIT

MU

TDT

TNA

TNET

TTEA

TTEET

TTIT

TTU

TX

ZT

Lösning

I den här uppgiften får man rekursera. Om man tänker sig att man skulle lösa problemet för hand skulle man t.ex. kunna börja genom att gå igenom vilka olika förstabokstäver och motsvarande morsekoder som kan väljas. I exempelindatan (--..-) kan vi t.ex. välja (G = --.) , (M = --) , (T = -) och (Z = --..). Väljer vi G som förstabokstav får vi kvar G(.-), väljer vi M får vi M(..-) o.s.v. Vi har då reducerat problemet till att hitta alla olika kombinationer till en kortare teckensekvens genom att välja en viss förstabokstav. Vi kan upprepa denna procedur igen tills hela teckensekvensen blivit vald och vi därmed hittat en lösning till huvudproblemet. I exemepllösningen nedan motsvaras denna procedur av funktionen placeNewChar som håller reda på dels vilken teckensekvens vi har kvar att tyda och dels vilka bokstäver vi redan valt. Från detta läge väljs alla nya möjliga bokstäver och funktionen anropar sig själv. Om det inte längre finns någon teckensekvens kvar skrivs lösningen ut, d.v.s. de valda bokstäverna, och rekursionen går tillbaks ett steg. Det är alltså på denna nivå som funktionen "bottnar". När rekursionen slutat har alla möjliga lösningar skrivits ut, och dessutom har de skrivits ut i bokstavsordning eftersom funktionen alltid väljer en så tidig bokstav som möjligt i lexiografisk ordning innan den går vidare. Alla G(.-)lösningar väljs alltså innan M(..-)lösningarna och TN(.-)lösningarna väljs innan TT(.--)lösningarna o.s.v.

Exempellösningen fungerar så här:

1. Läs in teckensekvensen vi ska tyda
2. Räkna ut antalet tecken i in-sekvensen
3. Läs in morsekoderna
4. Anropa placeNewChar i startläget

Exempellösning i C++:

//Onlinekvalet 2007
//Uppgift 4 - Mångtydig morse

#include <iostream>
using namespace std;

int  nTecken;             //antalet tecken i inputen
char input[16];           //input-tecknena
char abc[26][5];          //morsekoderna
char word[16];            //innehåller våra möjliga lösningar

//############### Placerar ut alla möjliga morsekoder från ett visst läge ##################
void placeNewChar(int cTecken, int cBokstav){
  int i, j, w;
  bool poss;

  for(i = 0; i <= 25; i++){                                         //loopa igenom alla morsekoder
    //------------- Undersök ifall morsekod nr i passar ----------------
    poss = true;                                                    //defaultvärde är sant
    for(w = 0; w <= 3 && abc[i][w] != 0 && poss; w++){              //kör tills morsekodens slut eller ej matchning
      if(input[cTecken+ w] != abc[i][w]) poss = false;              //tecknena matchar inte varandra
    }                                                               //om morsekoden passar är w antalet tecken i koden
    //-----------------------------------------------------------------------------------------

    if(poss == true){                                               //morsekod nr i passar
      word[cBokstav] = i + 65;                                      //lägg till bokstav nr i till lösningen

      if(cTecken+ w == nTecken){                                    //slut på inputraden...
        for(j = 0; j <= cBokstav; j++) cout << word[j];             //...printa ordet!
        cout << "\n";	
      }else{                                                        //vi har fler tecken kvar att tyda...
        placeNewChar(cTecken + w, cBokstav+ 1);                     //...placera en ny bokstav!
      }
    }											
  }
}
//#########################################################################################

int main(void){
  //------------------------ Läs in datan -----------------
  cin >> input;                                                       //läs in tecknen vi ska tyda
  for(nTecken = 0; nTecken <= 15 && input[nTecken] != 0; nTecken++){} //räkna ut antalet tecken på inputen
  for(int i = 0; i <= 25; i++) cin >> abc[i];                         //läs in morsekoderna
  //--------------------------------------------------------------

  placeNewChar(0, 0);                                                 //skapa alla möjliga lösningar
  return 0;
}