Showing posts with label Algorithm. Show all posts
Showing posts with label Algorithm. Show all posts

2014/03/18

Failure Function & 字串比對

網路上的教學都寫的有夠複雜有夠難懂,只好自己寫一篇。

首先先介紹 Failure Function

它的用途是讓你在比對字串時,知道可以向後跳多少,藉此減少比較次數。
其原理就是利用字串本身有相同的 前綴 跟 後綴 (簡單來說就是有部分一樣的地方),所以移動了這樣的距離後,因為前綴移動到的地方跟後綴一模一樣,所以不用再重複比較,最後只需要比較後面不一樣的地方即可。

中文的教學有看沒有懂,反而英文在 stackoverflow 有一篇文章把算法寫的相當清楚。
http://stackoverflow.com/questions/16125544/kmp-failure-function-calculation

failure function (by definition, this is the length of the longest prefix of the string which is a suffix also)
這定義很重要,知道了這定義就完全明白這是什麼鬼東西。

這時候就可以實際使用別人寫好的字串比對教學程式來驗證自己的想法

http://www.csie.ntnu.edu.tw/~u91029/StringMatching.html

這網站的教學文雖然寫的不太好,但工具很好,在理解 Failure Function 之後,用這工具就會馬上理解字串如何比對了。

2012/12/21

Next Permutation


  1. Find the highest index i such that s[i] < s[i+1]. If no such index exists, the permutation is the last permutation. 
  2. Find the highest index j > i such that s[j] > s[i]. Such a j must exist, since i+1 is such an index. 
  3. Swap s[i] with s[j]. 
  4. Reverse all the order of all of the elements after index i



private void getNext()
{
  int i = N - 1;

  while (Value[i-1] >= Value[i]) i = i-1;


  int j = N;


  while (Value[j-1] <= Value[i-1]) j = j-1;


  swap(i-1, j-1);    // swap values at positions (i-1) and (j-1)


  i++; j = N;


  while (i < j)
  {
    swap(i-1, j-1);
    i++;
    j--;
  }
}

參考資料:
http://stackoverflow.com/questions/1622532/algorithm-to-find-next-greater-permutation-of-a-given-string
http://www.freewebs.com/permute/lexico.html

2012/12/20

使用 N 維陣列實作 Lexicographical Order 排序

98 關務 三等
有 N 份資料,每份資料皆以兩個大寫英文字母標記(例如 AK、TA 等等)。請設計 一 O(N) 時間的演算法,將此組資料依標記的字典順序排序,並請說明此演算法所 需使用的空間。

本題有兩個變相,故宣告一二維陣列 (26x26)

A B .... Z
B
...
Z

讀取資料檔案,遇到對應的資料時,陣列內容值 + 1
最後再依序從陣列第一列開始讀到最後一列輸出遇到大於 0 的位置,即是排序後的結果。

製作陣列可以說是常數的時間複雜度,因為 26 * 26 是算的出來的,只取決於讀進的資料檔大小。

2012/12/16

Recursive & Iterative Way to compute X to the power N - O(LogN)


  • xn/2­·xn/2­ if n is even, or
  • x(n-1)/2·­x(n-1)/2·x, if n is odd.

Recursive:

Recursive-Power(x, n):
  if n == 1
    return x
  if n is even
    y = Recursive-Power(x, n/2)
    return y*y
  else
    y = Recursive-Power(x, (n-1)/2)
    return y*y*x

Iterative:

int powFast(int b, int e) {
    int p = 1;   
    while (e > 0) {
        if(e%2 != 0) {
            p = p*b;  
        } 
        e = e / 2;
        b = b * b;
    }
    return p;
}

Reference:
http://www.catonmat.net/blog/mit-introduction-to-algorithms-part-two/
http://stackoverflow.com/questions/4303046/how-can-i-implement-iterative-version-logn-base-to-power

Successor - Binary Search Tree

在 BST 當中, Successor(X) 代表 比 X 大的下一個數字。
通常可以用來找 Nth smallest  node.

找 X 的 Successor


  1. 如果 X 有右子樹,則找出右子樹中最小值
  2. 如果 X 沒有右子樹,則往 Parent 方向搜尋
  3. 如果 X 是 X->Parent 的右子樹的話,則繼續往 X->Parent->Parent 找
    直到找到X->Parent 為 X->Parent->Parent 的左子樹


 
    // min of right subtree
    if(root->right != NULL) return min(root->right);
 
    // ancestor of node without right subtree
    BST* ancestor = root->parent;
    while(ancestor != NULL && ancestor->right == root)
    {
        root = ancestor;
        ancestor = ancestor->parent;
    }
    return ancestor->data;
}


