Bạn có muốn phản ứng với tin nhắn này? Vui lòng đăng ký diễn đàn trong một vài cú nhấp chuột hoặc đăng nhập để tiếp tục.

.


2 posters

    Code đầy đủ cho vài bài trong đề cương PTTK :D

    duong.oriole
    duong.oriole
    Members
    Members


    Tổng số bài gửi : 3
    Ranh tiếng : 0
    Join date : 29/10/2011
    Age : 31

    ADMIN Code đầy đủ cho vài bài trong đề cương PTTK :D

    Bài gửi by duong.oriole 30/11/2011, 01:07

    [T]rung
    [T]rung
    Admin
    Admin


    Tổng số bài gửi : 69
    Ranh tiếng : 2
    Join date : 30/10/2010
    Age : 31
    Đến từ : Haiphong, Vietnam

    ADMIN Re: Code đầy đủ cho vài bài trong đề cương PTTK :D

    Bài gửi by [T]rung 1/12/2011, 23:08

    Bài làm chỉ mang tính chất tham khảo, tính đúng đắn và ổn định chưa được kiểm nghiệm.
    Câu 1: Sắp xếp mảng cấu trúc sinh viên (tên, tuổi, địa chỉ) bằng các thuật toán sắp xếp: đổi chỗ trực tiếp, chọn trực tiếp, chèn trực tiếp, nổi bọt, sắp xếp nhanh dựa vào dữ liệu nhập vào từ bàn phím.
    Code:
    #include<conio.h>
    #include<stdio.h>
    #include<malloc.h>
    #include<string.h>
    typedef struct
    {
       char ten[30];
       int tuoi;
       char dchi[100];
    }sv;
    void swap(sv &a,sv &b)
    {
       sv tg=a;
       a=b;
       b=tg;
    }
    void nhap(sv *a,int n)
    {
       int i;
       for(i=1;i<=n;i++)
       {
          printf("\nSinh vien thu %d",i);
          printf("\nHo ten : ");fflush(stdin);gets(a[i].ten);
          printf("Tuoi  : ");scanf("%d",&a[i].tuoi);
          printf("Dia chi: ");fflush(stdin);gets(a[i].dchi);
         }
    }
    void xuat(sv *a,int n)
    {
      int i;
      printf("\nHo ten-----------Tuoi---------Dia chi");
      for(i=1;i<=n;i++)
          printf("\n%-20s%-10d%-20s",a[i].ten,a[i].tuoi,a[i].dchi);   
    }
    void exchange_sort(sv*a,int n)
    {
       int i,j;
       for(i=1;i<n;i++)
         for(j=i+1;j<=n;j++)
           if(a[i].tuoi>a[j].tuoi) swap(a[i],a[j]);
             else if(a[i].tuoi==a[j].tuoi&&strcmpi(a[i].ten,a[j].ten)>0)
            swap(a[i],a[j]);
    }
    void selection_sort(sv *a,int n)
    {
      int i,j,vtmin;
      for(i=1;i<n;i++)
      { vtmin=i;
          for(j=i+1;j<=n;j++)
        if(a[vtmin].tuoi>a[j].tuoi)vtmin=j;
          else if(a[vtmin].tuoi==a[j].tuoi&&strcmpi(a[vtmin].ten,a[j].ten)>0)
             vtmin=j;
        if(vtmin!=i)swap(a[i],a[vtmin]);
      }
    }
    void insertion_sort(sv *a,int n)
    {
       int i,j;
       sv temp;
       for(i=1;i<=n;i++)
       {
         j=i;
         temp=a[i];
         while(j>1&&(temp.tuoi<a[j-1].tuoi ||(temp.tuoi==a[j-1].tuoi&&strcmpi(temp.ten,a[j-1].ten)<0)))
         {
              a[j]=a[j-1];
              j--;
          }
         a[j]=temp;   
       }
     }
    void bubble_sort(sv*a,int n)
    {
       int i,j;
       for(i=1;i<=n;i++)
         for(j=n;j>i;j--)
           if(a[j-1].tuoi>a[j].tuoi)swap(a[j-1],a[j]);
             else if(a[j-1].tuoi==a[j].tuoi&&strcmpi(a[j-1].ten,a[j].ten)>0)
               swap (a[j-1],a[j]);
    }
    int partition(sv*a,int l,int r)
    {
       sv p=a[l];
       int i=l+1;
        int j=r;
       while(l)
       {
          while(((a[i].tuoi<p.tuoi)||(a[i].tuoi==p.tuoi&&strcmpi(a[i].ten,p.ten)<0))&&i<r)i++;
          while(((a[j].tuoi>p.tuoi)||(a[j].tuoi==p.tuoi&&strcmpi(a[j].ten,p.ten)<0))&&l<j)j--;      
          if(i>=j)
          {
             swap(a[l],a[j]);
             return j;
          }
          else swap(a[i],a[j]);
       } 
    }
    void quick_sort(sv *a,int l,int r)
    {
        if(l<r)
       {
          int p=partition(a,l,r);
          quick_sort(a,l,p-1);
          quick_sort(a,p+1,r);
       }   
    }
    int main()
    {
      sv *a;
      int n;
      printf("\n Nhap so phan tu cua mang :");
      scanf("%d",&n);
      a=(sv*)malloc(n*sizeof(sv));
      nhap(a,n);
      printf("\n Danh sach sinh vien da nhap:\n");
      xuat(a,n);
      printf("\n Danh sach sinh vien da duoc sap xep(tang dan theo tuoi,cung tuoi theo ten):\n");
    //  exchange_sort(a,n);
    //  selection_sort(a,n);
    //  insertion_sort(a,n);
    //  bubble_sort(a,n); 
      quick_sort(a,1,n);
      xuat(a,n);
      getch();
      return 0;
    }
    Câu 2: Sắp xếp danh sách liên kết cấu trúc nhân viên (tên, năm sinh, lương) áp dụng thuật toán sắp xếp đổi chỗ trực tiếp và chọn trực tiếp. (dữ liệu nhân viên nhập từ bàn phím)
    Code:
    #include<stdio.h>
    #include<conio.h>
    #include<stdlib.h>
    #include<string.h>

    typedef struct
    {
            int nsinh;
          long luong;
            char ten[30];
    }Data;
    typedef struct tagNode
    {
            Data infor;
            struct tagNode *link;
    }Node,*pNode;

    void nhap(Data *x)
    {
     float y;
     printf("Ho ten: ");
     fflush(stdin);
     gets(x->ten);
     printf("Nam sinh: ");
     scanf("%d",&(x->nsinh));
     printf("Luong: ");
     scanf("%d",&(x->luong));
    }
    void hthi(Data x)
    {
     printf("\n%-20s%-10d%20ld",x.ten,x.nsinh,x.luong);
    }
    void init(pNode *head)
    {
     (*head)=NULL;
    }
    void insert_head(Data x, pNode *head)
    {
     pNode p;
     nhap(&x);
     p=(Node*)malloc(sizeof(Node));
     p->infor=x;
     p->link=(*head);
     (*head)=p;
    }
    void trave(pNode head)
    {
     pNode p=head;
     while (p!=NULL)
    {
     hthi(p->infor);
     p=p->link;
    }
    }           
    void ds_LIFO(pNode *head)
    {
     Data x;
     char ch;
     do{
       printf("Co tiep ko?");
       fflush(stdin);
       scanf("%c",&ch);
       if((ch=='y')||(ch=='Y'))
       insert_head(x, head);
        }while((ch=='y')||(ch=='Y'));
    }
    void Exchange_sort(pNode head)
    {
       pNode q,p=head;
       Data x;
       while(p->link!=NULL)
       {  q=p->link;
          while(q!=NULL)
           { 
              if(p->infor.nsinh>q->infor.nsinh||(p->infor.nsinh==q->infor.nsinh&&strcmpi(p->infor.ten,q->infor.ten)>0))
              {
                 x=p->infor;
                 p->infor=q->infor;
                 q->infor=x;
                 }
                 q=q->link;
            }
            p=p->link;
       }
    }
    void Selection_sort(pNode head)
    {
       pNode p=head,q,vt;
       Data x;
       while(p->link!=NULL)
       {
          vt=p;
          q=p->link;
           while(q!=NULL)
           {
              if(vt->infor.nsinh>q->infor.nsinh)vt=q;
                if(vt->infor.nsinh==q->infor.nsinh&&strcmpi(vt->infor.ten,q->infor.ten)>0)vt=q;
              q=q->link;
           }
           if(vt!=p)
           {
              x=p->infor;
              p->infor=vt->infor;
              vt->infor=x;
           }
           p=p->link;
       }
    }
    int main()
    {
     pNode head;
     init(&head);
     ds_LIFO(&head);
     printf("\n Danh sach nhan vien:\n");
     printf("Ho ten------------Nam sinh----------------Luong");
     trave(head);
     printf("\n Danh sach nhan vien sau khi sap xep(tang dan theo nam sinh,cung nam sinh theo ten):\n");
     printf("Ho ten------------Nam sinh----------------Luong");
    // Exchange_sort(head);
     Selection_sort(head);
     trave(head);
     getch();
     return 0;
    }
    Câu 3: Cài đặt cấu trúc mảng các mặt hàng (tên, mã số, loại mặt hàng). Nhập dữ liệu từ bàn phím và xuất danh sách mặt hàng ra màn hình. Thực hiện tìm kiếm mặt hàng theo mã số được nhập vào theo thuật toán tìm kiếm nhị phân.
    Code:
    #include<conio.h>
    #include<stdio.h>
    #include<malloc.h>
    #include<string.h>
    typedef struct
    {
            int maso;
          char loai[10];
            char ten[30];
    }hang;
    void nhap(hang *a,int n)
    {
    int i;
    for(i=1;i<=n;i++)
    {
     printf("\nMat hang thu %d",i);
     printf("\nMa so: ");
     scanf("%d",&a[i].maso);
     printf("Ten: ");
     fflush(stdin);
     gets(a[i].ten);
     printf("Loai: ");
     fflush(stdin);
     gets(a[i].loai);
    }
    }
    void xuat(hang *a,int n)
    {
      int i;
      printf("\n-Ma so----------Ten---------------Loai");
      for(i=1;i<=n;i++)
          printf("\n %-15d%-20s%-15s",a[i].maso,a[i].ten,a[i].loai);   
    }
    int search(hang *a,int n,int k)
    {
       int i,d=0;;
       for(i=1;i<=n;i++)
        if (a[i].maso==k)return i;
        return -1;
    }
    void swap(hang &a,hang &b)
    {
       hang tg=a;
       a=b;
       b=tg;
    }
    int partition(hang *a,int l,int r)
    {
       hang p=a[l];
       int i=l+1;
       int j=r;
       while(l)
       {
          while(a[i].maso<=p.maso&&i<r)i++;
          while(a[j].maso>=p.maso&&j>l)j--;
          if(i>=j)
          {
             swap(a[j],a[l]);
             return j;
          }
          else swap(a[i],a[j]);
       }
    }
    void quick_sort(hang *a,int l,int r)
    {
       if(l<r)
       {
          int p=partition(a,l,r);
          quick_sort(a,l,p-1);
          quick_sort(a,p+1,r);
       }
    }
    int binary_search(hang *a,int left,int right,int k)
    {
       int mid;
       while(left<=right)
       {
          mid=(left+right)/2;
          if(a[mid].maso==k)return mid;
          if(a[mid].maso==k)left=mid+1;
           else right=mid-1;
       }
       return -1;
    }
    int main()
    {
      hang *a;
      int k;
      int m,n;
      printf("\n Nhap so luong cac mat hang:");
      scanf("%d",&n);
      a=(hang*)malloc(n*sizeof(hang));
      nhap(a,n);
      printf("\n Danh sach cac mat hang da nhap:\n");
      xuat(a,n);
      printf("\n Nhap ma so mat hang can tim kiem:");
      scanf ("%d",&k);
      printf("\n Danh sach mat hang sau khi tim kiem(theo ma mat hang):\n");
      printf("\n-Ma so----------Ten---------------Loai");
    //  m=search(a,n,k);
      quick_sort(a,1,n);
      m=binary_search(a,1,n,k);
      if(m==-1)printf("\n Ban oi ko co ^_^ !");
      else
           printf("\n %-15d%-20s%-20s",a[m].maso,a[m].ten,a[m].loai);
      getch();
      return 0;
    }
    Câu 4: Liệt kê tất cả các hoán vị các phần tử của mảng a={1,2,...,n}.
    Code:
    #include<conio.h>
    #include<stdio.h>
    #include<malloc.h>
    #include<math.h>
    int songuyento(int n)
    {
      int i;
      if(n<=1)return 0;
      for(i=2;i<=n/2;i++)
      if(n%i==0)return 0;
      return 1;
    }
    void swap(int &a,int &b)
    {
       int tg=a;
       a=b;
       b=tg;
    }
    int sohoanhao(int n)
    {
        int i,m,t=0;
        if(n<=1)return 0;
        for(i=1;i<=n/2;i++)
            if(n%i==0)t=t+i;
        if(t==n)return 1;
        return 0;
    }
    void inmang(int *a,int n)
    {
       int i,tong;
        for(i=1;i<n;i++)
        {
        tong=a[i]+a[i+1];
    //    if(songuyento(tong))
    //    if(sohoanhao(tong))
          {
          for(i=1;i<=n;i++)
            printf("%3d",a[i]);
          printf("\n");
          break;
          }
        }
    }
    void hoanvi(int *a,int n)
    {
     int i,k,dau,cuoi;
     for(i=1;i<=n;i++)
        a[i]=i;
     do
     {
      inmang(a,n);
      i=n-1;
      while(i>=1&&a[i+1]<a[i])i--;
      if(i>=1)
      {
        k=n;
        while(a[k]<a[i])k--;
        swap(a[i],a[k]);
        dau=i+1;
        cuoi=n;
        while(dau<cuoi)
        {
           swap(a[dau],a[cuoi]);
           dau++;
          cuoi--;
        }
      }
     }while(i>=1);
    }
    int main()
    {
       int *a,n;
       printf("\nNhap n=");
       scanf("%d",&n);
       a=(int*)malloc(n*sizeof(int));
       hoanvi(a,n);
       getch ();
       return 0;
    }
    Câu 5: Liệt kê tất cả các dãy nhị phân n phần tử thỏa mãn một trong các điều kiện sau: biểu diễn thập phân của dãy nhị phân là số hoàn hảo (hoặc số nguyên tố), dãy nhị phân không tồn tại 3 (hoặc 2) phần tử liền kề giống nhau, tồn tại 2 phần tử liền kề giống nhau.
    Code:
    #include<stdio.h>
    #include<conio.h>
    #include<malloc.h>
    #include<math.h>
    int tong(int *a,int n)
    {
        int i,t=0;
        for(i=1;i<=n;i++)
         t+=a[i]*pow(2,n-i);
        return t;
    }
    int songuyento(int tong)
    {
        int i;
        if(tong<=1)return 0;
        for(i=2;i<=tong/2;i++)
        if(tong%i==0)return 0;
        return 1;
    }
    int sohoanhao(int tong)
    {
       int i,s=0;
       if(tong<=1)return 0;
       for(i=1;i<=tong/2;i++)
          if(tong%i==0)s+=i;
        if(s==tong)return 1;
        return 0;
    }
    int love(int *a,int n)
    {
    //Khong co 3 phan tu lien tiep giong nhau 
        int i;
        if(n<3)return 1;
        for(i=1;i<=n-2;i++)
        if(a[i]==a[i+1]&a[i]==a[i+2])return 0;
        return 1;
    }
    //cai nay hoi ao?!!!
    int hate(int *a,int n)
    {
          int i;
        if(n<2)return 1;
        for(i=1;i<n;i++)
    //yeu cau :2 phan tu lien tiep phai khac nhau
          if(a[i]==a[i+1])return 0;
        return 1;
    /*hay : chi can 2 phan tu lien tiep bat ki khac nhau la duoc ??? 
      if(a[i]!=a[i+1])return 1;
        return 0;
    */
    }
    void innghiem(int *a,int n)
    {
       int i;
    //   if(sohoanhao(tong(a,n)))
    //  if(songuyento(tong(a,n)))
    //  if(love(a,n))
    //  if(hate(a,n))
        {
        for(i=1;i<=n;i++)
         printf("%d",a[i]);
        printf("\n");
        }
    }
    void nhiphan(int*x,int n,int k)
    {
       int i;
        for(i=0;i<=1;i++)
         {
           x[k]=i;
            if(k==n)innghiem(x,n);
            else  nhiphan(x,n,k+1);
           }
    }
    int main()
    {
       int n,*x;
       printf("\nNhap N=");
       scanf("%d",&n);
       x=(int*)malloc(n*sizeof(int));
       nhiphan(x,n,1);
       getch();
       return 0;
    }
    Câu 6: Liệt kê tất cả các số nguyên từ 1 đến số lớn nhất có k chữ số (k nhập từ bàn phím) thỏa mãn điều kiện giá trị số đó là số nguyên tố, hoặc tổng các chữ số của số đó là số hoàn hảo, hoặc số đó không tồn tại 2 chữ số cạnh nhau giống nhau.
    Code:
    #include<stdio.h>
    #include<conio.h>
    #include<malloc.h>
    #include<math.h>
    int test(int *a,int n)
    {
      int i;
      if(n<2)return 1;
      for(i=1;i<=n;i++)
        if(a[i]==a[i+1])return 0;
      return 1;
    }
    int sohoanhao(int x)
    {
       int i,t=0;
       if(x<2)return 0;
       for(i=1;i<=x/2;i++)
         if(x%i==0)t+=i;
       if(t==x)return 1;
       return 0;
    }
    int songuyento(int x)
    {
       int i;
       if(x<2)return 0;
       for(i=2;i<=x/2;i++)
        if(x%i==0)return 0;
        return 1;
     }
    int so(int *a,int n)
    {
    //tinh gia tri cua so: VD 234->t=234
       int i;
       double t=0;
       for(i=1;i<=n;i++)
         t+=a[i]*pow(10,n-i);
       int y=(int)t; 
        return y;
    }
    int so1(int *a,int n)
    {
    // tinh tong cac chu so: VD 234->t=9
        int i,t;
        for(i=1;i<=n;i++)
        t+=a[i];
        return t;
    }
    void hthi(int*a,int n)
    {
       int i;
       if(a[1]!=0)
    //     if(songuyento(so(a,n)))
    //    if(sohoanhao(so1(a,n)))
        if(test(a,n))
         {
         for(i=1;i<=n;i++)
           printf("%d",a[i]);
          printf("\n");
          }
    }
    void songuyen(int *a,int n,int k)
    {
       int i;
       for(i=0;i<10;i++)
       {
         a[k]=i;
         if(k==n)hthi(a,n);
         else
           songuyen(a,n,k+1);
       }
    }
    int main()
    {
       int n,*a;
       printf("\n Nhap so phan tu K=");
       scanf("%d",&n);
       if(n>0)
       {
        a=(int *)malloc(n*sizeof(int));
         printf("\n so nguyen co %d chu so thoa man dieu kien:\n",n);
        songuyen(a,n,1);
       }
       getch();
       return 0;
    }
    duong.oriole
    duong.oriole
    Members
    Members


    Tổng số bài gửi : 3
    Ranh tiếng : 0
    Join date : 29/10/2011
    Age : 31

    ADMIN Re: Code đầy đủ cho vài bài trong đề cương PTTK :D

    Bài gửi by duong.oriole 11/12/2011, 20:50

    câu 8:

    1.
    Trình bày thuật toán tìm xâu con chung dài nhất của hai xâu.
    Áp dụng tìm xâu con chung dài nhất của hai xâu con sau: “CDADDADC”, “ACDDCCA”.





    Code:
    #include<stdio.h>
    #include<conio.h>
    #include<stdlib.h>
    #include<iostream>
    #include<string.h>
    #include<math.h>
    int max(int a,int b)
    {
        if(a>b)return a;
        else return b;
    }
    void inmang(int c[100][100],int m,int n )

    {
        int i,j;
        for(i=0;i<=m;i++)
        {
        for(j=0;j<=n;j++)
          printf("%4d",c[i][j]);
        printf("\n");
        }
         
    }
    void daychung(char a[100],char b[100])
    {
        int n=strlen(a),m=strlen (b);
        int c[100][100],i,j;
        char kq[100];
       
        for(i=0;i<=m;i++)c[i][0]=0;
        for(j=0;j<=n;j++)c[0][j]=0;
       
        for(i=1;i<=m;i++)
          for(j=1;j<=n;j++)
          if(a[j-1]==b[i-1])
                  c[i][j]=c[i-1][j-1]+1;
          else c[i][j]=max(c[i-1][j],c[i][j-1]);
      printf("\n");
      inmang(c,m,n);
     
       
      printf("\n Do dai xau con chung lon nhat: %d",c[m][n]);
     
      i=m,j=n;
      while(i>0&&j>0)
      {
        if(a[j-1]==b[i-1])
          {
              kq[c[i][j]]=a[j-1];
              i=i-1;
              j=j-1;
          }
        else 
          if(c[i][j-1]==c[i][j]) j=j-1;
              else i=i-1;
      }
      printf("\n Day chung dai nhat :");
      for(i=1;i<=c[m][n];i++)
      printf("%c",kq[i]);
    }
    int main()
    {
        char a[100],b[100];
        printf("\nnhap day A  : ");
        fflush(stdin);
        gets(a);
        printf("\nnhap day B  : ");
        fflush(stdin);
        gets(b);
        daychung(a,b);
        getch();
        return 0;
    }

    Sponsored content


    ADMIN Re: Code đầy đủ cho vài bài trong đề cương PTTK :D

    Bài gửi by Sponsored content


      Hôm nay: 28/3/2024, 21:55