Math

[thezu-twt]

Factorial 階層

1. write down a non-recursive algorithm or code for n!

int Fac (int n)
{
 if (n==0) return 1;
 else //n>0
   {
     int s=1 ; i;
     for ( i=1; i<=n; i++)
       s=s*i;
       return s;
   }
}

2. write a recursive algorithm or code

def: n!=1, if (n=0) //初值，終止條件 n!=(n-1)!*n, if(n>0)

int Fac (int n)
{
  if (n==0) return 1;
  else //n>0
    return Fac (n-1) * n;
}

[thezu-twt]

Summation 總和

sum(n) = 1+2+3+…+n sum(0)=0

int sum (int n)
{
  if (n==0) return 0;
  else return sum (n-1) + n;
}

[thezu-twt]

Fibonacci Number 費氏數列

F(n) = 0, if n=0 = 1, if n=1 = F(n-1) + F(n-2), if n>1

int F(int n)
{
  int A[n+1];
  A[0]=0;
  A[1]=1;
  if (n==0) return A[0];
  else if (n==1) return A[1];
  else
  {
    for (int i=2; i<=n; i++;)
      A[i] = A[i-1] + A[i-2];
    return A[n];
  }
}

[thezu-twt]

Binomial Coefficent 二項式係數

(n, m) = 1, if n=m或m=0 = (n-1, m)+(n-1, m-1), otherwise

int Bin( int n, int m)
{
  if ( n==m || m==0 ) return 1;
  else return Bin(n-1, m) + Bin(n-1, m-1);
}

[thezu-twt]

Greatest Common Divisor 最大公因數

GCD(A,B) = B, if (A mod B)=0 = GCD(B, A mod B), otherwise

int GCD(int A, int B)
{
if ((A%B)==0 return B;
else GCD(B, (A%B));
}

[thezu-twt]

Ackerman’s Function

A(m, n) = n+1 ,if m=0 = A(m-1, 1), if n=0 = A(m-1, A(m, n-1)), otherwise

int A (int m, int n)
{
  if (m==0) return (n+1);
  else if (n==0) return A(m-1, 1);
  else return A(m-1, A(m, n-1));
  }

[thezu-twt]

Towers of Hanoi 河內塔問題

A：起點 B：輔助 C：終點 從A搬(n-1)個盤子到B 從A搬最底部盤子到C 從B搬(n-1)個盤子到C (即B成為起點)

void Hanoi(int n, char A, char B, char C)
{
  if (n==1) printf (“ move disk %d from %c to %c”, n, A, C);
  else
    {
      Hanoi(n-1, A, C, B);
      printf(“ move disk %d from %c to %c”, n, A, C);
      Hanoi(n-1, B, A, C);
    }
}

時間定義： T(n) = T(n-1) + T(1) + T(n-1), and T(1)=1 T(n) = 2*T(n-1) + T(1), T(1)=1 T(n) = 2^n-1, O(2^n)

[thezu-twt]

Permutation 排列組合

n個data輪流當head，其後接(n-1)個data之perm

void Perm (char list[], int i, int n)  //列印 list[i] ~ list[n] 之排列組合
{
  if ( i==n )
    {
      for (j=1; j<=n; j++)
      printf ( list[j] );
    }//列印整個list當時內容
  else // i<n
    {
      for ( j=i;  j<=n; j++ )
        {
          SWAP (list[i], list[j]);     //list[ j ]當head
      Perm (list, i+1, n);          //後面剩下的排列組合 ( i=n 時終止)
      SWAP (list[i], list[j]);     //還原成原list[]內容
        }
     }
}