unit1.~cpp

利用最少回合數 對於給定一個字串 再給定一些參考字元 利用替換掉字元來達到與給定的字串為目的

//---------------------------------------------------------------------------

#include <vcl.h>
#pragma hdrstop

#include "Unit1.h"
//---------------------------------------------------------------------------
#pragma package(smart_init)
#pragma resource "*.dfm"
AnsiString original,change;
int compare[100][100][2];
TForm1 *Form1;
//---------------------------------------------------------------------------
__fastcall TForm1::TForm1(TComponent* Owner)
        : TForm(Owner)
{
        /*Canvas->Pen->Color=clRed;
        Canvas->Pen->Width=2;
        Canvas->MoveTo(x+i*w,y);
        Canvas->LineTo(x+i*w,y+450);
        Canvas->Ellipse(x-8,y-8,x+8,y+8);
        Canvas->Rectangle(0,0,1000,1000);
        Canvas->Font->Size=8;
        Canvas->Font->Name="Time New Roman";
        Canvas->TextOut(x-4,y-5, b);*/
}
//---------------------------------------------------------------------------

void __fastcall TForm1::Button1Click(TObject *Sender)
{
        int i,j,n,m,a,b,c;
        original=Edit1->Text;
        change=Edit2->Text;
        n=original.Length();
        m=change.Length();
        for(i=0;i<=n;i++)
        {
                compare[i][0][0]=i;
                compare[i][0][1]=1;
        }
        for(j=0;j<=m;j++)
        {
                compare[0][j][0]=j;
                compare[0][j][1]=3;
        }
        for(i=1;i<=n;i++)
                for(j=1;j<=m;j++)
                {
                        compare[i][j][0]=0;
                        compare[i][j][1]=0;
                }
        for(i=1;i<=n;i++)
                for(j=1;j<=m;j++)
                {
                        a=compare[i-1][j][0]+1;
                        b=compare[i][j-1][0]+1;
                        c=compare[i-1][j-1][0];
                        if(original[i]!=change[j])
                                c++;
                        if(c<=a&&c<=b)
                        {
                                compare[i][j][0]=c;
                                if(original[i]!=change[j])
                                        compare[i][j][1]=2;
                                else
                                        compare[i][j][1]=4;
                        }
                        else if(a<b)
                        {
                                compare[i][j][0]=a;
                                compare[i][j][1]=1;
                        }
                        else
                        {
                                compare[i][j][0]=b;
                                compare[i][j][1]=3;
                        }
                }
        printtable(n,m);
        printstring(n,m);
}
//---------------------------------------------------------------------------
void __fastcall TForm1::printtable(int n,int m)
{
        int i,j;
        Canvas->Rectangle(5,80,1000,1000);
        for(i=1;i<=n;i++)
                Canvas->TextOut(30*i+230,100, original[i]);
        for(j=1;j<=m;j++)
                Canvas->TextOut(200,30*j+130, change[j]);
        for(i=0;i<=n;i++)
        for(j=0;j<=m;j++)
        {
                Canvas->TextOut(30*i+230,30*j+130, compare[i][j][0]);
                if(compare[i][j][1]==1)
                {
                        Canvas->MoveTo(30*i+228,30*j+135);
                        Canvas->LineTo(30*i+220,30*j+135);
                        Canvas->LineTo(30*i+223,30*j+132);
                        Canvas->MoveTo(30*i+220,30*j+135);
                        Canvas->LineTo(30*i+223,30*j+138);
                }
                else if(compare[i][j][1]==2)
                {
                        Canvas->MoveTo(30*i+229,30*j+131);
                        Canvas->LineTo(30*i+223,30*j+125);
                        Canvas->LineTo(30*i+228,30*j+125);
                        Canvas->MoveTo(30*i+223,30*j+125);
                        Canvas->LineTo(30*i+223,30*j+130);
                }
                else if(compare[i][j][1]==3)
                {
                        Canvas->MoveTo(30*i+233,30*j+129);
                        Canvas->LineTo(30*i+233,30*j+121);
                        Canvas->LineTo(30*i+236,30*j+124);
                        Canvas->MoveTo(30*i+233,30*j+121);
                        Canvas->LineTo(30*i+230,30*j+124);
                }
                else if(compare[i][j][1]==4)
                {
                        Canvas->Pen->Width=2;
                        Canvas->MoveTo(30*i+229,30*j+131);
                        Canvas->LineTo(30*i+223,30*j+125);
                        Canvas->LineTo(30*i+228,30*j+125);
                        Canvas->MoveTo(30*i+223,30*j+124);
                        Canvas->LineTo(30*i+223,30*j+130);
                        Canvas->Pen->Width=1;
                }
        }
}

void __fastcall TForm1::printstring(int n,int m)
{
        int i,j,time=0;
        AnsiString test=change;
        Canvas->TextOut(10,90, "original");
        Canvas->TextOut(70,95, original);
        Canvas->TextOut(10,120, "change");
        Canvas->TextOut(70,125, change);
        i=n;
        j=m;
        while(i>0||j>0)
        {
                if(compare[i][j][1]==1)
                {
                        test.Insert(original[i],j+1);
                        Canvas->TextOut(10,time*30+150, "insert");
                        Canvas->TextOut(70,time*30+155, test);
                        time++;
                        i--;
                }
                else if(compare[i][j][1]==2)
                {
                        test[j]=original[i];
                        Canvas->TextOut(10,time*30+150, "replace");
                        Canvas->TextOut(70,time*30+155, test);
                        time++;
                        j--;
                        i--;
                }
                else if(compare[i][j][1]==3)
                {
                        test.Delete(j,1);
                        Canvas->TextOut(10,time*30+150, "delete");
                        Canvas->TextOut(70,time*30+155, test);
                        time++;
                        j--;
                }
                else
                {
                        i--;
                        j--;
                }
        }
        Label3->Caption=compare[n][m][0];
}