数学建模社区-数学中国

标题: 回文问题（用c++编写） [打印本页]
作者: lynnyan    时间: 2005-4-22 01:27
标题: 回文问题（用c++编写）
<>#include&lt;iostream&gt;
# n6 S8 ^/ w" T* z#include&lt;fstream&gt;
+ v) c" [9 Q: l  J$ t" |8 U8 [. H5 ~#include"string.h"
; S3 _) Z! Y- N! A2 k* q) f//#include"time.h"
/ `* E, h8 F; f! Q5 d) U1 Nusing namespace std;: q8 }5 N) `8 ^7 E, ]% |
ifstream in("input.txt");9 I0 n) N% T& _1 ]5 \
ofstream out("output.txt");
: B9 }. ~3 t3 N9 m+ s. O- nclass String 5 N7 B( I: y( ?3 |5 H0 x
{! q% a' T% m  K7 g8 R$ Q5 z6 y
public:' S, V; P4 C7 ~9 K4 q
String(char *s="");
" c' p4 t' X) }3 H2 d String(const String&amp; s);" }( N6 B* P) u* ], A
~String() {delete[] str; delete[] pre;}
, I, C! p4 s8 M String&amp; operator=(const String&amp; s);/ h3 d+ U* U( `
int length()const {return size-1;}
# f% P+ l- v. l% [2 `! ^ int get();% D+ s# A" C) W2 J3 C
String&amp; change(int *p,int n);
+ l( y0 {, P, K, ~5 i void get(int *p);+ P# ]3 p  m- F: C# |* r) H6 H
void display(){out&lt;&lt;str&lt;&lt;endl;}
- z( {) w% w( B9 M8 uprivate:  j5 M" B1 U. E5 Y' d
char *str;. C* ^+ b, j9 Z* O
    int  *pre;# D% _8 D2 |% M3 P' ^
int  size;. z7 y- O; S( w! U& K5 {
};</P>
% |8 S7 g4 H) @<>String::String(char *s)
* D# @& f# S2 s! I: U{
5 O) m- f. b7 i; @$ V( Z& F size=strlen(s)+1;1 J+ n+ h, C) j! K/ j
str=new char[size];
" r/ }- Y! b0 C) s/ h$ ? if(str==0)  throw "error";. q9 w- {" n# N
strcpy(str,s);7 D- ]7 M6 S% a! \3 ?
pre=new int[size];3 Y* x7 Q; m' Z0 ~
if(pre==0)  throw "error";
& V/ n5 e" f# x, h  I4 k5 N0 a}</P>
+ g$ h" j- `1 O$ n3 T<>String::String(const String&amp;s)+ Y$ o. m& W! U& p) i
{
& S# I! {4 x) o1 K# v# y8 \ size=s.size;
; R/ _# E/ j" O+ Q+ j! z str=new char[size];
- G3 G3 [: S9 I# W if(str==0) throw "error";. O- G# d/ X- D6 P/ F" r; M
strcpy(str,s.str);! J$ w6 F1 u! ~" x
pre=new int[size];" X) ~0 b0 f) B5 @0 M
if(pre==0) throw "error";- s5 {4 D: e% s* Q# C* m" I
}</P>6 F- c. D& \) [0 W0 L: I8 k
<>String&amp; String:perator=(const String&amp; s)
: b5 x% p' A/ H* r{
& x7 X9 a$ \5 o' _1 x' o if(s.size!=size)  D" s8 s1 z# m$ I: Z
{
' D/ }6 V+ [. O& |! R  delete[] str;) z# |! |# F# N0 [& |, ^6 w
  str=new char[s.size];+ U- R5 |8 a. w  z* Q* G
  if(str==0)
% c# Q# }9 i" n8 m$ I# b1 D   throw "error";
, |9 b1 A% j7 ?- _( v  size=s.size;; y( A4 |  {) _& s
}" d" B7 U6 B' k) k( K+ v
strcpy(str,s.str);1 y5 N  P% x& C; t$ j
return *this;
  M( }2 {; n6 P. X  y}</P>! |) \" i5 |1 u! T% ?4 k; u
<>String&amp; String::change(int *p,int n)//将整型数组改成字符串5 y8 j+ t! l% O& a
{
' s9 S5 B2 B0 j  {& ?- t1 b int i;
* s0 }* @! j% o) E  p: b1 p4 X delete[] str;
8 v* x8 X& U9 L* i str=new char[n+1];& n! h, S% \; x4 y5 Z: A9 }3 X
for(i=0;i&lt;n;i++)& A" V+ f+ P1 U: G) Q% K* e
  if(p&gt;=0&amp;&amp;p&lt;=9)0 ]6 U+ T1 Y& s
   str=p+48;
: u  N; p- F; F( K8 [  else& y) |( U- N/ i
   switch(p)
& X; d  v4 |! K# Y( T   {: N) K9 g! |) G; ^8 v1 A
       case 10: str='A'; break;( e8 A2 U$ c* M, Y: t5 K$ `
    case 11: str='B'; break;
( f4 L+ C% i( [# ^  r    case 12: str='C'; break;
5 a, k: a! l' F/ x# ?       case 13: str='D'; break;  E( E5 u  o" S- c  s" V
    case 14: str='E'; break;
: A& e. a& q9 c$ L0 O/ A2 `    case 15: str='F'; break;
. Y, p1 W* v4 o, o   }
, x1 ^  W2 B. b1 }- a8 ~5 v  str[n]='\0';
( _9 b- l, d. `; u' c  return *this;! T- C0 j4 x; u, o
}; G( M1 D. O' j; c
int String::get()//输入一个字符串7 c4 j) n& i% v6 V5 g. i7 i
{" R: }- I$ L; `- e* j$ w1 d3 F# l5 ~
char tmp[40000];7 p+ ~/ j: D; Y
in&gt;&gt;tmp;
- l% ?/ v1 h/ R delete[] str;* n! v- {; b# d9 `) r1 C2 r7 s
size=strlen(tmp)+1;
" H# Z2 i7 S5 z str=new char[size];4 e) J4 F7 ]# v- y- I, ?% Z
if(str==0)
8 z0 t1 Q! l8 k2 ^  throw "error";) M& g. y. v0 d" X8 W
strcpy(str,tmp);
7 c# R# ?+ V. @6 V! U  Y9 V2 B return size-1;
( V$ w- {# e5 f  m7 U5 n* w}</P># y( j- t; I: f
<>void String::get(int *p)//将字符串改成整型数组) i% m* _- b+ g
{
% q; J; A/ _0 s! C( E- Q int i,j;- Q& C2 |" }2 Z) ?/ G- T8 K
for(i=0,j=size-2;j&gt;=0;i++,j--): {6 E5 X& J. {
  if(str[j]&gt;='0'&amp;&amp;str[j]&lt;='9')
  e& z# U& f+ F/ q      p=str[j]-48;# Z1 F5 u2 V, w8 }* e8 k3 ^
  else
9 N3 x( B! k4 b8 Q' c  {
2 ]8 p+ h4 v6 |   switch(str[j])
% _& Z- @) ~( y7 \   {# k4 ?" F: A& W: h
       case 'A': p=10; break;
  t+ N1 k* b8 F2 w& O) P) ^    case 'B': p=11; break;
# C+ ]' A. z/ q6 s9 @    case 'C': p=12; break;
0 n7 x/ C; b1 {, Q7 ?/ v7 [       case 'D': p=13; break;
* `. U2 G0 C6 K    case 'E': p=14; break;9 @7 n3 r' W# W7 t7 a
    case 'F': p=15; break;
7 y- z8 [! W! v; b- z   }( ^0 r. C0 G/ q: z: a1 c; S, u% q& O+ w& q
  }
* U/ V& l2 d) G. P7 g% y$ ^}</P>
. v2 |* V: ]8 ?7 ^<>void add(int *p,int &amp;m,int *c,int k)//将一个数同其倒置数相加: @/ W! X- W: p, k/ g0 i7 m
{
* H0 P' S2 d  w4 S3 e3 J# a# P2 p* _) t int i,j,a=0;4 n+ z( q1 i. @2 s7 t
    for(j=m-1,i=0;j&gt;=0 &amp;&amp; i&lt;m;j--,i++)6 z' u! Z6 d8 K: L- R& Y
{8 @2 X; |! c5 I/ w+ E0 N
     c=p+p[j]+a;
7 c5 J/ C, v% K! i2 `  a=0;
, y; J7 s3 u# ~' d2 i; M  i: T0 F  if(c&gt;=k)
( U* K0 y/ e9 j8 o* [3 P  {
' \7 Z( S3 I8 }7 [) P7 \   a=c/k;3 t" z5 `( W" T7 ~$ P: \
   c=c%k;% f( G$ n4 _, i+ ~: B( f
  }# g* l4 S: Q6 P' l" F& Z
} ' G1 s! S7 }! Z7 H  X, y3 w
if(a!=0). A  u( r6 p; p# E2 o8 p
{. @6 T9 G" [0 I# e; x+ B
  c=a;+ `; N+ n' C0 M& G; X
  m++;" H2 H# T+ ]5 K) i6 _% m
}/ j! v; U) B$ j- ?9 _
}</P>
8 n- A( V8 j. k9 O  K: l9 O<>bool match(int *a,int n)//判断是否为回文数  z9 e* {# S) y- Z4 k8 L
{$ g- B8 I2 m& A4 L
int i,j,h=0;
8 {$ v; o. {* O1 v! t for(i=0,j=n-1;i&lt;=n/2 &amp;&amp; j&gt;=n/2;i++,j--)+ l/ G0 s5 r: ]( J/ @$ r# W5 Z
{
2 ^3 w! D% Z7 b3 D  if(a==a[j])$ F' L* j9 p/ b' M% ]
   continue;/ N0 [2 I* P# T9 h9 G) T$ e
        h=1;! y3 e4 B( Q0 H2 E
  break;* n9 g; c) U7 t: ]
}+ c( ?) w: X( W4 _' F; f' d
if(h==0)
6 Y6 e7 s: a1 V8 E2 |2 f/ @  return true;
  L$ j" t( t/ c. h, Y else
2 `" M% }. t/ m6 X- d1 X% H  return false;
9 I$ h& k7 V" _$ M3 E}. x- G8 E5 F! Y( a1 ^1 M  R6 ~+ O
//clock_t start,finish;
5 g, W, E6 f! D3 m0 Z/ R& p  Lint main()) N8 x- |2 t' D" T
{//start=clock();
; b) b* S# c0 ^: X3 A% ] if(in.fail())- R1 T. l: j) h8 Q0 @+ w
{
7 d' C+ I) Q+ J* {7 q3 S" t  cout&lt;&lt;"the input.txt is not exist!";
/ t3 W4 b" H5 F! q' O/ @$ r  exit(1);2 i+ u' k9 p- A3 k: T
}
5 V" l% `5 J; c  d8 l String s,s1;* b6 \4 ^' c4 {1 j) K9 F
int n,g,k,*a,*c,m,h=0;
2 ?5 g( {+ F/ e* e$ G( p    in&gt;&gt;k&gt;&gt;g; ( I( P( O8 c7 Q  h: T5 p
    s.get();
( _1 G  {. P" ]0 C( ?) F9 M) }
/ f& V' P2 g  X0 s# d/ [& A    n=s.length();
# d3 w3 R* Z, Q- w* ^ m=n+g+1;' f3 Q5 f0 n" h- h
a=new int[m];
( S- |1 c, O  y5 F, ^: \7 x c=new int[m];
8 C1 R/ k( O# w% ^ s.get(a);
' ?8 a1 i2 ~, M3 \" a8 n' |6 { if(match(a,n))
0 k/ e* k" Z( L3 x$ R9 w* ]( \: A {9 u+ l% _* |; D: k) I  Z! \; A" L
  out&lt;&lt;0&lt;&lt;endl;" h* f/ w* i) v2 C, N* J7 r* m" L' d
  s.display();1 _3 k7 g7 Z# G
  return 1;
# m( ]7 q* p1 e, }, |- w7 L' U( y }
: I% g- Y$ ]7 w1 h+ R& i$ i do2 J- I0 q, o0 }- Z5 g$ r8 p0 m
{! N2 ^% j1 [+ ]' E: U
     if(h%2==0)6 A. F0 T! d/ W" P- ~6 b
      add(a,n,c,k);
3 P% ^0 p5 N+ ^; g- `5 l+ x) |% K" Z3 L  else' o; Q6 O, P! |. B- F
   add(c,n,a,k);7 A* Q6 d( ^5 \4 I* r  G& t# a5 }1 L
  h++;
: N% ?1 }1 i- |: p, }; u* Q  if(h&gt;g)  s, I' q5 F' V) q8 `& s( g
   break;$ i. k) M% L3 x& i
}
4 X  T, L' U: b( o# U+ D while(!match(a,n)&amp;&amp;!match(c,n));
9 A+ [: ?3 d& P# G, R if(h&gt;g)+ s( P1 u4 J7 r0 w. \
     out&lt;&lt;"No Solution!"&lt;&lt;endl;
* y5 P5 x' t4 ?/ |) r5 x) P else
5 ~0 k& I8 m$ t0 b, D, u. P5 a. N {5 G" _+ m% _2 I$ F
      out&lt;&lt;h&lt;&lt;endl;
  Q$ G5 y; U" x+ P0 F2 j     if(h%2==0)
" ~2 d, Q# E) g8 [      s1.change(a,n);3 ^" d2 s( Z' i% g, R$ v& I
     else
( O6 S. y, g8 {' H! k9 {  `      s1.change(c,n);
- r: H+ f4 I" ?5 @1 d     s1.display();' a1 D2 y2 n# @/ u4 C6 e
}
  w2 F4 p* \& o0 h# S1 D+ B# K delete[] a;+ q8 {" H( h! K5 A$ s; J) Z/ m
delete[] c;  _; |5 x( w/ C3 h
// finish=clock();
8 W' ?( V0 X0 F+ {. C5 A( v// cout&lt;&lt;finish-start&lt;&lt;endl;
  o% x! r; l7 u/ ~9 W, E# V& w4 }! V. @ return 1;5 q, m4 B1 }6 S7 n' x' W
}</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