- 在线时间
- 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"; R; d7 h5 a, _+ ]+ l
#include "string.h"6 x$ s" [+ N# ?$ I$ ^" q! g
#define N 50 - e5 H; Z1 A; \4 R4 Q5 r- Y9 f
int jisuan(int a[N][N][N],int h,int z,int i,int j);1 X' }; Y: R4 h5 s( C) o
void micifang(int a[N][N][N],int h,int t);
4 p6 q* U. |( o" i* m& l3 Kvoid buer(int a[N][N][N],int h);
1 x9 f* `, K3 Avoid warshall(int a[N][N][N],int h);) a' d0 F6 x" p8 y& s ]+ b8 }
main()
( h+ T+ G6 b' M2 f/ Z, q. a7 M& @) ~/ x{, t8 F6 t6 h# _, c! ^
int i,h,j,t;
& m8 |3 X% M8 |$ z. v# q; Bint a[N][N][N];
0 {& W' \% e6 ?5 ~0 q; Tprintf("请输入邻接矩阵A的行数(或列数):\n");. f) H- ^5 E o$ J
scanf("%d",&h);% L- [. V! c7 o- j! |
printf("\n请输入邻接矩阵A:\n\n");
: B: ]0 K$ Z C4 T6 T" W$ U: Ufor(i=0;i<h;i++)
1 c2 ~/ c: d* K4 w$ c- O$ `{
% }0 R. W- ?3 k' V6 C7 Yprintf("请输入邻接矩阵A的第%d行.\n",i+1);
6 a" `! Z; M8 I5 Lfor(j=0;j<h;j++)* t4 L8 }9 a4 |
scanf("%d",&a[0][i][j]); " y3 x) I8 j# x( E/ T9 M( I
}
k2 k+ Q4 `+ d9 |5 R% `printf("\n邻接矩阵A为:\n");! d7 k% z2 ^; T# u/ r
for(i=0;i<h;i++)$ ~/ _% a, C% {6 |7 v. {, D
{/ K* y/ Z' M" {8 x+ J; Q, W
for(j=0;j<h;j++)% e5 k0 F* c9 @
printf(" %d ",a[0][i][j]);7 `3 m* K8 z- [2 L6 ^# [2 X6 L
printf("\n");6 g5 t3 y; ?/ y* a1 s
}' P* `2 R: u' \7 N: ^8 S
printf("\n\n\n算法一:\n");- }. I5 g( e0 M/ D2 B- `; h
printf("\n矩阵A的1次方为:\n");
5 A3 `: x+ w+ O3 S/ ]for(i=0;i<h;i++)
* f8 B% m. ~, H* H{2 ^6 _: T2 E( f o% ?
for(j=0;j<h;j++)) _5 D- _! n# y8 R( Q
printf(" %d ",a[0][i][j]);( }% t& s. _6 v' P
printf("\n");) O9 ^: K E1 r2 b4 l9 G% n# E$ c. a
}1 k* U( L+ ~2 [: l- O; y" |9 m
micifang(a,h,2);
6 p0 I% o: P) N# V1 _for(i=0;i<h;i++); m7 y7 T8 e# W0 C
for(j=0;j<h;j++)
6 {' h! \% k; U |+ x3 Wa[h][i][j]=0; //全部赋值为0!$ Y* G( B; j3 f o W1 Z
for(i=0;i<h;i++)! ^" x3 s3 T4 W/ V7 Q
for(j=0;j<h;j++)
" @5 W- x$ C4 xfor(t=0;t<h;t++)- F2 h+ R, b' b1 I- G% U
a[h][i][j]=a[h][i][j]+a[t][i][j];
2 ?3 t1 g3 z& B0 K wprintf("\n\nB的值如下:\n");$ Y+ U9 I1 x$ L; M. b
for(i=0;i<h;i++)
1 s& e0 @6 O8 ~; e/ { J- P0 ` e: }{
, q* T0 ?! a; [, p. D3 t/ Q0 Qfor(j=0;j<h;j++)1 g9 Q! M; }1 N4 r
printf(" %d ",a[h][i][j]);
9 T/ I; U T+ D" H) Iprintf("\n");( {7 u$ i- ?- Q. v O2 b
}$ D, U, g# D$ i; L# b8 c5 w
printf("\n\n\n算法二:\n");3 M( h( }! ]5 q w0 o( n5 {
printf("\n矩阵A的1次布尔幂次方为:\n");
% |" s( o0 f9 @* Q3 ufor(i=0;i<h;i++)6 t# a: O& k+ F$ d2 N8 s3 |
{
6 E) P J7 b( f# A. pfor(j=0;j<h;j++)
& i+ _2 Z% B) \{
; A1 P1 I0 e5 c/ k) g* aif(a[0][i][j]>1)4 _: l( V4 k# u2 T9 {
a[0][i][j]=1;
% f8 D9 C4 y6 M9 eprintf(" %d ",a[0][i][j]);5 M7 a2 D! ^6 z
}6 z" z, Q% ^+ a6 S0 y7 {
printf("\n");8 e! ?* F$ D+ e0 h) V7 n8 I
}& V" p# g4 W/ l. U8 y8 ^9 h
buer(a,h,2);
+ W% d; S1 C* S3 q! {+ d' uprintf("\n\nP的值如下:\n");
8 u D! j, S7 m( A* Jfor(i=0;i<h;i++)
; D7 S& }8 G' a( W& b) |{' ]( K5 R1 O s1 D$ V) Z( B5 B
for(j=0;j<h;j++), \( k8 Z+ h) Y6 d3 u- W" I! F
{
: g+ z$ m( e- R8 \8 Y- ]: X- fif(a[h][i][j]>1)
1 s6 t% O. v9 |a[h][i][j]=1;6 O: e+ ~: \- O0 V& K4 J
printf(" %d ",a[h][i][j]);
8 u7 Z, [1 U& }( @ S}: r" V& g" p9 n' u3 y- |2 h
printf("\n");
* J% g& N) N d- p7 V}9 T- u+ o) S4 [
printf("\n\n\nwarshall算法:\n\n");9 O" l$ ]1 \6 H' T& m/ p
# E1 w: F# k: F8 w8 l/ k
for(i=0;i<h;i++) //处理邻接矩阵A.转化成可达矩阵。/ H% |# U/ I* v
for(j=0;j<h;j++)7 ]" S& x/ L& a. [1 q5 o
if(a[0][i][j]!=0)
7 e. l# z1 u: {8 Ta[0][i][j]=1;( W: I8 D* T, d
printf("整理后的可达矩阵为:\n");9 g; b8 ?. z$ v0 ^" s5 }& [
for(i=0;i<h;i++)
* s' R' o6 }: ]+ ~; P& p{
: x" o! m" L3 @7 r$ B0 @for(j=0;j<h;j++)2 W" i, w m. E3 I, f
printf(" %d ",a[0][i][j]);/ i1 U4 q6 u* Q) u: @- W
printf("\n");, x- ^* V; w; f, p# `7 ^
}
+ p5 E' U% W7 J: o. o/ v/ n% Zwarshall(a,h);5 z9 L' k2 k \( o+ g: ]; @
getch();% F0 J( q5 D! G" T6 U
}
9 b6 \9 p/ `* `7 C4 C. Wint jisuan(int a[N][N][N],int h,int z,int i,int j)7 [8 k% F) k" |9 A d
{
- y) g2 _* N, p6 uint s,jg=0;( o9 c+ L' \, {. M( C
if(z==2)
9 F8 S% O% n9 n0 m: D7 X' c, M# W4 afor(s=0;s<h;s++)' D0 W" C! ~! h7 m5 b$ L
jg=jg+a[z-2][i][s]*a[z-2][s][j];; U: J) g, R, V3 j) w; ]' P
else 9 H& D% U g5 i) S' t
for(s=0;s<h;s++)/ {" i* [$ x1 k* G; M2 g
jg=jg+a[z-2][i][s]*a[0][s][j];
, h% ]4 v5 b( Kreturn jg;
# |) Z, a. ]- [& r8 m, Z}% E" V/ E2 f& g# U! y8 u0 I1 g% M
void micifang(int a[N][N][N],int h,int t)
: ?# M! v* k. g1 z/ Z{5 s& e4 x6 v- t/ f
int i,j,s=0;' o, z9 N4 T5 Z) c
int z=t;
( e1 B- M& K d0 x4 s, D K: hif(z<h) //矩阵的值不全为零。+ c) _2 c' k* j3 e1 O$ {1 t) r$ Z) y
{ ; O7 [* T3 N, J9 S1 Y5 B2 `
for(i=0;i<h;i++)) _3 Q6 ^5 \9 [8 j* o) n/ k
for(j=0;j<h;j++)- L, r# q: _. [4 V
a[z-1][i][j]=0; //全部赋值为0!
- @ H+ Y. H4 h/ U/ Lfor(i=0;i<h;i++)
4 Z- @( i) |% Afor(j=0;j<h;j++)
a/ t4 K o8 X* Ta[z-1][i][j]=jisuan(a,h,z,i,j);
6 l- a' H9 \' G) Vprintf("\n矩阵A的%d次方为:\n",z); U$ v( }. |( ]2 V6 ]" _; n
for(i=0;i<h;i++)0 p; \' F/ s g5 U6 P' s. U- H: j* N
{
& R8 {3 }, T) n/ I& H$ \' Hfor(j=0;j<h;j++)& ]' u5 T# l9 u# i7 i Y8 f2 J3 h6 o% |
printf(" %d ",a[z-1][i][j]);3 h8 \! [2 k, a9 J
printf("\n");
. i+ E7 N; \8 s0 w. J8 f}& y# A4 R" u4 X9 g6 K
micifang(a,h,++z);
) d7 f# L7 q7 V# W! |}
. w' \* J# Y$ I d/ e& f. P1 ?; D}
/ V1 t# T; I$ m# C" F: A9 Z: tvoid buer(int a[N][N][N],int h,int t)' G- A |; P' [$ h, m8 C) p
{0 E6 a) t" q0 o8 h/ p2 @; ^
int i,j,s=0;" D, E X) R- |/ m7 s9 R% @+ k
int z=t;& g3 t: w Y* q- ?& M, j3 C9 t
if(z<h) //矩阵的值不全为零。$ m1 Y& X4 W, b& o+ o( ^7 `% ~
{ . F7 r+ H' a% W; L7 p8 a7 y0 K
for(i=0;i<h;i++)
8 q& l0 @/ G( M; H; N$ {- L& ]for(j=0;j<h;j++)
% x6 [. _) Q3 z( F( `0 p- K4 v/ R' aa[z-1][i][j]=0; //全部赋值为0!
* n9 |: n7 Y( H& g. H- Zfor(i=0;i<h;i++)
# N, P. T7 a9 Q z( sfor(j=0;j<h;j++)
+ _" j! v* a$ Na[z-1][i][j]=jisuan(a,h,z,i,j);
# E* k E6 \) |$ O$ e) qprintf("\n矩阵A的%d次布尔幂次方为:\n",z);* @! m' i h) P- ?. C
for(i=0;i<h;i++)- \8 f/ R' K1 ^6 L8 D' K# x
{
. Y0 y Z5 c8 D! e$ d, Pfor(j=0;j<h;j++)* z8 A! ^/ L* A
{
, H ]! f4 P( \' h$ sif(a[z-1][i][j]>1)& [; ]3 P* h& h' J
a[z-1][i][j]=1;
1 a5 d, [0 w: ~printf(" %d ",a[z-1][i][j]);
3 r0 C$ k! Z6 S F* b}
0 N/ X2 D! f$ R9 t! cprintf("\n");" U6 @6 M- ~, k& d2 s% R/ ?: E6 \
}3 m" g( X" \9 _1 ?
buer(a,h,++z);
$ L) Y8 t$ ^+ c- a/ q}8 J# r; k; X) \2 n
}" R2 r- ]4 n9 f9 i* o
void warshall(int a[N][N][N],int h)
. U" ]2 K# V5 y+ ^: q; Z8 @{, {5 q4 o! T0 n, `9 R! T+ M
int i,j,p,q,r=0,s;
- T' E' F/ ^( ^$ p' b& Q1 [for(j=0;j<h;j++)1 a/ [8 [# x* `
for(i=0;i<h;i++)2 `# R# Y) [1 x) Z" i
if(i!=j && a[0][i][j]==1)9 X5 g, J6 [: ]0 f9 m: A. M
{
% z+ R( Y' o! V' L* q# B: pfor(s=0;s<h;s++)3 U! y" @, Y* U6 r9 c
{ , N2 d5 a3 w+ T3 _$ W5 ]6 b, c3 f
a[0][i][s]=a[0][i][s]+a[0][j][s];' o, y5 }; G& q" O
if(a[0][i][s]==2)
' g' @0 _+ k. }+ q6 O$ c' z* U$ Oa[0][i][s]=1;
/ D4 o: r& t' v/ r+ {}
* Q9 k& N8 y" h% L1 D, J/ J$ |, s! yprintf("\n第%d次运算的结果如下:\n",++r);$ T2 X4 @/ J2 H9 d( ]
for(p=0;p<h;p++)
. M2 T) u' Z# y, M$ E, L( {" L) T$ l9 \{
. M- W$ H9 h* q; M+ mfor(q=0;q<h;q++): l+ a3 x4 l- D; y; G
printf(" %d ",a[0][p][q]);0 o( m9 q. K& x
printf("\n");
6 U) W) c. x# ?}
: P, D; o; _* k# z}. W, {6 ~! D3 `# b; ^& [
} |
zan
|