回文问题（用c++编写）

[复制链接]

字体大小: 正常放大

lynnyan

2 主题	2 听众	26 积分

升级 22.11%

该用户从未签到

电梯直达

1^#

发表于 2005-4-22 01:27 |只看该作者 |倒序浏览

|招呼Ta 关注Ta

<

>

游客，如果您要查看本帖隐藏内容请回复

#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)7 Y/ r& ^" y4 A
str=p+48;1 q& V/ f7 }2 [' D# j
 else
, B+ @, @8 m! \. P" f) @1 j9 j switch(p)& P$ C" B. @0 _/ u
{% o8 \& S: g* N% l4 v
 case 10: str='A'; break;
+ y5 v0 e6 Q3 W4 i0 M+ r case 11: str='B'; break; K7 c$ _; M0 h i& T
case 12: str='C'; break;
" A- `/ k2 h3 @( G+ y case 13: str='D'; break;
* p/ i0 M' k" I% k1 G2 R8 s case 14: str='E'; break;* `$ t* I% O- y9 L0 _& K' A9 {
case 15: str='F'; break;
2 w; t% s r S- W, a _. Y }+ e) o# [3 F/ _7 J, o! z. }
 str[n]='\0';& D+ R/ u0 z1 w
 return *this;- W2 {& z+ }) n8 w
}
; {: I% Y `: N- k6 Bint String::get()//输入一个字符串
. K- }' b; q0 s z; R) ^{8 {5 {0 a4 |% d
char tmp[40000];) A) T) w; _. R2 u' g
in>>tmp;" M- z% u3 |1 C5 w/ C
delete[] str;
. B* L. X& L" G+ j size=strlen(tmp)+1;9 I6 _" u6 b* v) y4 Y' c+ d8 h
str=new char[size];
$ W* n! H5 V. k% `. ~$ s if(str==0)
9 {/ G& I# G* M2 s' _, l8 c0 x- ~* s throw "error";
; Y# ~/ P% [ A6 k strcpy(str,tmp);9 y5 M1 @) ]" ?8 N! P
return size-1;# }) N4 L- G+ d; K' v1 p+ X
}
 h j- O; A! Y X<>void String::get(int *p)//将字符串改成整型数组( L* G# ?# `$ A3 Y; A
{ O' ~7 F* W3 G3 E; e
int i,j;2 c# D1 {4 q" l
for(i=0,j=size-2;j>=0;i++,j--)
- r! J( a0 I; M1 z) O6 f if(str[j]>='0'&&str[j]<='9')
8 K) T: F4 M3 M8 w p=str[j]-48;
' B& U; S( b% U" a9 b' Q, w else" j ]' Z* H4 d/ \4 _7 I% g" ~
 {! G: u; C2 `/ B1 d9 O$ x! ~. |& Z3 Z
switch(str[j])
/ i+ N- ^$ u# H {7 T( F& _! `3 z, f4 ?7 ^
 case 'A': p=10; break;
& g1 V. s- m; ~% m" [ case 'B': p=11; break;( f7 q! G3 V/ a
case 'C': p=12; break;% s/ J% u" H0 P* e; |( L
 case 'D': p=13; break;9 G$ P/ x* N3 }- d
case 'E': p=14; break;
/ V/ `5 _: _( \ case 'F': p=15; break;, n: _7 f7 G, E u0 l/ [/ B3 {- D
}
- ]. \8 c8 ]. P' _# q' c3 F' _( a% W }3 v( j+ G. m9 {3 u% h
}
 T8 m8 o' b/ A: L6 B5 S" [<>void add(int *p,int &m,int *c,int k)//将一个数同其倒置数相加1 K" k# z+ B: ?5 v; _( E9 A+ f5 w/ v
{" F# J+ ^+ L3 T! R" b5 x
int i,j,a=0;
5 Y# d6 q$ Y% E) ]/ z1 k- [. q for(j=m-1,i=0;j>=0 && i<m;j--,i++)
" q; _ I8 K) S {
: s( p- L- @6 U# p c=p+p[j]+a;
 e8 i% `/ R- }! ]. O3 y a=0;
