Programozás‎ > ‎Feladatok‎ > ‎Telefonszámok‎ > ‎Megoldás‎ > ‎

og_phone2.cpp

Letöltés: og_phone2.cpp

#include <stdio.h>
#include <iostream>
#include <string>
#include <algorithm>
 
using namespace std;
 
void beolvas(char*);
void atir();
void keres();
int egyezik(int,int);
void kiir();
 
char* s;
int sl;
 
int n;
 
struct szo
{
    int bl;
    char* b;
    char* a;
    int r;
};
 
int* fix;
int* osszo;
int* oshely;
int* ki;
 
 
bool stro(szo, szo);
 
szo* szavak;
 
 
char c;
 
 
 
int main()
{
    beolvas("PHONE.I0");
    atir();
    keres();
 //   cout << "Solution " << fix[sl+1] << "\n";
    // osok keresese
    if(fix[sl+1]==10000) {cout << "No solution."; return 0;}
    int i=sl+1;
    ki= new int[100];
    int kil=0;
    while(i!=0)
    {
        ki[kil]=osszo[i];
        kil++;
        i=oshely[i];
    }
    //kiiras forditva
    for(int j=0; j<kil; j++)
    {
        cout << szavak[ki[kil-j-1]].b << " ";
    }
    return 1;
}
 
void beolvas(char* file)
{
    FILE* be = fopen(file, "r");
    s = new char[101];
    for(int i=0; i<101; i++)
    {
        fscanf(be, "%c", &s[i]);
        if (s[i]=='\n') {sl=i-1; break;}
 
 //   cout << s[i];
 
    }
 
    fscanf(be, "%d", &n);
   // cout << "\n" <<sl <<"\n"<<n<<"\n";
 
    szavak =new szo[n];
    fscanf(be, "%c", &c);
    for (int i=0; i<n; i++)
    {
        szavak[i].b = new char[51];
 
 
     //   cout << i<< "\n";
        for(int j=0; j<101; j++)
        {
            fscanf(be, "%c", &szavak[i].b[j]);
 
            if ((szavak[i].b[j]=='\n') || (szavak[i].b[j]=='\r')) 
                {szavak[i].bl = j; szavak[i].b[j]='\0'; break;}
 
        }
 
    }
 
  /*  for(int i=0; i<n; i++)
    {
       cout << szavak[i].b <<" " << szavak[i].bl << "\n";
    }*/
 
    fclose(be);
}
 
 
// a szavak átírása számokra, rendezése (nincs kihasználva)
void atir()
{
 
    for (int i=0; i<n; i++)
    {
        szavak[i].a = new char[szavak[i].bl+1];
        for (int j=0 ; j<szavak[i].bl;j++)
        {
            if ((szavak[i].b[j]=='i') || (szavak[i].b[j]=='j')) {szavak[i].a[j]='1';}
            else if ((szavak[i].b[j]=='a') || (szavak[i].b[j]=='b') || (szavak[i].b[j]=='c')) {szavak[i].a[j]='2';}
            else if ((szavak[i].b[j]=='d') || (szavak[i].b[j]=='e') || (szavak[i].b[j]=='f')) {szavak[i].a[j]='3';}
            else if ((szavak[i].b[j]=='g') || (szavak[i].b[j]=='h'))  {szavak[i].a[j]='4';}
            else if ((szavak[i].b[j]=='k') || (szavak[i].b[j]=='l'))  {szavak[i].a[j]='5';}
            else if ((szavak[i].b[j]=='m') || (szavak[i].b[j]=='n'))  {szavak[i].a[j]='6';}
            else if ((szavak[i].b[j]=='p') || (szavak[i].b[j]=='r') || (szavak[i].b[j]=='s')) {szavak[i].a[j]='7';}
            else if ((szavak[i].b[j]=='t') || (szavak[i].b[j]=='u') || (szavak[i].b[j]=='v')) {szavak[i].a[j]='8';}
            else if ((szavak[i].b[j]=='w') || (szavak[i].b[j]=='x') || (szavak[i].b[j]=='y')) {szavak[i].a[j]='9';}
            else if ((szavak[i].b[j]=='o') || (szavak[i].b[j]=='q') || (szavak[i].b[j]=='z')) {szavak[i].a[j]='0';}
          //  cout << szavak[i].a[j];
        }
        szavak[i].a[szavak[i].bl]='\0';
        //cout << "\n";
 
 // cout << szavak[i].a <<" " << szavak[i].bl << "\n";
    }
 
 
  //  sort(szavak, szavak+n ,stro); // abc szerinti rendezés (nincs kihasználva)
    }
 
/*
//megnézi, hogy két sz közül megyik van elõbb az abc-ben
bool stro(szo first, szo second)
{
    for(int i=0; i<min(first.bl, second.bl); i++)
    {
        if(first.a[i]>second.a[i]) {return false;}
        else if (first.a[i]<second.a[i]) {return true;}
    }
    return true;
}*/
 
 
////////// végigmegy a pontokon (i), és megnézi, hogy minden következõ pontra(j) eljuthatunk-e kevesebb lépésbõl mint amit eddig becsültünk
void keres()
{
    // inicializálás
    fix=new int[sl+2];
    osszo=new int[sl+2];
    oshely=new int[sl+2];
 
    for(int i=0; i<sl+2; i++)
    {
        fix[i]=10000;
    }
    fix[0]=0;
 
    for(int i=0; i<sl+1; i++)
    {
   //     cout << "Doing " <<i << " fixi " << fix[i] << "\n";
        if (!(fix[i]==10000)) // ha ide lehetett jutni
        {
            for(int j=i+1; j<sl+2; j++)
            {
                int bol=egyezik(j,i);
                if((bol!=10001) && (fix[j]>fix[i]+1))
                // ha illeszthetõ szó, és gyosabban értünk ide mint ahogy eddig becsültük
                {
                    osszo[j]=bol;    // az a szó amivel idáig jutottunk
                    oshely[j]=i;  ///// az a pont ahonnan ide jutottunk
                    fix[j]=fix[i]+1;  //// úgy becslés
      //              cout << j <<"\n";
                }
            }
        }
    }
}
 
 
///// megnézi hogy i-tõl j-ig van-e megfelelõ szó, és visszaadja, hogy melyik az
int egyezik(int j, int i)
{
    bool bol=true;
    for(int l=0; l<n; l++)
    {
        if(szavak[l].bl==(j-i))
        {
            bol=true;
            for(int k=0; k<szavak[l].bl; k++)
            {
                if(szavak[l].a[k]!=s[i+k]) {bol=false; break;}
            }
            if(bol) {return l;}
        }
    }
    return 10001;
}