- 在线时间
- 3 小时
- 最后登录
- 2017-8-7
- 注册时间
- 2011-2-27
- 听众数
- 2
- 收听数
- 0
- 能力
- 0 分
- 体力
- 21 点
- 威望
- 0 点
- 阅读权限
- 20
- 积分
- 7
- 相册
- 0
- 日志
- 0
- 记录
- 0
- 帖子
- 1
- 主题
- 1
- 精华
- 0
- 分享
- 0
- 好友
- 0
升级   2.11% 该用户从未签到
 |
#include "stdio.h"/ {& x0 Q% S5 D! J, y, E
#include "string.h"9 i" l I3 i4 [+ p7 a3 ~7 o
#define N 50 ) X4 Y8 Z& U- [& U2 ^ h7 R' M
int jisuan(int a[N][N][N],int h,int z,int i,int j);
4 e) b1 K7 `; g: u1 t9 j$ k1 z evoid micifang(int a[N][N][N],int h,int t);
\/ _3 ?; ?. H Nvoid buer(int a[N][N][N],int h);# E1 X1 v" k- Y b+ _) J
void warshall(int a[N][N][N],int h);
) z) S; v9 }0 ^/ y `- b- Pmain()6 `* N$ L# T" k P- i F1 _
{3 Q2 S! z5 a7 a3 {2 R' k8 r
int i,h,j,t;
2 g, O; h) o. Aint a[N][N][N];3 M/ {, e# l4 Z( k2 e5 _
printf("请输入邻接矩阵A的行数(或列数):\n");3 s4 n' v/ c6 W F' u/ w& F
scanf("%d",&h);( w+ S: \7 J5 l+ `5 T- y
printf("\n请输入邻接矩阵A:\n\n");
2 J( m' C3 x$ N, Vfor(i=0;i<h;i++); q7 M: A$ m) m2 c f
{5 m+ R4 q* M- K+ T4 B/ c& ~; @4 u
printf("请输入邻接矩阵A的第%d行.\n",i+1);
& Q7 ~8 O' Y* O2 f1 G# `) a# X- Ffor(j=0;j<h;j++)9 [9 J" A# i; c' N3 q: ^- h
scanf("%d",&a[0][i][j]); 1 T1 ?" ~! z2 \# b3 L: ~6 r
}
$ H) a3 W9 m( j0 N1 k6 g; U& Hprintf("\n邻接矩阵A为:\n");; J; z0 i: t$ a* Z$ L, g9 f8 u; N
for(i=0;i<h;i++)
9 q- w& N# g. A9 O{
7 G( F0 f. @, r1 F* hfor(j=0;j<h;j++)
& a# T, D( v( X9 ]. Y, I5 Z2 rprintf(" %d ",a[0][i][j]);
/ ?, v& Y/ l( D. y, vprintf("\n");
i' _. f* H+ i+ l/ }}# v( O$ P. c2 g. R: }3 ] c" Q% h
printf("\n\n\n算法一:\n");: {3 ]! {( S( v$ ~ G
printf("\n矩阵A的1次方为:\n");
( }4 h1 j+ g5 B1 n, ] s" ~for(i=0;i<h;i++)
* X; I$ y: g" v( l{
9 {9 I$ j6 r; o& C3 |for(j=0;j<h;j++)7 S- f$ t$ _5 A3 s
printf(" %d ",a[0][i][j]);! Q3 ~( v) x& U. ` |. q
printf("\n");- @+ k, ]2 C- K" z+ m, L
}
* p8 p# K$ O9 ~, Z; o8 N; amicifang(a,h,2);
9 u3 d* o+ c8 H) ^% N; ^for(i=0;i<h;i++)% P$ p9 e% A2 G9 d2 r8 k
for(j=0;j<h;j++)" c) X5 a, A( S* i
a[h][i][j]=0; //全部赋值为0!2 g( k6 [, ?, K& N( g2 @9 `3 |5 c8 ?
for(i=0;i<h;i++)
/ \* T1 x& g5 J: n: J+ mfor(j=0;j<h;j++)
3 |. N/ Q" F+ [9 n7 i `for(t=0;t<h;t++); K% P4 s# F. u3 {
a[h][i][j]=a[h][i][j]+a[t][i][j];0 m/ T/ I$ j1 T* k2 _
printf("\n\nB的值如下:\n");2 M6 X3 Y" o, \3 `
for(i=0;i<h;i++)" p/ f, m4 Z d
{+ K6 S& U0 e8 W$ }+ m* O- } P
for(j=0;j<h;j++)- ]/ w2 f* L- @9 Q$ v
printf(" %d ",a[h][i][j]);
! j$ Y5 ~ }) w, P. U6 sprintf("\n");; [9 |/ i/ J8 `- p5 R1 V5 a
}/ d6 ^) z8 y6 {( `/ i
printf("\n\n\n算法二:\n");
( @) L: t: n9 Y5 L, b) K1 Fprintf("\n矩阵A的1次布尔幂次方为:\n");: g$ L2 Q* h1 R
for(i=0;i<h;i++)9 w1 H: o7 Z! N+ }; C& f& T& g
{% [2 L; ~( J# w# `/ t
for(j=0;j<h;j++)1 e% K6 G$ T7 C" c
{% F; X; j" \% u! Q
if(a[0][i][j]>1)% K7 w% Z2 j5 _$ z4 K
a[0][i][j]=1;+ @9 g& V" Q* _- f0 v y
printf(" %d ",a[0][i][j]);' q+ a9 M* E2 n- T2 g! H3 v
}) A; ^, C' l B' n/ w
printf("\n");7 {& b8 t( W* e" y" f& M% b6 S
}: O* K y" g& x2 |5 V
buer(a,h,2);
+ _# W9 f4 b) }5 Oprintf("\n\nP的值如下:\n");9 ?7 n7 m) `) D" @- O: {) `3 |
for(i=0;i<h;i++)/ w2 b6 }/ G, y9 ^/ U+ v* |
{6 ?. T5 ~+ r0 u5 w" P
for(j=0;j<h;j++)3 E5 Q$ Z" }! ]1 m1 N
{ 9 V4 H" a9 Y0 N Z) I- O# O
if(a[h][i][j]>1)/ J: u0 d: ~0 y! w
a[h][i][j]=1;3 h7 Q& q S" k4 |
printf(" %d ",a[h][i][j]);! p) T' r; d: }0 w3 R- e7 E
}
7 u3 l8 S$ B3 b& |printf("\n");
( D; h& v% D' Z; A}
# o) ?$ J' V' S5 D( Uprintf("\n\n\nwarshall算法:\n\n");
/ A8 J! n6 v2 Z5 Q& y0 f% |* G+ ~/ h
for(i=0;i<h;i++) //处理邻接矩阵A.转化成可达矩阵。
. {' t0 H6 v* b7 K* rfor(j=0;j<h;j++)
* k1 G2 R0 k7 r% b1 u. h' xif(a[0][i][j]!=0)
8 w3 r) \7 _. f: U4 l# Na[0][i][j]=1; G7 Z; Z& p% c6 F8 [
printf("整理后的可达矩阵为:\n");
. O9 j& h! k+ r$ h) q/ Z. ?* s) Hfor(i=0;i<h;i++)
$ {# B }2 i4 B7 l* T{
: c9 L" m* n* z1 g2 xfor(j=0;j<h;j++)
4 n2 O; E2 R0 F2 C! [" I; Mprintf(" %d ",a[0][i][j]);
0 m9 W7 @ g$ w- O1 I0 _printf("\n");% D2 ~3 Z) m9 @$ H. ?( @# B
}
8 q$ d( C4 V7 q) {5 u" L$ Cwarshall(a,h);/ D: [. k+ J8 P: }2 [: V5 R6 o- A2 N
getch(); [3 N& t8 I1 M4 t' b
}' o2 w: [, d8 W& g1 k
int jisuan(int a[N][N][N],int h,int z,int i,int j)
, h* _0 P6 q' _. C( z3 r{; [+ j9 X/ I: Y. q9 Z
int s,jg=0;' R, p ^8 H4 I' \: {# O q
if(z==2)
8 u9 y8 l" W+ m/ R2 {0 zfor(s=0;s<h;s++). ?3 b/ \) R5 V2 l1 N
jg=jg+a[z-2][i][s]*a[z-2][s][j];+ c" K5 o( _# n8 u. Z% `% a
else
3 q& B1 S; Y; v# a, m0 w& ffor(s=0;s<h;s++)
$ X" M$ K9 T3 g; m8 Q; Ljg=jg+a[z-2][i][s]*a[0][s][j];2 L* T/ A5 M7 O; O
return jg; 0 o, E5 R$ X+ T: A" R* b8 C
}/ J# N% ?, Y) G
void micifang(int a[N][N][N],int h,int t)) C8 T P0 T4 y+ K5 X: J3 P
{, ]0 f3 K1 t# r' h' [% R% \
int i,j,s=0;
* B* S* i2 q! A. A/ x! J" Oint z=t;
* N( ]" G: k! y' u2 K gif(z<h) //矩阵的值不全为零。' g- n9 g4 J9 s5 m6 x" X$ l
{
* \7 v# V$ ]9 O9 A' x3 R: C% Afor(i=0;i<h;i++), E* G& f5 B8 v C5 o
for(j=0;j<h;j++)% P# Y, a3 I7 |' f" w
a[z-1][i][j]=0; //全部赋值为0!4 l7 T# B) j$ E' {- r2 L2 _/ x# m
for(i=0;i<h;i++)
! p! h, P/ j C. O, lfor(j=0;j<h;j++)" o% I8 K3 X; Q6 w9 J0 @+ J' G
a[z-1][i][j]=jisuan(a,h,z,i,j);
9 Z$ A* ^6 t5 h2 B& V, e4 q4 E" \6 ~printf("\n矩阵A的%d次方为:\n",z);
4 m7 C F% E- W3 K" N* _( w8 _for(i=0;i<h;i++)3 K; N# R4 m7 C( S$ D7 a+ L# h
{, p1 [/ Z. W) s
for(j=0;j<h;j++)6 d1 [7 K/ A8 ~7 O" ]4 a( B: w6 r9 v3 w
printf(" %d ",a[z-1][i][j]);
; l u, ]6 ?7 E1 ]3 W3 x: nprintf("\n");
8 c0 u- M* G& Z8 U; m}
; j8 E" I, q: Omicifang(a,h,++z); / F& i% J, T8 Y" o/ ~
}5 b4 ~0 @8 m6 L* j( r5 }
}6 `& b# f' v* d. S# x! ?8 E0 X
void buer(int a[N][N][N],int h,int t)
/ p4 ^; N: a) J/ E{
% b4 j+ M/ h7 ]$ I3 N$ R$ s% pint i,j,s=0;
* t) y$ j# t, O# ]* zint z=t;- G' T1 k5 [7 Q1 X" q
if(z<h) //矩阵的值不全为零。
0 y3 W* t8 w4 {7 T{ : V; K( {! f$ E4 i( \% ?
for(i=0;i<h;i++); E+ l' l& j/ p! p B+ B6 [
for(j=0;j<h;j++)
; x3 K! c8 k2 t; }) `a[z-1][i][j]=0; //全部赋值为0!
7 N& W6 j3 m D Qfor(i=0;i<h;i++)+ c u/ A/ n/ k% b& S
for(j=0;j<h;j++)
( H4 \+ F6 ?: m3 N- y! a. h1 V5 |a[z-1][i][j]=jisuan(a,h,z,i,j);7 b+ m ]6 k; R8 z6 ~: i
printf("\n矩阵A的%d次布尔幂次方为:\n",z);: P/ Y% R" W: w! o- L" E# v+ z
for(i=0;i<h;i++). H- q0 E: W$ x
{
8 D$ z& s. W* D. S! s0 hfor(j=0;j<h;j++)6 F* i9 ]) W" ~- u' D
{
0 j2 [: I# I) V) bif(a[z-1][i][j]>1)
* p& ?1 P, w2 B& Ga[z-1][i][j]=1; ! q0 ^9 y- _6 |
printf(" %d ",a[z-1][i][j]);
# w9 Q8 _1 F% u8 s}$ G- v. _' u6 P) B$ i6 d P6 v
printf("\n");9 l1 d: d8 z0 M# n6 s5 ?9 R5 m- q2 |
}7 T& n3 N) K& {( `( d/ ]
buer(a,h,++z);
9 D/ K2 t) ^+ S# H1 g}
( V' K/ @. r( N) t}$ ?7 P! @' m2 S9 v7 N
void warshall(int a[N][N][N],int h)- o( P% O) H+ b3 `
{ k4 {" D. h3 v! x5 M
int i,j,p,q,r=0,s;3 N$ @2 A4 a& u: p% k5 r
for(j=0;j<h;j++)
6 N' M2 a- t4 ]# \2 J: g4 Q H, Ifor(i=0;i<h;i++)
" ~. S1 T$ z; \; rif(i!=j && a[0][i][j]==1)! f5 d; N+ l0 K4 N
{
2 z, u4 g& s0 Dfor(s=0;s<h;s++)5 b0 D3 ~( [: P4 T$ V
{
S9 d7 D$ `* s, g+ m7 Ya[0][i][s]=a[0][i][s]+a[0][j][s];4 P! k1 Q0 L/ o( c, L1 X) f8 m+ Z
if(a[0][i][s]==2)
( C% L. p9 o3 U/ W1 o, xa[0][i][s]=1;
" |& `2 D% L7 w' `$ E}
! c; o6 \5 Y- Y6 Mprintf("\n第%d次运算的结果如下:\n",++r);
8 ^' g$ z5 Y% Vfor(p=0;p<h;p++)
* A0 b ^ R- N6 w{/ B3 s2 G- f5 h# q/ n' g
for(q=0;q<h;q++)4 C% R. J% c5 w. B
printf(" %d ",a[0][p][q]);
$ d# [: O0 F" ~+ r* S6 lprintf("\n");" q& M! T4 {0 u( P- D" n$ K+ `, x
}
; I+ B6 W8 f. F1 w4 w}* v! O0 \9 R* [) A2 u2 m
} |
zan
|