# UVA 10200 - Prime Time (質數 + 精度)
透過前綴和紀錄結果，使用 check() 是否為質數 (未建表)
#include <stdio.h> | |
#include <stdbool.h> | |
int num[10010]; | |
bool check(int n){ | |
for(int i = 2; i * i <= n; i++){ | |
if(n % i == 0) | |
return false; | |
} | |
return true; | |
} | |
void init(){ | |
for(int i = 0; i <= 10000; i++){ | |
int tmp = i * i + i + 41; | |
num[i] = num[i-1]; | |
if(check(tmp)) num[i]++; | |
} | |
} | |
int main(){ | |
int a,b; | |
init(); | |
while(scanf("%d%d",&a,&b) != EOF){ | |
int ans = b - a + 1; | |
int cnt = num[b] - num[a]; | |
if(check(a*a+a+41)) cnt++; | |
printf("%.2f\n",((cnt*1.0)/(ans*1.0)+1e-8)*100.0); | |
} | |
return 0; | |
} |
# 大數乘法
跟大數加法很像，先讓 的每項先乘上，在統一處理進位問題。
如果乘數，才可以這麼做喔。
否則，就要寫成for (i: lenA) for(j: lenB) sum[i+j] += a[i] * b[j];
#include<stdio.h> | |
#include<string.h> | |
#define MAX_SIZE 100000 | |
char s1[MAX_SIZE+10]; | |
int a[MAX_SIZE+10]; | |
int b; | |
int sum[MAX_SIZE+10]; | |
void solve(){ | |
memset(a,0,sizeof(a)); | |
memset(sum,0,sizeof(sum)); | |
int lenA = strlen(s1); | |
// 將 字元 轉成 數字 ，並 反方向 紀錄 (比較好處理進位) | |
for (int i=0,j=lenA-1;j>=0;j--,i++) a[i]=s1[j]-'0'; | |
// 兩數相乘 (先不要管進位) | |
for (int i=0;i<lenA;i++) sum[i] += a[i] * b; | |
// 處理進位 | |
for (int i=0;i<MAX_SIZE;i++){ | |
if(sum[i]>=100000){ | |
sum[i+5]+=sum[i]/100000; | |
sum[i]=sum[i]%100000; | |
} | |
if(sum[i]>=10000){ | |
sum[i+4]+=sum[i]/10000; | |
sum[i]=sum[i]%10000; | |
} | |
if(sum[i]>=1000){ | |
sum[i+3]+=sum[i]/1000; | |
sum[i]=sum[i]%1000; | |
} | |
if(sum[i]>=100){ | |
sum[i+2]+=sum[i]/100; | |
sum[i]=sum[i]%100; | |
} | |
if(sum[i]>=10){ | |
sum[i+1]+=sum[i]/10; | |
sum[i]=sum[i]%10; | |
} | |
} | |
int flag = 0; | |
for(int i=MAX_SIZE;i>=0;i--) | |
if(sum[i] != 0){ | |
flag = i; | |
break; | |
} | |
for(int i=flag;i>=0;i--) | |
printf("%d",sum[i]); | |
printf("\n"); | |
} | |
int main(){ | |
while (scanf("%s %d",s1,&b)!=EOF){ | |
solve(); | |
} | |
return 0; | |
} |
# UVA 00245 - Uncompress (Linked list + str)
實作 Linked list 跟 字串處理 的練習題
基本上，就是實作出題目的敘述。
#include <stdio.h> | |
#include <string.h> | |
#include <stdbool.h> | |
typedef struct Node{ | |
char word[25]; | |
struct Node *next; | |
}Node; | |
bool is_number(char ch){ | |
return '0' <= ch && ch <= '9'; | |
} | |
bool is_alphabet(char ch){ | |
return ('a' <= ch && ch <= 'z') || ('A' <= ch && ch <= 'Z'); | |
} | |
int main(){ | |
Node *head = NULL; | |
char ch; | |
ch = getchar(); | |
while(true){ | |
if(is_number(ch)){ // is_number | |
if(ch == '0') break; | |
int num = 0; | |
while(is_number(ch)){ | |
num = num * 10 + (ch - '0'); | |
ch = getchar(); | |
} | |
Node *now = head, *prev = NULL; | |
for(int i = 1; i < num ; i ++){ | |
prev = now; | |
now = now->next; | |
} | |
printf("%s",now->word); | |
if(now != head){ | |
prev->next = now->next; | |
now->next = head; | |
head = now; | |
} | |
}else if(is_alphabet(ch)){ // first time | |
char word[200] = "\0"; // 記得要初始化 | |
int tmp = 0; | |
while(is_alphabet(ch)){ | |
word[tmp++] = ch; | |
ch = getchar(); | |
} | |
printf("%s",word); | |
Node *cur = (Node *)malloc(sizeof(Node)); | |
strcpy(cur->word,word); // 不能直接賦予 | |
cur->next = head; | |
head = cur; | |
}else{ //other symbol 包含換行 | |
putchar(ch); | |
ch = getchar(); | |
} | |
} | |
return 0; | |
} |
# 聽說助教會改題目，遞迴建表
遞迴建表就是開一個陣列 record[] ，紀錄已經算過的值，這樣就可以避免反覆運算。
這邊以期中考的題目為例:
#include <stdio.h> | |
#define SIZE 10101 | |
int record[SIZE]; | |
int step(int n) { | |
if (n > 10000) { | |
if (n % 2 == 1) return 1 + step(3 * n + 1); | |
return 1 + step(n / 2); | |
} | |
int index = 100 + n; | |
if (record[index] != -1) return record[index]; // 當數值已經被算過 | |
if (n < 0) return record[index] = 1 + step(n * n); | |
if (n == 1) return record[index] = 1; | |
if (n%2==1) return record[index] = 1 + step(3 * n + 1); | |
return record[index] = 1 + step(n / 2); | |
} | |
int main() { | |
int lower, upper, maxIndex, maxValue; | |
for (int i = 0; i < SIZE; i++) record[i] = -1; | |
record[100] = 0; | |
while (scanf("%d %d", &lower, &upper) != EOF) { | |
maxIndex = lower; | |
maxValue = -1; | |
for (int i = lower; i <= upper; i++) { | |
int val = step(i); | |
if (val > maxValue) { | |
maxIndex = i; | |
maxValue = val; | |
} | |
} | |
printf("Room_%d %d\n", maxIndex, maxValue); | |
} | |
return 0; | |
} |
