2010年1月31日 星期日

Problem 10789 Prime Frequency,字出現次數是否為質數

Problem 10789 此題要輸入一字串,判斷每個字出現的次數以及它的出現次數是否為質數,如果為質數,則列出此字;反之,則否。

此題只須記錄每字出現以及它的次數,印出時要注意是以ASCII值由小到大排列,除此之外就沒問題了。

先設幾個全域變數:
struct Num
{
char word;
int count;
};
struct Num N[201];
int repeatIndex = 0, index = 0;

再來是主程式區塊:
int n, i, j, isPut;
char str[2001], ch;
scanf("%d", &n);
for (i = 0; i < n ; i ++)
{
index = 0, isPut = 0;
memset(str, 0, strlen(str));
scanf("%s", str);
for (j = 0;j < strlen(str); j ++)
insert(str[j]);
printf("Case %d: ", i + 1);
for (j = 0;j < index;j ++)
if (isPrime(N[j].count)) printf("%c", N[j].word), isPut = 1;
if (isPut != 1) printf("empty");
printf("\n");
}

最後是函式部分:
void insert (char ch)
{
int i;
if ( !checkRepeat(ch))
{
N[index].word = ch, N[index].count = 1, index ++;
for (i = index ; i >= 2; i--)
if ( !change(i - 1, i - 2)) break;
}
else
N[repeatIndex].count ++;
}

int checkRepeat (char ch)
{
for (repeatIndex = 0 ; repeatIndex < index; repeatIndex ++)
{
if (N[repeatIndex].word == ch)
return 1;
}
return 0;
}

int change (int i, int j)
{
struct Num temp;
int k = (int)N[i].word, h = (int)N[j].word;
if (N[i].word < N[j].word )
{
temp = N[i], N[i] = N[j], N[j] = temp;
return 1;
}
return 0;
}

int isPrime (int n)
{
int i;
if (n == 1) return 0;
for (i = 2; i < n; i ++)
if (n % i == 0) return 0;
return 1;
}

By David.K

p10789題目連結
回ACM題庫目錄
回首頁

沒有留言: