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ác bài tập hay về C
Trả lời cùng với trích dẫn
Các bài tập hay về C --Tiếp