參考: http://analgorithmaday.blogspot.tw/2011/03/successor-and-predecessorbst.html

2011/07/18

Algorithm to merge sorted arrays

Algorithm to merge sorted arrays

In the article we present an algorithm for merging two sorted arrays. One can learn how to operate with several arrays and master read/write indices. Also, the algorithm has certain applications in practice, for instance in merge sort.

Merge algorithm

Assume, that both arrays are sorted in ascending order and we want resulting array to maintain the same order. Algorithm to merge two arrays A[0..m-1] and B[0..n-1] into an array C[0..m+n-1] is as following:
  1. Introduce read-indices i, j to traverse arrays A and B, accordingly. Introduce write-index k to store position of the first free cell in the resulting array. By default i = j = k = 0.
  2. At each step: if both indices are in range (i < m and j < n), choose minimum of (A[i], B[j]) and write it to C[k]. Otherwise go to step 4.
  3. Increase k and index of the array, algorithm located minimal value at, by one. Repeat step 2.
  4. Copy the rest values from the array, which index is still in range, to the resulting array.

Enhancements

Algorithm could be enhanced in many ways. For instance, it is reasonable to check, if A[m - 1] < B[0]or B[n - 1] < A[0]. In any of those cases, there is no need to do more comparisons. Algorithm could just copy source arrays in the resulting one in the right order. More complicated enhancements may include searching for interleaving parts and run merge algorithm for them only. It could save up much time, when sizes of merged arrays differ in scores of times.

Complexity analysis

Merge algorithm's time complexity is O(n + m). Additionally, it requires O(n + m) additional space to store resulting array.

C++ implementation

// m - size of A
// n - size of B
// size of C array must be equal or greater than
// m + n
void merge(int m, int n, int A[], int B[], int C[]) {
      int i, j, k;
      i = 0;
      j = 0;
      k = 0;
      while (i < m && j < n) {
            if (A[i] <= B[j]) {
                  C[k] = A[i];
                  i++;
            } else {
                  C[k] = B[j];
                  j++;
            }
            k++;
      }
      if (i < m) {
            for (int p = i; p < m; p++) {
                  C[k] = A[p];
                  k++;
            }
      } else {
            for (int p = j; p < n; p++) {
                  C[k] = B[p];
                  k++;
            }
      }
}

單向鏈結串列的反轉


如果鏈結串列如下:
number123456789
namePeter1Peter2Peter3Peter4Peter5Peter6Peter7Peter8Peter9
next
(指標)
指向2號節點
指向3號節點
指向4號節點
指向5號節點
指向6號節點
指向7號節點
指向8號節點
指向9號節點
NULL

改成這樣:
number123456789
namePeter1Peter2Peter3Peter4Peter5Peter6Peter7Peter8Peter9
next
(指標)
NULL
指向1號節點
指向2號節點
指向3號節點
指向4號節點
指向5號節點
指向6號節點
指向7號節點

指向8號節點

做一個反轉,應該如何做??
我們先使用1,2,3號節點的位置,把1號節點的next設為Null.
再把2號的next指向1號節點,
接著使用2,3,4號節點.
再把3號的next指向2號節點,
接著使用3,4,5號節點.
再把4號的next指向3號節點,

接著使用4,5,6號節點.

...........................
接著使用7,8,9號節點.
將8號節點的next指向7號節點,

發現9號節點next是NULL,跳出迴圈.
把9號節點的next指向8號,接著把head(頭指標)指向9號節點,大公告成.
每一次迴圈次需要使用3個節點,把第2個節點的next指向第1個節點,
下一次的第一個節點是這一次的第二個節點,
下一次的第二個節點是這一次的第三個節點.
下一次的第三個節點是這一次的第三個節點的next.

struct node{
    int data;
    struct node *link;
};
void reverse()
{
    struct node *p = first,
                *q = NULL,
                *r;
    while (p != NULL)
    {
        r = q;
        q = p;
        p = p->link;
        q->link = r;
    }
    q = first;
}


參考自

2010/02/03

Going to the Movies

有很多牛,Car有最大重量限制,要如何放最大重量的牛。

用暴力法,每支牛可能放可能不放,所以是2n種可能的組合。
用1 << n 直接求出 2n
用 & 運算子來產生不同的組合,


