2013-01-23 18:11:38Morris
[資料結構][作業] dijkstra、矩陣乘法、eigenvalue
FinalExerciseA-page-001.jpg
FinalExerciseA-page-002.jpg
PartI.cpp
#include <stdio.h>
#include <math.h>
class Matrix {
public:
long long v[3][3]; // fixed
void scan() {
puts("Input 3x3 matrix: (integer entity)");
int i, j;
for(i = 0; i < 3; i++)
for(j = 0; j < 3; j++)
scanf("%lld", &v[i][j]);
}
void print() {
int i, j;
for(i = 0; i < 3; i++, puts(""))
for(j = 0; j < 3; j++)
printf("%lld ", v[i][j]);
}
Matrix operator+(const Matrix &y) {
Matrix z;
int i, j;
for(i = 0; i < 3; i++)
for(j = 0; j < 3; j++)
z.v[i][j] = v[i][j] + y.v[i][j];
return z;
}
Matrix operator*(const Matrix &y) {
Matrix z;
int i, j, k;
for(i = 0; i < 3; i++)
for(j = 0; j < 3; j++) {
z.v[i][j] = 0;
for(k = 0; k < 3; k++)
z.v[i][j] += v[i][k]*y.v[k][j];
}
return z;
}
long long det() {
return v[0][0]*v[1][1]*v[2][2]+v[0][1]*v[1][2]*v[2][0]+v[0][2]*v[1][0]*v[2][1]
-v[0][2]*v[1][1]*v[2][0]-v[1][2]*v[2][1]*v[0][0]-v[2][2]*v[1][0]*v[0][1];
}
void eigenvalue() { // x^3 + ax^2 + bx + c
long long a, b, c, ta, tb, tc;
a = -(v[0][0]+v[1][1])-v[2][2];
b = v[0][0]*v[1][1]+v[2][2]*(v[0][0]+v[1][1])-v[0][2]*v[2][0]-v[1][2]*v[2][1]-v[0][1]*v[1][0];
c = -v[0][0]*v[1][1]*v[2][2]+v[0][2]*v[1][1]*v[2][0]+v[0][0]*v[1][2]*v[2][1]+v[0][1]*v[1][0]*v[2][2]
-v[0][1]*v[2][0]*v[1][2]-v[0][2]*v[1][0]*v[2][1];
printf("Characteristic polynomial: x^3 + %lldx^2 + %lldx + %lld\n", a, b, c);
printf("eigenvalue = ");
tc = c;
if(c < 0) tc = -c;
for(long long i = -tc; i <= tc; i++) {
if(i == 0 || c%i == 0) {
if(i*i*i+a*i*i+b*i+c == 0) {
printf("%lf ", (double)i);
ta = a+i;
tb = b+a*i+i*i;
if(ta*ta-4*tb < 0)//bb-4ac
break;
printf("%lf %lf", (double)(-ta-sqrt(ta*ta-4*tb))/2.0
, (double)(-ta+sqrt(ta*ta-4*tb))/2.0);
break;
}
}
}
puts("");
}
};
int main() {
Matrix A, B, C, D;
A.scan();
B.scan();
C = A+B;
puts("------");
puts("1. A+B"), C.print();
D = A*B;
puts("------");
puts("2. AB"), D.print();
puts("------");
puts("3. det(AB)"), printf(" = %lld\n", D.det());
puts("------");
puts("4. Find Matrix A & Matrix B's eigenvalues");
puts("A : ");
A.eigenvalue();
puts("B : ");
B.eigenvalue();
return 0;
}
/*
3 0 -1
2 3 1
-3 4 5
1 2 2
3 -2 1
0 1 1
*/
PartII.cpp
#include <stdio.h>
#include <stdlib.h>
int g[7][7] = { // adjacency matrix
{0,1,2,0,1,0,0}, // A
{1,0,0,3,0,0,0}, // B
{2,0,0,0,1,2,0}, // C
{0,3,0,0,0,1,0}, // D
{1,0,1,0,0,0,5}, // E
{0,0,2,1,0,0,3}, // F
{0,0,0,0,5,3,0}, // G
};
//<BFS>
#define SIZE 128
void BFS() {
int i;
int QUEUE[SIZE], front = 0, rear = 0;
int preND[SIZE], visited[SIZE];
for(i = 0; i < 7; i++)
visited[i] = 0;
QUEUE[0] = 0, preND[0] = -1, visited[0] = 1; // A
while(front <= rear) {
int from = QUEUE[front];
for(i = 0; i < 7; i++) {
if(g[from][i] != 0 && visited[i] == 0) {
preND[i] = from;
visited[i] = 1;
QUEUE[++rear] = i;
//<print path>
int buffer[SIZE], idx = 0, nd = i;
while(nd != -1)
buffer[idx++] = nd, nd = preND[nd];
for(idx--; idx >= 0; idx--) {
printf("%c", buffer[idx]+'A');
if(idx) printf("->");
}
puts("");
//</print path>
}
}
front++;
}
puts("Search Terminated");
printf("Final Path: ");
//<print path>
int buffer[SIZE], idx = 0, nd = 6;
while(nd != -1)
buffer[idx++] = nd, nd = preND[nd];
for(idx--; idx >= 0; idx--) {
printf("%c", buffer[idx]+'A');
if(idx) printf("->");
}
puts("");
//</print path>
}
//</BFS>
//<Dijkstra>
void Dijkstra() {
int D[SIZE], preND[SIZE], used[SIZE];
int i, j;
for(i = 0; i < 7; i++)
D[i] = 0xffff, used[i] = 0;
D[0] = 0, preND[0] = -1, used[0] = 1;
for(i = 0; i < 7; i++) {
if(g[0][i]) {
if(D[i] > D[0]+g[0][i]) {
D[i] = D[0]+g[0][i];
preND[i] = 0;
}
}
}
for(i = 0; i < 7-1; i++) {
int mn = 0xffff, next = -1;
for(j = 0; j < 7; j++) {
if(used[j] == 0 && D[j] < mn)
mn = D[j], next = j;
}
for(j = 0; j < 7; j++) {
if(g[next][j]) {
if(D[j] > D[next]+g[next][j]) {
D[j] = D[next]+g[next][j];
preND[j] = next;
}
}
}
used[next] = 1;
//<print path>
int buffer[SIZE], idx = 0, nd = next;
while(nd != -1)
buffer[idx++] = nd, nd = preND[nd];
for(idx--; idx >= 0; idx--) {
printf("%c", buffer[idx]+'A');
if(idx) printf("->");
}
//</print path>
printf(" cost:%d\n", D[next]);
}
puts("Search Terminated");
printf("Final Path: ");
int buffer[SIZE], idx = 0, nd = 6;
while(nd != -1)
buffer[idx++] = nd, nd = preND[nd];
for(idx--; idx >= 0; idx--) {
printf("%c", buffer[idx]+'A');
if(idx) printf("->");
}
//</print path>
printf(" total cost:%d\n", D[6]);
}
//</Dijkstra>
int main() {
BFS();
puts("=====");
Dijkstra();
system("pause");
return 0;
}