# HW03 參考答案
## 3.1 Circle Functions
Credit: 41247006S 張呈義
```c=
#include <stdio.h>
#include <stdint.h>
#include <math.h>
static double radius = -1.0;
static uint8_t is_radius_set = 0;
int32_t set_radius( double r){
if(r <= 0)
return -1;
else{
is_radius_set = 1;
radius = r;
return 0;
}
}
double get_circle_circumference(){
if(is_radius_set)
return (double) 2 * radius * M_PI;
else
return -1.0;
}
double get_circle_area(){
if(is_radius_set)
return (double) radius * radius * M_PI;
else
return -1.0;
}
double get_tangent_area( double x ){
double y = 0, m_point = 0, m_tangent = 0, b = 0;
double area = 0;
x = fabs(x); //fabs: absolute value for double
if((x >= radius))
return -1;
if(is_radius_set){
y = sqrt(radius*radius - x*x);
m_point = y / fabs(x);
m_tangent = -(1 / m_point);
//tangent: y = m_tangent*x + b;
b = y - m_tangent*x;
area = fabs(b) * fabs(-b / m_tangent) / 2;
if(m_tangent == 0)
return -1;
return area;
}
else
return -1;
}
double get_inner_regular_polygon_area( int32_t n ){
if(n < 3)
return -1;
long double alpha = (2*M_PI) / (long double) n;//the angles of split triangles;
long double area = 0;
if(is_radius_set){
area = n * (radius * radius * sin(alpha)) / 2;
return (double) area;
}
else
return -1;
}
double get_outer_regular_polygon_area( int32_t n ){
if(n < 3)
return -1;
long double alpha = (2*M_PI) / (long double) n, beta = alpha / 2;
long double side = 0, area = 0;
//the angles of split triangles; beta = alpha / 2.
if(is_radius_set){
side = radius / (cos(beta));
area = n * (side * side * sin(alpha)) / 2;
return (double) area;
}
else
return -1;
}
```
## 3.2 Control Game Character
mycontrol.h
```c=
#pragma once
#include <stdio.h>
#include <stdint.h>
#include <stdbool.h>
#include <math.h>
// Setup the initial position to (x,y) and the moving direction.
// a is the angle counterclockwise from x axis.
void initialize( double x, double y, double a);
// From the current , move forward length with the givendirection.
// If the initial position is not set, return -1.
int32_t forward( double length );
// From the current direction , turn clockwise/counterclockwisex.
// If the initial position is not set, return -1.
int32_t clock_turn( double x );
int32_t counterclock_turn( double x );
// Print the current location and the direction.
// The print format is "position: (x,y), angle: a".
// a is the angle counterclockwise from x axis and 0 <= a <= 2 pi
// If the initial position is not set, return -1.
int32_t print();
```
mycontrol.c
```c=
#include "mycontrol.h"
static double character_x, character_y, character_a;
static bool initialized = false;
void initialize( double x, double y, double a) {
character_x = x;
character_y = y;
character_a = a;
initialized = true;
}
int32_t forward( double length ) {
if (!initialized) {
return -1;
}
character_x += length * cos(character_a);
character_y += length * sin(character_a);
return 0;
}
int32_t clock_turn( double x ) {
if (!initialized) {
return -1;
}
character_a -= x;
return 0;
}
int32_t counterclock_turn( double x ) {
if (!initialized) {
return -1;
}
character_a += x;
return 0;
}
int32_t print() {
if (!initialized) {
return -1;
}
while (character_a >= 2 * M_PI) {
character_a -= 2 * M_PI;
}
while (character_a < 0) {
character_a += 2 * M_PI;
}
printf("position: (%.2lf,%.2lf), angle: %.2lf\n", round(character_x * 100.0)/100.0, round(character_y * 100.0)/100.0, round(character_a / M_PI * 100.0)/100.0);
return 0;
}
```
## 3.3 Binary Form
Credit: 41247034S 伍Ｏ宇
```c=
#include <stdio.h>
#include <stdint.h>
#include <math.h>
void BinaryForm(int64_t num);
int main(){
int64_t input=0;
printf("Please enter the number: ");
scanf("%ld", &input);
//input error
if(input>2147483647||input<-2147483648){
printf("The input number should be a signed 32-bit integer\n");
return 0;
}
BinaryForm(input);
return 0;
}
void BinaryForm(int64_t num){
if(num<0){
num=4294967296+num;
}
static int64_t digit=32;
int64_t out=0;
if(digit>0){
if(digit%8==0 && digit!=32){
printf(" ");
}
out=num/pow(2,digit-1);
printf("%ld",out);
num%=(int64_t)pow(2,digit-1);
digit--;
BinaryForm(num);
}else{
printf("\n");
return;
}
}
```
## 3.4 Tower of Hanoi
Credit: 41247004S 廖Ｏ翔
```c=
// hw0304.h
#pragma once
#include <stdint.h>
#include <stdio.h>
// from a to b, c is buf
void hanoi(int32_t disk, int8_t a, int8_t b, int8_t c);
```
```c=
// hw0304.c
#include "hw0304.h"
#include <stdint.h>
#include <stdio.h>
int main(int argc, char const *argv[]) {
int32_t disk = 0;
double input = 0;
printf("Please enter the disk number (2-20): ");
scanf("%lf", &input);
if (input - (int)(input) != 0) {
printf("wrong input.\n");
return 1;
}
disk = (int)(input);
if (disk < 2 || disk > 20) {
printf("wrong input.\n");
return 1;
}
hanoi(disk, 1, 2, 3);
return 0;
}
```
```c=
// hw0304-1.c
#include <stdint.h>
#include <stdio.h>
#include "hw0304.h"
void hanoi(int32_t disk, int8_t a, int8_t b, int8_t c) {
/*
| | |
-------
A B C
*/
if (disk == 1) {
printf("move disk %d to rod %d\n", disk, b);
} else {
hanoi(disk - 1, a, c, b);
printf("move disk %d to rod %d\n", disk, b);
hanoi(disk - 1, c, b, a);
}
}
```
```c=
// hw0304-2.c
#include <math.h>
#include <stdint.h>
#include <stdio.h>
#include "hw0304.h"
void hanoi(int32_t disk, int8_t a, int8_t b, int8_t c) {
int32_t disk_p = 0, times = 0, lo2 = 0, number = 0, rod = 0, pow_2_disk = 1 << disk,
breaker = 0, ii = 0;
double count = 0;
for (int32_t i = 1; i < pow_2_disk; i++) {
if (i % 2) {
disk_p = 1;
times = (i + 1) / 2;
} else {
ii = i;
while (ii % 2 != 1) {
ii /= 2;
disk_p++;
}
times = (i + pow(2, disk_p - 1)) / pow(2, disk_p);
}
times = (int)(times) % 3;
if (disk % 2 == 0) {
if (disk_p % 2 == 1) {
if (times % 3 == 1) {
rod = 3;
} else if (times % 3 == 2) {
rod = 2;
} else {
rod = 1;
}
} else {
if (times % 3 == 1) {
rod = 2;
} else if (times % 3 == 2) {
rod = 3;
} else {
rod = 1;
}
}
} else {
if (disk_p % 2 == 1) {
if (times % 3 == 1) {
rod = 2;
} else if (times % 3 == 2) {
rod = 3;
} else {
rod = 1;
}
} else {
if (times % 3 == 1) {
rod = 3;
} else if (times % 3 == 2) {
rod = 2;
} else {
rod = 1;
}
}
}
printf("move disk %d to rod %d\n", disk_p, rod);
}
}
```
```makefile=
# Makefile, relevant-part only
all:
gcc -c hw0304-1.c -o hw0304-1.o
gcc -c hw0304-2.c -o hw0304-2.o
gcc hw0304.c hw0304-1.o -o hw0304-1 -lm
gcc hw0304.c hw0304-2.o -o hw0304-2 -lm
```
## 3.5 How to roll your dice SE (Simple Edition)?
本題有非常多有創意的同學不僅把骰子的程式寫出來，還又寫了超帥的介面或超級好玩的遊戲！
我就不提供解答了，歡迎去 Discord 伺服器分享彼此的程式分享給大家！
某些人的真的超好玩 你們好棒
## 3.6 Bonus: diff and patch
Credit: 41147054S 廖Ｏ嫺
我們可以使用 Linux patch命令來修改或更新文件。具體方式如下：
- 1. 首先可以使用cat指令查看升級文件與原文件之內容，如下：
```bash
$ cat myfile1 #查看myfile1
This is myfile1.
$ cat myfile2 #查看myfile2
This is myfile2.
```
- 2. diff指令在於比較檔案的不同。若兩個檔案的內容相同, diff 指令不會有任何輸出; 如果兩個檔案有不同的地方, diff 便會將不同的行列出，如下：
```bash
$ diff myfile1 myfile2 #比較兩個檔案
1c1
<This is myfile1.
---
>This is myfile2.
```
- 3. 將比較的結果保存至 myfile.patch 文件中，如下：
```bash
$ diff myfile1 myfile2 > myfile.patch #符號 > 表示將
```
該符號左邊的文件內容寫入右邊所指向的文件中，反之亦然。
```bash
$ cat myfile.patch #查看myfile.patch
1c1
<This is myfile1.
---
>This is myfile2.
```
- 4. 將補丁(patch)寫入原文件，如下：
```bash
$ patch -p0 myfile1 myfile.patch
patching file myfile1
```
- 5. 於是乎我們可以得到文件被修改後的內容，如下：
```bash
$ cat myfile1 #查看myfile1
This is myfile2.#此時myfile1已被修改成與myfile2相同的內容
```
## 3.7 Bonus: Plagiarism Detection
Credit: 41044028S 黃Ｏ耘
```
我想用香水來做比喻 code，Moss 就是要抓相似的香水
想象一下，如果老師手裡有一堆學生的 coding 作業，他想知道這些作業里有沒有人是抄襲別人的。但是，如果學生們只是簡單地把別人的 code 複製過來，然後改改變量名或者加點注釋，這樣肉眼看起來 code 就不一樣了，老師很難發現真相。
這時候 Moss 就派上用場了。它不是去看 code 長得像不像，而是通過一種特別的方法來「嗅」code，找出 code 的獨特「味道」。就像是不同的香水即使瓶子換了，味道還是能被辨認出來一樣。
Moss 的做法是這樣的：
* 清潔：首先，Moss 會把 code 里的空格、注釋這些看起來不重要的東西都去掉，就像洗掉香水瓶上的標籤一樣。
* 提取「香味」：然後，它會從剩下的 code 中提取一些特別的標記，這些標記就像是香水的味道成分，可以代表這段 code 的特點。
* 挑選特徵：接下來，Moss 會用一種叫「winnowing」的方法，從這些標記中挑出最能代表 code 特色的幾個，就像是挑選出最有代表性的香味成分。
* 比較：有了這些特徵，Moss 就可以把不同學生的 code 放在一起比較了，看看誰和誰的「香味」特別相似。
* 出結果：最後，Moss 會告訴老師，哪些學生的作業里有類似的「香味」，可能是抄襲的。
這個方法很厲害，因為即使學生們改變了 code 的樣子，Moss 還是能通過這些「香味」成分找到相似之處。但是，如果一個學生把抄來的 code 改得面目全非，或者用一個完全不同的方法來寫相同的功能，Moss 就可能找不到了。就像是如果一個香水的味道成分被改得太多，你就認不出它是不是原來那個香水了。
```
Credit: 60840031S 鄭Ｏ文
```
參考文獻來源：
http://theory.stanford.edu/~aiken/publications/papers/sigmod03.pdf
(1)摘要
此篇文獻敘述關於文件指紋識別技術的應用與重要性，特別是在識別大
量文檔集中的部分複製時，如何精確地識別文件複製的情況，即使是文件的
一小部分也能被檢測出來。
(2)核心檢測概念
K-gram 哈希化: 文檔被分解成 k 個字符長度的子串（k-grams），對於文
檔中的每個 k-gram，使用哈希函數計算出一個哈希值。
選擇性指紋: 算法接下來並不會使用所有的哈希值作為文檔的指紋。而
是通過一種叫做"winnowing"的方法來選取哈希值的子集作為指紋。這個過
程包含了對相鄰哈希值的分析，選取這些值中的最小者，通常是在一個窗口
範圍內最小的哈希值。
保持局部最小值: 在選取指紋的過程中，winnowing 算法會選擇局部範
圍內的最小哈希值。這確保了當文檔發生局部修改時，其指紋的絕大部分仍
然是不變的，這樣就可以容忍一些改動，同時依舊能夠檢測到文檔之間的相
似性。
抗雜訊和冗餘: 由於 winnowing 選取的是局部最小值，因此對於常見的
和無意義的 k-gram（例如頻繁出現的單詞或者空格）不太可能被選為指
紋，這樣可以避免這些普遍存在的元素導致的雜訊。
有效性和效率: 所產生的指紋集合不僅反映了文檔的獨特特徵，而且由
於其節省空間的特性和局部最小化過程，算法是高效的，這使得它特別適合
於大規模的文檔比對工作，例如抄襲檢測。
```
> hash：一般來說會用「雜湊」一詞，但對岸較常用「哈希」
> local：此例會用「局部」一詞，用「本地」比較奇怪
> winnowing：在此為演算法專有名詞，盡量用原文，有些人用了「風選」一詞勉強猜得到
Sign in with Wallet
Connect another wallet