# WEEK10
## CPE 題目一值不通過怎麼辦?
1. 使用瘋狂程設
[安裝連結](http://coding-frenzy.arping.me/)
>CPE考試用的軟體
>有較完整的功能
2. Udebug
[https://www.udebug.com/](https://www.udebug.com/)
>用題目號碼搜尋題目，點選一組側資進行測試
## 作業說明
### 2.17 最終速度
>請撰寫一個程式，要求使用者輸入某物件的初始速度和加速度，以及已經經過的時間，將這些值放 入變數 u、a 和 t 中，並印出最終速度 v 和所經過的距離 s。
>將輸入值依照公式計算後輸出結果
```cpp
#include <stdio.h>
int main(void){
float u, a, t;
scanf("%f %f %f", &u, &a, &t);
printf("%.2f\n%.2f", u + a * t, u * t + 0.5 * a * t * t);
return 0;
}
```
### 2.20 從秒轉換到小時、分鐘和秒
>撰寫一個程式，要求使用者輸入自某事件發生以來經過的總時間（以秒為單位）， 並將其轉換為小時、分鐘和秒。時間應顯示為小時：分鐘：秒。（提示：使用模數運算子。）
>用除法、取餘數求得小時、分鐘和秒
>除以 3600 得到小時
>除以 3600 的餘數為不足一小時的部分
>將此部分除以 60 得到分鐘、除 60 的餘數為秒
```cpp
#include <stdio.h>
int main() {
int totalSeconds, hours=0, minutes=0, seconds=0;
scanf("%d", &totalSeconds);
// 計算小時、分鐘和秒
hours = totalSeconds / 3600;
totalSeconds %= 3600;
minutes = totalSeconds / 60;
seconds = totalSeconds % 60;
// 顯示結果
printf("%d:%d:%d", hours, minutes, seconds);
return 0;
}
```
### 3.16 營業稅
>營業稅是向買方收取並轉付給政府的，零售商必須提交每月營業稅報表，其中列出該月的營業額和所徵 收的營業稅額，並分別列出郡政府稅和州政府稅。請開發一個程式，輸入一個月的總收入，計算收入的營業稅，並 分別顯示出郡政府稅和州政府稅。假設州的營業稅率是 4％，郡的營業稅是 5％。以下是輸入／輸出的對話範例。
```cpp
#include <stdio.h>
int main(void){
float totalAmount;
scanf("%f", &totalAmount);
float countySales = totalAmount * 0.05,
float stateSalse = totalAmount * 0.04;
printf("Sales: $ %.2f\n", totalAmount - countySales - stateSalse);
printf("County Sales Tax: $ %.2f\n", countySales);
printf("State Sales Tax: $ %.2f\n", stateSalse);
printf("Total Sales Tax Collected: $ %.2f", countySales + stateSalse);
return 0;
}
```
### 3.17 抵押計算工具
>開發一個 C 程式來計算銀行客戶抵押貸款的利息。對於每個客戶，我們有以下各項資訊：
1 帳號
2 抵押金額
3 抵押期限
4 利率
該程式應輸入每項資訊，計算出應付利息總額（=抵押金額×利率×抵押期限），並將其加到抵押金額中以獲得應付 的總金額。它應該透過將應付總金額除以抵押期的月份數來計算每月所需支付的款項。該程式應顯示每月所需支 付款項，四捨五入到最接近的金額（美元）。該程式應同時處理每個客戶的帳戶。以下是一個輸入／輸出的對話範 例：
```cpp
#include <stdio.h>
#include <math.h>
int main(void){
float rate, account, amount, term;
printf("Enter account number: ");
scanf("%f", &account);
printf("Enter mortgage amount: ");
scanf("%f", &amount);
printf("Enter mortgate term: ");
scanf("%f", &term);
printf("Enter interest rate: ");
scanf("%f", &rate);
float total = amount + (amount * term * rate);
float monthly = total / (float)(term * 12.0);
printf("The monthly payable interest $ %.0f", roundf(monthly));
return 0;
}
```
### 3.18 銷售傭金計算工具
>某家公司付給銷售員的酬勞是以抽佣金的方式來計算的。銷售員每週可領到$200 元加上當週 銷售金額的 9%。舉例來說，若某位銷售員在一週內賣出了$5000 元的商品，那麼那一週他便可領到$200 加$5000 的 9%，即$650 元。請撰寫一個 C 程式，輸入每個銷售員上週的銷售額，然後計算並顯示他的收入。請一次處理一個 銷售員的資料。以下是輸入／輸出對話的範例。
```cpp
#include <stdio.h>
int main(void){
printf("Enter sales in dollars: ");
float sales;
scanf("%f", &sales);
printf("Salary is: $%.2f", 200 + sales * 0.09);
return 0;
}
```
### 3.22 檢查數字是否為質數
>質數是大於 1 的任何自然數，只能由 1 和數字本身整除。請編寫一個讀取整數並確定它是否為質數的 C 程式。
>A prime number is a positive integer that is divisible only by 1 and itself. For example: 2, 3, 5, 7, 11, 13, 17.
>In the program, a for loop is iterated from i = 2 to i < n/2.
>In each iteration, whether n is perfectly divisible by i is checked using:
```
if (n % i == 0) {
flag = 1;
break;
}
```
>If n is perfectly divisible by i, n is not a prime number. In this case, flag is set to >1, and the loop is terminated using the break statement.
>Notice that we have initialized flag as 0 during the start of our program.
>So, if n is a prime number after the loop, flag will still be 0. However, if n is a non-prime number, flag will be 1.
```cpp
#include <stdio.h>
int main() {
int n, i, flag = 0;
scanf("%d", &n);
// 0 and 1 are not prime numbers
// change flag to 1 for non-prime number
if (n == 0 || n == 1)
flag = 1;
for (i = 2; i <= n / 2; ++i) {
// if n is divisible by i, then n is not prime
// change flag to 1 for non-prime number
if (n % i == 0) {
flag = 1;
break;
}
}
// flag is 0 for prime numbers
if (flag == 0)
printf("%d is a prime number.", n);
else
printf("%d is not a prime number.", n);
return 0;
}
```
### 3.24 表格輸出
>撰寫一個 C 程式利用迴圈印出下表。在 printf 敘述式中使用水平定位點\t 來分隔欄位。
>
```cpp
#include <stdio.h>
int main(void){
for(int i = 1; i <= 10; i++){
printf("%d\t%d\t%d\t%d\n", i, i * i, i * i * i, i * i * i * i);
}
return 0;
}
```
### 3.25 表格輸出
>撰寫一個 C 程式利用迴圈印出下表
>
```cpp
#include <stdio.h>
int main(void){
int A = 7;
printf("A\tA+3\tA+6\tA+9\n");
for(int i = 1; i <= 5; i++){
printf("%d\t%d\t%d\t%d\n", A * i, A * i + 3, A * i + 6, A * i + 9);
}
return 0;
}
```
### 3.34 弗洛伊德三角形
>弗洛伊德三角形是一個直角三角形的自然數陣列，它透過用連續整數填入列來定義。因此，第 1 列 有數字 1，第 2 列有數字 2 和 3，依此類推。請撰寫一個有 10 列的弗洛伊德三角形的程式。外迴圈可以控制要列印的列 數，內迴圈可以確保每列包含正確的
>整數數量。
>
>第一列印一個、第二列印兩個、第三列印三個
>=>遞 i 列印 i 個
>每印一個把 number + 1
```cpp
#include <stdio.h>
int main() {
int rows, i, j, number = 1;
scanf("%d", &rows);
for (i = 1; i <= rows; i++) {
for (j = 1; j <= i; ++j) {
printf("%d ", number);
++number;
}
printf("\n");
}
return 0;
}
```
### 3.36 阿姆斯壯數
>阿姆斯壯數是一個 n 位數，其各位數字的 n 次方和等於該數本身。例如，數字 153 等於 1^3 + 5^3 + 3^3 ，因
此它是阿姆斯壯數。編寫一個程式來顯示所有三位阿姆斯壯數。
```cpp
#include <stdio.h>
#include <math.h>
int main() {
int num, originalNum, remainder, result = 0;
// 從100到999進行迴圈
for (num = 100; num <= 999; num++) {
originalNum = num;
result = 0;
// 求出每個數字的立方和
while (originalNum != 0) {
remainder = originalNum % 10;
result += pow(remainder, 3);
originalNum /= 10;
}
// 如果立方和等於原始數字，則為阿姆斯壯數
if (result == num) {
printf("%d\n", num);
}
}
return 0;
}
```
### 3.37 檢出某數的倍數
>撰寫一個程式印出 500 個錢號（$），一次印一個。每印 50 個錢號必須印一個換行字元（提示：從 1 數到 500，使用模數運算子來判斷計數器是否為 50 的倍數）。
```cpp
#include <stdio.h>
int main() {
int count;
for (count = 1; count <= 500; count++) {
printf("$");
// 判斷是否需要換行
if (count % 50 == 0) {
printf("\n");
}
}
return 0;
}
```
### 3.38 計算 9 的個數
>撰寫一個程式讀入一個整數（5 位數以下），判斷並印出此數中有多少個數字為 9。
```cpp
#include<stdio.h>
int main(){
int num
int a,c = 0;
scanf("%d",&num);
while(num != 0){
a = num % 10;
if(a == 9){
c++;
}
num /= 10;
}
printf("%d",c);
return 0;
}
```
方法2 : 字串方法
>宣告一個 char 型態的陣列，將陣列走一次
```cpp
#include <stdio.h>
int main(void){
char s[100] = {'\0'};
scanf("%s", s);
int count = 0;
for(int i = 0; s[i] != '\0'; i++){
if(s[i] == '9'){
count++;
}
}
printf("%d", count);
}
```
### 3.40 計算 3 的次方
>撰寫一個程式持續印出 3 的次方數，即 3、9、27、91、273 等等。你的迴圈不會結束，換句話說，它是個無窮迴圈。當你執行這個程式時，會出現什麼結果？
```cpp
#include <stdio.h>
int main(void){
int num = 1;
for(int i = 1; i <= 10; i++){
printf("%d\n", num *= 3);
}
return 0;
}
```
### 3.45 階乘
> 非負整數 n 的階乘寫作 n!，（讀作「n 的階乘」）其定義如下：
> n!= n (n - 1) (n - 2) … 1 （大於等於1時）
> n=0 （n等於0時）
> 
> b) 的值會大約等於 2.71828
```cpp
#include <stdio.h>
double Factorial(double num){
double result = 1;
for(int i = 1; i <= num; i++){
result *= i;
}
return result;
}
double e(){
double sum = 1;
for(int i = 1; i <= 10000; i++){
sum += 1 / Factorial(i);
}
return sum;
}
double pow(double base, double power){
double result = 1.0;
for(int i = 0; i < power; i++){
result *= base;
}
return result;
}
void eX(double n){ // e^x
printf("%lf", pow(e(), n));
}
int main(void){
double n;
scanf("%lf", &n);
printf("%lf\n", Factorial(n));
printf("%lf\n", e());
eX(n);
return 0;
}
```
### 4.10 將攝氏溫度轉換為華氏溫度
```cpp
#include <stdio.h>
int main(void){
float C;
scanf("%f", &C);
printf("%.1f", 9 * C / 5 + 32);
return 0;
}
```
### 4.11 計算倍數的和
>請撰寫一個程式，計算及印出 1 到 100 之間所有 7 的倍數之和。
>用 for 迴圈從1到100，遇到7的倍數就累加
```cpp
#include <stdio.h>
int main(void){
int sum = 0;
for(int i = 1; i <= 100; i++){
if(i % 7 == 0){
sum += i;
}
}
printf("%d", sum);
return 0;
}
```
### 4.12 質數
>請撰寫一個程式，計算並印出從 1 到 100 之間所有質數。
```cpp
#include <stdio.h>
int main()
{
int total = 0,count = 0;;
for(int i = 1 ; i < 100 ; i++){
count = 0;
for(int j = 1 ; j <= i ; j++){
if(i%j==0){
count++;
}
}
if(count == 2){
printf("%d ",i);
}
}
}
```
### 4.13 自然數的計算
>編寫一個程式，印出從 1 到使用者輸入之任何數字之間的所有自然數的總和、平方和以及立方和。
```cpp
#include <stdio.h>
#include <math.h>
int main()
{
int a ,b=0,c=0,d=0;
scanf("%d",&a);
for(int i = 1 ; i <= a ; i++){
b += i;
c += pow(i,2);
d += pow(i,3);
}
printf("%d\n",b);
printf("%d\n",c);
printf("%d\n",d);
}
```
```cpp
#include <stdio.h>
int main() {
int num, sum = 0, sumOfSquares = 0, sumOfCubes = 0;
// 請求使用者輸入一個整數
scanf("%d", &num);
// 計算總和、平方和以及立方和
for (int i = 1; i <= num; i++) {
sum += i;
sumOfSquares += i * i;
sumOfCubes += i * i * i;
}
// 顯示結果
printf("%d\n", sum);
printf("%d\n", sumOfSquares);
printf("%d\n", sumOfCubes);
return 0;
}
```
### 4.21 ASCII 值
>編寫一個程式來轉換和印出 ASCII 值為 0 到 127 的字元。程式應該每行印出 10 個字元。
```cpp
#include <stdio.h>
#include <ctype.h>
int main() {
int asciiValue;
int count = 0; // 計數器，用於每行印出10個字元
for (asciiValue = 0; asciiValue <= 127; asciiValue++) {
if(isprint(asciiValue))
printf("%c ", asciiValue); // 轉換並印出ASCII值對應的字元
else
printf(" "); // 如果是不可列印字元，印出問號
count++;
// 如果已經印出了10個字元，換行並重置計數器
if (count == 10) {
printf("\n");
count = 0;
}
}
return 0;
}
```
如果輸出結果會亂掉，可以在「不能輸出的字元」的位置印一個空白，可以參考 isprint() 函式
If the output result would become garbled, you can print a space at the position of "characters that cannot be output", and you can refer to the isprint() function.
### 4.25 十進制、二進制、八進制、和十六進制數字比較表
>撰寫一個程式，印出從 1 到 256 的二進制、八進制和十六 進制數字的比較表。如果你不熟悉這些數字系統的話，請先參>考附錄 C。（注意：你可以用轉換指示詞%o 與%X 使 數字分別以八進制和十六進制的方式印出。）
```cpp
#include <stdio.h>
int main() {
int num;
for (num = 1; num <= 256; num++) {
printf("%d\t", num); // 印出十進制數字
// 印出二進制數字
for (int bit = 7; bit >= 0; bit--) {
printf("%d", (num >> bit) & 1);
}
printf("\t%o\t%X\n", num, num); // 印出八進制和十六進制數字
}
return 0;
}
```
> 二進位需要自己算!!! (連續除二之餘數)
> 需使用 '>>' 邏輯移位運算子
>
> 
> 八進制、和十六進制可以用格式化輸出，%o %X
>
> 
## 程式設計(I)結束考說明
### 01
>善用 math.h 中的函數
```cpp
#include <stdio.h>
#include <math.h>
int main() {
int x1, x2, y1, y2;
float distance;
scanf("%d %d %d %d", &x1, &y1, &x2, &y2);
// 計算距離
distance = sqrt(pow(x2 - x1, 2) + pow(y2 - y1, 2));
printf("%.3f", distance);
return 0;
}
```
### 02
>解題方法:
> 將輸入不斷的除2、3、5，看是否最後能整除 (n 剩下1)
> 解題思路:
> 1. 輸入一個數
> 2. 用 while 迴圈重複進行除法
> 3. 看是否最後能整除 (n 剩下1)
```cpp
#include<stdio.h>
int main(){
int n,x;
int c;
scanf("%d", &n);
while(n>1){
if(n%2==0){
n=n/2;
}else if(n%3==0){
n=n/3;
}else if(n%5==0){
n=n/5;
}else{
printf("false");
break;
}
}
if ( n == 1){
printf("true");
}
}
```
### 03
>看起來很難，但其實只要依照題目敘述依序寫出判斷條件即可
```cpp
#include <stdio.h>
int main() {
int n, cycle=1, i;
scanf("%d", &n);
while(n!=1) {
if(n%2 == 1)
n = 3*n+1;
else
n/=2;
cycle++;
}
printf("%d", cycle);
return 0;
}
```
### 04
---
仿射密碼屬於替換密碼的一種，加密函數為 $e(x)=(ax+b)\ (mod\ m)$
其中 $a$ 和 $m$ 互質
$m$ 為字母的數量，即$26$
$b$為欲加密之密文
$x$為欲加密之明文
而解碼函數為$d(x)=a^{-1}(c-b) (mod\ m)$其中$a^{-1}$是 $a$ 在{\displaystyle \mathbb {Z} _{m}}群的乘法反元素。
在這道題中你首先需要完成互質的部分，請撰寫一個程式讓使用者輸入兩個數字，並且判斷這兩個數字是否互質。
Affine cipher is a kind of substitution cipher, and the encryption function is$e(x)=(ax+b)\ (mod\ m)$
where $a$ and $m$ are relatively prime
$m$ is the number of letters
The decoding function is $d(x)=a^{-1}(x-b) (mod\ m)$, where $a^{-1}$ is $a$ in{\displaystyle \mathbb {Z} _{m}}group.
In this question, you first need to complete theco-primepart. Please write a program to allow the user to input two numbers and determine whether the two numbers are co-prime.
---
```cpp
#include <stdio.h>
int gcd(int, int);
int main() {
int n, m;
scanf("%d %d", &n, &m);
// printf("%d", gcd(n, m));
if(gcd(n, m) == 1)
printf("True");
else
printf("False");
return 0;
}
int gcd(int a, int b) {
if(a%b == 0)
return b;
return gcd(b, a%b);
}
```
### 05
>有一個建築由很多層正立方體組成，最底層之正立方體邊長為 n (體積為 n^3)，底層的上一層之正立方體邊長為 (n-1)，一直到最上層之正立方體邊長為 1
>撰寫一個程式，輸入一個總體積 m，是否可以剛好形成一個上述的建築，若可以則輸出該建築最底層之正立方體邊長 n，如果不行則輸出 -1
>使用while迴圈，從最上層開始往下累加，直到超過輸入值
>每累加一次就檢查是否等於輸入，等於代表可以找到，輸出正立方體邊長為 n
>累加完一次，累計體積已超過輸入值 m ，代表找不到，輸出 -1
```cpp
#include <stdio.h>
int main()
{
long long output = 1;
long long check = 0;
long long m;
scanf("%lld", &m);
while (check <= m) {
check += output * output * output;
if (check == m){
printf("%lld", output);
break;
}
if (check > m){
printf("-1");
break;
}
output++;
}
return 0;
}
```
### 06
> 除了單純加3、最後3個另外處理的做法
> 可以使用 %26 來使字母循環
> 但需要特別注意要先將 ASCII code 的值減去 'A' 在 ASCII 表中的位置(65)
> 讓字母 shift 到 0-26
```cpp
#include<stdio.h>
int main(){
char c;
scanf("%c", &c);
printf("%c", (c-65+3)%26+65);
return 0;
}
```
### 07
>給定整數n的所有正因數的個數，並將這個數字輸出
>Count the number of divisors of a positive integern.
```
4 --> 3 // we have 3 divisors - 1, 2 and 4
5 --> 2 // we have 2 divisors - 1 and 5
12 --> 6 // we have 6 divisors - 1, 2, 3, 4, 6 and 12
30 --> 8 // we have 8 divisors - 1, 2, 3, 5, 6, 10, 15 and 30
```
```cpp
#include <stdio.h>
int main()
{
int count = 0;
int n;
scanf("%d", &n);
for (int i = 1; i * i <= n; i++) {
// If i divides n, increment count
if (n % i == 0) {
// If divisors are same, count only once
if (n / i == i) {
count++;
} else {
// Otherwise, count both divisors
count += 2;
}
}
}
printf("%d", count);
return 0;
}
```
```cpp
#include<stdio.h>
int main(){
int a,i,b;
b=0;
scanf("%d",&a);
for (i=1;i<=a;i++){
if (a%i==0){
b++;
}
}
printf("%d",b);
}
```
### 08
>撰寫一個程式讀入一個整數，判斷並印出此數中有多少個數字為9。輸入值為0時，終止程式執行。
>每次取數字的最後一個位元，判斷是否為9
>每一次while迴圈，將輸入數字除以10，值到輸入等於0為止
```cpp
#include <stdio.h>
int main(){
int input;
while(scanf("\n%d", &input)!= EOF){
if(input == 0){
break;
}
int count = 0;
while(input != 0){
if(input % 10 == 9){
count++;
}
input /= 10;
}
printf("%d\n", count);
}
}
```
### 09
>找規律
>2/1，3/2，5/3，8/5，13/8，21/13 ......
>
>F1/F2 F3/F4
>F1+F2=F3
>F1=F4
for 回圈內:
>輸出F1/F2
>
>1. 需要先將F1存到temp
>2. F1+F2存到F1
>3. 再將F2存回F2
```cpp
#include <stdio.h>
int main() {
int i, j, f1=2, f2=1, temp;
for(i=0;i<20;i++) {
if(i%5==0 && i!=0)
printf("\n");
printf("%d/%d ", f1, f2);
temp = f1;
f1 = f1 + f2;
f2 = temp;
}
return 0;
}
```
### 10
>1
```cpp
#include <stdio.h>
int main() {
int n;
while (scanf("%d", &n) != EOF) {
int ans = n;
while (n >= 3){
ans += n / 3;
n = n / 3 + n % 3;
}
ans += (n == 2);
printf("%d\n", ans);
}
return 0;
}
```
>要求重複輸入，又沒給測資數量，就要用 EOF
>一開始買多少代表喝多少，喝多少便產生多少空瓶，所以 Coke_sum 、 Coke_empty 初始化為輸入數
>只要空瓶大於等於 3 即可兌換可樂，用迴圈重複檢查，疊加喝掉的瓶數 空瓶 / 3 = 兌換量，且兌換多少即產生多少空瓶，加上沒兌換到的空瓶，更新空瓶為 空瓶 / 3 + 空瓶 % 3
>跳出迴圈後即可輸出結果，但因為若空瓶為 2，可和朋友借一空瓶湊成 3 瓶去兌換，喝完再歸還空瓶。可透過偉大且神奇的除法來達成這項檢查
```cpp
#include<stdio.h>
int main(){
int Coke;
int Coke_sum;
int Coke_empty;
while(scanf("%d", &Coke) != EOF){
Coke_sum = Coke;
Coke_empty = Coke;
while(Coke_empty >= 3){
Coke_sum = Coke_sum + (Coke_empty / 3);
Coke_empty = (Coke_empty / 3) + (Coke_empty % 3);
}
printf("%d\n", Coke_sum + Coke_empty / 2);
}
return 0;
}
```
### 11
>分數加法
>此題需要兩個步驟:
>1. 計算分子、分母的值
>2. 約分:計算分子、分母值的最大公因數。
>a/b + c/d
>分子: a*d+c*b
>分母: b*d
> GCD(a*d+c*b, b*d)
```cpp
#include <stdio.h>
int gcd(int, int);
int main() {
int a, b, c, d;
char q;
scanf("%d%c%d", &a, &q, &b);
scanf("%d%c%d", &c, &q, &d);
int base = b*d, top = a*d+c*b;
int g = gcd(base, top);
base/=g;
top/=g;
printf("%d/%d", top, base);
return 0;
}
int gcd(int a, int b) {
if(a%b == 0)
return b;
return gcd(b, a%b);
}
```
### 12
>偶數位減去奇數位
>請撰寫一程式，讓使用者輸入一整數n，並計算出該正整數的偶數位與奇數位和之差。
>例如：$n=1234567$，則偶數位和為 $2+4+6=12$，奇數位和為$1+3+5+7=16$，結果則為 $12-16=-4$
```cpp
#include<stdio.h>
int main(){
int n;
scanf("%d",&n);
int ev=0,od=0;
int isev=1;
while(n>0){
int dig=n%10;
if(isev){
ev=ev+dig;
}
else{
od=od+dig;
}
isev=!isev;
n=n/10;
}
printf("%d",-(ev-od));
}
```
```cpp
#include<stdio.h>
#include<math.h>
int main(){
int num,sum = 0,n,t=0;
scanf("%d",&num);
while(num>0){
n = num%10;
t += 1;
if(t%2 == 0)
sum += n;
else if(t%2 != 0)
sum -= n;
num = num/10;
}
printf("%d",sum);
}
```
### 13
>模擬機器人移動
>請撰寫一個程式，讓使用者可以輸入移動方向以及移動步數來控制機器人，最後輸出機器人的座標位子。
>(請使用迴圈一次處理多筆輸入測資，判斷至EOF時程式結束)
```cpp
#include <stdio.h>
int main() {
int d, x=0, y=0, n;
while(scanf("%d", &d) != EOF) {
if(d == 1) {
scanf("%d", &n);
x += n;
}
else if(d == 2) {
scanf("%d", &n);
x -= n;
}
else if(d == 3) {
scanf("%d", &n);
y += n;
}
else if(d == 4) {
scanf("%d", &n);
y -= n;
}
else
printf("Please input again\n");
}
printf("(%d,%d)\n", x, y);
return 0;
}
```
### 14
>費波納契數 (需使用遞迴才算分)
>費波那契數用文字來說就是由0和1開始，之後的費波那契數就是由之前的兩數相加而得出。首幾個費波那契數是：
>1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377
```cpp
#include<stdio.h>
int fib(int n) {
if(n==1 || n==2)
return 1;
else
return fib(n-1) + fib(n-2);
}
int main(){
int a=0;
scanf("%d",&a);
printf("%d", fib(a));
return 0;
}
```
### 15
>Funny Encryption Method
>一位來自墨西哥蒙特瑞技術研究學院(ITESM Campus Monterrey)的學生想發表一種新的數值加密演算法。
>
>演算法步驟如下：
>
>1. 讀入一個整數N，N為欲加密的數字：N = 265
>2. 將N當作十進位的數值：X1 = 265(decimal)
>3. 把X1由十進制轉為二進制：X1 = 100001001(binary)
>4. 計算二進制的X1有幾個1：b1 = 3
>5. 把N當作十六進位數值：X2 = 265(hexadecimal)
>6. 把X2由十六進制轉為二進制：X2 = 1001100101(binary)
>7. 計算二進制的X2有幾個1：b2 = 5
>8. 最後的編碼為N xor (b1*b2)：265 xor (3*5) = 262
>這位學生並未通過這次的計算機組識考試，所以他請求校方在ACM的試題上出一題計算共有幾個位元1的題目，好讓他>能順利發表他的數值加密演算法。
>必須寫一個程式能讀入一個整數，然後輸出該整數的b1, b2值。
> 使用到 &, >> 運算子，計算二進制中 1 的數量
```cpp
#include <stdio.h>
int main() {
int T, N;
scanf("%d", &T);
while (T--) {
scanf("%d", &N);
int X1 = N;
int b1 = 0;
// 由X1計算b1
while (X1) {
b1 += X1 & 1;
X1 >>= 1;
}
// 將N由10進為轉16進位
int X2 = 0;
int mul = 1;
X1 = N;
while (X1) {
X2 += (X1 % 10) * mul;
X1 /= 10;
mul *= 16;
}
// 由X2計算b2
int b2 = 0;
while (X2) {
b2 += X2 & 1;
X2 >>= 1;
}
printf("%d %d\n", b1, b2);
}
return 0;
}
```
### 介紹 C/C++ 中 &, &&, |, ||
&與|是"算術運算子"，意思就是這兩個符號是用在對於bit的運算，&對應至"AND"，而|則是對應至"or"，例如說以下面的bit運算為例:
[介紹 C/C++ 中 &, &&, |, ||](https://hackmd.io/@wsp50317/rygXrgxoB)
```cpp
int main()
{
int a = 4;
int b = -5;
int c = a & b;
int d = a | b;
cout<<"a= "<<std::bitset<8>(a)<<endl;
cout<<"b= "<<std::bitset<8>(b)<<endl;
cout<<"c= "<<std::bitset<8>(c)<<endl;
cout<<"d= "<<std::bitset<8>(d)<<endl;
}
```
```
a= 00000100
b= 11111011
c= 00000000
d= 11111111
```
### 16
>Primary Arithmetic
>在小學時我們都做過加法的運算，就是把2個整數靠右對齊然後，由右至左一位一位相加。如果相加的結果大於等於10就有進位（carry）的情況出現。你的任務就是要判斷2個整數相加時產生了幾次進位的情況。這將幫助小學老師分析加法題目的難度。
> 由低位元開始做加法
> 假設輸入為 n1 n2
> 將 n1 的最低位元 + n2 的最低位元 + 前一個位數的進位 carry
> 若此相加的值 >= 10，代表有進位，將 counter +1 且將進位存起來，供下一輪計算使用
> 若此相加的值 < 10，代表無進位，接著進行下一輪計算使用
```cpp
#include <stdio.h>
int main() {
int n1, n2;
while (scanf("%d %d", &n1, &n2) == 2) {
if (n1 == 0 && n2 == 0) break;
int carry = 0, cnt = 0;
while (n1 > 0 || n2 > 0) {
int tmp = n1 % 10 + n2 % 10 + carry;
if (tmp >= 10) {
carry = tmp / 10;
cnt++;
} else {
carry = 0;
}
n1 /= 10;
n2 /= 10;
}
if (cnt == 0) printf("No carry operation.\n");
else if (cnt == 1) printf("1 carry operation.\n");
else printf("%d carry operations.\n", cnt);
}
return 0;
}
```
### 17
>Beat the Spread!
>超級盃又來了，為了打發中場休息時間，大家就來下注最後的結果會如何。大家下注的目標為兩隊最後的分數和，或者兩隊最後分數差的絕對值。
>給你這2個值，你能推出這2隊最後的得分是多少嗎？
在這個程式中，**if ((s + d) % 2 != 0 || s < d)** 這行程式用來判斷給定的分數和 (s) 和分數差 (d) 是否能夠推導出兩個有效的、非負的整數分數。
1. (s + d) % 2 != 0：
此條件檢查 s + d 是否為偶數。若不是偶數（即是奇數），則無法將其平均分成兩個整數。因為若要從和與差推導出兩隊的分數 x 和 y，我們需要解這兩個方程：
x + y = s
x - y = d 或 y - x = d
從這兩個方程可以推導出 x = (s + d) / 2 和 y = (s - d) / 2。若 s + d 不是偶數，則 x 和 y 不會是整數。
2. s < d：
這個條件檢查分數和是否小於分數差。如果 s 小於 d，則無法推導出合理的分數，因為如果 d（分數差的絕對值）比 s（分數和）還大，表示其中一隊的分數必定為負數，這在遊戲中是不可能的。
```cpp
#include <stdio.h>
int main() {
int T, s, d;
scanf("%d", &T);
while (T--) {
scanf("%d %d", &s, &d);
if ((s + d) % 2 != 0 || s < d) {
printf("impossible\n");
} else {
printf("%d %d\n", (s + d) / 2, (s - d) / 2);
}
}
return 0;
}
```
### 18
>Tell me the frequencies!
>給你一列文字，請你找出各字元出現的次數。
>
```cpp
# include<stdio.h>
int main(){
int i, len, max;
int set = 0; //代表第幾組測試資料
int freq[256];
char ch;
char str[10000]; //讀取輸入字串
while(gets(str)!=NULL){
// 清除前次統計數據
for(i=0;i<256;i++){
freq[i] = 0;
}
// 統計每個字元出現頻率
len = (int)strlen(str);
for(i=0;i<len;i++){
freq[str[i]]++; //輸入字串的第i個字元的ASCII Code 當作 index，去 freq陣列中把這個字元的頻率加1
}
// 找最大頻率值
for(i=0,max=0;i<127;i++){
if(freq[i]>max){
max = freq[i];
}
}
set++; //每次 (每組資料)讀完，將set++
// 第二組開始要先輸出一個換行
if(set>1){
printf("\n");
}
// 頻率由小到大
for(i=1;i<=max;i++){
// ASCII由大到小
for(ch=127;ch>0;ch--){
if(freq[ch]==i){
printf("%d %d\n",ch,freq[ch]);
}
}
}
}
return 0;
}
```
### 19
>You can say 11
>你的任務是，給你一個正整數 N，判定它是否是 11 的倍數。
>
```cpp=
#include <stdio.h>
#include <string.h>
int main() {
char s[1001]; // Assume the input won't exceed 1000 digits.
while (scanf("%s", s) == 1) {
if (strcmp(s, "0") == 0) break;
int odd = 0, even = 0;
int length = strlen(s);
for (int i = 0; i < length; i++) {
if (i % 2 == 0) {
even += s[i] - '0'; //ASCII 轉 10進位
} else {
odd += s[i] - '0'; //ASCII 轉 10進位
}
}
if ((odd - even) % 11 == 0) {
printf("%s is a multiple of 11.\n", s);
} else {
printf("%s is not a multiple of 11.\n", s);
}
}
return 0;
}
```
### 最大公因數 GCD
>最大公因數 : 可以整除兩數的最大的整數
>the largest integer that can exactly divide both numbers (without a remainder).
>n this program, two integers entered by the user are stored in variable n1 and n2.Then, for loop >is iterated until i is less than n1 and n2.
>In each iteration, if both n1 and n2 are exactly divisible by i, the value of i is assigned to gcd.
>When the for loop is completed, the greatest common divisor of two numbers is stored in variable gcd.
```cpp
#include <stdio.h>
int main()
{
int n1, n2, i, gcd;
scanf("%d %d", &n1, &n2);
for(i=1; i <= n1 && i <= n2; ++i)
{
// Checks if i is factor of both integers
if(n1%i==0 && n2%i==0)
gcd = i;
}
printf("G.C.D of %d and %d is %d", n1, n2, gcd);
return 0;
}
```
>smaller integer is subtracted from the larger integer, and the result is assigned to the variable holding larger integer. This process is continued until n1 and n2 are equal.
```cpp
#include <stdio.h>
int main()
{
int n1, n2;
scanf("%d %d",&n1,&n2);
while(n1!=n2)
{
if(n1 > n2)
n1 -= n2;
else
n2 -= n1;
}
printf("GCD = %d",n1);
return 0;
}
```
>一個函數求兩個整數的最大公因數:
>此函數需要兩個參數x,y
>當y不能整除x時,將x設成為y,y設為x%y, 重複此步驟直到x%y為0
>此時y就是這兩個數的最大公因數
```cpp
nt gcd(int x, int y) {
int tmp;
// 如果x < y 則下面的迴圈執行第一次時就會交換x,y了
while (x % y != 0)
{
tmp = y;
y = x % y;
x = tmp;
}
return y;
}
```
>將上述方法寫成遞迴
```cpp
int GCD(int num1,int num2)
{
if(num2==0)
{
return num1;
}
return GCD(num2,num1%num2);
}
```
## 本周題目說明
### 01 遞迴程式練習
>
### 02 函式呼叫列⽰質數列表
>需要寫一個判斷是否為質數的函式
### 仿射加密法 (Affine Cipher)
1. 屬於標準替換密碼
2. 字母表中的每一個字母都對應到另一個固定的字母
3. 函式的功能為:建立一個規定，控制一個某字元映射到哪一個字元
與凱撒挪移法一樣，也是一種「單套字母替代法」，將字母化為數字代碼 a=0, b=1, c=2, …, z=25，其加密函數為 E(m)=αm+β (mod 26)，其中α與β為整數，且α必須與26互質。
為何α必須與26互質？？
假設gcd(α, 26)=g>1，此時函數E將不是1對1，不同明文字母x1, x2將會對應到相同值。以gcd(α, 26)=g>1而言，g值有可能是2或13，以g=2時為例，只需x1 ≡ x2 (mod 13)，而當g=13時，只需x1 ≡ x2 (mod 2)，都會滿足αx1+β ≡ αx2+β (mod 26)。
=> 當加密函數不是1對1時，就無法存在反函數，如此的情況必須排除。
以集合Z/26 = {0,1,2,3,…,25}而言，可以在該集合上進行模加減乘法，但是「模除法」就不是每個元素都能做(必須要有乘法反元素)。而要觀察x是否有乘法反元素，只需考量x是否與模數n互質–>即xy ≡ 1 (mod 26)有y解並求出(使用Extended Euclidean Algorithm)。
Z/26乘法反元素對照表：
整數和其乘法反元素的乘積必定在模 26 下與 1 同餘
有了Z/26乘法反元素對照表，就可以很容易找出加密函數之反函數，即 D(c) = α^-1(c-β) (mod 26)。
總結:
E(m)=α*m+β (mod 26)
D(c) = α^-1(c-β) (mod 26)
加解密範例：
欲將明文 m="affine" 用仿射密碼加密
(金鑰產生)事先協定一把密鑰 K=(3,8)，其中 gcd(3,26)=1。
(加密)使用加密函數E(m)=3*m+8 (mod 26)計算得： m="affine"=(0,5,5,8,13,4) –––––> (8,23,23,6,21,20)="IXXGVU"=c
(解密)使用密文c，使用解密函數D(c)=3^-1(c-8)=9(c-8) (mod 26)計算得： c="IXXGVU"=(8,23,23,6,21,20) ––––––> (0,5,5,8,13,4)="affine"=m
弱點：
因爲仿射密碼仍爲單字母表密碼, 其依舊保留了該類別加密之弱點。當α=1，仿射加密為凱撒加密，因為加密方程可簡化為線性移動。 在小於26之數中有12數與26互質，因此共有 12*26=312可能之關鍵值。 因為密碼缺少複雜性，這套系統是不安全的。
[古典密碼學](https://hackmd.io/@HuangPX/ryT2y54dY)
[密碼卷宗 數論篇 ](https://ithelp.ithome.com.tw/articles/10224347)
### 03 仿射密碼-1
>求 GCD
### 04 仿射密碼-2
>在前面一道題目我們實作了求兩數是否互質，在這一題中呢我們要嘗試著完成求乘法反元素，也就是實作擴展歐幾里德演算法。
### 05 仿射密碼-3
>我們前面實作了判斷是否互質、以及找出乘法反元素，接下來讓我們實作加密函數吧！
### 06 仿射密碼-4
> 在這道題目中請你完成仿射密碼的解密的部分
### 07 仿射密碼-final
> 到這邊恭喜你完成了整個仿射密碼的加解密過程，現在你必須撰寫一個完整的程式，包含前面的所有功能，讓使用者能夠進行加解密的動作。
### 08 CPE 033 UVa10235 Simply Emirp
>反轉跟找質數都有寫過，組合起來即可
### 09 CPE 028 UVa10931 Parity
### 10 CPE 016 UVa10056 What is the Probability
Sign in with Wallet
Connect another wallet