rakha asyrofi
/
KNN_coba4
mantap jaya
main.cpp@0:3d12bad4186e, 2018-04-15 (annotated)
- Committer:
- asyrofi
- Date:
- Sun Apr 15 04:01:33 2018 +0000
- Revision:
- 0:3d12bad4186e
bismillah bisa...
Who changed what in which revision?
User | Revision | Line number | New contents of line |
---|---|---|---|
asyrofi | 0:3d12bad4186e | 1 | #include<stdio.h> |
asyrofi | 0:3d12bad4186e | 2 | #include "mbed.h" |
asyrofi | 0:3d12bad4186e | 3 | #include "Serial.h" |
asyrofi | 0:3d12bad4186e | 4 | Serial uart1(USBTX,USBRX); |
asyrofi | 0:3d12bad4186e | 5 | /* Function to find the cross over point (the point before |
asyrofi | 0:3d12bad4186e | 6 | which elements are smaller than or equal to x and after |
asyrofi | 0:3d12bad4186e | 7 | which greater than x)*/ |
asyrofi | 0:3d12bad4186e | 8 | int findCrossOver(int arr[], int low, int high, int x) |
asyrofi | 0:3d12bad4186e | 9 | { |
asyrofi | 0:3d12bad4186e | 10 | // Base cases |
asyrofi | 0:3d12bad4186e | 11 | if (arr[high] <= x) // x is greater than all |
asyrofi | 0:3d12bad4186e | 12 | return high; |
asyrofi | 0:3d12bad4186e | 13 | if (arr[low] > x) // x is smaller than all |
asyrofi | 0:3d12bad4186e | 14 | return low; |
asyrofi | 0:3d12bad4186e | 15 | |
asyrofi | 0:3d12bad4186e | 16 | // Find the middle point |
asyrofi | 0:3d12bad4186e | 17 | int mid = (low + high)/2; /* low + (high - low)/2 */ |
asyrofi | 0:3d12bad4186e | 18 | |
asyrofi | 0:3d12bad4186e | 19 | /* If x is same as middle element, then return mid */ |
asyrofi | 0:3d12bad4186e | 20 | if (arr[mid] <= x && arr[mid+1] > x) |
asyrofi | 0:3d12bad4186e | 21 | return mid; |
asyrofi | 0:3d12bad4186e | 22 | |
asyrofi | 0:3d12bad4186e | 23 | /* If x is greater than arr[mid], then either arr[mid + 1] |
asyrofi | 0:3d12bad4186e | 24 | is ceiling of x or ceiling lies in arr[mid+1...high] */ |
asyrofi | 0:3d12bad4186e | 25 | if(arr[mid] < x) |
asyrofi | 0:3d12bad4186e | 26 | return findCrossOver(arr, mid+1, high, x); |
asyrofi | 0:3d12bad4186e | 27 | |
asyrofi | 0:3d12bad4186e | 28 | return findCrossOver(arr, low, mid - 1, x); |
asyrofi | 0:3d12bad4186e | 29 | } |
asyrofi | 0:3d12bad4186e | 30 | |
asyrofi | 0:3d12bad4186e | 31 | // This function prints k closest elements to x in arr[]. |
asyrofi | 0:3d12bad4186e | 32 | // n is the number of elements in arr[] |
asyrofi | 0:3d12bad4186e | 33 | void printKclosest(int arr[], int x, int k, int n) |
asyrofi | 0:3d12bad4186e | 34 | { |
asyrofi | 0:3d12bad4186e | 35 | // Find the crossover point |
asyrofi | 0:3d12bad4186e | 36 | int l = findCrossOver(arr, 0, n-1, x); |
asyrofi | 0:3d12bad4186e | 37 | int r = l+1; // Right index to search |
asyrofi | 0:3d12bad4186e | 38 | int count = 0; // To keep track of count of elements already printed |
asyrofi | 0:3d12bad4186e | 39 | |
asyrofi | 0:3d12bad4186e | 40 | // If x is present in arr[], then reduce left index |
asyrofi | 0:3d12bad4186e | 41 | // Assumption: all elements in arr[] are distinct |
asyrofi | 0:3d12bad4186e | 42 | if (arr[l] == x) l--; |
asyrofi | 0:3d12bad4186e | 43 | |
asyrofi | 0:3d12bad4186e | 44 | // Compare elements on left and right of crossover |
asyrofi | 0:3d12bad4186e | 45 | // point to find the k closest elements |
asyrofi | 0:3d12bad4186e | 46 | while (l >= 0 && r < n && count < k) |
asyrofi | 0:3d12bad4186e | 47 | { |
asyrofi | 0:3d12bad4186e | 48 | if (x - arr[l] < arr[r] - x) |
asyrofi | 0:3d12bad4186e | 49 | uart1.printf("%d ", arr[l--]); |
asyrofi | 0:3d12bad4186e | 50 | else |
asyrofi | 0:3d12bad4186e | 51 | uart1.printf("%d ", arr[r++]); |
asyrofi | 0:3d12bad4186e | 52 | count++; |
asyrofi | 0:3d12bad4186e | 53 | } |
asyrofi | 0:3d12bad4186e | 54 | |
asyrofi | 0:3d12bad4186e | 55 | // If there are no more elements on right side, then |
asyrofi | 0:3d12bad4186e | 56 | // print left elements |
asyrofi | 0:3d12bad4186e | 57 | while (count < k && l >= 0) |
asyrofi | 0:3d12bad4186e | 58 | uart1.printf("%d ", arr[l--]), count++; |
asyrofi | 0:3d12bad4186e | 59 | |
asyrofi | 0:3d12bad4186e | 60 | // If there are no more elements on left side, then |
asyrofi | 0:3d12bad4186e | 61 | // print right elements |
asyrofi | 0:3d12bad4186e | 62 | while (count < k && r < n) |
asyrofi | 0:3d12bad4186e | 63 | uart1.printf("%d ", arr[r++]), count++; |
asyrofi | 0:3d12bad4186e | 64 | } |
asyrofi | 0:3d12bad4186e | 65 | |
asyrofi | 0:3d12bad4186e | 66 | /* Driver program to check above functions */ |
asyrofi | 0:3d12bad4186e | 67 | int main() |
asyrofi | 0:3d12bad4186e | 68 | { |
asyrofi | 0:3d12bad4186e | 69 | uart1.baud(9600); |
asyrofi | 0:3d12bad4186e | 70 | wait(0.1); |
asyrofi | 0:3d12bad4186e | 71 | int arr[] ={12, 16, 22, 30, 35, 39, 42, |
asyrofi | 0:3d12bad4186e | 72 | 45, 48, 50, 53, 55, 56}; |
asyrofi | 0:3d12bad4186e | 73 | int n = sizeof(arr)/sizeof(arr[0]); |
asyrofi | 0:3d12bad4186e | 74 | int x = 35, k = 4; |
asyrofi | 0:3d12bad4186e | 75 | printKclosest(arr, x, 4, n); |
asyrofi | 0:3d12bad4186e | 76 | while(1) |
asyrofi | 0:3d12bad4186e | 77 | { |
asyrofi | 0:3d12bad4186e | 78 | wait(0.1); |
asyrofi | 0:3d12bad4186e | 79 | uart1.printf("%d \n",printKclosest); |
asyrofi | 0:3d12bad4186e | 80 | } |
asyrofi | 0:3d12bad4186e | 81 | //return 0; |
asyrofi | 0:3d12bad4186e | 82 | } |