User Tag List

+ Trả lời chủ đề
Hiện kết quả từ 1 tới 7 của 7

Chủ đề: Code hoàn chỉnh các ví dụ trong bài giảng Giải thuật của thầy N.Đ Nghĩa

  1. #1
    .:: Grumpy svBKer ::. Avatar của 1973
    Tham gia ngày
    Mar 2010
    Bài gửi
    3.793

    Mặc định Code hoàn chỉnh các ví dụ trong bài giảng Giải thuật của thầy N.Đ Nghĩa

    Chắc nhiều bạn cũng học môn Cấu trúc dữ liệu và giải thuật do thầy Nghĩa dạy, nếu mọi người đã mua cuốn "Bài giảng Cấu trúc dữ liệu và giải thuật" do thầy viết thì sẽ thấy rằng các ví dụ minh họa thuật toán trong bài thầy thường sử dụng mã giả hoặc gần giả. Do đó mình lập chủ đề này với mục đích cung cấp cho các bạn các đoạn mã hoàn chỉnh cho các ví dụ minh họa trong sách của thầy.

    Do khả năng có hạn nên có thể thiếu sót, mong các bạn khác vào giúp đỡ hoàn chỉnh các đoạn code minh họa

    Bây giờ chúng ta cùng bắt đầu

    Bài đầu tiên về giải thuật thầy giáo có một ví dụ minh họa với đề bài sau: (thật ra đây không phải là ví dụ thầy nghĩ ra mà là ví dụ của 1 ông GS gì đó rất nổi tiếng, phải nói là ví dụ này rất hay)

    Bài toán tìm dãy con lớn nhất: Cho dãy số a1, a2,...., an.

    Dãy số ai, ai+1,..., aj với 1 <= i <= j <= n được gọi là dãy con của dãy đã cho và tổng các phần tử của dãy con này được gọi là trọng lượng của nó.

    Vấn đề đặt ra là: hãy tìm trọng lượng lớn nhất của dãy con, tức là tìm dãy con có tổng các phần tử đạt giá trị lớn nhất. Để đơn giản, ta gọi dãy con có trọng lượng lớn nhất là dãy con lớn nhất.

    Ví dụ: nếu dãy đã cho là -2, 11, -4, 13, -5, 2 thì cần đưa ra câu trả lời là 20 (trọng lượng của dãn con 11, -4, 13)


    Các thuật toán minh họa:

    Thuật toán trực tiếp --> đơn giản nên mình sẽ không minh họa

    Thuật toán nhanh hơn:


    PHP Code:
    /* Vi du tim day con lon nhat mon Giai thuat */
    #include<stdio.h>
    #define NMAX 50
    int maxSum(int [], int);
    int main()
    {
            
    int ni;
            
    int a[NMAX];
            
            
    printf("\nNhap n: ");
            
    scanf("%d", &n);
            
    printf("Nhap so lieu cho mang:\n");
            for (
    i=0i<ni++)
            {
                    
    printf("a[%d] = "i+1);
                    
    scanf("%d", &a[i]);
            }
            
            
    printf("Trong luong lon nhat cua day con la: %d\n"maxSum(an));
            
            return 
    0;
    }

    //Thuat toan nhanh hon
    int maxSum(int a[], int n)
    {
            
    int ijsummaxS;
            
    maxS a[0];
            
            for (
    i=0i<ni++)
            {
                    
    sum 0;
                    for (
    j=ij<nj++)
                    {
                            
    sum += a[j];
                            if (
    sum maxS)
                                    
    maxS sum;
                    }
            }
            return 
    maxS;


    Thuật toán đệ quy:


    PHP Code:
    /* Vi du tim day con lon nhat mon Giai thuat */
    #include<stdio.h>
    #define NMAX 50
    int maxSub(int [], intint);
    int maxMid(int [], intintint);
    int main()
    {
            
    int ni;
            
    int a[NMAX];
            
            
    printf("\nNhap n: ");
            
    scanf("%d", &n);
            
    printf("Nhap so lieu cho mang:\n");
            for (
    i=0i<ni++)
            {
                    
    printf("a[%d] = "i+1);
                    
    scanf("%d", &a[i]);
            }
            
            
            
    printf("Trong luong lon nhat cua day con la: %d\n"maxSub(a0n-1));
            return 
    0;
    }

    // Thuat toan de quy
    // a la ten mang, m la chi so dau, n la chi so cuoi
    int maxSub(int a[], int mint n)
    {
            
    int mid;
            
    int maxLmaxRmaxMmaxS;
            
            if (
    == m)
                    return 
    a[m];
            else
            {
                    
    mid = (m+n)/2;
                    
                    
    maxL maxSub(ammid);
                    
    maxR maxSub(amid+1n);
                    
    maxM maxMid(ammidn);
                    
                    
    maxS maxL>maxR?maxL:maxR;
                    return 
    maxS>maxM?maxS:maxM;
            }
            
    }

    int maxMid(int a[], int mint midint n)
    {
            
    int isum 0;
            
    int maxL a[mid], maxR a[mid+1];
            
            
    //tinh maxL
            
    for (i=midi>=mi--)
            {
                    
    sum += a[i];
                    if (
    sum>maxL)
                            
    maxL sum;
            }
            
            
    //tinh maxR
            
    sum 0;
            for (
    i=mid+1i<=ni++)
            {
                    
    sum += a[i];
                    if (
    sum>maxR)
                            
    maxR sum;
            }
            
            return 
    maxL+maxR;

    Thuật toán quy hoạch động --> mình sẽ post lên sau
    Contact me:
    Email: sangnd [at] svBK.vn
    Personal website: My Blog | Chat với người lạ
    Facebook Page của Bách Khoa Forum: http://www.facebook.com/svbk.vn

  2. Có 3 thành viên cảm ơn bài viết của 1973 có chất lượng:


  3. #2
    .:: Grumpy svBKer ::. Avatar của 1973
    Tham gia ngày
    Mar 2010
    Bài gửi
    3.793

    Mặc định Re: Code hoàn chỉnh các ví dụ trong bài giảng Giải thuật của thầy N.Đ Nghĩa

    Mình vừa sửa 1 lỗi ở phần thuật toán đệ quy do mảng trong C bắt đầu từ 0 và kết thúc ở n-1 nên mình có chút nhầm lẫn. Sau đây là bài làm sử dụng thuật toán quy hoạch động:

    PHP Code:
    /* Vi du tim day con lon nhat mon Giai thuat */
    #include<stdio.h>
    #define NMAX 50
    int maxQuy(int [], int);
    int main()
    {
            
    int ni;
            
    int a[NMAX];
            
            
    printf("\nNhap n: ");
            
    scanf("%d", &n);
            
    printf("Nhap so lieu cho mang:\n");
            for (
    i=0i<ni++)
            {
                    
    printf("a[%d] = "i+1);
                    
    scanf("%d", &a[i]);
            }
            
            
            
    printf("Trong luong lon nhat cua day con la: %d\n"maxQuy(an));
            return 
    0;
    }

    //quy hoach dong
    //a la ten mang, n la kich thuoc mang
    int maxQuy(int a[], int n)
    {
            
    int sMax a[0]; //trong luong cua day con lon nhat
            
    int maxEnd 0;
            
    int uv;
            
    int i;
            
            for (
    i=0i<ni++)
            {
                    
    maxEnd a[i];
                    
    a[i];
                    
    maxEnd u>v?u:v;
                    if (
    maxEnd>sMax)
                            
    sMax maxEnd;
            }
            return 
    sMax;


  4. #3
    Chia sẻ Tri thức Avatar của Francisco
    Tham gia ngày
    Sep 2010
    Bài gửi
    90

    Mặc định Re: Code hoàn chỉnh các ví dụ trong bài giảng Giải thuật của thầy N.Đ Nghĩa

    ở dòng đầu khai báo hàm nhầm một chút:
    PHP Code:
    int maxQuy(int [], int 
    ~/http://sonkimdinhhust.wordpress.com/
    Franicso
    >_


  5. #4
    .:: Grumpy svBKer ::. Avatar của 1973
    Tham gia ngày
    Mar 2010
    Bài gửi
    3.793

    Mặc định Re: Code hoàn chỉnh các ví dụ trong bài giảng Giải thuật của thầy N.Đ Nghĩa

    Quote Nguyên văn bởi Francisco Xem bài viết
    ở dòng đầu khai báo hàm nhầm một chút:
    PHP Code:
    int maxQuy(int [], int 
    Ừ, cảm ơn cậu, thật ra thấy C không bắt lỗi nên tớ cứ nghĩ đặt maxQuy() cũng không vấn đề gì. Tớ đã sửa rồi

  6. #5
    HUT's Engineer
    Tham gia ngày
    Jun 2011
    Bài gửi
    686

    Mặc định Re: Code hoàn chỉnh các ví dụ trong bài giảng Giải thuật của thầy N.Đ Nghĩa

    nice nhưng hơi cũ khi vẫn dùng C

  7. #6
    Khánh Hòa
    Tham gia ngày
    Apr 2010
    Bài gửi
    159

    Mặc định Re: Code hoàn chỉnh các ví dụ trong bài giảng Giải thuật của thầy N.Đ Nghĩa

    có bài nào nữa không nhỉ, @sang c post đề lên đi, rồi mọi người cùng làm

  8. #7
    .:: Grumpy svBKer ::. Avatar của 1973
    Tham gia ngày
    Mar 2010
    Bài gửi
    3.793

    Mặc định Re: Code hoàn chỉnh các ví dụ trong bài giảng Giải thuật của thầy N.Đ Nghĩa

    Dạo này lười quá, chả cốt gì cả, hôm nay code được mấy bài quăng lên đây cho anh em tham khảo.

    Thuật toán sắp xếp trộn trang 25

    PHP Code:
    /* Thuat toan sap xep tron
     */
    #include<stdio.h>
    #define NMAX 50

    int a[NMAX];
    int n//so phan tu cua mang

    /*######################################################################################*/

    int Nhap(); //nhap vao mot mang
    int Xuat(); //xuat ra mang
    int SapXep(int *aint leftint right); //thuat toan sap xep tron
    int Tron(int *aint leftint midint right);

    /*######################################################################################*/

    int main()
    {
        
    Nhap();
        
    printf("Mang vua nhap la:\n");
        
    Xuat();
        
    SapXep(a0n-1);
        
    printf("Mang sau khi sap xep la:\n");
        
    Xuat();
        
    getchar();
        return 
    0;
    }
    /*######################################################################################*/
    int Nhap()
    {
        
    int i;
        do 
        {
            
    printf("Nhap n: ");
            
    scanf("%d", &n);
        } while (
    n<|| n>NMAX);

        
    printf("Nhap du lieu cho cac phan tu:\n");
        for (
    i=0i<;i++)
        {
            
    printf("a[%d] = "i);
            
    scanf("%d", &a[i]);

        }
        return 
    0;
    }

    int Xuat()
    {
        
    int i;
        for (
    i=0i<ni++)
        {
            
    printf("a[%d] = %d\n"ia[i]);
        }
        return 
    0;
    }

    int SapXep(int *aint leftint right)
    {
        
    int mid;
        if (
    left<right//dieu kien neo
        
    {
            
    mid = (left+right)/2//chia
            
    SapXep(aleftmid); //tri
            
    SapXep(amid+1right); //tri
            
    Tron(aleftmidright); //to hop
        
    }
        return 
    0;
    }

    int Tron(int *aint leftint midint right)
    {
        
    int le[NMAX], ri[NMAX]; //2 mang con le va ri dung de tron
        
    int ijk;
        
    //sao chep vao 2 mang con
        
    0;
        for (
    i=lefti<=midi++)
            
    le[j++] = a[i];
        
    le[j] = 65535;
        
    0;
        for (
    i=mid+1i<=righti++)
            
    ri[j++] = a[i];
        
    ri[j] = 65535;
        
    //tron vao mang a
        
    00;
        for (
    i=lefti<=righti++)
            if (
    le[j] < ri[k])
                
    a[i] = le[j++];
            else
                
    a[i] = ri[k++];
        return 
    0;


    Ví dụ đệ quy có nhớ tính hệ số tổ hợp C(n, k)

    PHP Code:
    /* De quy co nho tinh he so to hop */
    #include<stdio.h>
    #define NMAX 50
    int D[NMAX][NMAX];// mang luu tru nhung ket qua da tinh
    int nk;
    int Nhap(); //nhap n va k
    int KhoiTaoMang(); //khoi tao mang D
    int HeSoToHop(int nint k); //tinh he so to hop

    int main()
    {
        
    Nhap();
        
    KhoiTaoMang();
        
    printf("C(%d, %d) = %d\n"nkHeSoToHop(nk));
        
    getchar();
        return 
    0;
    }

    int Nhap()
    {
        do
        {
            
    printf("Nhap n: ");
            
    scanf("%d", &n);
        } while (
    n<|| n>NMAX);
        do 
        {
            
    printf("Nhap k: ");
            
    scanf("%d", &k);
        } while (
    k<|| k>n);
        return 
    0;
    }

    int KhoiTaoMang()
    {
        
    int ij;
        for (
    i=0i<ni++)
            for (
    j=0j<nj++)
                if (
    i==|| j==0)
                    
    D[i][j] = 1;
                else
                    
    D[i][j] = 0;
        return 
    0;
    }

    int HeSoToHop(int nint k)
    {
        if (
    D[n][k] > 0)
            return 
    D[n][k];
        
    D[n][k] = HeSoToHop(n-1k-1) + HeSoToHop(n-1k);
        return 
    D[n][k];


  9. Tớ cảm ơn 1973 đã chia sẻ.


+ Trả lời chủ đề

Thông tin chủ đề

Users Browsing this Thread

Hiện có 1 người đọc bài này. (0 thành viên và 1 khách)

Chủ đề tương tự

  1. Hướng dẫn các chức năng chính của Source Code C2C (Code To Coder)
    Gửi bởi hoaianvn trong mục Thư viện mã nguồn
    Trả lời: 1
    Bài cuối: 23-10-2009, 02:13 PM
  2. Chửi thề trong code
    Gửi bởi [N]am trong mục Các vấn đề CNTT khác
    Trả lời: 4
    Bài cuối: 18-04-2009, 01:44 PM
  3. Trả lời: 1
    Bài cuối: 21-02-2009, 10:14 PM
  4. ~x( Suy nghĩ về việc Sinh viên ĐTVT đi làm Code
    Gửi bởi Silent_cOntrol trong mục Giảng đường khoa ĐTVT
    Trả lời: 36
    Bài cuối: 26-01-2008, 12:20 PM
  5. Wi-Fi là 'một thuật ngữ không có nghĩa'?
    Gửi bởi 1m76-78kg trong mục Hệ thống Viễn thông
    Trả lời: 3
    Bài cuối: 24-11-2005, 09:17 AM

Từ khóa (Tag) của chủ đề này

Quyền viết bài

  • Bạn không thể gửi chủ đề mới
  • Bạn không thể gửi trả lời
  • Bạn không thể gửi file đính kèm
  • Bạn không thể sửa bài viết của mình


About svBK.VN

    Bách Khoa Forum - Diễn đàn thảo luận chung của sinh viên ĐH Bách Khoa Hà Nội. Nơi giao lưu giữa sinh viên - cựu sinh viên - giảng viên của trường.

Follow us on

Twitter Facebook youtube