技巧

看觀念題的方法

斐波那契數列 0 1 1 2 3 5 ...

int a = 0; b = 1; c = 0;
for (int i = 0; i < n; i++) {
    c = a + b;
    a = b;
    b = c;
}
c 會等於 第n個 斐波那契數列 的的值
/* -------------------------------------------------------------------------- */
int f(int n) {
    if (n == 0) return 0;
    if (n == 1) return 1;
    return f(n - 1) + f(n - 2);
}
f(n) 等於 第n個 斐波那契數列 的的值

排列

int f(int n, int k) {
    if (k == 0)
        return 1; 
    else if (k == 1)
        return n;  
    else
        return n * p(n - 1, k - 1);
}
f(5, 4) 會等於 n!/(n-k)!

組合

int f(int n, int k) {
    if (k == 0 || k == n)
        return 1;
    return c(n - 1, k - 1) + c(n - 1, k);
}
f(5,3) 會等於 n!/k!(n-k)!

求和

int c = 0;
for (int i = 1; i <= n; i++) {
    c += i;
}
c = [n(n+1)]/2

平方和

int c = 0;
for (int i = 1; i <= n; i++) {
    c += i*i;
}
c = [n(n+1)(2n+1)]/6

階乘

int c = 1;
for (int i = 1; i <= n; i++) {
    c *= i;
}

泡沫排序

for (int i = 0; i < n - 1; i++) {
    for (int j = 0; j < n - i - 1; j++) {
        if (arr[j] > arr[j + 1]) {
            int temp = arr[j];
            arr[j] = arr[j + 1];
            arr[j + 1] = temp;
        }
    }
}
/* -------------------------------------------------------------------------- */
for (int i = 0; i < n - 1; i++) {
    for (int j = i; j < n - 1; j++) {
        if (arr[j] > arr[j + 1]) {
            int temp = arr[j];
            arr[j] = arr[j + 1];
            arr[j + 1] = temp;
        }
    }
}
/* -------------------------------------------------------------------------- */
arr[j] > arr[j + 1] 小~大
arr[j] < arr[j + 1] 大~小

選擇排序

void f(int a[], int n) {
    int t;
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            if (a[i] < a[j]) {
                t = a[i];
                a[i] = a[j];
                a[j] = t;
            }
        }
    }
}
arr[i] < arr[j] 大~小
arr[i] > arr[j] 小~大

交換變數

a = a * b;
b = a / b; 
a = a / b;
/* -------------------------------------------------------------------------- */
a = a ^ b;
b = a ^ b;
a = a ^ b;
/* -------------------------------------------------------------------------- */
temp = a;
a = b;
b = temp;

河內塔

void f(int n, int a, int b, int c) {
    if (n == 1) {
        return;
    }
    f(n - 1, a, c, b);
    f(n - 1, b, a, c);
}

左直角三角形

main.cpp

for (int i = 1; i <= n; ++i) {
    for (int j = 1; j <= i; ++j) {
        cout << "*";
    }
    cout << endl;
}

graph

*
**
***
****
*****

右直角三角形

main.cpp

for (int i = 1; i <= n; ++i) {
    for (int j = 1; j <= n - i; ++j) {
        cout << " ";
    }
    for (int j = 1; j <= i; ++j) {
        cout << "*";
    }
    cout << endl;
}

graph

    *
   **
  ***
 ****
*****

等腰三角形

main.cpp

for (int i = 1; i <= n; ++i) {
    for (int j = 1; j <= n - i; ++j) {
        cout << " ";
    }
    for (int j = 1; j <= 2 * i - 1; ++j) {
        cout << "*";
    }
    cout << endl;
}

graph

    *
   ***
  *****
 *******
*********

倒等腰三角形

main.cpp

for (int i = 1; i <= n; ++i) {
    for (int j = 1; j <= n - i; ++j) {
        cout << " ";
    }
    for (int j = 1; j <= 2 * i - 1; ++j) {
        if (j == 1 || j == 2 * i - 1 || i == n) {
            cout << "*";
        } else {
            cout << " ";
        }
    }
    cout << endl;
}

graph

    *
   * *
  *   *
 *     *
*********

輾轉相除法

int gcd(int a, int b) {
    while (b != 0) {
        int temp = b;
        b = a % b;
        a = temp;
    }
    return a;
}
//-----------------------
int gcd(int a, int b) {
    if (b == 0) return a;
    return gcd(b, a % b);
}

帕斯卡三角形

int pas[6] = {1};
for(int i=0; i<6; i++) {
        int prev=0; // 用來暫存上一個元素
        for(int j=0; j<=i; j++) { 
            int tmp = pas[j]; 
            pas[j] = prev + pas[j];
            prev = tmp;
        }
}