# HW02 參考答案
## 2.1 $\sqrt{2}$
```c=
#include <stdio.h>
#include <stdint.h>
#include <float.h>
#include <math.h>
int main() {
uint16_t n = 0;
double result = 1.0;
double sq2 = sqrt(2.0);
// printf("Precision of double: %d decimal digits\n", DBL_DIG);
// printf("%.15lf\n", sq2);
printf("Please enter n (16-bits unsigned): ");
scanf("%hu", &n);
for(int32_t i = 1 ; i <= n ; i++){
printf("n = %hu: %.15lf (%.15lf)\n", i, result, result - sq2);
result = 1 + (1/(1+result));
}
}
```
## 2.2 Multiplication v2
```c=
#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
int main() {
int64_t a, b;
printf("Please enter the first number: ");
scanf("%lld", &a);
if (a < 0 || 2147483647 < a) {
printf("Wrong input, your input must between 0 ~ 4294967295.\n");
return 0;
}
printf("Please enter the second number: ");
scanf("%lld", &b);
if (b < 0 || 2147483647 < b) {
printf("Wrong input, your input must between 0 ~ 4294967295.\n");
return 0;
}
uint64_t c = (uint64_t)a * (uint64_t)b;
uint64_t len_a = 0, len_b = 0, len_c = 0;
if (a == 0) {
len_a = 1;
}
for (uint64_t i = 1; i <= a; i *= 10) {
len_a++;
if (i == 10000000000UL) {
if (a / i > 1) {
len_a++;
}
break;
}
}
if (b == 0) {
len_b = 1;
}
for (uint64_t i = 1; i <= b; i *= 10) {
len_b++;
if (i == 10000000000UL) {
if (b / i > 1) {
len_b++;
}
break;
}
}
if (c == 0) {
len_c = 1;
}
for (uint64_t i = 1; i <= c; i *= 10) {
len_c++;
if (i == 10000000000000000000UL) {
if (c / i > 1) {
len_c++;
}
break;
}
}
uint64_t max_len = len_a > len_b ? len_a : len_b;
max_len = max_len > len_c ? max_len : len_c;
// print a
printf(" ");
for (int i = 0; i < max_len - len_a; i++) {
printf(" ");
}
if (a == 0) {
printf("0\n");
} else {
uint64_t div_a = 1, tmp_a = a;
for (int i = 0; i < len_a - 1; i++) {
div_a *= 10;
}
for (int i = 0; i < len_a; i++) {
printf("%lld ", tmp_a / div_a);
tmp_a %= div_a;
div_a /= 10;
}
printf("\n");
}
// print b
printf("*)");
for (int i = 0; i < max_len - len_b; i++) {
printf(" ");
}
if (b == 0) {
printf("0\n");
} else {
uint64_t div_b = 1, tmp_b = b;
for (int i = 0; i < len_b - 1; i++) {
div_b *= 10;
}
for (int i = 0; i < len_b; i++) {
printf("%lld ", tmp_b / div_b);
tmp_b %= div_b;
div_b /= 10;
}
printf("\n");
}
//print line
for (int i = 0; i < max_len * 2 + 1; i++) {
printf("-");
}
printf("\n");
if (len_b != 1 && c != 0) {
uint64_t tmp_b = b;
for (int i = 0; i < len_b; i++) {
uint64_t d = (tmp_b % 10) * a, len_d = 0;
if (d == 0) {
len_d = 1;
} else {
for (uint64_t j = 1; j <= d; j *= 10) {
len_d++;
if (j == 10000000000UL) {
if (d / j > 1) {
len_d++;
}
break;
}
}
}
// print middle
printf(" ");
for (int j = 0; j < max_len - len_d - i; j++) {
printf(" ");
}
uint64_t div_d = 1;
for (int j = 0; j < len_d - 1; j++) {
div_d *= 10;
}
for (int j = 0; j < len_d; j++) {
printf("%lld ", d / div_d);
d %= div_d;
div_d /= 10;
}
printf("\n");
tmp_b /= 10;
}
//print line
for (int i = 0; i < max_len * 2 + 1; i++) {
printf("-");
}
printf("\n");
}
// print c
printf(" ");
for (int i = 0; i < max_len - len_c; i++) {
printf(" ");
}
if (c == 0) {
printf("0\n");
} else {
uint64_t div_c = 1, tmp_c = c;
for (int i = 0; i < len_c - 1; i++) {
div_c *= 10;
}
for (int i = 0; i < len_c; i++) {
printf("%lld ", tmp_c / div_c);
tmp_c %= div_c;
div_c /= 10;
}
printf("\n");
}
return 0;
}
```
## 2.3 Non-deterministic Finite State Machine
:::spoiler 簡單的解答
```c
#include <inttypes.h>
#include <stdbool.h>
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
#define ever (;;) // 無窮迴圈的巧妙寫法
int main() {
// 定義各狀態變數
bool S0_active = true, S1_active = false, S2_active = false, S3_active = false,
S4_active = false, S5_active = false, S6_active = false;
// 定義各狀態的下一個狀態變數
bool next_S0_active, next_S1_active, next_S2_active, next_S3_active, next_S4_active,
next_S5_active, next_S6_active;
int64_t input; // 輸入整數
bool is_even; // 判斷輸入是否為偶數
int8_t remaining; // 紀錄尚有幾個最終狀態未輸出
// 無窮迴圈
for ever {
printf("Please enter an integer: ");
scanf("%" SCNd64, &input);
// 若輸入為 0，則跳出迴圈
if (input == 0) {
break;
}
// 初始化各狀態的下一個狀態為 false
next_S0_active = false;
next_S1_active = false;
next_S2_active = false;
next_S3_active = false;
next_S4_active = false;
next_S5_active = false;
next_S6_active = false;
is_even = input % 2 == 0; // 判斷輸入是否為偶數
// 根據各狀態當前是否存在和輸入奇偶性，計算下一個狀態
// 下一個狀態存儲在 next_Sx_active 變數中
if (S0_active) {
if (is_even) {
next_S3_active = true;
} else {
next_S1_active = true;
next_S2_active = true;
}
}
if (S1_active) {
if (is_even) {
next_S4_active = true;
} else {
next_S2_active = true;
}
}
if (S2_active) {
if (is_even) {
next_S5_active = true;
} else {
next_S3_active = true;
}
}
if (S3_active) {
if (is_even) {
next_S0_active = true;
} else {
next_S5_active = true;
}
}
if (S4_active) {
if (is_even) {
next_S2_active = true;
next_S6_active = true;
} else {
next_S5_active = true;
}
}
if (S5_active) {
if (is_even) {
next_S0_active = true;
} else {
next_S6_active = true;
}
}
if (S6_active) {
if (is_even) {
next_S1_active = true;
} else {
next_S6_active = true;
}
}
// 更新狀態
S0_active = next_S0_active;
S1_active = next_S1_active;
S2_active = next_S2_active;
S3_active = next_S3_active;
S4_active = next_S4_active;
S5_active = next_S5_active;
S6_active = next_S6_active;
}
// 計算共有幾個最終狀態
remaining = S0_active + S1_active + S2_active + S3_active + S4_active + S5_active + S6_active;
// 輸出所有可能的狀態
printf("Possible States: ");
if (S0_active) {
printf("S0");
--remaining >= 1 && printf(", ");
}
if (S1_active) {
printf("S1");
--remaining >= 1 && printf(", ");
}
if (S2_active) {
printf("S2");
--remaining >= 1 && printf(", ");
}
if (S3_active) {
printf("S3");
--remaining >= 1 && printf(", ");
}
if (S4_active) {
printf("S4");
--remaining >= 1 && printf(", ");
}
if (S5_active) {
printf("S5");
--remaining >= 1 && printf(", ");
}
if (S6_active) {
printf("S6");
--remaining >= 1 && printf(", ");
}
printf("\n");
return EXIT_SUCCESS;
}
```
:::
:::spoiler 三成就解答（Credit: 41247006S 張Ｏ義）
```c
#include <stdint.h>
#include <stdio.h>
uint8_t state = 0b00000001; // 0000 0001, from left to right: non_define, S6 ~ S0
// initial state: S0
uint8_t state_trans(uint8_t);
uint64_t odd = 0b01000000010000000010000000100000000010000000010000000110;
// S6~S0 0100 0000 /0100 0000 /0010 0000 /0010 0000 /0000 1000 /0000 0100 /0000 0110
uint64_t even = 0b00000010000000010100010000000001001000000001000000001000;
// S6~S0 0000 0010 /0000 0001 /0100 0100 /0000 0001 /0010 0000 /0001 0000 /0000 1000
int main() {
int64_t n = 1;
while (n != 0) {
printf("Please enter an integer: ");
scanf("%ld", &n);
if (n != 0) state = state_trans(n % 2);
}
printf("Possible States:");
for (uint16_t i = 1, j = 0; j < 7; i <<= 1, j++) {
if (state & i) {
if (n != 0) printf(",");
printf(" S%d ", j);
n = 1;
}
}
printf("\n");
// printf("Debug: state = %d\n",state);
return 0;
}
uint8_t state_trans(uint8_t k) {
// k = 0: n is even
// k = 1: n is odd
uint8_t result = 0;
if (k) {
for (uint8_t i = 1, j = 0; j < 7; i <<= 1, j++)
if (state & i) result |= (odd >> j * 8);
} else {
for (uint8_t i = 1, j = 0; j < 7; i <<= 1, j++)
if (state & i) result |= (even >> j * 8);
}
return result;
}
```
:::
:::spoiler 很好理解的成就二解答（Credit: 41009035E 戴Ｏ彩）
```c
#include <stdint.h>
#include <stdio.h>
#define CHECK_BIT(var, pos) (((var) >> (pos)) & 1) // check bit: read number is 1 or not
uint8_t stateMachineStatus = 0b00000001; // binary
uint8_t s0 = 0b00000001; // 0th bit 1 as S0 state
uint8_t s1 = 0b00000010; // 1st bit 1 as S1 state
uint8_t s2 = 0b00000100; // 2nd bit 1 as S2 state
uint8_t s3 = 0b00001000; // 3rd bit 1 as S3 state
uint8_t s4 = 0b00010000; // 4th bit 1 as S4 state
uint8_t s5 = 0b00100000; // 5th bit 1 as S5 state
uint8_t s6 = 0b01000000; // 6th bit 1 as S6 state
void MoveToNextState(int num);
int main() {
int32_t num;
while (1) {
printf("Please enter an integer: ");
scanf("%d", &num);
if (num == 0) {
int count = 0;
printf("Possible States: ");
for (int i = 0; i < 7; i++) {
if (CHECK_BIT(stateMachineStatus, i)) {
if (count > 0) {
printf(", S%d", i);
} else {
printf("S%d", i);
}
count = count + 1;
}
}
printf("\n");
break;
} else {
MoveToNextState(num);
}
}
return 0;
}
void MoveToNextState(int num) {
uint8_t stateMachineStatusChange = 0;
if (CHECK_BIT(stateMachineStatus, 0)) // S0
{
if ((num % 2) == 0) // even Number
{
stateMachineStatusChange = stateMachineStatusChange | s3;
} else // odd number
{
stateMachineStatusChange = stateMachineStatusChange | s1;
stateMachineStatusChange = stateMachineStatusChange | s2;
}
}
if (CHECK_BIT(stateMachineStatus, 1)) // S1
{
if ((num % 2) == 0) {
stateMachineStatusChange = stateMachineStatusChange | s4;
} else {
stateMachineStatusChange = stateMachineStatusChange | s2;
}
}
if (CHECK_BIT(stateMachineStatus, 2)) // S2
{
if ((num % 2) == 0) {
stateMachineStatusChange = stateMachineStatusChange | s5;
} else {
stateMachineStatusChange = stateMachineStatusChange | s3;
}
}
if (CHECK_BIT(stateMachineStatus, 3)) // S3
{
if ((num % 2) == 0) {
stateMachineStatusChange = stateMachineStatusChange | s0;
} else {
stateMachineStatusChange = stateMachineStatusChange | s5;
}
}
if (CHECK_BIT(stateMachineStatus, 4)) // S4
{
if ((num % 2) == 0) {
stateMachineStatusChange = stateMachineStatusChange | s6;
stateMachineStatusChange = stateMachineStatusChange | s2;
} else {
stateMachineStatusChange = stateMachineStatusChange | s5;
}
}
if (CHECK_BIT(stateMachineStatus, 5)) // S5
{
if ((num % 2) == 0) {
stateMachineStatusChange = stateMachineStatusChange | s0;
} else {
stateMachineStatusChange = stateMachineStatusChange | s6;
}
}
if (CHECK_BIT(stateMachineStatus, 6)) // S6
{
if ((num % 2) == 0) {
stateMachineStatusChange = stateMachineStatusChange | s1;
} else {
stateMachineStatusChange = stateMachineStatusChange | s6;
}
}
stateMachineStatus = stateMachineStatusChange;
}
```
:::
## 2.4 Dollar Cost Averaging Calculator
Credit: 41247004S 廖Ｏ翔
```c
#include <stdio.h>
#include <stdint.h>
int32_t rounded(int32_t rate)
{
if(rate%10 < 5)
return rate/10;
else
return (rate/10)+1;
}
int32_t int_judge(double input)
{
if (input-(int32_t)(input) > 0)
return 1;
else
return 0;
}
int main(int argc, char const *argv[])
{
double i_investment = 0, monthly_investment = -1, s_month = 0, s_year = 0, e_month = 0, e_year = 0;
double initial_investment = 0, y_rate = 0, m_rate = 0;
printf("Initial Investment:\t\t");
scanf("%lf", &i_investment);
if (int_judge(i_investment))
{
printf("Error: please enter a integer.\n");
return 11;
}
if (i_investment < 1 || i_investment > 10000000)
{
printf("Error: please enter a integer for Initial Investment between 1~10000000\n");
return 1;
}
initial_investment = i_investment;
printf("Recurring Monthly Investment:\t");
scanf("%lf", &monthly_investment);
if (int_judge(monthly_investment))
{
printf("Error: please enter a integer.\n");
return 11;
}
if (monthly_investment < 0 || monthly_investment > 10000000)
{
printf("Error: please enter enter a integer for Recurring Monthly Investment between 0~10000000\n");
return 1;
}
printf("Start Month:\t\t\t");
scanf("%lf", &s_month);
if (int_judge(s_month))
{
printf("Error: please enter a integer.\n");
return 11;
}
if (s_month < 1 || s_month > 12)
{
printf("Error: please enter enter a integer for Start Month between 1~12\n");
return 1;
}
printf("Start Year:\t\t\t");
scanf("%lf", &s_year);
if (int_judge(s_year))
{
printf("Error: please enter a integer.\n");
return 11;
}
if (s_year < 1 || s_year > 10000)
{
printf("Error: please enter enter a integer for Start Year between 1~10000\n");
return 1;
}
printf("End Month:\t\t\t");
scanf("%lf", &e_month);
if (int_judge(e_month))
{
printf("Error: please enter a integer.\n");
return 11;
}
if (e_month < 1 || e_month > 12)
{
printf("Error: please enter enter a integer for End Month between 1~12\n");
return 1;
}
printf("End Year:\t\t\t");
scanf("%lf", &e_year);
if (int_judge(e_year))
{
printf("Error: please enter a integer.\n");
return 11;
}
if (e_year < 1 || e_year > 10000)
{
printf("Error: please enter enter a integer for End Year between 1~10000\n");
return 1;
}
printf("Annual Rate of Return (%%):\t");
scanf("%lf", &y_rate);
if (int_judge(y_rate))
{
printf("Error: please enter a integer.\n");
return 11;
}
if (y_rate < 1 || y_rate > 100)
{
printf("Error: please enter enter a integer for Annual Rate of Return between 1~10000000\n");
return 1;
}
if (e_year-s_year < 0 || (e_year-s_year == 0 && e_month-s_month <= 0) )
{
printf("Error: Time range must larger than a month.\n");
return 1;
}
m_rate = (y_rate/12)/100;
// printf("%lf\n", m_rate);
printf("--- Output ---\n");
double total = initial_investment, investment = initial_investment;
int32_t month = s_month;
for (int32_t year = s_year; year <= e_year; year++)
{
for (; month <= 12; month++)
{
int32_t rate = (int32_t)(((total-initial_investment)/total)*100000);
rate = rounded(rate);
printf("%d.", year);
if (month < 10)
printf("0");
if (initial_investment < 1000000000000000 && total < 1000000000000000)
if (rate%10 > 0 )
printf("%d) %.0lf/%.0lf/%.0lf/%.2lf%%\n", month, initial_investment, total, total-initial_investment, rate/100.0);
else if (rate % 100 > 0)
printf("%d) %.0lf/%.0lf/%.0lf/%.0lf.%.0lf%%\n", month, initial_investment, total, total-initial_investment, (double)(rate/100), (double)(rate%100)/10);
else
printf("%d) %.0lf/%.0lf/%.0lf/%.0lf%%\n", month, initial_investment, total, total-initial_investment, (double)(rate/100));
else
printf("%d) */*/*/*%%\n", month);
if (year == e_year && month == e_month-1)
{
break;
}
investment = total*(1+m_rate);
total = investment + monthly_investment;
initial_investment += monthly_investment;
}
month = 1;
}
return 0;
}
```
## 2.5 Catan Simple Islands Engine
```c=
#include <stdio.h>
#include <stdint.h>
#include <stdbool.h>
int main(){
int32_t L = 0;
int32_t N = 0;
printf("Please input the length: ");
scanf("%d", &L);
printf("Please input the number of layer: ");
scanf("%d", &N);
uint64_t max_width = (2*N-1)*(2*L-2)+L;
if(max_width > 80){
printf("Error\n");
return 0;
}
// upper
for(int32_t outi = 1; outi <= 2*N-1; outi ++){
int32_t outj = outi;
for(int32_t inni = 0; inni < L-1; inni ++){
int32_t base = 1+(N-outi)*(2*L-2);
for(int32_t j = 0; j < base; j ++){
printf(" ");
}
for(int32_t innj = base; innj < base+outj*(4*L-4); innj ++){
if(innj < 0 || innj >= max_width){
continue;
}
int32_t basej = (innj - base)%(4*L-4);
int32_t basei = inni;
bool left_slope = basei+basej==(L-2), mid_line = (basei==0 && basej >= L-2 && basej <= L-2+L-1 ), right_slope = basej-basei==2*L-3;
if(left_slope + mid_line + right_slope >= 2){
printf("*");
}else if(left_slope){
printf("/");
}else if(mid_line){
printf("-");
}else if(right_slope){
printf("\\");
}else{
printf(" ");
}
}
printf("\n");
}
}
// middle
if(N%2==0) {
for(int32_t i = 0; i < L - 1; i++) {
printf(" ");
}
printf("*");
for(int32_t i = 0; i < L - 2; i++) {
printf("-");
}
}
printf("*");
for(int32_t i = 0; i < (N - 1) / 2 * 2; i++) {
for(int32_t j = 0; j < 3 * L - 4; j++) {
printf(" ");
}
printf("*");
for(int32_t j = 0; j < L - 2; j++) {
printf("-");
}
printf("*");
}
for(int32_t j = 0; j < 3 * L - 4; j++) {
printf(" ");
}
printf("*");
if(N%2==0) {
for(int32_t i = 0; i < L - 2; i++) {
printf("-");
}
printf("*");
}
printf("\n");
// lower
for(int32_t outi = 2*N-1; outi >= 1; outi --){
int32_t outj = outi;
for(int32_t inni = 0; inni < L-1; inni ++){
int32_t base = 1+(N-outi)*(2*L-2);
for(int32_t j = 0; j < base; j ++){
printf(" ");
}
for(int32_t innj = base; innj < base+outj*(4*L-4); innj ++){
if(innj < 0 || innj >= max_width){
continue;
}
int32_t basej = (innj - base)%(4*L-4);
int32_t basei = (L-2)-inni;
bool right_slope = basei+basej==(L-2), mid_line = (basei==0 && basej >= L-2 && basej <= L-2+L-1 ), left_slope = basej-basei==2*L-3;
if(left_slope + mid_line + right_slope >= 2){
printf("*");
}else if(left_slope){
printf("/");
}else if(mid_line){
printf("-");
}else if(right_slope){
printf("\\");
}else{
printf(" ");
}
}
printf("\n");
}
}
}
```
## 2.6 Bonus: What Happens??
在不同類型的型別進行加法運算時，會依據其 rank 較高者先進行轉型，rank 高低如下，以下只列出整數型別部分
1. 記憶體儲存較大者 rank 較高，如 int32_t > uint16_t
2. 在相同記憶體大小情況下，unsigned 者較高，如 uint32_t > int32_t
而在 ui + si 進行運算時， ui(uint32_t) rank > si(int32_t) rank，因此 si 會被轉型為 uint32_t，但由於 -1 無法被 uint32_t 表示，因此會透過重複加或是減「新型別的最大值+1」，直到數字可以存入新型別中。所以 si 變成 (-1) + (4294967295 + 1) = 4294967295 ，因此最終的加法為 0 + 4294967295 = 4294967295
而同理，在進行 us + si 時，us(uint16_t) rank < si(int32_t) rank，因此 us 會被轉型為 int32_t，而 0 可以在 int32_t 被直接表示，所以最終加法會去 0 + (-1) = -1
Sign in with Wallet
Connect another wallet