3 I* T1 X/ n$ g5 u+ U9 G! {/ ]# _ if(c>=k)# B+ Y0 d9 g$ G' Q
 {2 j5 \8 l( t* T2 o3 \
a=c/k;: X# B! V- Q/ k" X9 h0 a
c=c%k;! X$ n+ x3 B6 G1 d! K% W9 ~
 }
: Z3 g) a# a" W* ? }
4 H2 {" J8 Y' q1 m6 P2 \2 b3 J if(a!=0)$ b- n V: z* o7 _) v6 H `, M8 J% i
{, C: v* a: e- f$ |1 f9 k* T. v
 c=a;
( ~# B; p; l( e- O4 { a m++;
) W5 z& X/ l5 \4 j) M- r }* ]- Z! Y4 M( K! Q# c! y
}
4 }8 t/ @5 v. N A<>bool match(int *a,int n)//判断是否为回文数: ^& ^1 b& \. W4 `) Z" h z
{
$ q7 h8 ^! B: l) k int i,j,h=0;
6 W, q' | u* _+ Q for(i=0,j=n-1;i<=n/2 && j>=n/2;i++,j--)
& H5 j- o7 R8 K1 W9 V3 B' k {/ d& h, v( v# ~, I6 {7 _4 F
 if(a==a[j])* U2 W( a9 R( Y8 t0 d
continue;
! k6 K9 c$ o' y2 Y h=1;" `4 i) u2 l( A- W) ^1 l# j( k" x
 break;5 L+ b$ A) Z8 o; a+ ^( G
}
+ [* `' b- r( j1 v9 | if(h==0)
! y8 w$ ^; f; i; ] return true;' J* n# G0 w$ }* h/ C. J
else
$ `+ s4 o8 G/ d7 b' S7 h3 e return false;! D) t4 T- K" M& r
}
, d) a% {9 L0 P; `+ i/ i//clock_t start,finish;' M* m5 e; a# u4 x
int main()6 R: d& U+ N. c: j6 J- e# P# ?
{//start=clock();8 ~! n+ Q' s5 M9 \/ h
if(in.fail())
2 V4 h) N& S) G {/ b, c+ g8 y: u0 {! S
 cout<<"the input.txt is not exist!";( q. L& \$ g- N/ g: v% i7 }
 exit(1);4 `8 z3 M# O& o/ |3 x0 N
}
2 Q$ W( S1 B* U$ \9 s String s,s1;5 D7 H, l" g8 p9 Q7 ^
int n,g,k,*a,*c,m,h=0;6 P! r) M' c2 r! L( a" j. a
in>>k>>g; 9 ?( K9 u" |! ]. m9 c3 g
s.get();, S2 t9 E( W3 b7 A

9 s* ^: t4 L9 X! T* B9 N. e' s n=s.length();, Z% U. N5 f1 l1 b5 `0 v
m=n+g+1;
! i! P6 |6 m+ P2 }9 o; ` a=new int[m];, U2 G) \& A" I# G9 k3 D
c=new int[m];, D ^$ @) ^1 w2 z) R
s.get(a);
7 R c% A* |5 I$ l3 v( K if(match(a,n))5 U( S2 d" N# `( ^8 |
{( r; H% c2 M' P7 l! m# b9 W
 out<<0<<endl;2 d. x; t7 x) M0 u0 ~
 s.display();- C) A' Q5 Y. _7 w* b! L* N
 return 1; ~* m. `5 [, w! t. m2 v
}
* p& p+ {- o X! K do
" S9 x. `' I4 f {
& W3 Z5 o7 a& a0 ~ if(h%2==0)
; i+ ?2 U: P" Y& W5 y, g1 ]( L add(a,n,c,k);
8 S5 W* G$ e/ I else% O- e3 r+ b5 M" U: W
add(c,n,a,k);
, V$ @6 n; t D* P. W h++;
5 [1 z0 J8 i R if(h>g)0 d" T9 S7 v$ j- x5 N2 o" `
break;
! \( I1 J: [& F/ `. I1 C } E( z( o( F& k6 a% }' [
while(!match(a,n)&&!match(c,n));; p; J, G; V6 z/ ?& p% i: D
if(h>g), M( n/ @" Z+ c/ s; o
 out<<"No Solution!"<<endl;
* S( m) G. O1 u0 M) \6 ?, g else9 Y f' D& E: U
{
* }. o; J8 t' Z" a* F out<<h<<endl;
7 \3 s* ^1 ~; h0 y" I7 U if(h%2==0)' B$ M( Q- V; w! P; o
 s1.change(a,n);6 J1 P, H; b# E8 ~8 C/ S" a% Z' S6 U' b
 else0 d4 k) {! B: S L' H
 s1.change(c,n);+ Y: L' ~5 u5 L6 k1 H$ \. g4 ^; H2 }
 s1.display();+ C+ ?5 h1 [$ V( r4 T! Y
}. R. F% s& y2 Q; t) R5 S7 x: F
delete[] a;
4 v. E7 y) _) G W' w delete[] c;
' Q4 M. f8 p4 h" m0 e8 M! G0 T// finish=clock();# D/ W3 \7 e' D! {$ L) t
// cout<<finish-start<<endl;
/ [4 x; X" G1 x% y- w, H9 ~6 R return 1;
! z/ c( V% f! a, I2 E}