User Tag List

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

Chủ đề: Cau Truc Du Lieu va GT(Bang ngon ngu C)

  1. #1
    WildMan
    Guest

    Mặc định

    :monalisa)
    Xin chao tat ca cac ban !
    Mình là Wildman. Hôm nay sau khoảng tháng trời ẩn cư nay tái xuất giang hồ.
    Hôm nay mình xin được trao đổi về một vấn đề đó là:
    "Bài toán xếp lịch"
    Xin được nói qua về bài toán nay:
    Phát biểu:
    G/s có n chi tiết máy được gia công trên hai máy A và B.
    Thời gian thi công các chi tiết trên máy A là a1,a2,..,an và
    Thời gian thi công các chi tiết trên máy B là b1,b2,..,bn .
    Hỏi phải xắp xếp lịch thực hiện công viêc sao cho tiết kiệm thời gian nhất.
    Đấy là một vấn đề thuộc lĩnh vưc "vận trù học" tìm cách giải quyết tối ưu
    một vấn đề nào đó sao cho tiết kiệm được thời gian và nguyên liệu
    một vấn đề có ý nghĩa trong cuộc sống.
    Nhưng bài toán tối ưu đôi khi rất khó tim được thuật giải tối ưu
    Bây giờ tôi xin được đề cập tới một giải thuật tên là Johnson
    Tư tưởng của giải thuật này không có gì khó tuy nhiên để chứng minh
    tính đúng đắn của giải thuật thì không đơn giản.
    Sau đây tôi xin được trình bày giải thuật viết bằng ngôn ngữ C:

    /*Program Johnson;*/
    #include<stdio.h>
    #include<conio.h>
    #include<alloc.h>/*Tep tiêu đề dùng dể cấo phát bộ nhớ*/
    #include<stdlib.h>
    typedef struct p_contro{
    int data;
    struct p_contro link;/*dia chi lien ket chi toi phan tu ke tiep trong Stack */
    }contro
    void pop(contro *,int *);/* thu tuc Pop lay 1 phan tu tu dinh Stack */
    contro *push(contro *,int);/*ham them 1 phan tu vao Stack*/
    void main(){
    contro *N1;
    contro *N2;
    int n;
    int a[20];
    int b[20];
    int *c;
    int i,j;
    clrscr();
    printf("Bat daun");
    printf("Nhap n:n");scanf("%d",&n);
    for (i=0;i<n;i++){
    printf("Nhap a[%d]:n",i);scanf("%d",&a[i]);
    printf("Nhap b[%d]:n",i);scanf("%d",&b[i]);
    }
    /*xap xep day b[i] theo chieu tang dan*/
    for (i=0;i<n-1;i++)
    for (j=i+1;j<n;j++)
    if (b[i]>b[j]) {
    int temp;
    temp=b[i];
    b[i]=b[j];
    b[j]=temp;
    temp=a[i];
    a[i]=a[j];
    a[j]=temp;
    }
    for (i=0;i<n;i++){
    if (a[i]<b[i])
    N1=push(N1,a[i]);
    else
    N2=push(N2,a[i]);
    }
    i=0;
    while(N1&#33;=NULL){
    pop(N1,c+i);
    i=i+1;
    N1=N1->link;
    }
    int k;
    for (k=0;k<i-1;k++)
    for (j=k+1;j<i;j++)
    if(*(c+k)>*(c+j)){
    int temp;
    temp=*(c+k);
    *(c+k)=*(c+j);
    *(c+j)=temp;}
    for (j=0;j<i;j++)
    printf("%3d",*(c+j));
    i=0;
    while(N2&#33;=NULL){
    pop(N2,c+i);
    i=i+1;
    N2=N2->link;
    }
    for (j=0;j<i;j++)
    printf("%3d",*(c+j));
    getch();
    }
    contro *push(contro *s,int x){
    contro *p;
    p=(contro *)malloc(sizeof(contro))/*cap phat vung nho cho vung ma con tro p cho toi */
    p->data=x;
    p->link=s;
    return p;
    }
    void pop(contro *s,int *L){
    contro *p;
    p=s;
    *L=p->data;
    free(p);/*giai phong bo nho*/
    }

    Tren day la toan bo giai thuat .
    toi da chay thu va ra duoc ket qua tuy nhien con truong hop co
    nhieu nghiem(co nhieu cach xap lich) moi chi ra duoc mot ket qua.
    Hy vong vao mot dip khac se dua ra duoc mot cach giai hay hon
    Từ kinh nghiệm bản thân tôi xin có một số ý kiến nhỏ:
    -các bạn có thể thấy thủ tục Push tôi dùng hàm trong khi pop tôi lại dùng thủ tục đó là vì nếu Push dung thủ tục (như cô giảng trên lớp thì
    trong thủ tục Push co đoạn S=S->link điều này sẽ cho ra kết quả không
    mong muốn là S sẽ đươc thay bởi link(S) vì nên nhó rằng hàm trong C
    Luôn truyền theo trị do vây khi goi ham Push trong ham Main() thi S vẫn là S.
    Tren đây là một số ý kiến của tôi xin hẹn trở lai vấn đè này vào dịp khác
    rất mong nhạn được ý kiến trao đổi.
    GoodBye (QuangMinh7482@hotmail.com)



    <!--EDIT|Admin|Oct 12 2002, 01:13 PM-->

  2. #2
    Vịt Bầu
    Guest

    Mặc định

    Có vẻ bà con không khoái lập trình nhỉ
    Bác wildman post bài hay lắm cho dù em cũng không thử cái thuật toán của bác. Tôi nghĩ nếu ai có băn khuăn thắc mắc gì thì hãy post lên đây ta cùng bàn bạc. Chắc chắn nếu có thể chúng ta sẽ giúp đỡ nhau cùng phát triển nhé các bác .

  3. #3
    kylix
    Guest

    Mặc định

    rất hay đó

  4. #4
    thedeath
    Guest

    Mặc định

    Kiếm sách QUẢn LÝ DOANH NGHIỆP ĐẠI CƯƠNG
    Trong đó có nói về vấn đề như trên nhưng giải theo tiêu chí đưa vào.
    Để có thể ra nhiều nghiệm, chỉ cần lựa tiêu chí, đẩy bộ kết quả vào linklist. All done, right?&#33;&#33;&#33;

  5. #5
    svBK's Newbie
    Tham gia ngày
    Dec 2007
    Bài gửi
    2

    Mặc định

    bạn ơi có bài toán cái túi,người đi du lịch k ?

  6. #6
    svBK's Newbie
    Tham gia ngày
    Oct 2008
    Bài gửi
    6

    Mặc định

    Tư tưởng và chứng minh tính đúng đắn của giải thật cũng không khó lắm. Nó trong quyển toán rời rạc mà khoa toán tin đang học. Chỉ có điều năm 2 thì chưa có những kiến thức vững về lập trình. Nên mình chỉ hiểu được chứ chưa thể viết được thành chương trình mang tính ứng dụng. Trong đó có cả bài toán cái túi và người du lịch.

+ 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. Ngon ngu lap trinh C++ ???????
    Gửi bởi Net_HaLong trong mục Lập Trình
    Trả lời: 9
    Bài cuối: 30-11-2005, 08:05 PM
  2. Ngon Ngu Lap Trinh
    Gửi bởi Khách_WildMan trong mục Các vấn đề CNTT khác
    Trả lời: 5
    Bài cuối: 15-11-2004, 05:20 PM
  3. co' ai huong da^n dos o vay ta`i lieu bang tieng viet nha ??
    Gửi bởi nghiemleduy trong mục Các vấn đề CNTT khác
    Trả lời: 13
    Bài cuối: 09-06-2004, 12:36 AM
  4. bang bang - nhac Phap - Thân tặng bác Dkqdiep
    Gửi bởi bambou trong mục V-Music
    Trả lời: 0
    Bài cuối: 23-03-2004, 05:03 PM

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