Bài toán dãy con lớn nhất ngôn ngữ c
/*
Doc tu file Array.in
Dong 1: So luonng phan tu n = ? va k = ?
DOng 2: Danh sach cac phan tu
Tim Day con co k phan tu lien tiep --> Tong lon nhat
*/
#include<stdio.h>
void readFile(FILE *fp, int a[], int n);
void writeFile(int index, int k, int a[100]);
void maxSum(int a[100], int n, int k);
void Display(int a[100], int n);
void Init(int b[100], int a[100], int n);
void maxSum1(int b[100], int n, int k, int a[100]);
int main(){
int a[100];
int n, k;
int b[100];
FILE *fpInput;
FILE *fpOutput;
fpInput = fopen("SequenceMax.txt", "r");
if(fpInput == NULL){
printf("\n Can't this file!");
}
else{
fscanf(fpInput, "%d %d", &n, &k);
readFile(fpInput, a, n);
fclose(fpInput);
}
Display(a, n);
printf("\n --------Thuat toan 1: Thoi gian O(n*n)------------");
maxSum(a, n, k);
printf("\n --------Thuat toan 2: Thoi gian O(n)------------");
Init(b, a, n);
maxSum1(b, n, k, a);
}
/* Doc du lieu tu file */
void readFile(FILE *fp, int a[100], int n){
int i;
for(i = 0; i < n; i++){
fscanf(fp, "%d", &a[i]);
}
}
/* Ghi Du lieu ra file */
void writeFile(int index, int k, int a[100]){
FILE *fpOutput = fopen("DanhSachConLonNhat.out", "w");
int i;
for(i = index; i < index + k; ++i){
fprintf(fpOutput, "%2d", a[i]);
}
fclose(fpOutput);
}
/* In du lieu ra man hinh */
void Display(int a[100], int n){
int i;
printf("\n Day so %d phan tu ban dau la: ", n);
for(i = 0; i < n; i++){
printf("%5d", a[i]);
}
}
/* Day con co k phan tu lien tiep --> Tong lon nhat */
void maxSum(int a[100], int n, int k){
int i;
int max = 0;
int c;
int sum[100] = {}; // Mang luu tong cac phan tu
int index = 0; // Luu chi so cua day lon nhat
/* Khoi tao max ban dau */
for(i = 0; i < k; i++){
max += a[i];
}
/* Luu tong cac day con k phan tu vao mang Sum[100] */
for(i = 0; i <= n-k; i++){
/* Tinh tong sum de so sanh voi max */
for(c = i; c < k+i; c++){
sum[i] += a[c];
}
if(max < sum[i]){
max = sum[i];
index = i;
}
if(i == n-k){
printf("\n Day con lien tiep co %d phan tu co tong lon nhat bang %d ", k, max);
printf("\n");
for(c = index; c < index + k; c++){
printf(" %3d", a[c]);
}
}
}
}
/* ----------------------------------------------------------------------------------------*/
/* Tao mang b[100] co phan tu b[i] la tong i+1 phan tu dau cua mang a[100] */
void Init(int b[100], int a[100], int n){
int i;
/* Khoi tao mang B[0] */
b[0] = a[0];
/* Tao mang B[i] */
for(i = 0; i < n; i++){
b[i] = b[i-1] + a[i];
}
}
/* Tim Day con co k phan tu lien tiep tong max */
void maxSum1(int b[100], int n, int k, int a[100]){
int i;
int index = 0;
int max = b[k-1];
int maxSum;
for(i = 0; i < n-k; i++){
maxSum = b[i+k] - b[i];
if(maxSum > max){
max = maxSum;
index = i + 1;
}
}
printf("\n Day con lien tiep co %d phan tu co tong lon nhat bang %d ", k, max);
printf("\n");
for(i = index; i < index + k; i++){
printf(" %3d", a[i]);
}
writeFile(index, k, a);
}
10 2
3 -2 5 -8 0 9 -9 10 -12 14
