Greatest Common Divisor (GCD) C++ Source Code

GCD or Greatest Common Divisor, is the number which can divide two or more numbers to zero (without remainder). or from wikipedia like this :

In mathematics, the greatest common divisor (gcd), also known as the greatest common factor (gcf), the greatest common denominator[1], or highest common factor (hcf), of two or more non-zero integers, is the largest positive integer that divides the numbers without a remainder.

At this post, we will discuss three ways to solve the GCD (Greatest Common Divisor) problems. The first, we are going to search each integer number between the lower number to 1, if the number can devide two numbers, that’s the GCD. The second and third way, we use euclidean algorithm which using modulus operation :: GCD(a,b) = GCD(b, a mod b)

Okay, that’s just the preface… let’s get to C++ Source code. First, the header


#include <iostream>

using std::cout;
using std::cin;
using std::endl;

Then we define the function prototype


void swapInteger(int* a, int* b);
int gcdSearch(int a, int b);
int gcdEuclidIterative(int a, int b);
int gcdEuclidRecursive(int a, int b);

The function for swapping two integers is


void swapInteger(int* a, int* b){
     int swap = *a;
     *a = *b;
     *b = swap;
}

Now, the function of searching GCD


int gcdSearch(int a, int b){
    int low = 0;
    if (a < b) low = a;
    else low = b;

    for (int i=low;i>0;i--){
        if (a % i == 0 && b % i == 0)
        return i;
    }
}

Then, finding GCD using Iterative Euclidean Algorithm


int gcdEuclidIterative(int a, int b){
    if (a < b) swapInteger(&a, &b);
    int remainder = a % b;

    while (remainder != 0){
          a = b;
          b = remainder;
          remainder = a % b;
    }
    return b;
}

And the last, using Recursive Euclidean


int gcdEuclidRecursive(int a, int b){
    if (a < b) swapInteger(&a, &b);
    int remainder = a % b;

    if (remainder == 0) return b;
    else return gcdEuclidRecursive(b,remainder);
}

Greedy Activity Selector C Source Code

The details of this problem can be find on my previous post : Greedy Activity Selector Java Source Code

First we must declare the function prototype

void recursiveActivitySelector(int*, int*, int, int, int*);
void greedyActivitySelector(int*, int*, int, int*);

Then here is the Recursive Solution of Greedy Activity Selector

void recursiveActivitySelector(int s[], int f[], int i, int j, int a[]){
     int m = i + 1;
     while (m < j && s[m] < f[i]){
           m = m + 1;
     }
     if (m < j){
           a[m] = 1;
           recursiveActivitySelector(s,f,m,j,a);
     }
}

And the Iterative Solution is

void greedyActivitySelector(int s[], int f[], int len, int a[]){
     int n = len;
     int i = 1;
     for (int m=1;m<n;m++){
         if (s[m] >= f[i]){
            a[m] = 1;
            i = m;
         }
     }
}

For testing the program, you can use main function like this

int main(){
    int a1[] = {1,0,0,0,0,0,0,0,0,0,0};
    int a2[] = {1,0,0,0,0,0,0,0,0,0,0};
    int s[] = {1,3,0,5,3,5,6,8,8,2,12};
    int f[] = {4,5,6,7,8,9,10,11,12,13,14};

    int len = sizeof(s) / sizeof(int);

    recursiveActivitySelector(s, f, 0, len, a1);
    printf("Recursive Solution : ");
    for (int i=0;i<len;i++){
        if (a1[i] == 1)
        printf("%d ",i+1);
    }

    printf("n");

    greedyActivitySelector(s, f, len, a2);
    printf("Iterative Solution : ");
    for (int i=0;i<len;i++){
        if (a2[i] == 1)
        printf("%d ",i+1);
    }

    getch();
}

Greedy Activity Selector Java Source Code

Activity Selector is problem to choose which event will be choosen to get maximum number of event for using the resources (time). Each event has start time and finish time. Two or more event cannot use the resource at the same time.

And here is the recursive and iterative solution pseudocode based on Introduction to Algorithm, 2nd edition

RECURSIVE-ACTIVITY-SELECTOR(s, f, i, j)
1 m ← i + 1
2 while m  < j and sm < fi ▹ Find the first activity in Sij.
3     do m ← m + 1
4 if m < j
5    then return {am} ∪ RECURSIVE-ACTIVITY-SELECTOR(s, f, m, j)
6    else return Ø

GREEDY-ACTIVITY-SELECTOR(s, f)
1 n ← length[s]
2 A ← {a1}
3 i ← 1
4 for m ← 2 to n
5      do if sm ≥ fi
6            then A ← A ∪ {am}
7                 i ← m
8 return A

How about the implementation on java source code…. Let’s check this out

    public static String recursiveActivitySelector(int[] s, int[] f, int i, int j){
        int m = i + 1;
        while (m < j && s[m] < f[i]){
            m = m + 1;
        }
        if (m < j){
            return Integer.toString(m+1) +" "+ recursiveActivitySelector(s, f, m, j);
        }
        else return "";
    }

And the iterative solution is….

    public static String iterativeActivitySelector(int[] s, int[] f){
        String a = "1";
        int i = 0;
        int n = s.length;

        for (int m=1;m<n;m++){
            if (s[m] >= f[i]){
                a = a + " " + (m+1);
                i = m;
            }
        }
        return a;
    }

Okay, that’s it… Try and keep going with your work

Java ResultSet to JTable

How to Show Java ResultSet to JTable?

First, let me write some requirements for this post

  1. mysql-connector-java-5.1.x.jar (as a library for connecting mysql dan java)
  2. Some import
    import java.sql.ResultSet;
    import javax.swing.table.DefaultTableModel;
    

And here is the method

    public static DefaultTableModel ResultSet2TableModel(ResultSet rs){
        try{
                DefaultTableModel dtm = new DefaultTableModel();
                ResultSetMetaData meta = rs.getMetaData();
                int col = meta.getColumnCount();

                rs.last();
                int row = rs.getRow();
                rs.beforeFirst();

                Object[] rowData = new Object[col];
                Object[] colData = new Object[col];

                for (int i=0;i<col;i++){
                    colData[i] = meta.getColumnLabel(i+1);
                }

                dtm.setColumnIdentifiers(colData);

                for (int i=0;i<row;i++){
                    rs.next();
                    for (int j=0;j<col;j++){
                        rowData[j] = rs.getString(j+1);
                    }
                    dtm.addRow(rowData);
                }

                return dtm;
        } catch (Exception ex){
            JOptionPane.showMessageDialog(null, "ResultSet to TableModel Converter : "+ex.getMessage());
            return null;
        }
    }

The return value is DefaultTableModel, you can use it like

ResultSet rs = con.executeQuery(sql);
DefaultTableModel dtm = ResultSet2TableModel(rs);
myJTable.setModel(dtm);

Note : I’m Using

  1. NetBeans IDE 6.7
  2. JDK 7
  3. mysql-connector-java-5.1.6.jar
  4. Windows XP SP3 Operating System

Set JFrame Center Position Java Source Code

This is simple, just make a method like below and pass your JFrame object to the method parameter.

public static void setCenterPos(JFrame frame){
    Dimension screen = Toolkit.getDefaultToolkit().getScreenSize();
    int x = (int) ((screen.getWidth() - frame.getWidth()) / 2);
    int y = (int) ((screen.getHeight() - frame.getHeight()) / 2);
    frame.setLocation(x, y);
}