数学建模社区-数学中国

标题: 公交路线最小换乘次数的路径选择算法（C代码）（请求高手指教） [打印本页]
作者: 舞情＿Dong    时间: 2012-8-19 18:02
标题: 公交路线最小换乘次数的路径选择算法（C代码）（请求高手指教）
第三天了，关于交通路线的选择，用C语言写成了个样子，下面代码可以正常运行，就是路线选择的结果不是很好，结果有好多重复的，有些站点似乎选不出来，这和存放交通路线的数组a有关，我们是把公交路线的上行和下行放在二维数组的同一行的，肯定有重复，但对程序算法也有质疑，实在是惭愧，自己不才，对其它语法实在是不太了解，用的都是for，if循环嵌套，还请仁兄指教。这是2007年的全国竞赛题，网上也有各种算法（基于不同语言），我们建模培训做真题，按自己想法用C编写了下面的程序，但结果不是很好，自己对其它的语句又不是很了解，实在没辙了，真心请教各位大侠，现在在改数组，打算将同一条交通路线的上行和下行放入数组的不同行里，真心寻求帮助，请求仁兄指导，谢谢！
% y. @8 t/ H+ z  b
, R! O% m# c( k. \1 F5 t  C' m  P) c
编写的C代码如下，由于数组a的数据带大，粘贴不过来（520条数据）, t, C2 h" H4 k9 j& j
本人实在是很惭愧，对C其他语法语句不是很熟悉，用的全是for，if循环嵌套，还请仁兄耐心查看! `" ~9 w( M8 m* [' F% q# g

2 Z9 i9 M8 W1 S# S' P5 L. F6 S" y6 m
        uint value1,value2;  s; g. J9 I) R; R5 j! a
        uint a[200],a1[200];//定义一个数组" I0 p' m9 P& S: k' p
        uint b[200],b1[200];( q8 y: U/ }9 ^
    uint c[200];
1 E2 X, p: P) }4 ^/ j- O9 }( k! h2 l' @% ^9 }% j! \5 G

9 X) `+ b' `* Z6 B; l0 @9 r' N* `( V% c1 `* c( g
void routes()$ v; `# W7 y8 E# P- y
{8 F3 x: Q( r2 r
       
. i: K& F$ E5 ]0 o9 |, m, e; P        uint i,j,j1,j2,j3,j4,c1,c2,k=0,k1=0,k2=0;- v9 x& z9 L. c2 K
        uint linshi1,linshi2,e=0,f=0;
+ [; V0 {$ @, j! N; z# e  J& U. [" d        uint q1,q2,q3,t;
* |6 Q0 p5 k& W        uint luxian1=0;. b- V4 T2 |% @, c1 W3 ~
        uint m=0;$ l2 N7 u, w2 X+ ^
        uint n=0;5 o/ G- H: B: ?
        for(i=0;i<520;i++)
$ [, |; @! j9 L7 ^' y' J# A2 W        {
8 F9 T2 @9 M' D  L6 G- h; a( m                for(j=0;j<200;j++)3 g$ i0 e, B$ {4 M8 \
                {5 u9 h; v) q! [
                        if(y[i][j]==value1)//寻找包含起点的所有路线,将路线值放入数组a
# Q1 @1 k8 ~) e+ \+ I; u( t- ^4 U- o, P8 c                        {
6 o. T3 m" X3 Q& _                                a[m]=i;
0 n0 n2 d' q1 o5 F" P2 v/ l                                //a1[m]=j;7 ~9 t* s0 M; u' a
                                m++;
6 {* j# V# S4 y' l6 G* ~8 g5 m                        }! X& Q. q  q: |  n5 |
                        if(y[i][j]==value2)//寻找包含终点的所有路线，将其放入数组b
8 }7 i' ]2 Q4 V                        {; J3 ^& i0 T# s2 y2 x1 R
                                b[n]=i;
* u& E  o; `) y. n$ b  d                                //b1[n]=j;6 y  R* Y. K" F' n, E
                                n++;
6 J/ C9 J& P' _                        }* A  h; m9 i! U9 ~
                }               
