NPSC補完計劃

登入註冊帳號.

請輸入帳號, 密碼以及預計登入時間
進階搜尋  

最新消息:

歡迎光臨NPSC補完計劃

+ NPSC補完計劃 » NPSC高中組 » NPSC2005高中組決賽
 NPSC 2005 高中組 決賽 E.智慧型單字查詢

作者 主題: NPSC 2005 高中組 決賽 E.智慧型單字查詢  (閱讀 1704 次)

sagit

  • 管理員
  • 白金會員
  • *****
  • 文章數: 238
    • 檢視個人資料
NPSC 2005 高中組 決賽 E.智慧型單字查詢
« 於: 十二月 08, 2009, 02:31:29 pm »

NPSC 2005 高中組 決賽 E.智慧型單字查詢

說明:給你一堆單字當做字庫,然後給你 xxx* *xxx* *xxx 之類的字首、字根、字尾,請問你有多少個單字符合這些條件。

解法:利用一個陣列來記錄那些單字符合條件。因為一行查詢可能有多個條件,所以要熟練字串的拆解。另外,可以用 Top-down 的方式來簡化思考,也就是把某些東西寫成函數,不要只用一個 main 硬做,這樣會很辛苦。

參考程式:(By sagit)

代碼: [選擇]
// NPSC 2005 決賽 - 題目 E - 智慧型單字查詢 //
#include <iostream>
#include <fstream>
#include <cstdlib>
#include <string.h>
#define MAX 1000 // 單字個數
#define LEN 41 // 字串長度 

using namespace std;

char Word[MAX][LEN]; // 記錄字典裡的單字
int Match[MAX], Num=0;
// Match[] 陣列記錄是否符合查詢條件, Num 記錄字典單字的總數 

int MatchWord(char s[], int n, int t)
// 比較 Word[n] 是否符合字串 s 的條件
// t 為字串 s 的類型: 1 -> 字首 2 -> 字尾 3 -> 字根
// 符合則傳回 1, 不符合則傳回 0
{
    int l1, l2;
    l1=strlen(s);
    l2=strlen(Word[n]);
    switch (t)
    {
        case 1: // 字首
            return (strncmp(Word[n], s, l1)==0);
        case 2: // 字尾
            return (strcmp(Word[n]+l2-l1, s)==0);
        case 3: // 字根
            return (strstr(Word[n], s)!=0);
        default: // 不可能
            return 0;
    }
}

void Query(char str[])
// 以字串 str 為條件, 對整個字典做查詢
// 並將結果記錄在 Match[] 陣列 
{
    int i, j, t, l;
    char buf[LEN], *p1, *p2;
    for (i=0; i<Num; i++)
        Match[i]=1;
    strcpy(buf, str); // 原始的 str 不能被破壞 
    p1=buf;
    for (p1=buf; p1; p1=p2)
    {
        p2=strchr(p1, ' ');
        if (p2) *p2++=0;
        t=0;
        l=strlen(p1);
        if (p1[l-1]=='*')
        {
            t+=1;
            p1[l-1]=0; // 去掉結尾的 '*'
        }
        if (p1[0]=='*')
        {
            t+=2;
            p1++; // 去掉前面的 '*'
        }
        // t = 1:字首 2:字尾 3:字根
        for (i=0; i<Num; i++)
        {
            if (Match[i]==0) continue;
            if (MatchWord(p1, i, t)==0) Match[i]=0;
        }
    }
}

int main()
{
    ifstream fin("pe.in");
    ofstream fout("pe.out");
    char str[LEN];
    int m, n, i, j;

    // 輸入字典的單字
    fin >> Num;
    for (i=0; i<Num; i++)
        fin >> Word[i];

    // 開始查詢
    fin >> m;
    fin.getline(str, LEN); // 讀取換行
    for (i=1; i<=m; i++)
    {
        fin.getline(str, LEN);
        Query(str);
        for (j=0, n=0; j<Num; j++) // 計算符合條件的個數
            if (Match[j]) n++;
        fout << "Query " << i << ": " << str << ", " << n <<
             " item(s) is found." << endl;
        for (j=0; j<Num; j++)
            if (Match[j]) fout << Word[j] << endl;
        fout << endl;
    }

//    system("PAUSE");
    return 0;
}
記錄
+ NPSC補完計劃 » NPSC高中組 » NPSC2005高中組決賽
 NPSC 2005 高中組 決賽 E.智慧型單字查詢