Archive

Archive for the ‘Algorithm’ Category

Thuật toán Euclid tìm ước chung lớn nhất của 2 số

1.Giới thiệu
Thuật toán Euclid tìm ước chung lớn nhất của 2 số dựa trên nguyên lý sau:

Nếu p>q thì UCLN(p,q) = UCLN(r,q) với r = p%q

2.Cài đặt trong Java

public static int gcd(int p, int q) {
   if (q == 0) {
      return p;
   }
   return gcd(q, p % q);
}
Categories: Algorithm

Sinh hoán vị ngẫu nhiên

1. Đặt bài toán

Sinh ngẫu nhiên cho mảng nguyên a một hoán vị của 1..n

2. Thuật toán

– Xuất phát từ hoán vị đơn vị a = (1,2,…,n), thực hiện đổi chỗ a[0] với một phần tử a[j], trong đó j = random(n)

– Có thể lặp lại thao tác trên nhiều lần để tăng sự xáo trộn ngẫu nhiên

3. Code C# :

/// <summary>
 /// Sinh hoán vị đều
 /// </summary>
 /// <param name="n">Số phần tử cần sinh</param>
 /// <returns>Mảng n số nguyên là một hoán vị của 1..n</returns>
 public static int[] GenRandomPermutation(int n)
 {
    Random r = new Random();
    int[] a = new int[n];
    for (int i = 0; i < n; i++)
    {
       a[i] = i + 1;
    }
    for (int i = 0; i < n; i++)
    {
       int j = r.Next(n);
       int t = a[0];
       a[0] = a[j];
       a[j] = t;
    }
    return a;
 }
Categories: Algorithm

Sinh ngẫu nhiên tăng

1. Đặt bài toán :

Sinh ngẫu nhiên mảng nguyên n phần tử được sắp không giảm

2. Thuật toán :

  • Sinh ngẫu nhiên phần tử đầu tiên : a[0] = random(n);
  • Từ phần tử thứ 2 trở đi, giá trị được sinh bằng giá trị của phần tử đứng liền trước nó cộng thêm một đại lượng dương ngẫu nhiên :

(i=2…n):a[i]:=a[i-1]+random(n) . Do đó a[i] >= a[i-1]

3. Code C# :

/// <summary>
 /// Sinh ngẫu nhiên tăng
 /// </summary>
 /// <param name="n">Số phần tử cần sinh ra</param>
 /// <returns>Mảng n số nguyên theo tứ tự không giảm</returns>
 public static int[] GenRandomInCrease(int n)
 {
     Random r = new Random();
     int[] a = new int[n];
     a[0] = r.Next(5);
     for (int i = 1; i < n; i++)
     {
         a[i] = a[i - 1] + r.Next(10);
     }
     return a;
 }
Categories: Algorithm

Sinh ngẫu nhiên theo khoảng

1. Tổng quan vào, ra dữ liệu trong lập trình

Hầu hết các bài toán lập trình đều đòi hỏi dữ liệu đầu vào và trả về dữ liệu đầu ra.

Đầu vào có thể được :

  • Nạp trực tiếp từ bàn phím
  • Sinh ngẫu nhiên
  • Đọc từ tệp văn bản

Đầu ra có thể được :

  • Hiển thị trên màn hình
  • Ghi vào 1 tệp văn bản

2. Sinh ngẫu nhiên theo khoảng

Đặt bài toán : 

Sinh ngẫu nhiên cho mảng nguyên n phần tử trong khoảng từ c đến d

Cài đặt : 

Code C# :

/// <summary>
 /// Sinh ngẫu nhiên theo khoảng
 /// </summary>
 /// <param name="n">Số phần tử cần sinh ra</param>
 /// <param name="c">Giá trị thứ nhất</param>
 /// <param name="d">Giá trị thứ hai</param>
 /// <returns>Mảng n số nguyên trong khoảng từ c đến d </returns>
 public static int[] GenRandomFromTo(int n, int c, int d)
 {
     Random r = new Random();
     int len = d - c + 1;
     int[] a = new int[n];
     for (int i = 0; i < n; i++)
     {
         a[i] = c + r.Next(len);
     }
     return a;
 }

Code Java : 

/**
 * Sinh ngau nhien mang n phan tu nguyen trong khoang tu c den d 
 * @param n
 * @param c
 * @param d
 * @return
 */
 public static int[] genRandomFromTo(int n, int c, int d)
 {
     Random r = new Random();
     int len = d - c + 1;
     int[] a = new int[n];
     for (int i = 0; i < n; i++)
     {
         a[i] = c + r.nextInt(len);
     }
     return a;
 }
Categories: Algorithm

Thuật toán sắp xếp Gnome – Gnome Sort

1. Giới thiệu

Thuật toán sắp xếp Gnome là một trong những thuật toán sắp xếp đơn giản nhất, thuộc nhóm các thuật toán có độ phức tạp thuật toán là O(n^2) như sắp xếp nổi bọt, sắp xếp chèn…. Điểm khác biệt ở chỗ sắp xếp Gnome chỉ sử dụng một vòng lặp thay vì 2 vòng lặp như các thuật toán trên.

2. Cài đặt

2.1 Code C#, Java : 

