最大公因數 (輾轉相除法) 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;
}