# 程式題

## GCD

int gcd_recursive(int a, int b) {
    return b == 0 ? a : gcd_recursive(b, a % b);
}

int gcd_iterative(int a, int b) {
    while(b != 0) {
        int temp = a;
        a = b;
        b = temp % b;
    }
    return a;
}

int lcm(int a, int b) {
    return a * b / gcd_recursive(a, b);
}

## find prime numbers in a given range

#include <stdio.h>
#include <stdbool.h>

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

bool isPrime6n(int n) {
    /*
    every n can be classified into 6n, 6n + 1, 6n + 2,
    ... 6n + 5, and only 6n + 1 and 6n + 5 is not divisible by
    2 & 3, so we can test whether n is divisible by 2 & 3 first,
    if it does, then it is not prime. Next, test 6n + 1 and 6n + 5, 
    check is n divisible by these two pattern.
    
    (6n + 1)  + 4 = (6n + 5), and (6n + 5)  + 2  = (6n + 1), and so on.
    So the gap is 2, 4, 2, 4, ...
    */
    if(n <= 1) return false;
    if(n == 2) return true;
    if(n == 3) return true;
    
    if(n % 2 == 0) return false;
    if(n % 3 == 0) return false;
    
    for(int i = 5, gap = 2; i * i <= n; i += gap, gap = 6 - gap) {
        if(n % i == 0) return false;
    }
    
    return true;
}

void findPrimeInRange(int a, int b) {
    for(int i = a; i <= b; i++)  {
        if(isPrime(i)) 
            printf("%d ", i);
    }
    printf("\n");
}

int main()
{
    findPrimeInRange(1, 100);
    return 0;
}

## Write a program can round off

寫一個簡單的四捨五入程式, input只會到小數點第一位, 所以要進位到個位數
ex: 5.5=>6, 5.4=>5
一般都會限制不給用if-else, 所以要善用C的型別轉換

int round(float x)
{
    return (int)(x + 0.5);
}

## Write a program to reverse string(char array)

void swap(char *c1, char *c2)
{
    char tmp = ' ';
    
    tmp = *c1;
    *c1 = *c2;
    *c2 = tmp;
}

char *reverse_str(char *str)
{
    const int len = strlen(str);

    for (int i = 0; i < len/2; i++)
        swap(&str[i], &str[len-1-i]);

    return str;
}

## strcpy, strcat, strlen, strcmp

/* strcpy */
void strcpy(char *dest, const char *src)
{
    if (dest == NULL || src == NULL) return;
    
    while (*src != '\0') {
        *dest = *src;
        dest++;
        src++;
    }
}

/* strcat */
void strcat(char *dest, const char *src)
{
    char *p = dest;
    int loc = 0;

    if (dest == NULL || src == NULL) return;

    while(*(p++) != '\0') loc++;
    
    while(*src != '\0') {
        dest[loc] = *src;
        src++;
        loc++;
    }
}

/* strlen */
int strlen(const char *str)
{
    int len = 0;
    while (*str++ != '\0') len++;
    
    return len;
}

/* strcmp */
int strcmp(const char* str1, const char* str2) {
    while(*str1 && *str2 && *str1 == *str2) {
        ++str1;
        ++str2;
    }
    return *str1 - *str2;
}

## 大小寫轉換

大寫轉小寫, 小寫轉大寫
大寫’A’在ascii是65
小寫’a’在ascii是97
兩個差32, 所以也就是說大寫加32就會變小寫, 反之

char convert(char c)
{
    if (c >= 'A' && c <= 'Z')
        return c + 32;
    else if (c >= 'a' && c <= 'z')
        return c - 32;
    else
        return 0;
}

## Sorting

insertion sort, selection sort, bubble sort, quick sort

#include <stdio.h>
#define ARR_LEN 10

void insertion_sort(int *arr, int len) {
    int j;
    for(int i = 1; i < len; i++) {
        j = i - 1;
        int cur = arr[i];
        while(j >= 0 && cur < arr[j]) {
            arr[j + 1] = arr[j];
            j--;
        }
        arr[j + 1] = cur;
    }
}

void selection_sort(int *arr, int len) {
    for(int i = 0; i < len; i++) {
        int min_index = i;
        for(int j = i + 1; j < len; j++) {
            if(arr[j] < arr[min_index]) {
                min_index = j;
            }
        }
        if(min_index != i) {
            int temp = arr[i];
            arr[i] = arr[min_index];
            arr[min_index] = temp;
        }
    }
}

void bubble_sort(int *arr, int len) {
    for(int i = 0; i < len; i++) {
        for(int j = 0; j < len - 1 - i; j++) {
            if(arr[j] > arr[j + 1]) {
                int temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
        }
    }
}

int quick_sort_partition(int *arr, int left, int right) {
    int pivot = arr[right];
    int i = left - 1;
    int temp;
    for(int j = left; j < right; j++) {
        if(arr[j] <= pivot) {
            i++;
            temp = arr[j];
            arr[i] = arr[j];
            arr[j] = temp;
        }
    }
    temp = arr[i + 1];
    arr[i + 1] = pivot;
    arr[right] = temp;
    return i + 1;
}


void quick_sort(int *arr, int left, int right) {
    if(left < right) {
        int mid = quick_sort_partition(arr, left, right);
        quick_sort(arr, left, mid - 1);
        quick_sort(arr, mid + 1, right);
    }
}


int main(void)
{   
    
    int arr[ARR_LEN] = {111, 47, 78, 75, 21, 167, 92, 163, 93, 66};
        
    selection_sort(arr, ARR_LEN);
    // quick_sort(arr, 0, ARR_LEN - 1);
    
    for(int i = 0; i < ARR_LEN; i++) {
        printf("%d ", arr[i]);
    }
    
    return 0;
}