2 posters
Code đầy đủ cho vài bài trong đề cương PTTK :D
duong.oriole- Members
- Tổng số bài gửi : 3
Ranh tiếng : 0
Join date : 29/10/2011
Age : 31
[T]rung- Admin
- Tổng số bài gửi : 69
Ranh tiếng : 2
Join date : 30/10/2010
Age : 31
Đến từ : Haiphong, Vietnam
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.
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;
}
- 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;
}
- 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;
}
- 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;
}
- 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;
}
- 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- Members
- Tổng số bài gửi : 3
Ranh tiếng : 0
Join date : 29/10/2011
Age : 31
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”.
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;
}
|
|