Từ 1 tới 3 trên tổng số 3 kết quả

Đề tài: Các bài tập hay về C

  1. #1
    Ngày gia nhập
    09 2008
    Bài viết
    2

    Smile Các bài tập hay về C

    Các bài tập mình đã làm trong đợt ôn luyện chọn ra danh sách SV thi OLP tin học sinh viên của trường đại học Nha Trang. Mình post đề và các bài giải của mình lên để chúng ta cùng học hỏi lẫn nhau. Mong các bạn đóng góp ý kiến.
    BÀI 1: TỪ CHUẨN
    Một từ loại M là một dãy các chữ số, mỗi chữ số nằm trong khoảng từ 1 đến M. Số lượng các chữ số có mặt trong một từ được gọi là chiều dài của từ đó. Từ loại M được gọi là từ chuẩn nếu nó không chứa hai khúc (từ con) liền nhau mà giống nhau.
    Ví dụ:
    1213123 là từ chuẩn loại 3, chiều dài 7.
    1213213 không phải là từ chuẩn vì nó chứa liên tiếp hai từ con giống nhau là 213.
    Tương tự, 12332 không phải là từ chuẩn vì chứa liên tiếp hai từ con giống nhau là 3.
    Với mỗi cặp giá trị N và M cho trước, tìm mọi từ chuẩn loại M có chiều dài N.
    2  M  3; 1  N  40000.
    Dữ liệu vào: Tệp văn bản TC_INP.TXT gồm 10 dòng, mỗi dòng ghi hai số M và N.
    Dữ liệu ra: Tệp văn bản TC_OUT.TXT gồm 10 dòng – tương ứng với 10 dòng dữ liệu vào – cấu trúc mỗi dòng như sau:
     Số 0: Nếu không tìm được.
     Số T: Nếu tìm được và T là số từ chuẩn tìm được.
    BÀI 2: DÃY SỐ TỰ NHIÊN Xn
    Ứng với mỗi số tự nhiên x, ta có số tự nhiên f(x) bằng tổng bình phương các chữ số của x. Từ x ta xây dựng dãy (Xn) như sau:
    X1=x; X2=f(X1); X3=f(X2); …; Xn=f(Xn-1)=Xi với 0<i<n
    Ví dụ:
    x=12 ta có dãy :
    12, 5, 25, 29, 85, 89, 145, 42, 20, 4, 16, 37, 58, 89
    x=4 ta có dãy : 4, 16, 37, 58, 89, 145, 42, 20, 4
    x=13 ta có dãy : 13, 10, 1, 1
    Với hai số tự nhiên a, b (a<b<=30000), em hãy chỉ ra các số x (a<=x <=b) sao cho từ x ta có thể xây dựng được dãy (Xn) dài nhất trong các dãy được xây dựng.
    Dữ liệu vào: Tệp văn bản DS_INP.TXT có 10 dòng, mỗi dòng chứa hai số tự nhiên a, b.
    Kết quả ra: Tệp văn bản DS_OUT.TXT có 10 dòng – tương ứng với 10 dòng của dữ liệu vào – cấu trúc mỗi dòng như sau:
    - Số đầu tiên là độ dài của các dãy dài nhất.
    - Các số tiếp sau là số x, là số ta có thể xây dựng được dãy dài nhất.

    BÀI 3: BĂNG NHẠC
    Người ta cần ghi N bài hát, được mã số từ 1 đến N, vào một băng nhạc có thời lượng tính theo phút đủ chứa toàn bộ các bài đã cho. Với mỗi bài hát ta biết thời lượng phát của bài đó. Băng sẽ được lắp vào một máy phát nhạc đặt trong một siêu thị. Khách hàng muốn nghe bài hát nào chỉ việc nhấn phím ứng với bài đó. Để tìm và phát bài thứ i trên băng, máy xuất phát từ đầu cuộn băng, quay băng để bỏ qua i – 1 bài ghi trước bài đó. Thời gian quay băng bỏ qua mỗi bài và thời gian phát bài đó được tính là như nhau. Tính trung bình, các bài hát trong một ngày được khách hàng lựa chọn với số lần (tần suất) như nhau. Hãy tìm cách ghi các bài trên băng sao cho tổng thời gian quay băng trong mỗi ngày là ít nhất.
    Dữ liệu vào được ghi trong tệp văn bản tên BN_INP.TXT.
    - Dòng đầu tiên là số tự nhiên N cho biết số lượng bài hát.
    - Tiếp đến là N số nguyên dương thể hiện dung lượng tính theo phút của mỗi bài. Mỗi đơn vị dữ liệu cách nhau qua dấu cách.
    Thí dụ:
    BN_INP.TXT
    3
    7 2 3
    cho biết có N = 3 bài hát:
    - Bài 1 phát trong thời gian 7 phút.
    - Bài 2 phát trong thời gian 2 phút.
    - Bài 3 phát trong thời gian 3 phút.
    Dữ liệu ra được ghi trong tệp văn bản tên BN_OUT.TXT theo dạng thức sau:
    - N dòng đầu tiên thể hiện trật tự ghi bài hát trên băng.
    - Mỗi dòng gồm hai số nguyên dương j và d cách nhau bởi dấu cách, trong đó j là mã số của bài hát cần ghi, d là thời gian tìm và phát bài đó theo trật tự ghi này.
    - Dòng thứ n + 1 ghi tổng số thời gian quay băng nếu mỗi bài hát được phát một lần trong ngày.
    Với thí dụ trên, kết quả thu được sẽ như sau:
    BN_OUT.TXT
    2 2
    3 5
    1 12
    19
    Kết quả trên cho biết các thông tin sau:
    - Cần ghi lần lượt trên băng các bài theo trật tự sau: bài 2, bài 3, bài 1;
    - Để tìm và phát bài 2 cần 2 phút;
    - Để tìm và phát bài 3 cần 5 phút;
    - Để tìm và phát bài 1 cần 12 phút;
    - Tổng thời gian để tìm và phát mỗi bài một lần là: 19 phút.



    Code:
    #include<conio.h>
    #include<stdio.h>
    #include<stdlib.h>
    #include<fstream.h>
    #include<process.h>
    const char *INP="SODOCAO.INP";
    const char *OUT="SODOCAO.OUT";
    int h;
    int kq[400],so=0;
    void DocFile();
    void Tim();
    void GhiFile();
    main(){
    	DocFile();
    	Tim();
    		for(int i=1;i<=so;i++){
    		printf("  %d ",kq[i]);
    	   //	f>>kq[i]>>" ";
    		}
    	GhiFile();
    	return 0;
    }
    void DocFile(){
    	fstream f;
    	f.open(INP,fstream::in);
    	f>>h;
    	f.close();
    }
    void Tim(){
    	int amin,amax,bmin,bmax,con,x,y;
    	if(h<9)
    		amax=h;
    	else
    		amax=9;
    	if(h<18)
    		amin=0;
    	else
    		amin=h-18;
    	for(int a=amin;a<=amax;a++){
    		x=a*100;
    		con=h-a;
    		if(con<9)
    			bmax=con;
    		else
    			bmax=9;
    		if(con<9)
    			bmin=0;
    		else
    			bmin=con-9;
    		for(int b=bmin;b<=bmax;b++){
    			so++;
    			y=x+b*10+(con-b);
    			kq[so]=y;
    			}
    		}
    
    }
    void GhiFile(){
    	fstream f;
    	f.open(OUT,fstream::out);
    	for(int i=1;i<=so;i++){
    		f <<kq[i]<<" ";
    		}
    	f.close();
    }

  2. #2
    Ngày gia nhập
    09 2008
    Bài viết
    2

    Mặc định Các bài tập hay về C --Tiếp

    Đề mẫu
    Bài 1: Sắp theo chỉ dẫn (ABC.*)
    Cho xâu S gồm N kí tự tạo từ các chữ cái 'a'..'z'. ta gọi S là xâu mẫu. Từ xâu mẫu S này người ta tạo ra N xâu thứ cấp bằng cách dịch xâu S qua trái i vị trí theo dạng vòng tròn, tức là i kí tự đầu xâu lần lượt được chuyển về cuối xâu, i = 0, 1,…, N - 1. Như vậy xâu thứ cấp với i = 0 sẽ trùng với xâu mẫu S. Giả sử ta đã sắp tăng N xâu thu được theo trật tự từ điển. Hãy tìm xâu thứ k trong dãy.
    Tên chương trình: abc.*.
    Dữ liệu vào: tệp văn bản abc.inp có cấu trúc như sau:
    - Dòng thứ nhất chứa hai số tự nhiên N và k cách nhau qua dấu cách,
    6  N  500, 1  k  N. N cho biết chiều dài xâu S, k cho biết vị trí của xâu thứ cấp trong dãy được sắp tăng theo thứ tự từ điển.
    - Dòng thứ hai: xâu mẫu S.
    Dữ liệu ra: tệp văn bản abc.out gồm một dòng chứa xâu thứ k trong dãy được sắp.
    Thí dụ:
    abc.inp abc.out
    6 3
    Dabdec cdabde


    Bài 2: Tìm đường trong mê cung (MECUNG.*)
    Mê cung là một đồ thị vô hướng bao gồm N đỉnh, được mã số từ 1 đến N, với các cạnh, mỗi cạnh nối hai đỉnh nào đó với nhau. Cho hai đỉnh S và T trong một mê cung. Hãy tìm một đường đi bao gồm các cạnh gối đầu nhau liên tiếp bắt đầu từ đỉnh S, kết thúc tại đỉnh T sao cho không qua đỉnh nào quá một lần.
    Dữ liệu vào: Tệp văn bản tên MECUNG.INP với cấu trúc như sau:
    - Dòng đầu tiên, được gọi là dòng 0, chứa ba số tự nhiên N, S và T ghi cách nhau bởi dấu cách, trong đó N là số lượng đỉnh của mê cung, S là đỉnh xuất phát, T là đỉnh kết thúc.
    - Dòng thứ i, i = 1..(N - 1) cho biết có hay không cạnh nối đỉnh i với đỉnh j, j = (i + 1)..N.
    Thí dụ:
    MECUNG.INP
    9 6 7
    1 0 1 1 1 0 0 0
    1 1 0 0 0 0 0
    0 0 0 1 0 0
    0 1 1 0 0
    0 0 0 0
    0 0 0
    0 0
    1
    cho biết:
    - Dòng 0: 9 6 7 - mê cung gồm 9 đỉnh mã số 1..9, cần tìm đường đi từ đỉnh 6 đến đỉnh 7.
    - Dòng 1: 1 0 1 1 1 0 0 0 - đỉnh 1 được nối với các đỉnh 2, 4, 5, và 6. Không có cạnh nối đỉnh 1 với các đỉnh 3, 7, 8 và 9.
    - ...
    - Dòng 8: 1 – đỉnh 8 có nối với đỉnh 9.
    Đương nhiên, vì đồ thị là vô hướng nên cạnh nối đỉnh x với đỉnh y cũng chính là cạnh nối đỉnh y với đỉnh x.
    Thông tin về đỉnh N không cần thông báo, vì với mỗi đỉnh i ta chỉ liệt kê các đỉnh j > i tạo thành cạnh (i, j).
    Kết quả ra ghi trong tệp văn bản MECUNG.OUT:
    - Dòng đầu tiên ghi số tự nhiên k là số đỉnh trên đường đi từ s đến t, nếu vô nghiệm, ghi số 0.
    - Từ dòng tiếp theo ghi lần lượt các đỉnh có trên đường đi.
    Với thí dụ đã cho kết quả có thể là:
    MECUNG.OUT
    5
    6 1 2 3 7
    Từ đỉnh 6 có thể đến được đỉnh 7, qua 5 đỉnh theo đường bốn khúc:
    6  1  2  3  7.
    Với mê cung đã cho, nếu yêu cầu tìm đường đi từ đỉnh 6 đến đỉnh 9, tức là với dữ liệu vào như trên thì sẽ nhận được kết quả:
    MECUNG.OUT
    0

    với ý nghĩa là không có đường đi từ đỉnh 6 đến đỉnh 9, do mê cung đã cho không liên thông, đỉnh 6 và đỉnh 9 nằm trong hai vùng liên thông khác nhau.

    Bài 3: Lát nền (LATNEN.*)
    Người ta cần lát kín một nền nhà hình vuông cạnh dài n = 2k, (k là một số tự nhiên trong khoảng 1..6) khuyết một phần tư tại góc trên phải bằng những viên gạch màu hình thước thợ (chữ L) tạo bởi 3 ô vuông đơn vị như trong hình 2b. Hai viên gạch kề cạnh nhau dù chỉ 1 đơn vị dài phải có màu khác nhau. Hãy cho biết một cách lát với số màu ít nhất.

    Hình 2
    Dữ liệu vào: tệp văn bản LATNEN.INP chứa số tự nhiên n.
    Dữ liệu ra: tệp văn bản LATNEN.OUT. Dòng đầu tiên là hai số tự nhiên m biểu thị số viên gạch và c là số màu cần dùng cho việc lát nền. Tiếp đến là một phương án lát nền tìm được, trong đó mỗi viên gạch lát được tạo bởi ba chữ số giống nhau thể hiện màu của viên gạch đó. Các số trên mỗi dòng cách nhau qua dấu cách.
    LATNEN.INP LATNEN.OUT
    8 16 3
    3 3 1 1
    3 2 2 1
    1 2 3 3
    1 1 3 2
    3 3 1 2 2 3 1 1
    3 2 1 1 3 3 2 1
    1 2 2 3 1 2 2 3
    1 1 3 3 1 1 3 3
    Thí dụ, với n = 8 ta có một cách lát nền như sau:
    3 3 1 1
    3 2 2 1
    1 2 3 3
    1 1 3 2
    3 3 1 2 2 3 1 1
    3 2 1 1 3 3 2 1
    1 2 2 3 1 2 2 3
    1 1 3 3 1 1 3 3
    Hình 3. Nền nhà với n = 8
    Đây là bài toán lát nền
    Code:
    #include<conio.h>
    #include<stdio.h>
    #include<process.h>
    #include<fstream.h>
    #include<stdlib.h>
    const char *INP="LATNEN.INP";
    const char *OUT="LATNEN.OUT";
    int N,nuaN,a[64][64];
    void DocFile();
    void KhoiTao();
    void DichTrai(int c);
    void LatPhai();
    void LatLen();
    void XuLi();
    void GhiFile(int mau);
    void main(){
    
    }
    void DocFile(){
    	fstream f;
    	f.open(INP,fstream::in);
    	f>>N;
    	nuaN=N/2;
    	f.close();
    }
    void KhoiTao(){
    	a[N-1][1]=1;
    	a[N-1][2]=2;
    	a[N][1]=1;
    	a[N][2]=1;
    }
    void DichTrai(int c){
    	for(int i=1;i<=c;i++)
    		for(int j=1;j<=c;j++)
    			a[N-1-i][j+2]=a[N+1-i][j];
    
    }
    void LatPhai(int c){
    	for(int i=N-c+1;i<=N;i++)
    		for(int j=1;j<=c;j++){
    			a[i][2*c+1-j]=a[i][j];
    			if(a[i][j]==1) a[i][2*c+1-j]=3;
    			if(a[i][j]==3) a[i][2*c+1-j]=1;
    		}
    }
    void LatLen(int c){
    	for(int i=1;i<=c;i++)
    		for(int j=1;j<=c;j++){
    			a[N-2*c+i][j]=a[N-i+1][j];
    			if(a[N-i+1][j]==1) a[N-2*c+i][j]=3;
    			if(a[N-i+1][j]==3) a[N-2*c+i][j]=1;
    
    		}
    }
    void XuLi(){
    	int lap,c;
    	if(N==2) GhiFile(1);
    	else{
    		c=1;
    		lap=1;//1 tuong ung la true
    		while(lap){
    			c*=2;
    			if(c<nuaN) DichTrai(c);
    			LatPhai(c);
    			LatLen(c);
    			if(c=nuaN) lap=0;//thoat khoi vong while
    			}
    		}
    	GhiFile(3);
    
    
    
    }
    void GhiFile(int mau){
    	fstream f;
    	f.open(OUT,fstream::out);
    	for(int i=1;i<=nuaN;i++)//
    		for(int j=1;j<=nuaN;j++)
    			f<<a[i][j];
    }
    Code:
    #include<conio.h>
    #include<stdio.h>
    #include<process.h>
    #include<fstream.h>
    const char *INP="BN_INP.TXT";
    const char *OUT="BN_OUT.TXT";
    int n,so;	//n la so bai hat
    int a[100],ID[100];
    void DocFile();
    void GhiFile();
    void InitID();
    void IdQuickSort(int m,int n);
    main(){
    	DocFile();
    	InitID();
           IdQuickSort(1,n);
    	GhiFile();
    	return 0;
    }
    void DocFile(){
    	fstream f;
    	f.open(INP,fstream::in);
    	f>>n;
    	for(int i=1;i<=n;i++)
    		f>>a[i];
    	f.close();
    }
    void InitID(){
    	for(int i=1;i<=n;i++)
    		ID[i]=i;
    }
    void IdQuickSort(int m, int n){
    	int left,right,mid,tam;
    	left=m;
    	right=n;
    	mid=a[ID[(left+right)/2]];//Lay phan tu giua
    	while(left<right){
    		while(a[ID[left]]<mid) left++;
    		while(a[ID[right]]>mid) right--;
    		if(left<right){
    			tam=ID[left];
    			ID[left]=ID[right];
    			ID[right]=tam;
    			left++;
    			right--;
    			}
    		}
    	if(m<right) IdQuickSort(m,right);
    	if(left<n) IdQuickSort(left,n);
    }
    void GhiFile(){
    	fstream f;
    	f.open(OUT,fstream::out);
    	int t=0,tt=0;
    	for(int i=1;i<=n;i++){
    		t+=a[ID[i]];
    		tt+=t;
    		f<<ID[i]<<" "<<t<<"\n";
    	}
    	f<<tt;
    	f.close();
    }

  3. #3
    Ngày gia nhập
    09 2008
    Bài viết
    2

    Mặc định Các bài tập hay về C --Tiếpnua

    Cho dãy số. dãy con là dãy mà các phần tử lấy từ dãy đã cho.
    ví dụ:Cho dãy 3 11 45 32 23 2 4 6 8
    Dãy 3 11 32 là dãy con. Dãy 11 45 33 không phải là dãy con.
    Dãy chia hết là dãy mà các phần tử liền sau chia hết cho các phần tử liền trước đó
    Vd: 2 4 6 8
    Tìm dãy đoạn con chia hết dài nhất
    Code:
    #include<conio.h>
    #include<stdio.h>
    #include<fstream.h>
    #include<process.h>
    #include<stdlib.h>
    const char *INP="SEQ.INP" ;
    const char *OUT="SEQ.OUT" ;
    int N,*a,M,*id;
    void DocFile();
    int SEQCON();
    void GhiFile();
    void main(){
    	DocFile();
    	M=SEQCON();
    	GhiFile();
    }
    void DocFile(){
    	fstream f;
    	f.open(INP,fstream::in);
    	f>>N;
    	printf("N=%d\n",N);
    	a=(int*)malloc(sizeof(int)*N);
    	for(int i=1;i<=N;i++){
    		f>>a[i];
    		printf("a[%d]=%d  ",i,a[i]);
    		}
    	f.close();
    }
    int SEQCON(){
    	int x,d,vt,lap,Max;
    	for(int i=1;i<=N-1;i++)
    		for(int j=i+1;j<=N;j++){
    			x=a[i];
    			d=1;
    			vt=j;
    			lap=1;//1 tuong ung la true
    			while(lap){
    				if(a[vt]%x==0){
    					x=a[vt];
    					vt++;
    					d++;
    					}
    				else{
    					vt++;
    					}
    				if(vt>=N+1){
    					if(Max<d) Max=d;
    					lap=0;//0 tuong ung la false
    					}
    				}
    			}
    	return Max;
    }
    void InitID(){
    	id=(int*)malloc(sizeof(int)*N);
    	for(int i=1;i<=N;i++)
    		id[i]=-1;
    }
    void GhiFile(){
    	fstream f;
    	f.open(OUT,fstream::out);
    	f<<M;
    	f.close();
    }
    Bài toán Chia mảng:
    Chia mảng thành hai phần sao cho tổng phần truớc gấp k lần phần sau
    Code:
    #include<conio.h>
    #include<process.h>
    #include<stdio.h>
    int a[50],n,k;
    int chia=0;
    int d1,c1,T1,d2,c2,T2;
    void NhapMang();
    int Tong(int a[],int d, int c);
    void Chia();
    main(){
    	clrscr();
    	NhapMang();
    	Chia();
    	if(chia==1){
    		printf("Mang chia duoc.\n");
    		printf("%d\n",chia);
    		printf("d1=%d c1=%d T1=%d \n",d1,c1,T1);
    		printf("d2=%d c2=%d T2=%d",d2,c2,T2);
    	}
    	else
    		printf("Khong chia duoc.");
    	getch();
    return 0;
    }
    void Chia(){
    	int td,tt,ts;
    //td la tong cua ca mang. tt la tong cua doan truoc.
    //ts la tong cua doan sau
    	td=Tong(a,1,n);
    	for(int i=1;i<=n;i++){
    		tt=Tong(a,1,i);
    		ts=td-tt;
    		//neu tong truoc nho hon tong sau
    		if((tt*(k+1))==td){
    			chia=1;
    			d1=1;
    			c1=i;
    			T1=tt;
    			d2=i+1;
    			c2=n;
    			T2=ts;
    			}
    		//neu tong sau nho hon tong truoc
    		if((ts*(k+1))==td){
    			chia=1;
    			d1=n-i;
    			c1=n;
    			T1=ts;
    			d2=1;
    			c2=i-1;
    			T2=tt;
    			}
    		}
    }
    void NhapMang(){
    	printf("So phan tu cua mang:");
    	scanf("%d", &n);
    	printf("Ti le cua mang can chia:");
    	scanf("%d",&k);
    	//Nhap mang
    	for(int i=1;i<=n;i++){
    		printf("a[%d]=",i);
    		scanf("%d",&a[i]);
    	}
    }
    int Tong(int a[],int d,int c){
    	int t=0;
    	for(int i=d;i<=c;i++)
    		t+=a[i];
    	return t;
    }
    Đây là cách viết theo Đọc dữ liệu từ File và xuất kết quả ra file.
    Code:
    #include<conio.h>
    #include<stdio.h>
    #include<fstream.h>
    #include<process.h>
    const char *INP="CHIADOAN.INP";
    const char *OUT="CHIADOAN.OUT";
    int n,k;	// n la so phan tu cua mang can chia
    //k la ti le can chia
    int a[500];
    int kq,d1,c1,T1,d2,c2,T2;
    void DocFile();
    void GhiFile();
    int Tong(int m, int n);
    void Chia();
    main(){
    	DocFile();
    	Chia();
    	GhiFile();
    	return 0;
    }
    int Tong(int m,int n){
    	int t=0;
    	for(int i=m;i<=n;i++)	t+=a[i];
    	return t;
    }
    void DocFile(){
    	fstream f;
    	f.open(INP,fstream::in);
    	//Doc du lieu cho bien n va cho bien k
    	f >>n>>k;
    	//Doc cac phan tu cho mang
    	for(int i=1;i<=n;i++)
    		f>>a[i];
    	f.close();
    }
    void Chia(){
    	kq=0; //Gia su khong chia duoc
    	int td=0,tt=0,ts=0;
    	//Tinh tong cac phan tu cua mang can chia
    	td=Tong(1,n);
    	//Tinh tong cac phan tu cua doan truoc
    	for(int i=1;i<=n;i++){
    		tt=Tong(1,i);
    		ts=td-tt;
    		if(tt*(k+1)==td||ts*(k+1)==td){
    			kq=1;	//Chia duoc
    			d1=1;
    			c1=i;
    			T1=tt;
    			d2=i+1;
    			c2=n;
    			T2=ts;
    			}
    		}
    
    }
    
    void GhiFile(){
    	fstream f;
    	f.open(OUT,fstream::out);
    	if(kq==0)
    		f<<kq;
    	else{
    		f<<kq<<"\n";
    		f<<d1<<" "<<c1<<" "<<T1<<"\n";
    		f<<d2<<" "<<c2<<" "<<T2<<"\n";
    	}
    	f.close();
    }
    Đã được chỉnh sửa lần cuối bởi studylanguageC : 31-10-2008 lúc 04:20 PM. Lý do: Bổ sung

Quyền hạn của bạn

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