数学建模社区-数学中国

标题: 回文问题（用c++编写） [打印本页]
作者: lynnyan    时间: 2005-4-22 01:27
标题: 回文问题（用c++编写）
<>#include&lt;iostream&gt;( o* t4 _8 H' I2 T. ?
#include&lt;fstream&gt;
4 }6 T( C; b6 K- ~1 u" M#include"string.h"9 q8 K$ S5 D. D" `+ o2 Y% \
//#include"time.h"
3 I- U' a! Z" O0 @using namespace std;/ b6 ]- c( O+ u) u' R! w; t+ r
ifstream in("input.txt");
( V4 `5 r3 W, h  S3 lofstream out("output.txt");
0 {' C) l/ d8 C: ^$ ^class String & E) @. C9 Y% e8 Q% T% m# r2 K
{
, I4 R4 U3 Y1 F+ i" H! f: y* u; ]public:! }: x4 b2 T% [7 a
String(char *s="");
0 }; g/ A' S5 q% Z7 y String(const String&amp; s);- O" R7 g/ \& R3 H/ b1 s' N
~String() {delete[] str; delete[] pre;}
7 a" Y! Z: O4 C- s" q) W String&amp; operator=(const String&amp; s);
7 i$ d6 m" e8 `! h; j int length()const {return size-1;}
  _& h6 ]) [& ?, X" F; V9 r int get();
" R3 U2 X4 P, \- | String&amp; change(int *p,int n);
. U+ O0 g8 C  g& n8 m: O6 I! |% l void get(int *p);
: q, H9 f# }8 U void display(){out&lt;&lt;str&lt;&lt;endl;}
6 P- G% l: [7 T% m% Rprivate:2 b. {! n: n/ s  {2 }9 l
char *str;
' g) ?4 f* ?/ {& t1 J. D! N0 z7 n4 b    int  *pre;3 q2 D2 [) R, ?# j3 P
int  size;8 Z) K. M7 l8 R/ x$ x6 k2 h* D
};</P>
$ \% U" `9 o, M/ T- X3 N7 D* i4 b0 p<>String::String(char *s)6 Q- ]" ?; Z' R
{
, x  T8 t0 j8 \3 R# V size=strlen(s)+1;% u6 [  X0 u$ n; s3 L
str=new char[size];2 P3 h6 j9 n4 V2 ^& }
if(str==0)  throw "error";4 {# h2 t6 J) s5 P
strcpy(str,s);5 P- J5 X, I3 S0 U* o# b& C
pre=new int[size];
1 d+ e) l6 J/ Q% `) [2 t, |* C if(pre==0)  throw "error";
/ h" ~) S6 l; l4 v( {1 I}</P>
7 {. ?0 O/ J" |1 v  d<>String::String(const String&amp;s)5 ^2 K5 V5 V8 l/ i8 ?  V
{; v  |& x/ o* c5 Q3 @
size=s.size;
: }, |- F7 j0 I str=new char[size];1 _) W+ _, E/ e
if(str==0) throw "error";. P, S- `# \) e; G: b. J# F& X; m
strcpy(str,s.str);
6 i. l* `. S4 e5 v% x2 p pre=new int[size];
5 c. _* H2 A# X" c if(pre==0) throw "error";
6 m3 e9 A% l5 z* |, v- d}</P>! K2 d( N5 I- |
<>String&amp; String:perator=(const String&amp; s)( k! y9 ]5 J# V9 H. `
{* a# u  e2 P/ q7 g2 \- `
if(s.size!=size)
# ~7 M, B% M8 m& J6 r4 j2 n {
" m$ R4 y; a% q# }! h' U  delete[] str;
/ K' [1 ?+ L! v" P  str=new char[s.size];- B; |& X  [8 S" Z! [: ^
  if(str==0)
7 ]6 U( p2 H7 y, r- A9 L! K   throw "error";9 |& [0 a' g; I7 V* E
  size=s.size;6 K2 W8 H+ f( o$ d' E- d
}
/ L+ k% S4 K, Y* x% y strcpy(str,s.str);! `) ?5 u5 [, V9 F" a7 t  h
return *this;4 a- A' a: ]: |7 e; K
}</P>: T+ W8 ~9 r) e9 d; b+ N9 h% f
<>String&amp; String::change(int *p,int n)//将整型数组改成字符串' o+ \! z8 z) B- m
{
( J5 ~& X; Y9 R  R3 i- ~ int i;
6 }0 W3 B7 V. k* n) o delete[] str;1 Y6 e+ Y# Q3 L9 e
str=new char[n+1];
- g" B. u* _1 q: U, C, P( M% V+ f; Z for(i=0;i&lt;n;i++)- V, r" t9 ]: O4 \/ c
  if(p&gt;=0&amp;&amp;p&lt;=9)
1 J4 ]- [/ y  ?   str=p+48;: H6 m) `2 [1 k: k' S+ i; I
  else6 ^2 C% u! w- M$ Y; @+ E
   switch(p)
, A2 z8 }9 h: V% a7 u7 p& C' ^   {7 p9 {' m; O  g$ A* ~
       case 10: str='A'; break;
$ v( e9 V0 F- J* m    case 11: str='B'; break;
$ s/ v2 z! P. U3 c& Z* C4 a    case 12: str='C'; break;
3 E4 Q% T6 @( O       case 13: str='D'; break;& k3 W( ], d7 T) m
    case 14: str='E'; break;
8 c) m4 u: `* ]* h# {9 U2 S1 V    case 15: str='F'; break;
+ w& F% |$ D# X+ m1 k   }5 T( G! b; x* k1 l$ ]( h
  str[n]='\0';
1 d* a& m2 o+ K  return *this;# @7 N, S4 F2 c; Q
}
  z% N# W1 Q0 s) @  Wint String::get()//输入一个字符串* c# ~9 j4 }$ ~# ~5 n% j4 b
{/ |  D- E8 }6 I  s6 C7 w
char tmp[40000];# W& J& |: k; V! k" C
in&gt;&gt;tmp;; p5 x" V2 d* B3 s/ V' y- u2 {
delete[] str;% _: M4 k1 G5 A+ t4 Y; w( I
size=strlen(tmp)+1;
  ^2 F/ |, z, M% `6 ]( @! I str=new char[size];) G/ ^; ~1 o$ o: f$ l' H
if(str==0)
4 O% y" j. `1 o3 `8 P7 \' B  throw "error";' P! V' H6 Y& i& g
strcpy(str,tmp);
, B. y  M1 c" U0 U8 J5 O- [ return size-1;" C: h3 }8 x2 I
}</P>
+ _( _6 M* I0 O; ]<>void String::get(int *p)//将字符串改成整型数组
/ b* W5 o1 B& Y: W! k( u+ O, \' ]{! P% L) m4 t. S8 D: ?. e
int i,j;
+ j9 o+ R* G  \. w* J% O6 Z3 Z for(i=0,j=size-2;j&gt;=0;i++,j--)/ M  `( F! ?# h
  if(str[j]&gt;='0'&amp;&amp;str[j]&lt;='9')
, _0 a2 L* x2 u( ?/ q# i      p=str[j]-48;
3 A' I- c8 J8 t# ^  else
- X7 ^- E' W9 W* g* h# b; t# \5 k  {
+ i+ @) U% ]  L: T   switch(str[j])! e/ M) ?6 S2 _2 E0 u/ @3 f
   {; P/ n/ @, u3 ]
       case 'A': p=10; break;
% p# s8 u3 U1 t6 c" L; f( s    case 'B': p=11; break;
# [5 r. {% m. A* F    case 'C': p=12; break;+ Q' h9 S- ^, w$ D! @! D9 O
       case 'D': p=13; break;8 V2 t% F6 D- L" E) F2 B( F/ L
    case 'E': p=14; break;
3 q" S& z* x% H0 R    case 'F': p=15; break;+ |0 l3 L2 Y3 T
   }4 I/ k0 X5 h& h/ }0 Y8 `% r. }
  }, q5 I# y' w$ z9 A3 Z, T  f0 b3 n6 C
}</P>' F- A9 H+ o2 J! z3 h  P/ P
<>void add(int *p,int &amp;m,int *c,int k)//将一个数同其倒置数相加
( |3 B! @/ c$ h5 s{5 J, a0 g5 }/ u' X+ S
int i,j,a=0;" [# L0 Q; @8 N- h, y
    for(j=m-1,i=0;j&gt;=0 &amp;&amp; i&lt;m;j--,i++)
' @$ Q7 ^& y& j+ |! e" w {
* ~3 p& m4 e, S* i0 S$ O' W     c=p+p[j]+a;
5 P7 f/ G  [. u  ^% v  a=0;
! [# O& B2 a1 b7 ?  if(c&gt;=k)0 K9 R7 \/ H0 n3 _
  {
1 x: M; B$ R/ i0 s   a=c/k;
* v, ^  m( s! q8 U   c=c%k;- ?( {6 f5 J) L) n& I! J2 h3 o
  }
; ?" T8 r& w* v4 A; d5 S& ` }
7 K2 ]9 Q4 u/ O5 e! W' p$ k if(a!=0)
! e! D  @1 }; f {
( V# S9 X, V' [: U: w  c=a;5 H" R/ ~8 o5 P9 b) c
  m++;# m- `2 M/ X# L4 s  H3 [3 b4 m
}8 s4 s5 f  Q7 t$ |& H
}</P>
9 v0 B, ?( ~& Q; |<>bool match(int *a,int n)//判断是否为回文数3 x- C: v9 j% W! O
{
. P/ O6 S7 ~5 q" ]) T3 S: g3 O int i,j,h=0;
' ^2 p/ W& o+ I- I' W for(i=0,j=n-1;i&lt;=n/2 &amp;&amp; j&gt;=n/2;i++,j--)
1 m3 ]' s6 g7 T( {, G* k {: }( m4 X, v# E9 d
  if(a==a[j])) v) A1 @( k5 D3 q# R
   continue;7 @9 N, P2 b/ L# K9 B8 T
        h=1;% l7 y0 y2 E. u' |( X
  break;
! Q. \  n0 L+ N3 ] }) i6 e# c4 S  V" w6 ]0 q( w
if(h==0), u/ P! W/ x9 Q- [8 V* E5 I" \5 d
  return true;
2 ]6 [- g4 q, q. D5 @& o+ S else
0 b. N' S0 {" K9 `  return false;
4 Q! b1 c3 P6 \+ [5 m}5 `) y+ y; m& `; ~( Z8 U8 U
//clock_t start,finish;
, n: v3 Q4 D' _5 k  tint main()% Y4 Y3 P1 X! F
{//start=clock();
; M% v8 p' |( A  u; _- v if(in.fail())4 Y; g; U5 u4 Y: |+ ]
{
' R* Z5 u1 m, o% R& w  cout&lt;&lt;"the input.txt is not exist!";* J( s9 T8 L9 s1 h) L) w7 A
  exit(1);2 B& R/ s+ c% f6 F- o& T8 M$ b6 }( e
}
# i+ }) |7 o9 t& Y; o String s,s1;1 N+ Y  P5 n( @, j: F# T9 E
int n,g,k,*a,*c,m,h=0;& G! R) P2 K. l7 Z
    in&gt;&gt;k&gt;&gt;g;
$ U2 i$ E, m+ {2 ~( T9 i    s.get();
) n. t8 L# c! o# l! Z; \$ A
, l: w; L! @) Q4 n& S* L8 N- R/ M    n=s.length();
5 h3 N. z0 ]: E' ^ m=n+g+1;. ?+ @# K7 W( _. k  T  w
a=new int[m];+ y* J. L6 M7 }* _( w
c=new int[m];% R  u/ _- Q9 ^& Y
s.get(a);
; y7 ?7 E9 J% d& v- u9 V+ Z if(match(a,n))& C- Y$ s% E8 w" j
{8 s- I) T/ k; Z  X1 f" [1 F
  out&lt;&lt;0&lt;&lt;endl;
4 P! @0 @$ A1 _+ o% _5 d  s.display();4 K: c. g( F9 _9 J
  return 1;
& L# t. b1 K% k( a }& S, b. d* B, u: Y/ p% R% b; t1 O6 M
do
( y- r/ k2 |- `9 h' e9 X; n% D  X6 o {
: C' p$ N: u( l) a! [$ k9 x! m     if(h%2==0)3 L# I& U' M0 F$ ~
      add(a,n,c,k);
; w/ S. o) _/ _" d7 }  else
5 V2 h2 |; e! u) X' E$ v6 ^4 D   add(c,n,a,k);# _8 W8 ?) \2 O
  h++;& s, }# W: w& n3 J2 I( A
  if(h&gt;g)1 f" s/ z- t! ]" U+ g0 b7 u  ^
   break;' [) U6 C! ~3 G4 K' g' n/ r5 T
}; w+ A7 ]4 M( M% V! [$ }
while(!match(a,n)&amp;&amp;!match(c,n));( U3 }0 k& d! S7 W
if(h&gt;g)$ E" B' _+ m) J! u- X
     out&lt;&lt;"No Solution!"&lt;&lt;endl;
/ P7 w$ O9 M7 U else
3 W6 q5 ?4 E3 S {
% f; [& J6 [% Z# J3 _! h      out&lt;&lt;h&lt;&lt;endl;
4 ]6 m' s- R+ Z: ^     if(h%2==0)& N: ~$ O' b& o  y0 M
      s1.change(a,n);' W7 z( E' a$ k1 x$ i# V
     else
* k4 a3 ^" V) i' [% Z      s1.change(c,n);, U5 S$ o# V. V' E5 E5 ^' J
     s1.display();( s: z4 P9 L( X; s
}+ G# X( {, M' O, D# Z* `
delete[] a;
" b6 p/ o, j4 @: {: s  X( J3 @ delete[] c;! n' A) G0 o$ Z1 S- X# M1 `& [. D( U/ v
// finish=clock();
5 J* @- X$ p7 \* Y1 |# \// cout&lt;&lt;finish-start&lt;&lt;endl;
# r9 _/ _3 ]4 j) Q: R" b return 1;
7 X5 Y+ {7 \$ I}</P>
作者: txj66    时间: 2005-8-22 02:00
<>谢谢</P>
作者: zxl_lucky    时间: 2005-8-24 17:02
<>谢谢 啊啊 </P>
作者: sabbanji    时间: 2006-11-21 04:52
　　一个指针从头向尾走，一个指针从尾向头走，至多走到两个指针相遇或相错，就可以检查出是否为回文了。上面的代码怎么弄得这么复杂？
作者: darkghost    时间: 2006-12-11 01:57
我觉得用堆栈也可以实现吧，先将各元素压栈，然后将其中的元素复制到另外一个栈中，再出栈比较。<br/>呵呵，可能还要麻烦，没做过。。。<br/>
作者: mustpeter    时间: 2006-12-12 16:42
<p>回文是什么意思？</p>
作者: zhuph    时间: 2006-12-26 09:11
有没有汇编写的？
作者: hero1632    时间: 2007-1-2 18:08
<p>不错，正在找</p>
作者: friendfb    时间: 2007-1-6 09:09
<p>设计算法的时候，应该充分考虑时间效率和空间效率！但是两者往往也是互相矛盾的。一个好的算法可以应该权衡这两个方面；或者更加特定的需求来设计算法。</p><p>在我的记忆中，回文是需要考虑标点符号的吧</p><p></p>
作者: zhaoyunfei1126    时间: 2007-4-7 11:50
什么啊？？？
作者: seashell7    时间: 2007-4-12 17:39
3Q~<br/>~
作者: hanyeyu2009    时间: 2010-12-5 11:01
看看是什么
作者: zengshengda    时间: 2011-1-30 21:52
很强大！！！！！！



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