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')) }
}
/* 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)) {
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;
}
|