; t6 [. a3 }$ L! i5 [/ m        }
" g! K5 x: }# R; [        printf("所有经过起点的路线a为：");# Y8 t) Z: D$ D
        for(i=0;i<m;i++)3 k& ^' T% z' V! S% l- s0 a8 ~* V
        {; G8 e* S" h* {
                printf("%d  ",a[i]);               
1 n# j6 k$ X+ P6 g. O; m7 K        }8 ]! K9 P5 s7 @: G& f
        printf("\n");% w" P, B. T! ~% @
        printf("所有经过终点的路线b为：");: ]% f$ z2 s: j! N; {( M& }& Q4 E* [" a
        for(i=0;i<n;i++)
4 w, {: T  ^& f        {* S9 S7 x4 s9 S" V9 ]
                printf("%d  ",b[i]);                7 L& v; C" u8 C' T
        }
8 j! Q7 Z" o( u) X: S2 A3 J        printf("\n");9 h2 Z- J' Z7 t9 P, F

! j% ]- K4 S8 h) W6 H9 G5 ]% G
1 k! W3 i* V1 R6 a
( }3 O4 c9 B/ s' ^2 h& d        for(i=0;i<m;i++)//直达路线的寻找9 B' O7 {6 Y6 C# I
        {
4 M6 D% W% w# J  {9 o  w  r& f7 X                for(j=0;j<n;j++)0 |* v; F  V0 |% K
                {
5 ^4 f1 x  J* h- d; i) w) h                        if(a[i]==b[j])
4 g' E4 W# S) @8 i                        {9 H  d" d# R3 d/ P3 `8 q  c3 w# i
                                c[k]=a[i];
$ c2 C% U- {) ^8 u: \" X' g8 P& f! l                                k++;                                        8 w( m5 t' D# K* A4 p, z
                        }
- [; e- x$ n% Q                }: c' |$ x/ z- D* R4 o
        }; A4 X% s& R; _/ e  p
        printf("您查询的站点的直达路线有：");
# {0 K- E  T) t2 v4 a8 i3 n7 ~        for(i=0;i<k;i++)+ \. S$ }& Q) u2 `2 `
        {
, h, F8 Q: L- I+ v                if(c[i]!=0)( h- Y; v3 E3 e( c
                printf("%d  ",c[i]);  A& w2 A; w1 s$ q' R3 P
        }
. y/ X5 _; F7 n# J2 @        printf("\n");//若没有直达路线这数组c为零，接着下面转乘一次路线的寻找8 C1 d' U* T9 U4 V: D9 J
3 V! b7 i( c5 T+ w& R

3 U2 f  _9 R( y# u! f! s- [4 _        if(k==0)8 \  |1 Y0 P1 S2 d
        {
) U" W  R8 a) ?  K' H( ]                for(c1=0;c1<m;c1++)//转乘一次路线的寻找
# [2 t+ R! ]% v                {
9 F, P  {5 X1 w: P; ~6 Z; u                        for(j=0;j<200;j++)
# ?7 z: E0 z5 `) e& {                        {
: ]! y# T5 w# \% p                                linshi1=a[c1];
3 x5 Q2 B/ X8 p# O: j3 }1 a                                k1=y[linshi1][j];//取出a中每一条路线上每一个站点，接着与b中站点进行比较，查询公共点。6 Q" A0 N7 R# j7 ~+ z9 S; f
                                for(c2=0;c2<n;c2++)
0 Q* _3 {6 u. Q9 \4 {5 ~6 o1 V                                {& \) d8 F' f8 D: H8 R- M/ U
                                        for(j=0;j<200;j++)//该算法不是很好，j小于200时还得往后遍历。
( r' C6 [$ E$ [- @  h) ?, Y                                        {
6 |; n) s) l$ ~" ]5 o# b/ `                                                linshi2=b[c2];( y" ?! E1 j5 Y& s% s
                                                k2=y[linshi2][j];//将b中的站点取出与k1进行比较判断。
; E# u* x7 J2 X2 {2 I                                                if(k1==k2/*||k1==k2+1||k1==k2-1*/&&(k1!=0)&&(linshi1!=0)&&(linshi2!=0))//寻找数组a,b中的站点，有相同的及为转乘一次的转乘点，并输出。5 Y9 a9 ?+ c0 L2 X
                                                {
# ]/ O% f6 E( G: s- m: z: R                                                        printf("您可以转乘一次，起始路线为:%d ，中间转站点为：%d ,%d终点路线为：%d\n",linshi1,k1,k2,linshi2);
% V+ R3 L% H; A4 ^/ i0 u                                                        luxian1++;
% w$ B+ K5 u& b6 T; u% u                                                }
0 V$ W6 }6 C9 ]                                        }                                ; B! q. G- O; \9 B0 V
                                 }       
' _8 c  R+ j* {                        }        
$ i: h  `0 H) A! q8 O                }$ m, ]+ a( Y5 T
        }, j, `. |3 q* L0 c" D8 U

5 N) ?& N& A0 C  S! J' w* [% G3 {6 i+ {; m5 A
        if(luxian1==0&&k==0)
