回文问题（用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)' d! t9 d7 X! o: A" @ |; U- [
str=p+48;6 Y W0 Y0 }" N! v0 ]
 else
5 k4 p: V7 C+ y G" W& F; M+ k switch(p)7 ?3 ]3 x" b, J. J+ w
{
' ^! C0 _/ n I+ ^" S3 \ case 10: str='A'; break;
' U; M+ u6 K3 q8 H) u case 11: str='B'; break;7 Q: J) u/ S' X/ `) c. h
case 12: str='C'; break;
: x! E' x: \- y- @5 o) B7 O$ Z case 13: str='D'; break;
+ B# Y: w5 W! X1 L5 Y+ \ case 14: str='E'; break;" e( X q$ Y3 t0 T' q. A2 H9 A
case 15: str='F'; break;
+ i) g8 ?( i8 n L }
! E4 j8 G' h, O. ~6 O str[n]='\0';- {3 M/ i2 b' k$ \7 e7 \
 return *this;
4 S: ]+ V* H6 c6 y1 P% J}
5 W. t2 G/ m* b4 xint String::get()//输入一个字符串' D g$ w. \4 I% d) V5 T' M3 r
{
: v! \* ] d' H2 [4 U$ W char tmp[40000];
2 b& t( x" x- q5 l in>>tmp;) L8 A. G6 a/ c/ E) s7 u, _
delete[] str;
6 f) z; Q4 X C% n. l3 M t size=strlen(tmp)+1;0 }5 o" z1 t& U8 x( h/ l! r
str=new char[size];" P& I, e. m2 ~/ U5 q ?0 }
if(str==0)
5 n/ o }$ t3 d; f. {# E throw "error";0 ^' a) p8 w" e2 C1 p5 i/ W
strcpy(str,tmp);
* G6 `6 Y# h; ? return size-1;
& l; \4 Q5 _, M: R! Z3 ]}1 x9 A9 i# ]/ m3 H$ W( I. x
<>void String::get(int *p)//将字符串改成整型数组: W: N# L8 e( {
{( G) O& M- c" [+ v$ m+ a
int i,j;# i% n4 R' q9 `
for(i=0,j=size-2;j>=0;i++,j--)
8 q9 c5 @" d# u: H* f: Z if(str[j]>='0'&&str[j]<='9')) d+ x) p: \) K& g4 p p; @
 p=str[j]-48;+ m8 l1 {7 c0 D* Q1 J0 Y
 else
. C4 v& G! T: C4 d {/ U. _+ r, s4 V# a/ i
switch(str[j]). L9 j9 A0 T$ Q7 S5 I! y
{2 ~( a; ~6 O# x; w" D
 case 'A': p=10; break;) t3 v) C& F+ s0 _+ r
case 'B': p=11; break;/ o* r6 i9 o& j
case 'C': p=12; break;
/ _; \$ S: w3 _5 A case 'D': p=13; break;$ O# l3 e! D/ B* f" l: J) p0 c
case 'E': p=14; break;
) M0 F$ }( u9 G case 'F': p=15; break;
5 p5 R" V' Q! Q8 y }
1 ~; G, y: Y' _/ ^, N }7 {: O: p* R/ F# K6 ~
}
' x$ g. u4 R i3 q4 c i% E<>void add(int *p,int &m,int *c,int k)//将一个数同其倒置数相加
- K1 T. j& R: T3 I6 A! V# m{2 |7 Y4 G4 z8 F
int i,j,a=0;8 H- T; \+ q3 M, l. O
for(j=m-1,i=0;j>=0 && i<m;j--,i++)
{. R7 {; w5 L7 ?0 T5 W
 c=p+p[j]+a;2 B& c9 d+ j! T! Y9 K
 a=0;0 y0 \. d3 T, L l: t0 c
 if(c>=k)
3 s) _% a1 w% X; W; D6 ^ {/ V) k0 Z$ e9 R' B3 _. O3 \
a=c/k;$ T/ V! Y+ `+ f% H# M0 f
c=c%k;
1 W6 W# Z8 v3 z4 u3 c. \ }: }3 D2 K' Z+ B, n% P/ B; j
}
8 i2 I% X7 B( s/ W% @ if(a!=0)
2 T! [6 a3 R p* @2 @0 ? {$ e& A' a8 Q9 }# F0 V
 c=a;
0 ^- Y0 J4 y* ^ A3 Y! ~ m++;# y2 a2 `# Y% f. ^. I
}
, _) e% _$ F, N0 }8 @2 d}
& H9 G2 B. V6 _<>bool match(int *a,int n)//判断是否为回文数
: Y; o5 x% y1 R{
* I+ N) }1 D/ t$ i. O* i/ V( ` int i,j,h=0;
" L( f3 ~ `" J7 y2 e* q/ X for(i=0,j=n-1;i<=n/2 && j>=n/2;i++,j--)% k4 P' `2 t8 ^9 k+ \
{2 l! C- a3 Z, U* B
 if(a==a[j])) G& z; C2 Z% O# Q% b# R
