2015年9月30日 星期三

Uva 860 Entropy Text Analyzer

題目來源:https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=10&page=show_problem&problem=801

題意:

這題在luckycat沒有翻譯..有點難過,畢竟英文真的沒有很好。

first,他會先輸入一篇文章,你要按照公式,分別輸出他的單字總數、ET、Erel。

胡言亂語:

//記得當時我問同學題意時,它們都說:你帶公式就好啦,但我就是不懂公式的意思咩=3=

作法講起來真的蠻簡單的

首先你要會將句子中的單字擷取出來,所以會用到strtok( )這個函式,他的用法是:


//開始分解str1,遇到, .:;!?()\"這些符號則分割成P
p = strtok(str1, ", .:;!?()\"");
while (p != NULL) {
cout<<p<<endl;//輸出p
//從剛剛還沒切玩的地方繼續切
p = strtok(NULL, ", .:;!?()\"");
}
view raw tet.cpp hosted with ❤ by GitHub



這樣就可以將單字取出來了!

//但要注意str1是 char[]喔~是cstring (char string)才可以使用=)

//比較兩個cstring是否相同可以使用strcmp(str1,str2),相同回傳0,不同回傳非零數字~

取出來後就可以順便計算其出現頻率。因此就用到map了!

剛認識map時,覺得他的感覺很像hash(雜湊),你的key會對應到一個抽屜,你可以在抽屜內放數字進去。因此在這邊,我們把剛剛取出的單字p當成key,把它出現頻率放到對應的抽屜裡:

#include<map>
using namespace std;
map <string,int> tree;//key是string 抽屜裡放的是int
map <string,int>::iterator it;
//用法:
p = strtok(str1, ", .:;!?()\"");
while (p != NULL) {
con++;
if(p[0]<97) p[0]+=32;//單字要全小寫
words=p;//將char[]->string
it = tree.find(words);//尋找key對應到的抽屜
if(it==tree.end()) tree[words] = 1;//沒找到
else tree[words]++;//找到,代表前面有出現過
p = strtok(NULL, ", .:;!?()\"");
}
view raw tet.cpp hosted with ❤ by GitHub

最後再將答案計算並輸出就好 ^_____^

//n表示有幾種單字,爛瘩表示總共有幾個單字。

程式碼:

#include<cstdio>
#include<iostream>
#include<cstring>
#include<map>
#include<cmath>
using namespace std;
map <string,int> tree;
map <string,int>::iterator it;
//計算並輸出
void printf_out(int con){
double ET = 0;
for(it = tree.begin();it!=tree.end();it++)
ET += it->second*(log10(con)-log10(it->second));
ET/=con;
printf("%d %.1lf %.0lf\n",con,ET,(ET/log10(con))*100);
}
int main(){
string words;
int con = 0;//計算總共有己的單字
char *p, str1[100005] ;
tree.clear();//清空map
while(cin.getline(str1,100005)){
if(!strcmp(str1,"****END_OF_INPUT****"))
break;
if(!strcmp(str1,"****END_OF_TEXT****")){
printf_out(con);
tree.clear();
con = 0;
}
else{
p = strtok(str1, ", .:;!?()\"");
while (p != NULL) {
con++;
if(p[0]<97) p[0]+=32;
words=p;
it = tree.find(words);
if(it==tree.end()) tree[words] = 1;//沒找到
else tree[words]++;
p = strtok(NULL, ", .:;!?()\"");
}
}
}
}
view raw tet.cpp hosted with ❤ by GitHub




沒有留言:

張貼留言

注意:只有此網誌的成員可以留言。