数学建模社区-数学中国

标题: 回文问题（用c++编写） [打印本页]

作者: lynnyan 时间: 2005-4-22 01:27
标题: 回文问题（用c++编写）
<

>#include<iostream>
#include<fstream>
#include"string.h"
//#include"time.h"
using namespace std;
ifstream in("input.txt");
ofstream out("output.txt");
class String
{
public:
String(char *s="");
String(const String& s);
~String() {delete[] str; delete[] pre;}
String& operator=(const String& s);
int length()const {return size-1;}
int get();
String& change(int *p,int n);
void get(int *p);
void display(){out<<str<<endl;}
private:
char *str;
int *pre;
int size;
};
<

>String::String(char *s)
{
size=strlen(s)+1;
str=new char[size];
if(str==0) throw "error";
strcpy(str,s);
pre=new int[size];
if(pre==0) throw "error";
}
<

>String::String(const String&s)
{
size=s.size;
str=new char[size];
if(str==0) throw "error";
strcpy(str,s.str);
pre=new int[size];
if(pre==0) throw "error";
}
<

>String& String:

perator=(const String& s)
{
if(s.size!=size)
{
 delete[] str;
 str=new char[s.size];
 if(str==0)
throw "error";
 size=s.size;
}
strcpy(str,s.str);
return *this;
}
<

>String& String::change(int *p,int n)//将整型数组改成字符串
{
int i;
delete[] str;
str=new char[n+1];
for(i=0;i<n;i++)
 if(p>=0&&p<=9), W% ]8 G( Q8 t% Z3 ?
str=p+48;4 O+ ^! i: L9 |1 Y2 ` y. M
 else6 L* `' j, o7 E* f( ~! O
switch(p). A. \9 n3 M( K; [( u7 K
{: L/ X' h- ~" m, P1 C+ w8 \0 ?
 case 10: str='A'; break;/ c8 d5 x* V" X% E1 n) C! s
case 11: str='B'; break;
7 B% ]$ ?5 C- j }, K case 12: str='C'; break;
% k8 H. o; N! Y& ~, A: G& d case 13: str='D'; break;
" b n0 z r9 T/ N& l+ P6 ] case 14: str='E'; break;
/ p6 a- }; K) A( O8 J5 k; w case 15: str='F'; break;
; L! ?* L! K# C g+ w0 U5 ~) C }
' }7 i2 Q3 x$ P# N str[n]='\0';) x5 r) C- k# x1 P0 H+ m- X: d
 return *this;
1 M& X! j4 d' ]6 ?}# }8 T A, ^) f$ c; q
int String::get()//输入一个字符串
& a# i5 r! e/ U' ~{4 Y) Z# |( d M; h: J( C7 p
char tmp[40000];
9 s6 Q" F* n4 j3 e `! n# l in>>tmp;
, d8 q2 h- S$ m7 f ` delete[] str;% ?2 u) e! z# e8 O+ o
size=strlen(tmp)+1;/ G8 A$ y- T" l- h6 T9 J. S
str=new char[size];( X! ~5 o2 U# P5 Q
if(str==0)
' @; @9 P) M S: D+ S throw "error";4 V% A1 O T$ n( K
strcpy(str,tmp);- p; f/ @9 y; c9 D1 R5 N0 B6 G. P+ `
return size-1;
: [% s7 A2 b i3 m5 I- i8 T}
5 i+ g$ E( b: P+ _; U/ Z<>void String::get(int *p)//将字符串改成整型数组
- ?, w3 V+ h8 Q8 @. C* m, R$ P{! J" L1 W4 s; n; ?( ^6 u
int i,j;
1 ~1 s5 ]8 Y9 f! \* h3 @ for(i=0,j=size-2;j>=0;i++,j--)
) i( D* }/ {+ W% }4 i if(str[j]>='0'&&str[j]<='9')
1 v5 u0 l# ^0 c5 q; S6 ^) m p=str[j]-48;
$ I0 E) l1 F! e2 T else
0 J5 G3 r* d+ p7 l3 N" z u; r {
* ^4 F4 d6 L1 \ switch(str[j])( h, @7 s! ^: ~+ f: s
{# F5 W# q3 X% R* ]6 P6 L1 d J/ D
 case 'A': p=10; break;
$ K* e- B* f, G; l2 U9 p& a case 'B': p=11; break;
$ B+ h& b6 T% @9 A, q$ P% ?! D7 K case 'C': p=12; break;6 l H" O Y# ]& w' L( x: O
 case 'D': p=13; break;
0 u' C0 t0 `" G/ g case 'E': p=14; break;- H2 C F9 y. F1 ]
case 'F': p=15; break;8 ]/ x8 x( F6 e# p
}/ |6 o$ G& m/ E! b1 v3 p1 w5 j
 }
0 [3 f3 v2 ?' u2 @5 t}
. n4 i$ }6 b4 v# W, r8 T<>void add(int *p,int &m,int *c,int k)//将一个数同其倒置数相加
5 y; V6 @0 ~, h6 L" ]1 R: B% I{
3 Q" b7 a, r: h9 } int i,j,a=0;
/ J, G0 ]: C( l) |1 e for(j=m-1,i=0;j>=0 && i<m;j--,i++)$ ?; x! a6 P" L* \8 N$ C
{' N* a$ A3 x8 Z u( \5 c# d
 c=p+p[j]+a;
, q0 U) i. n! G4 @& G a=0;# Z# K7 t6 b3 r- I7 Y
 if(c>=k)8 n! \5 M/ Y/ M
 {( E& x% D: X6 o7 E) r
a=c/k;
, o6 X- p8 F' o1 {( F/ @ c=c%k;5 p6 [8 @+ {+ I1 n* b
 }
 Q2 I& I5 {" y0 _2 b- u: @ }
8 V4 }2 i4 Y( s9 }$ L if(a!=0)
5 h, F0 @) }" r8 T! ? { }/ f, K+ a# X" [1 s
 c=a;
% I2 O+ K8 }4 Y/ i0 u, C m++;7 x4 x! _; ?% i9 J. a
}
 h& d' [& d$ b}