以牛編號為1 2 3為例,是否能產生所有組合:
先轉成二進位
1 -> 1
2 -> 10
3 -> 011
4 -> 100
5 -> 101
6 -> 110
7 -> 111
與1 << 0 , 1 << 1 ,1 << 2做&運算(分別為001, 010, 100)

1 可以產生 1
2 可以產生 2
3 可以產生 2 1
4 可以產生 3
5 可以產生 3 1
6 可以產生 3 2
7 可以產生 1 2 3


簡單來說因為1~1<< n 就包含了所有集合(000~111)

所以我們將每個組合順序取出之後,便詢問該組合的第一隻牛是否存在、第二隻牛是否存在.....
這就是使用&的用意了,我們使用 1 << j 會逐一產生第一隻牛存在的情況(001)、第二隻牛的存在的情況(010)、第三隻牛存在的情況(100),只要將它與取出的組合做&運算就能求出牛是否存在,存在的話就將重量加入。

例如說組合是110 我們要試探第一隻牛在不在用001,第二隻牛在不在用010,第三隻牛在不在用100

import java.util.Scanner;



public class JAVA {

    

    public static void main(String[] args) {

        

        Scanner sc = new Scanner(System.in);

        

        while(sc.hasNext()) {

            

            int limit = sc.nextInt();

            int cowsCount = sc.nextInt();

            int[] cows = new int[cowsCount];

            

            for(int i = 0; i < cowsCount; i++) {

                cows[i] = sc.nextInt();

            }

    

            int maxWeight = 0;

            int sum = 0;

            

            for(int i = 0; i < (1<<cowsCount); i++) {

                sum = 0;

                for(int j = 0; j < cowsCount; j++) {

                    if(binToDec(Integer.toBinaryString(i & (1<<j))) > 0) {

                        sum += cows[j];

                    }

                }

                if( sum <= limit && sum > maxWeight) maxWeight = sum;

            }

            

            System.out.println(maxWeight);

        }

    }

    

    public static int binToDec(String bin) {

        

        int sum = 0;

        

        for(int i = 0; i < bin.length(); i++) {

            if(bin.charAt(i) == '1') {

                sum += (1<<(bin.length()-i-1));

            }

        }

        

        return sum;

    }

}

2010/02/01

Hartals

計算在N天裡的因罷工而浪費的天數,假日不算。反正就是一個一個比較那天有沒有罷工就對了。

速度雖然比前一個人快一點,但是花的記憶體卻是快五倍...

import java.util.LinkedList;

public class JAVA {
      // 輸入緩衝區 (緩衝空間需要依照題目調整)
      public static byte[] cinbuf = new byte[1024];
     
      // 讀取一個單字 (英文姓名包含空白時請不要用)
      public static String readToken() {
        int offset = 0;
        int bytedata = -1;
        
        try {
          // 略過非單字的字元 '\t','\n','\r',' '
          bytedata = System.in.read();
          while(bytedata==9||bytedata==10||bytedata==13||bytedata==32) {
            bytedata = System.in.read();
          }
     
          // 載入單字的字元
          while(bytedata!=-1) {
            if(bytedata==9||bytedata==10||bytedata==13||bytedata==32) {
              break;
            } else {
              cinbuf[offset++] = (byte)bytedata;
            }
            bytedata = System.in.read();
          }
        } catch(Exception e) {}
        
        if(offset+bytedata==-1) return null; // 串流結束
        return new String(cinbuf,0,offset);
      }
      
      // 讀取一行
      public static String readLine() {
        int offset = 0;
        int bytedata = -1;
        
        try {
          // 載入整行
          bytedata = System.in.read();
          while(bytedata!=-1) {
            if(bytedata==10) {
              break;
            } else {
              cinbuf[offset++] = (byte)bytedata;
            }
            bytedata = System.in.read();
          }
        } catch(Exception e) {}
     
        if(offset+bytedata==-1) return null; // 串流結束
        if(cinbuf[offset-1]=='\r') offset--; // window 要去除 '\r' 字元
        return new String(cinbuf,0,offset);
      }
      
      // 轉成 int 型態 (比 Integer.parseInt() 快)
      public static int parseInt(String s) {
        int i;
        int mul = 10;
        int value = s.charAt(s.length()-1)-48;
        
        for(i=s.length()-2;i>=0;i--) {
          value += (s.charAt(i)-48)*mul;
          mul *= 10;
        }
        
        return value;
      }
      
