最大公因數 (輾轉相除法) by c programming

方法一: 當A B 此兩數要找最大公數，最簡單最直覺得就是，哪一個數比較小，
             就開始一直遞減找下去

例一:   40,6所以6比較小 ，然後用6下去除兩數看是否整除，不行則用5 然後4  .....直到2


方法二:輾轉相除法!!!

因為會一直取另外一個數去%另外一數，直到另一數為0
所以只要兩數都大於0則一直轉下去!!!




程式碼:

 #include <stdio.h>
#include <stdlib.h>
int gcd (int a ,int b);
int gcd2 (int a, int b);
int main()
{
    int answer,answer2;

    int num1= 189;
    int num2= 9;

    answer= gcd(num1,num2);
    answer2= gcd2(num1,num2);

    printf("answer: %d \r\n",answer);
    printf("answer2: %d \r\n",answer2);

    return 0;
}

int gcd (int a ,int b)
{
    int d,temp;
    if(a >b)
        temp=b;
    else
        temp=a;


    for(d=temp;!(a%d==0 && b%d==0);d--);

    return d;

}

int gcd2 (int a, int b)
{
    while(a>0 && b>0)
    {
        if(a>b)
            a=a%b;
        else
            b=b%a;
    }

    if(a==0)
        return b;
    else
        return a;
}

Binary Search using C

今天去面試考了binary Search.....

寫了一個recursive version

但是有些語法 錯誤，今天用電腦重新又寫了一個。

intput : array, valuern
output : index (the data index of the array)

note: if not found return -1

#include <stdio.h>
#include <stdlib.h>
#include <math.h>

int BinarySearch (int arr[],int value,int s,int l);

int main (void)
{


    int array1[] ={-5,1,5,30,70,90,98,99};
    int arraysize = sizeof(array1)/sizeof(int);
    int findvalue = 99;
    int findindex = -1;
    int i =0;

    findindex = BinarySearch(array1,findvalue,0,arraysize-1);

    printf("\nSearh index is:");
    printf("%d\n",findindex);

    return 0;
}

int BinarySearch (int arr[],int value,int s,int l)
{
    if(s<=l)
    {
        int i = floor((s+l)/2);

        if(arr[i] == value)
            return i;
        else
            if(arr[i]>value)
                return BinarySearch(arr,value,0,i-1);
            else
                return  BinarySearch(arr,value,i+1,l);

    }
    return -1;
}



以下是Iterative version


int BinarySearchI(int arr[],int value, int l)
{
    int s=0;

    while(s<=l)
    {
        int i = floor((s+l)/2);

        if(arr[i] == value)
            return i;
        else
            if(arr[i]>value)
                l=i-1;
            else
                s=i+1;


    }
    return 0;// not found



}

轉置矩陣 - C array transpose

array transpose

KEY:
1.要多再用一個ARRAY
2. ROW 和 COL 要互換 (因為如果不是方陣的話。)


#include <stdio.h>
#include <stdlib.h>

#define ROW 4
#define COL 5


int main (void)
{
    int i , j;

    int A[ROW][COL];

    int B[COL][ROW];

    for ( i=0;i<ROW;i++)
        for (j=0;j<COL;j++)
            A[i][j]= (rand()%8)+1;




// print the result

    for ( i=0;i<ROW;i++)
    {
        for (j=0;j<COL;j++)
            printf("%d ",A[i][j]);

        printf("\n");
    }


    for( i=0;i<COL;i++)
    {
        for(j=0;j<ROW;j++)
            B[i][j] = A[j][i];
    }

    printf("After reverse \r\n");
    for ( i=0;i<COL;i++)
    {
        for (j=0;j<ROW;j++)
            printf("%d ",B[i][j]);

        printf("\n");
    }


  //  system("pause");
    return 0;
}

alignment

 一開始本來再查甚麼是ABI (Appilcation Binary Interface)
其中有一點是

ABIs cover details such as

• the sizes, layout, and alignment of data types

 有點忘記甚麼叫做alignment所以就花了 一點時間去查一下


 那為什麼會有alignment這個名詞出現呢?

 因為變數再宣告的時候，會配置給他記憶體，但每種大小不一樣，比如說long  64  bit ,int 32bit , cahr 8bit，此時就產生了一個問題，那要怎麼樣塞進記憶體之後要取資料比較方便呢?
