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

Xem chủ đề cũ hơn Xem chủ đề mới hơn Go down

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

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

Click để tải trọn bộ Wink

duong.oriole
Members
Members

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

Về Đầu Trang Go down

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

Bài gửi by [T]rung on 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;
}

[T]rung
Admin
Admin

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

http://itisnotthat.wordpress.com/

Về Đầu Trang Go down

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

Bài gửi by duong.oriole on 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;
}

duong.oriole
Members
Members

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

Về Đầu Trang Go down

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

Bài gửi by Sponsored content Today at 14:44


Sponsored content


Về Đầu Trang Go down

Xem chủ đề cũ hơn Xem chủ đề mới hơn Về Đầu Trang

- Similar topics

 
Permissions in this forum:
Bạn không có quyền trả lời bài viết