public int[] GnomeSort(int[] arr)
{
    int pos = 1; /* Vi tri bat dau so sanh, la phan tu thu 2 trong mang*/
    int temp;
    int length = arr.Length;
    while (pos < length)
    {
        /* So sanh voi phan tu phia truoc */
       if (arr[pos] >= arr[pos - 1])
       {
           /* Neu lon hon ( da dung thu tu sap xep ) thi tien len 1 vi tri*/
           pos++;
       }
       else
       {
           /* Nguoc lai thi hoan vi 2 phan tu*/
           temp = arr[pos];
           arr[pos] = arr[pos - 1];
           arr[pos - 1] = temp;
           /* Lui ve 1 vi tri de kiem tra lai, vi sau khi hoan vi, mang van co the chua dung thu tu*/
           pos--;
           if (pos == 0) /* Kiem soat khong cho pos nho hon 1 */
           {
               pos = 1;
           }
        }
    }
    return arr;
 }

2.2 Code C, C++ :

void gnome_sort(int *iArray,int iLength)
{
    int iPos = 1;
    int iTemp=0;
    while(iPos<iLength)
    {
        if(iArray[iPos]>=iArray[iPos-1])
        {
            iPos++;
        }
        else
        {
            iTemp=iArray[iPos];
            iArray[iPos]=iArray[iPos-1];
            iArray[iPos-1]=iTemp;
iPos--; if(iPos==0) { iPos=1; } } } }

Xem thêm cách cài đặt bằng cách ngôn ngữ khác tại http://rosettacode.org/wiki/Sorting_algorithms/Gnome_sort hoặc http://en.wikibooks.org/wiki/Algorithm_Implementation/Sorting/Gnome_sort

Categories: Algorithm

Tìm kiếm nhị phân – Binary Search

1. Giới thiệu

Trong khoa học máy tính, tìm kiếm nhị phân ( binary search ) là một thuật toán dùng để tìm kiếm phần tử trong một danh sách đã sắp xếp ( sorted lists and array ).

Ý tưởng :  So sánh phần tử cần tìm với phần tử nằm chính giữa danh sách để xác định vùng dữ liệu có chứa giá trị cần tìm. Nếu 2 phần tử bằng nhau thì thuật toán kết thúc. Nếu 2 phần tử không bằng nhau thì tùy vào phần tử nào lớn hơn, thuật toán lặp lại bước so sánh trên với nửa đầu hoặc nửa sau của danh sách.

Vì sau mỗi bước tìm kiếm, miền dữ liệu cần xét giảm đi một nửa nên thời gian thực thi của thuật toán là hàm logarit.

2. Cài đặt

/// <summary>
/// Thuật toán tìm kiếm nhị phân trong 1 mảng đã sắp xếp
/// </summary>
/// <param name="value">Giá trị cần tìm</param>
/// <param name="arr">Mảng đã sắp xếp</param>
/// <returns></returns>
public int BinarySearch(int value, int[] arr)
{
    int left = 0, right = arr.Length, mid;
    int ret = -1;
    while (left < right)
    {
        mid = (left + right) / 2;
        if (arr[mid] == value)
        {
            ret = mid;
            break;
        }
        else if (arr[mid] > value)
        {
            right = mid;
        }
        else
        {
            left = mid + 1;
        }
     }
     return ret;
 }

3. Độ phức tạp thuật toán

– Tốt nhất : O(1) – Phần tử cần tìm ở chính giữa danh sách

– Xấu nhất : O(log2(n)) – Không có phần tử cần tìm trong danh sách

– Trung bình : O(log2(n/2)) – Xác suất các phần tử trong danh sách chứa giá trị cần tìm là như nhau.

 

Categories: Algorithm

Tìm kiếm tuyến tính – Linear Search

1. Giới thiệu :

Trong khoa học máy tính, tìm kiếm tuyến tính ( linear search ) hay tìm kiếm tuần tự ( sequential search ) là phương pháp tìm kiếm một phần tử cho trước trong một danh sách ( list hoặc array ) bằng cách duyệt lần lượt từng phần tử của danh sách đó cho đến khi tìm thấy phần tử cần tìm hay đã duyệt qua toàn bộ danh sách.

2. Cài đặt :

/// <summary>
/// Thuật toán tìm kiếm tuyến tính trong 1 mảng
/// </summary>
/// <param name="value">Giá trị cần tìm</param>
/// <param name="arr">Mảng</param>
/// <returns>Vị trí của phần tử tìm thấy đầu tiên, trả về -1 nếu không tìm thấy</returns>
public int LinearSearch(int value, int[] arr)
{
    int length = arr.Length;
    int ret = -1;
    for (int i = 0; i < length; i++)
    {
        if (arr[i] == value)
        {
            ret = i;
            break;
        }
    }
    return ret;
 }

3. Đánh giá độ phức tạp thuật toán :

– Tốt nhất : O(1)  – Phần tử cần tìm ở vị trí đầu tiên

– Xấu nhất : O(n+1) – Phần tử cần tìm ở vị trí cuối cùng

– Trung bình : O(n) – Xác suất các phần tử trong danh sách chứa giá trị cần tìm là như nhau

Categories: Algorithm