一般來說再32-bit的架構上我們一次會讀4個byte的資料出來，所以如果此時資料沒有放好我們會讀很多次才會讀到我們想要的資料，所以就有alignment這個方法的出現。


所以我就仿造我查到的網誌真的動手去試試看


int main (void)
{
    struct ali
    {
        char      x; //1byte
        int       y;//4bytes
        short int z;//2 bytes
    }align_ex;

    printf("align_ex size is %d\n",sizeof(align_ex));
    printf("x size is %d\n",sizeof(align_ex.x));
    printf("y size is %d\n",sizeof(align_ex.y));
    printf("z size is %d\n",sizeof(align_ex.z));

    printf("address of test is %p\n", &align_ex);
    printf("address of x is %p\n",    &align_ex.x);
    printf("address of y is %p\n",    &align_ex.y);
    printf("address of z is %p\n",    &align_ex.z);
}







真的會幫我配置好，只不過會有內部碎裂，看到的專業名詞叫做
:"padding"(幫你insert 空的資料 讓data可以對齊)

如果我改成以下 就會有不一樣的結果，或者順序也會影響記憶體配置

int main (void)
{
    struct ali
    {
        char        x;//1byte
        char        y;//1bytes
        int         z;//4 bytes
    }align_ex;

    printf("align_ex size is %d\n",sizeof(align_ex));
    printf("x size is %d\n",sizeof(align_ex.x));
    printf("y size is %d\n",sizeof(align_ex.y));
    printf("z size is %d\n",sizeof(align_ex.z));

    printf("address of test is %p\n", &align_ex);
    printf("address of x is %p\n",    &align_ex.x);
    printf("address of y is %p\n",    &align_ex.y);
    printf("address of z is %p\n",    &align_ex.z);
}


reference :

1.http://kezeodsnx.pixnet.net/blog/post/27585076-data-structure%E7%9A%84%E5%B0%8D%E9%BD%8A(alignment)

2. http://www.programmer-club.com.tw/ShowSameTitleN/c/38584.html

Insertion Sort (插入排序法)

(一) Concept:
  將第 i 筆 record 插入到前面 (i-1)筆 已經sorting 之list中，形成 i 筆已經排序好的list ie...i=2 to n 共執行 n-1回合。

(二)example:{88,7,87,9,80,100,800,10,5}

(三)每回合變化

 



程式碼:

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

int main (void)
{
    int k;
    int a[] = {88,7,87,9,80,100,800,10,5}; //You change the data what you want to sort
    int array_size = sizeof(a)/sizeof(int);


    printf("start Insertion sort\n");
    InsertionSort(a,array_size);


    printf("Ans is:");
    for(k = 0; k<array_size;k++) //print the result
        printf("%d ",a[k]);


}

void InsertionSort(int data[],int array_size)
{
    int i,j,index,q;
    int counta = 0;
    bool f;

    for(i=1; i< (array_size); i++) //execute the n-1 times
    {
        index = data[i];

        for(j=i;j>0&&data[j-1]>index;j--)//假如後者大於前者則對調
        {
            data[j] = data[j-1];
        }

        data[j] = index;
/*
     // print the every pass
        printf("pass%d ",i);
        for(q=0;q<array_size;q++)
            printf("%d ",data[q]);
        printf("\n");*/


    }

}

Selection sort (選擇排序法)

(一)key idea: 自 i+1 筆 到第 n 筆資料 挑出最小值然後和第i交換

(二)The example:{88,7,87,9,80,100,800,10,5}

(三)每回合變化

 


優點:

適合用在大型記錄之sorting，因為每回和頂多Swap 1次


程式碼

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

int main (void)
{
    int k;
    int a[] = {88,7,87,9,80,100,800,10,5}; //You change the data what you want to sort
    int array_size = sizeof(a)/sizeof(int);


    printf("start selection sort\n");
    SelectionSort(a,array_size);


    printf("Ans is:");
    for(k = 0; k<array_size;k++) //print the result
        printf("%d ",a[k]);


}