continue;1 O/ z' B7 X5 g) D6 B: u& K
 h=1;* I1 x( ~2 G, |: Z2 E! {2 r: |' a8 Q# A
 break;
# f. J7 w$ |) l" I7 _7 W& \ }& e- p+ G1 f3 R: Z6 |$ I; o
if(h==0)+ v0 w3 r& L6 T$ H. V1 q$ K0 r
 return true;& `) i9 i+ ~6 A$ N* ?# ~
else
& d! O- ~. M6 j. N7 o return false;. `! y4 ^9 X, l; Y- E
}
, X: C$ \8 U; O( t9 S: Q4 j- J//clock_t start,finish;2 j/ M+ K( @$ n3 H! R
int main()0 c3 l) t1 h( y/ M: j: D
{//start=clock();
6 {, v; s& v4 a" Z4 }0 r( {! Q if(in.fail())$ Q3 ~4 K: o; F9 j3 @/ V
{
/ A Z. X9 L4 n) `6 b3 y8 D: X cout<<"the input.txt is not exist!";
% t) q1 D2 ?- d7 r. v exit(1);5 E* T; w0 F8 N4 s3 o3 ~
}. x4 K6 @2 v, g( [
String s,s1;
 e$ f4 ~; m" r* n int n,g,k,*a,*c,m,h=0;
) w! o3 G( x8 U; z8 U0 d in>>k>>g; ; f5 N0 X; `8 [+ }
s.get();
$ b! j4 d1 d1 N* a3 l+ x9 ~- e ( B2 `) i9 P) }( F+ `
n=s.length();
' C7 }# R) ~- i m=n+g+1;! h: b5 F* |, w6 J6 P% x+ Y
a=new int[m];2 r5 y, y: n& Q3 I! T: h8 P! k
c=new int[m];
& M; ~/ U% c3 b0 K/ k s.get(a);
) F: D4 X1 z4 V. W! E if(match(a,n))% j3 T& N( X; S! Y, L( [2 K* G
{
% v8 |( z! R7 }& ?& _ out<<0<<endl;/ V) O2 F! K% H8 z4 b9 u
 s.display();; l) v$ l+ S. B T. `6 {* K
 return 1;
: `) m! b/ k& r0 a }
 o3 K- p2 E$ k: G' ^ do- e0 p0 A; F1 X* s# u, U( P
{
8 g z- A" m6 m# ~* ?& S1 K if(h%2==0)
/ h, c" ~/ r* r `3 [! v add(a,n,c,k);
" Z! a! ~% b4 _4 D# N. Y8 ?) @ else
1 Y0 G3 I# i: V- R add(c,n,a,k);& J% X7 e2 W6 s+ |9 j
 h++;2 o& w& B/ ^; F* _5 ?+ J9 Z4 C3 }
 if(h>g)7 D0 g: F! C# }* j! j
break;
% V% U) W: F8 Y$ H/ z2 R }
/ w5 W" K9 P" l+ n* I while(!match(a,n)&&!match(c,n));
& A& u+ h8 |( Z4 a- o if(h>g)
- c* j; _7 o6 [* e5 s9 _ out<<"No Solution!"<<endl;
8 G+ v. s" V; Q% s+ O/ E else( A) y2 I1 L! G2 n' g3 D# M
{
$ \) Z L2 y" |5 t/ q) ?- m out<<h<<endl; h) V6 h( C+ i# a% [6 [6 n5 ^" }' U/ M
 if(h%2==0)5 t3 x& L; m, N. |
 s1.change(a,n);8 a3 J, m. A0 }5 N- G; G3 ?. q
 else
7 Z+ K3 T( |5 {% P& I a' m) x& o s1.change(c,n);) s% ?/ L0 t; L/ h0 G% H3 s
 s1.display();. u z, r: Z$ M' ^5 J
}+ Y) d* o/ |. [- V$ M+ f! M
delete[] a;4 O& n. z; J M0 b8 f4 t! V5 P, ] S
delete[] c;
6 j; S% Q0 F+ {& n' C- ^// finish=clock(); u1 Y& C% \7 t; F* G
// cout<<finish-start<<endl;( S) q C; G6 d; G1 N6 V- a% N
return 1;, v+ z8 y! ~. W0 h
}