    public static void main(String[] args) {
        
        int testCase = parseInt(readLine());
        
        for(int i = 0; i < testCase; i++) {
            
            int days = parseInt(readLine());
            
            boolean[] calendar = new boolean[days+1]; 
            
            int parties = parseInt(readLine());
            
            LinkedList<Integer> partiesList = new LinkedList<Integer>();
            
            for(int j = 0; j < parties; j++) {
                Integer tmp = parseInt(readLine());
                partiesList.add(tmp);
            }
            
            // start processing.
            for(int j = 0; j < partiesList.size(); j++) {
            
                int now_party = partiesList.get(j);
                
                if(now_party == 0)
                    continue;
                
                for(int k = 1; k < calendar.length; k++) {
                    if(k % now_party == 0) {
                        calendar[k] = true;
                    }
                }
            }
            
            int count = 0;
            // start counting strike days on non-yasumi day
            for(int j = 1; j < calendar.length; j++) {
                
                if(!isYasumi(j) && calendar[j] == true) {
                    count++;
                }
            }
            
            System.out.println(count);
            
        }
        
    }
    
    public static boolean isYasumi(int day) {
        
        // first day is Sunday 
        if(day == 0)
            return true;
        
        // Sunday
        if(day % 7 == 0)
            return true;
        
        // Saturday
        while(day > 7) {
            day -= 7;
        }
        
        if(day == 6)
            return true;
        
        return false;
    }

}

Steps

計算兩個數字的距離的最短步數,每一步行走距離只能相差1或是相等。

public class JAVA {

      // 輸入緩衝區 (緩衝空間需要依照題目調整)
      public static byte[] cinbuf = new byte[1024];
     
      // 讀取一個單字 (英文姓名包含空白時請不要用)
      public static String readToken() {
        int offset = 0;
        int bytedata = -1;
        
        try {
          // 略過非單字的字元 '\t','\n','\r',' '
          bytedata = System.in.read();
          while(bytedata==9||bytedata==10||bytedata==13||bytedata==32) {
            bytedata = System.in.read();
          }
     
          // 載入單字的字元
          while(bytedata!=-1) {
            if(bytedata==9||bytedata==10||bytedata==13||bytedata==32) {
              break;
            } else {
              cinbuf[offset++] = (byte)bytedata;
            }
            bytedata = System.in.read();
          }
        } catch(Exception e) {}
        
        if(offset+bytedata==-1) return null; // 串流結束
        return new String(cinbuf,0,offset);
      }
      
      // 讀取一行
      public static String readLine() {
        int offset = 0;
        int bytedata = -1;
        
        try {
          // 載入整行
          bytedata = System.in.read();
          while(bytedata!=-1) {
            if(bytedata==10) {
              break;
            } else {
              cinbuf[offset++] = (byte)bytedata;
            }
            bytedata = System.in.read();
          }
        } catch(Exception e) {}
     
        if(offset+bytedata==-1) return null; // 串流結束
        if(cinbuf[offset-1]=='\r') offset--; // window 要去除 '\r' 字元
        return new String(cinbuf,0,offset);
      }
      
    public static void main(String[] args) {
        
        int testCase = parseInt(readLine());
        
        for(int i = 0; i < testCase; i++) {
            int a = parseInt(readToken());
            int b = parseInt(readToken());
            System.out.println(countStep(b-a));
        }
        
    }
    
    public static int countStep(int diff) {
        
        int step = 0;
        
        if(diff == 0)
            return 0;
        
        step = (int)(Math.sqrt(diff));
        
        if(step * step == diff) 
            step = step * 2 - 1;
        else if(step * step + step < diff)
            step = step * 2 + 1;
        else
            step = step * 2;
        
        return step;
    }

}

WERTYU

將鍵盤往左移一格

import java.util.HashMap;

public class JAVA {


      public static byte[] cinbuf = new byte[1024];
      
      public static String readLine() {
        int offset = 0;
        int bytedata = -1;
        
        try {

          bytedata = System.in.read();
          while(bytedata!=-1) {
            if(bytedata==10) {
              break;
            } else {
              cinbuf[offset++] = (byte)bytedata;
            }
            bytedata = System.in.read();
          }
        } catch(Exception e) {}
     
        if(offset+bytedata==-1) return null; 
        if(cinbuf[offset-1]=='\r') offset--; 
        return new String(cinbuf,0,offset);
      }
      
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        
        HashMap<Character, Character> maplist = new HashMap<Character, Character>();
        