void SelectionSort(int data[],int array_size)
{
    int i,j,minmum,q;
    int counta = 0;
    bool f;

    for(i=0; i< (array_size-1); i++) //execute the n-1 times
    {
        minmum = i;

        for(j=i+1;j<array_size;j++) //找出目前最小值在哪裡        {
            if(data[j]<data[minmum])
                minmum = j;
        }

        if(minmum != i )//如果和之前位置一樣就不用交換
            Swap(&data[i],&data[minmum]);

    /* // print the every pass
        printf("pass%d ",i);
        for(q=0;q<array_size;q++)
            printf("%d ",data[q]);
        printf("\n");*/


    }

}

void Swap(int *a, int *b)
{
    int temp = *a;
    *a = *b;
    *b = temp;
}

Bubble Sort 泡沫排序法

1.Time complexity:

worst case: n*n
best cace  :n

2.我一個flag 判斷如果此回合沒有執行 swap則表示sort完畢

code如下:

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

int main (void)
{
    int k;
    int a[] = {88,7,87,9,80,100,800,300,400}; //You change the data what you want to sort
    int array_size = sizeof(a)/sizeof(int);


    printf("start bubble sort\n");
    BubbleSort(a,array_size);

    for(k = 0; k<array_size;k++) //print the result
        printf("a = %d\n",a[k]);


}

void BubbleSort(int data[],int array_size)
{
    int i,j,temp,q;
    int counta = 0;
    bool f;

    for(i=0; i< (array_size-1); i++) //execute the n-1 times
    {
        f = false;

        for(j=0;j<array_size-1-i;j++)
        {
            if(data[j]>data[j+1])
            {
                Swap(&data[j],&data[j+1]);
                f = true;

            }
            counta++;
        }
        /*
        printf("pass%d ",i);
        for(q=0;q<array_size;q++)
            printf("%d ",data[q]);
        printf("\n");
        */
        if(!f)break;
    }

}

void Swap(int *a, int *b)
{
    int temp = *a;
    *a = *b;
    *b = temp;
}


 1.每回合執行如下所示:
 

 2.但如果我拿掉if(!f) break 他會執行完n-1回合
 


這時候就知道演算法的強大了。

call by value VS call by address (傳值VS傳址)

call by value VS call by address


1.call by address



#include <stdio.h>
#include <stdlib.h>

int main()
{
    int x =5;
    int y =30;
    Swap(x,y);
    printf("x:%d,y:%d",x,y);
}

void Swap(int a, int b)
{
    int temp = a;
    a = b;
    b = temp;
}


the result is :
 



 我要把x , y 兩數交換，但似乎沒有達成我的需求   WHY?

 當我執行到 int x =5 ，系統就會立刻分配記憶體空間給變數使用

所以每個變數都會有一個記憶體位址。


執行swap前

	main 中的x	Main 中的y	Swap中的a	Swap中的b
Value	5	30	5	10
Mem_addr	0x7	0x8	0xFF	0xFE

執行swap後

	main 中的x	Main 中的y	Swap中的a	Swap中的b
Value	5	30	10	5
Mem_addr	0x7	0x8	0xFF	0xFE

可以看出來他的確有把兩數交換，但他沒有真的把原始的位址傳入
所以call by vaule 只是把value複製給對方。



2.call by address:


#include <stdio.h>
#include <stdlib.h>

int main()
{
    int x =5;
    int y =30;
    Swap(&x,&y);
    printf("x:%d,y:%d",x,y);
}

void Swap(int *a, int *b)
{
    int temp = *a;
    *a = *b;
    *b = temp;
}
the result is:







1.&:取值運算子   ---就是把變數的位址取出來

2.然而void.......(int *a, .....) 指標 a 指向 x

執行swap前

	main 中的x	Main 中的y	Swap中的a	Swap中的b
Value	5	30	0x7	0x8
Mem_addr	0x7	0x8	0xFF	0xFE

執行swap後

	main 中的x	Main 中的y	Swap中的a	Swap中的b
Value	30	5	0x7	0x8
Mem_addr	0x7	0x8	0xFF	0xFE

reference:http://wp.mlab.tw/?p=176