- r" v5 b4 T0 [" z; |' G3 \# z<>bool match(int *a,int n)//判断是否为回文数
" X$ S) r0 v0 h) S; M{
$ H% B" {0 r$ d \2 { int i,j,h=0;
& H/ D4 Y& @" V/ G3 @ for(i=0,j=n-1;i<=n/2 && j>=n/2;i++,j--)0 o& \, d, O) g" u c' \
{& o0 V: c0 J3 l! v9 M1 m
 if(a==a[j])$ ~( ]4 ?; A7 T I
continue;1 [% K/ o& s8 v _. ]; \( s
 h=1;+ G6 S3 E, E9 w; E, z0 `3 M
 break;: z" q( G$ l$ s- G; M r# v3 T
}
( b+ m- |: K: B if(h==0)
; I/ x* x+ K5 h% i# x) k return true;# l( F7 p- o: _6 h( I9 L
else
6 |* O# ?$ y# b1 h$ ]. ~ return false;% }; W9 T7 ]! D. x0 R& h# |
}" i* d6 x5 j' N. c- m1 E
//clock_t start,finish;' y! j) G8 Q& G
int main()8 b' j8 d0 U/ p3 G' g3 ?' p3 V) ]
{//start=clock();! z, S- `' o! x+ J
if(in.fail()), p& p: \$ F" ]% L- c! p
{& c1 `# Z1 e4 A3 Z+ A6 J9 Y U
 cout<<"the input.txt is not exist!";8 E0 Z+ k( M5 E9 X5 x7 K1 J
 exit(1);; U8 P2 L5 W' z v
}+ \- v( J2 S0 F$ m9 K6 D7 k
String s,s1;
% \+ {/ K, v$ W2 B6 k a int n,g,k,*a,*c,m,h=0;
4 p8 g2 L; W5 D' b5 Y2 C in>>k>>g;
7 ~4 \/ R. }6 R# T, K2 C4 A s.get();$ L5 r( t3 O0 o9 r* j0 g* K/ y
 r5 c2 y" l9 E
n=s.length();2 X A+ C% J4 K
m=n+g+1;
$ c3 d1 G. ]* t+ j a=new int[m];
0 z$ x* n l0 G c=new int[m];# g) W' n$ {0 y) G# b# g
s.get(a);
" h K4 v' o+ B9 @' }8 V if(match(a,n))- W: W& Z' m( _5 Z* J9 M
{
 out<<0<<endl;7 g l* _4 E' b3 ?3 h( M( A
 s.display();
1 y+ h3 `% q" Q5 @2 N return 1;
! Y- E' S- {8 L }9 a4 E& a* v# W6 P
do
; i( }4 g- x+ F; E {
9 U1 {- F+ M$ C4 w. r/ ? if(h%2==0)2 i/ o. J! Z2 A% K9 E* V& ^# o, [
 add(a,n,c,k);2 \" R8 ?' _- n* Z
 else
1 p- b/ i% m" z0 [# e5 F add(c,n,a,k);
0 [% r) z: ~' s' l u# d' e h++;
6 y7 _/ |6 o8 V* g% x+ b" K if(h>g)7 H5 y1 u; h; \8 q5 S
break;. }" X' s1 h& W" f( F
}
/ A" n( R! ^8 H7 o: x while(!match(a,n)&&!match(c,n));
; N8 g* z2 Y2 C if(h>g)
 d1 u% |* V }! e out<<"No Solution!"<<endl;: z( X& n$ Z* P) [' _6 }2 X8 E
else
/ w& t5 S) ?6 K( I2 Z: g2 O) h, V {- O4 ~7 E. C) V6 F
 out<<h<<endl;
3 p- s# [- [7 Q& E4 @. V if(h%2==0)
/ e6 o L. j& R* e' {4 U s1.change(a,n);
) B5 ]0 U5 j! C8 t& J. x3 L else
" }& I( L, w3 [! z+ ?, g s1.change(c,n);
9 D* Z9 g5 a4 N: R4 Q2 W3 m4 ` s1.display();( e8 h7 C% t: s/ \
}
+ G4 r7 O% Z8 l$ S# b delete[] a;5 `+ C, N. b9 {% L* i& u1 \1 ]) D# K
delete[] c;
# ^7 B9 u1 W+ n4 I J0 }( X// finish=clock();
) x( x1 e4 E: { E4 T// cout<<finish-start<<endl;$ K& u* W* E& `4 J: X; z
return 1;
# e4 r# E9 B# ]( A$ g* o$ f}
作者: txj66 时间: 2005-8-22 02:00
<>谢谢
作者: zxl_lucky 时间: 2005-8-24 17:02
<>谢谢啊啊 
作者: sabbanji 时间: 2006-11-21 04:52
　　一个指针从头向尾走，一个指针从尾向头走，至多走到两个指针相遇或相错，就可以检查出是否为回文了。上面的代码怎么弄得这么复杂？
作者: darkghost 时间: 2006-12-11 01:57
我觉得用堆栈也可以实现吧，先将各元素压栈，然后将其中的元素复制到另外一个栈中，再出栈比较。 呵呵，可能还要麻烦，没做过。。。 
作者: mustpeter 时间: 2006-12-12 16:42
回文是什么意思？
作者: zhuph 时间: 2006-12-26 09:11
有没有汇编写的？
作者: hero1632 时间: 2007-1-2 18:08
不错，正在找
作者: friendfb 时间: 2007-1-6 09:09
设计算法的时候，应该充分考虑时间效率和空间效率！但是两者往往也是互相矛盾的。一个好的算法可以应该权衡这两个方面；或者更加特定的需求来设计算法。在我的记忆中，回文是需要考虑标点符号的吧
作者: zhaoyunfei1126 时间: 2007-4-7 11:50
什么啊？？？
作者: seashell7 时间: 2007-4-12 17:39
3Q~ ~
作者: hanyeyu2009 时间: 2010-12-5 11:01
看看是什么
作者: zengshengda 时间: 2011-1-30 21:52
很强大！！！！！！

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