        // first row
        maplist.put('1', '`');
        maplist.put('2', '1');
        maplist.put('3', '2');
        maplist.put('4', '3');
        maplist.put('5', '4');
        maplist.put('6', '5');
        maplist.put('7', '6');
        maplist.put('8', '7');
        maplist.put('9', '8');
        maplist.put('0', '9');
        maplist.put('-', '0');
        maplist.put('=', '-');
        
        // second row
        maplist.put('W', 'Q');
        maplist.put('E', 'W');
        maplist.put('R', 'E');
        maplist.put('T', 'R');
        maplist.put('Y', 'T');
        maplist.put('U', 'Y');
        maplist.put('I', 'U');
        maplist.put('O', 'I');
        maplist.put('P', 'O');
        maplist.put('[', 'P');
        maplist.put(']', '[');
        maplist.put('\\', ']');
        
        // third row
        maplist.put('S', 'A');
        maplist.put('D', 'S');
        maplist.put('F', 'D');
        maplist.put('G', 'F');
        maplist.put('H', 'G');
        maplist.put('J', 'H');
        maplist.put('K', 'J');
        maplist.put('L', 'K');
        maplist.put(';', 'L');
        maplist.put('\'', ';');
        
        // forth row
        maplist.put('X', 'Z');
        maplist.put('C', 'X');
        maplist.put('V', 'C');
        maplist.put('B', 'V');
        maplist.put('N', 'B');
        maplist.put('M', 'N');
        maplist.put(',', 'M');
        maplist.put('.', ',');
        maplist.put('/', '.');
        
        // space
        maplist.put(' ', ' ');
        
        String num;
        
        while((num = readLine()) != null) {
                    
            for(int i=0;i<num.length();i++){
                System.out.print(maplist.get(num.charAt(i)));
            }
            
            System.out.println();
        }
    }
}

2010/01/31

Vito's family

讀入陣列,求出中間數後,再逐一跟陣列每個元素相減求和。

import java.util.Arrays;

public class JAVA {
    
      // 輸入緩衝區 (緩衝空間需要依照題目調整)
      public static byte[] cinbuf = new byte[1024];
     
      // 讀取一個單字 (英文姓名包含空白時請不要用)
      public static String readToken() {
        int offset = 0;
        int bytedata = -1;
        
        try {
          // 略過非單字的字元 '\t','\n','\r',' '
          bytedata = System.in.read();
          while(bytedata==9||bytedata==10||bytedata==13||bytedata==32) {
            bytedata = System.in.read();
          }
     
          // 載入單字的字元
          while(bytedata!=-1) {
            if(bytedata==9||bytedata==10||bytedata==13||bytedata==32) {
              break;
            } else {
              cinbuf[offset++] = (byte)bytedata;
            }
            bytedata = System.in.read();
          }
        } catch(Exception e) {}
        
        if(offset+bytedata==-1) return null; // 串流結束
        return new String(cinbuf,0,offset);
      }
      
      // 讀取一行
      public static String readLine() {
        int offset = 0;
        int bytedata = -1;
        
        try {
          // 載入整行
          bytedata = System.in.read();
          while(bytedata!=-1) {
            if(bytedata==10) {
              break;
            } else {
              cinbuf[offset++] = (byte)bytedata;
            }
            bytedata = System.in.read();
          }
        } catch(Exception e) {}
     
        if(offset+bytedata==-1) return null; // 串流結束
        if(cinbuf[offset-1]=='\r') offset--; // window 要去除 '\r' 字元
        return new String(cinbuf,0,offset);
      }
      
      // 轉成 int 型態 (比 Integer.parseInt() 快)
      public static int parseInt(String s) {
        int i;
        int mul = 10;
        int value = s.charAt(s.length()-1)-48;
        
        for(i=s.length()-2;i>=0;i--) {
          value += (s.charAt(i)-48)*mul;
          mul *= 10;
        }
        
        return value;
      }
      
      
    public static void main(String[] args) {
        
        int testCase = parseInt(readLine());
        
        for(int i = 0; i < testCase; i++) {
            
            int size = parseInt(readToken());
            int[] streetArray = new int[size];
            
            for(int j = 0; j < size; j++)
                streetArray[j] = parseInt(readToken());
            
            Arrays.sort(streetArray);
            
            int mid;
            
            
            if(streetArray.length % 2 == 0) // if even
                mid = (streetArray[streetArray.length/2-1] + streetArray[(streetArray.length/2)])/ 2;
            else // if odd
                mid = streetArray[(streetArray.length+1)/2-1];
            
            int d_total = 0;
            
            for(int street : streetArray) {
                d_total += Math.abs(street - mid);
            }
            
            System.out.println(d_total);
        }
    }
}