# Z7 U; l$ h+ K% H9 @  y- ~        {
' Z& S8 W9 }+ u5 ~; D7 F6 M                for(c1=0;c1<m;c1++)//转乘两次路线的寻找# w: w4 ]+ k  F0 H5 d
                {
" T& s7 s: n  W/ e                        for(j=0;j<200;j++)2 O4 o5 d2 K1 h- v1 j
                        {% T! g% k* k# K" b" V; ]
                                linshi1=a[c1];
7 W% a8 v( j3 b                                k1=y[linshi1][j];//取出a中每一条路线上每一个站点，接着与b中站点进行比较，查询公共点。$ [6 w( [  M& b) ^( ~7 O  d
                                for(c2=0;c2<n;c2++)1 q- D" Z; y% l" v, V* [
                                {- }3 P  b' m7 s
                                        for(j=0;j<200;j++)//该算法不是很好，j小于200时还得往后遍历。4 t8 W4 u! g" z9 f& t% c; j
                                        {/ U# ~% s' c) }6 `7 H. M6 U* \
                                                linshi2=b[c2];, N2 j! G( G2 c! w( ?5 a/ a# k0 C* B
                                                k2=y[linshi2][j];//将b中的站点取出与k1进行比较判断。
: Q+ x9 {  b( m                                                for(i=0;i<520;i++); ?( O. Y7 k8 u5 _" K
                                                        {2 I  M3 u& v* a/ v- r
                                                                for(j=0;j<200;j++). p4 `" i/ o3 Z6 D8 g: O5 o
                                                                {# W3 Q' d4 V4 \% n5 N4 N1 q
                                                                if(k1==y[i][j]&&k1!=0)
$ {! q5 S3 D! g& ^1 S                                                                {
! f) u& _' e2 T, j+ _! D8 b: U1 y                                                                        f=i;
" r" E3 D/ v/ p; Z, H8 h                                                                        e=j;                                                                . y9 g( w# R5 k; N/ a! X- p1 J
                                                                        for(j=0;j<200;j++)# U8 g: y: y; `  f" }& n
                                                                        {
" V; `7 |. c+ `* P" y                                                                                if(k2==y[i][j]&&k2!=0&&(e<j)&&(linshi1!=0)&&(linshi2!=0))* J! s% z) C2 t# _( z+ k- C
                                                                                {' ?9 L8 l; ~3 M5 u) f+ a/ e
                                                                                        printf("您需转乘两次，起始路线为：%d ,第一个转车站点为：%d,中间路线为：%d,第二个转车站点为：%d,终点路线为：%d\n",linshi1,y[i][e],f,y[i][j],linshi2);6 I7 @" i# l: p) w. V2 O, \( x* Z
                                                                                        //q1=abs(e-a1[c1]);//计算每条路线上经过的站点数) g$ j# m3 u5 m, W3 i: E
                                                                                        //q2=abs(j-e);9 ]. C  Z1 \1 a0 f+ {4 t* Z  T
                                                                                        //q3=abs(b1[c2]-j);  [  R! W  T% `7 [
                                                                                        //t=3*(q1+q2+q3)+10;
. [1 i; m' ^$ K                                                                                        //printf("该路线总共计时为：%d 分钟\n",t);+ h$ C* s+ p1 R0 E
                                                                                }' l9 K9 H! O5 n* r. A: C
                                                                        }
) y2 k6 M4 f- O& f, [8 c7 w                                                                }
( v4 X: {% L  S, h3 l7 d, j                                                                }0 ^4 Q) M' f7 f" S) s
                                                        }    : u. }1 M9 B' {, \. P* R5 c
                                        }       
2 ?! a2 d; i- V. S- C* T, [3 s                                }
) A  {. U- M5 Z1 R$ ~1 s. w" m, }                        }
. [& X! Z; @2 _/ R4 w( r! _& |0 I/ u  H8 j! j* W
                }
+ z6 P8 A: V/ i5 J        }) W1 W8 _8 E. j! k
0 z. n8 r* O4 i: I, u5 S$ M% A
  e, z: @% |0 \
' F# W5 a$ O. s' [8 J3 z" [5 _: }% r" S
. Y  j: G' f  s, F: n+ f$ W

7 K. m+ Z' O2 @+ U7 q" p, {% M6 ~3 s2 B

  Q& F6 @7 {! h( U6 L: x5 M& B
6 S0 ?9 t. N) i& e3 [0 W# `
5 k6 r3 O  d& V
; U- g  N% |/ @0 T& f4 m* i# s3 c- G
4 @9 W: h" f" ]* D' D9 H% X+ c
}
: w. @5 X* [6 _# ~8 B% u8 Y6 R- @# S: M  B2 m
        void main(): |; b, Y: J$ q, s+ K, L0 H+ n, i* G
        {
. q  C5 `3 S% T+ Z6 U7 J                printf("请输入起始站点和终止站点（中间空格间开）: \n");: x0 p  j, C+ J8 m$ V! w
                scanf("%d %d",&value1,&value2);                ; Y1 M) O9 `  a) m# k
                routes();
3 F4 Y- |& }+ s3 M# P8 w" w& I; _2 R4 c2 j0 e7 U) d( o
        }
4 o/ {+ N* V+ Q8 Y, f7 W/ \       
作者: huakaibubai    时间: 2012-8-20 09:01
顶！！！！！！！！！
作者: huakaibubai    时间: 2012-8-20 09:01
好好！！！
作者: 倦了流年    时间: 2014-7-14 00:29
顶一个先！！！！！！！



欢迎光临 数学建模社区-数学中国 (http://www.madio.net/) Powered by Discuz! X2.5