#include <stdio.h>
#include <conio.h>
#include <stdlib.h>
int s = 1;//tim kc nn tu s den tat ca cac dinh
int const max = 20;
int a[max];//day so cho truoc
int mtk[max][max], n;
int d[max][max];//d[i][j]:kcnho nhât tu ai den aj
int p[max][max];//p[i][j]:dinh truoc dinh j tren duong nn tu i den j
int const avc = -100; //am vo cuc
void DocFile() {
int x;
FILE *f = fopen("E:\\daytang.txt", "r");// ta mở tập tin daytang.txt"kiểm tra xem nếu tập tin bằng null thì
if (f == NULL) { //file ko tồn tại còn ngược lại trả về EOF(-1)
printf("\nFile %s khong co");
}
n = 0;
while (fscanf(f, "%d", &x) != EOF) //
a[++n] = x;
fclose(f);
}
void matranke()
{
int i,j;
for (i = 1; i <= n; i++)
for (j = 1; j <= n; j++)
if (i == j)
mtk[i][j] = 0;
else mtk[i][j] = avc;
for (i = 1; i<n; i++)
for (j = i + 1; j <= n; j++)
if (a[i] <= a[j])
mtk[i][j] = 1;
else
mtk[i][j] = -1;
}
void Floyd() { //đường đi ngắn nhất
int i, j, k;
for (i = 1; i <= n; i++)
for (j = 1; j <= n; j++) {
d[i][j] = mtk[i][j];
p[i][j] = i;
}
for (k = 1; k <= n; k++)
for (i = 1; i <= n; i++)
for (j = 1; j <= n; j++)
if (d[i][j]<d[i][k] + d[k][j]) {
d[i][j] = d[i][k] + d[k][j];
p[i][j] = p[k][j];
}
}
void main() {
int i, j, k, i0, j0;
DocFile();
matranke();
for (i = 1; i <= n; i++)
printf("%3c%d", 'a', i);
printf("\n");
for (i = 1; i <= n; i++)
printf("%4d", a[i]);
Floyd();
printf("\nDay con khong giam dai nhat: ");
k = avc;
for (i = 1; i <= n; i++)
for (j = 1; j <= n; j++)
if (d[i][j]>k) {
k = d[i][j];
i0 = i;
j0 = j;
}
k = j0;
while (k != i0) {
printf("a%d-->",k);
k = p[i0][k];
}
printf("a%d: chieu dai=%d", i0, d[i0][j0] + 1);
printf("\n");
system("pause");
}
Và
printf("\nDay con khong giam dai nhat: ");
k = avc;
for (i = 1; i <= n; i++)
for (j = 1; j <= n; j++)
if (d[i][j]>k) {
k = d[i][j];
i0 = i;
j0 = j;
}
k = j0;
while (k != i0) {
printf("a%d-->",k);
k = p[i0][k];
}
printf("a%d: chieu dai=%d", i0, d[i0][j0] + 1);
printf("\n");