2010/01/29

p004 LC-Display

為了要方便表示,我們可以先做個約定


/* 
  * LED representation for each number, according to 
  * the following convention:
  *
  *  -0-
  * |   |
  * 2   1
  * |   |
  *  -3-
  * |   |
  * 5   4
  * |   |
  *  -6-
  *
  */


然後建立陣列

char[][] conversionTable = {
          /* 0   1   2   3   4   5   6 */
    /* 0 */{'-','|','|',' ','|','|','-'},   
    /* 1 */{' ','|',' ',' ','|',' ',' '},
    /* 2 */{'-','|',' ','-',' ','|','-'},
    /* 3 */{'-','|',' ','-','|',' ','-'},
    /* 4 */{' ','|','|','-','|',' ',' '},
    /* 5 */{'-',' ','|','-','|',' ','-'},
    /* 6 */{'-',' ','|','-','|','|','-'},
    /* 7 */{'-','|',' ',' ','|',' ',' '},
    /* 8 */{'-','|','|','-','|','|','-'},
    /* 9 */{'-','|','|','-','|',' ','-'},
  };

row分別代表1~9的數字,而0~6就是我們的約定位置。


import java.util.Scanner;

public class JAVA {
   
 public static void main(String[] args) {
  
  Scanner sc = new Scanner(System.in);
  
  char[][] conversionTable = {
          /* 0   1   2   3   4   5   6 */
    /* 0 */{'-','|','|',' ','|','|','-'},   
    /* 1 */{' ','|',' ',' ','|',' ',' '},
    /* 2 */{'-','|',' ','-',' ','|','-'},
    /* 3 */{'-','|',' ','-','|',' ','-'},
    /* 4 */{' ','|','|','-','|',' ',' '},
    /* 5 */{'-',' ','|','-','|',' ','-'},
    /* 6 */{'-',' ','|','-','|','|','-'},
    /* 7 */{'-','|',' ',' ','|',' ',' '},
    /* 8 */{'-','|','|','-','|','|','-'},
    /* 9 */{'-','|','|','-','|',' ','-'},
  };
  
  int i, j, k;
  
  while(sc.hasNext()) {
   
   int s = sc.nextInt();
   
   if(s == 0)
    break;
   
   //String digitNumber = readToken();
   String digitNumber = sc.next();
   int n = digitNumber.length();
 
   int digit;
   
   // display digitNumber in s size
   // Each digit occupies exactly s+2 columns and 2s+3 rows.
   for(i = 0; i < 2*s+3; i++) {
    for(j = 0; j < n; j++) {
     
     digit = digitNumber.charAt(j) - '0';

     /* upper, middle and lower parts */
     if ((i % (s + 1)) == 0) {
      System.out.printf(" ");
      for (k = 0; k < s; k++) {
       System.out.printf("%c", conversionTable[digit][(i / (s + 1)) * 3]);
      }
      System.out.printf(" ");
     }
     
     /* between upper and middle parts */
     if (i > 0 && i < (s + 1)) {
      System.out.printf("%c", conversionTable[digit][2]);
      for (k = 0; k < s; k++) {
       System.out.printf(" ");
      }
      System.out.printf("%c", conversionTable[digit][1]);
     }

     
     /* between middle and lower parts */
     if (i > (s + 1) && i < (2*s + 2)) {
      System.out.printf("%c", conversionTable[digit][5]);
      for (k = 0; k < s; k++) {
       System.out.printf(" ");
      }
      System.out.printf("%c", conversionTable[digit][4]);
     }
     
     /* if not the last number */
     if (j != n-1)
      System.out.printf(" ");
    }
    System.out.println();
   }
   System.out.println();
   
  }
 }
}
我們注意到幾個地方:
  • 每一個數字都佔有2s+3列跟s+2行(s代表輸入的大小)

    • 整個處理分成三個部份
    • 第一部份是正中間的上中下 i % (s + 1) == 0
    • 第二部份是上跟中的中間 s+1
    • 第三部份是中跟下的中間 2s+2
可以參考下圖~會更瞭解為什麼運算式這樣判斷



    參考資料:http://snippets.dzone.com/posts/show/5244