POJ總結(2159)

POJ2159 Ancient Cipher

題目思路：

1.我的第一思路是把他當作傳統密碼來解答的；其中的替換加密我自己預設使用了凱撒密碼、置換則不具體到某一算法；很開心的是暑假做了一個類似的密碼題，會用代碼實作凱撒密碼；然後就開心的将代碼寫完了。然而WR…

(2.還是想回顧一下錯誤解法的思路，首先凱撒替代一共有26種情況，那麼對這裡的每一種情況生成的中間字元串都做如下處理：

判斷該字元串中的字元串是否是密文字元串的字元置換。這個過程可以将兩個字元串進行排序，然後周遊比較。)

3.自以為這個題目很簡單，就沒有好好看清題目。題目中提到的“替代”并沒有特指如何替代，隻要替代為另一個不同的字元就好。

4.于是問題就轉化為，判斷兩個字元串中出現頻率相同的字元數目是否相同。也就是說，隻要滿足頻率不丢失就可以了。

5.那麼可以分别統計明文和密文的字元；并将各個字元出現的頻率存儲在整型數組；最後判斷兩個(有序的)整型數組是否相等就可以了

問題與解惑：

Q:字元排序？

A:這裡使用的是冒泡排序…希望可以複習一下字元串排序，但是還沒有使用…

Q:VC++6.0裡邊局部變量居然可以當作全局來用？

代碼：

#include <stdio.h>
#include <string.h>
void count(char *a,int alength,int *x);
bool isEqual(int* x,int* y);
void sort(char *a,int alength);
void sort(int* b);

int main()
{
    char a[]="";
    char b[]="";
    int freA[]={};
    int freB[]={};
    scanf("%s",a);
    scanf("%s",b);
    int alength=strlen(a),blength=strlen(b);

    if((alength-blength)!=)
    {
        printf("NO\n");
        return ;
    }

    sort(a,alength);
    sort(b,blength);

    count(a,alength,freA);
    count(b,blength,freB);

    sort(freA);
    sort(freB);

    if(isEqual(freA,freB)==true)
    {
        printf("YES\n");
    }
    else
    {
        printf("NO\n");
    }

    return ;
}

void count(char *a,int alength,int *x)
{
    int i=,flag=,k=;
    x[]=;
    for(i=;i<alength-;i++)
    {
        if(a[i+]!=a[i])
        {
            x[k]=flag;
            x[]++;
            k++;
            flag=;
        }
        else
        {
            flag++;
        }
    }
    x[k]=flag;
}

bool isEqual(int* x,int* y)
{
    if(x[]-y[]!=)
    {
        return false;
    }
    else
    {
        for(int i=;i<x[];i++)
        {
            if(x[i]-y[i]!=)
            {
                return false;
            }
        }
    }
    return true;
}

void sort(int* b)
{

    int i=;
    int blength=b[]+;

    for(i=;i<blength;i++)
    {
        for(int j=i+;j<blength;j++)
        {
            if(b[j]<b[i])
            {
                int swap=b[j];
                b[j]=b[i];
                b[i]=swap;
            }
        }
    }
}

void sort(char *a,int alength)
{
    int i=,j=;
    for(i=;i<alength;i++)
    {
        for(j=i+;j<alength;j++)
        {
            if(a[j]<a[i])
            {
                char mid=a[j];
                a[j]=a[i];
                a[i]=mid;
            }
        }
    }
}