回文问题（用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)! ]& h# X/ K8 @* K) T" o1 w# U
str=p+48;
+ ]! A `: w! |1 o/ T) G! c else3 U* n7 l* x4 h8 v- C* R6 ^' E
switch(p)5 v& u q) s2 m% }/ g
{" t/ S' j) _. v
 case 10: str='A'; break;0 h, Q3 }# ~8 p; _! d3 k
case 11: str='B'; break;
) \- l8 \' c2 b4 q5 J# A case 12: str='C'; break;
0 D+ z5 w& |( u' ^% _ case 13: str='D'; break;* `( L7 M9 g8 f, @: `
case 14: str='E'; break;% p: f8 f/ b% |* d
case 15: str='F'; break; b" g1 d- k% V, K
}
$ h0 s3 Y) W0 E6 g3 s str[n]='\0';" \3 ]. _: V0 L4 y. I! I
 return *this;8 ^+ m' \6 s- e, ?/ @1 ~$ A
}
int String::get()//输入一个字符串: U3 Y3 S' w) R1 I; |+ Y8 m; U) [
{2 x+ d0 c4 t- t* T. T5 z
char tmp[40000]; _# v3 C+ |1 m. @) D7 H, m1 f8 o' Q
in>>tmp;( ?( N& j5 ?; |5 y. N
delete[] str;) b6 N8 v4 s3 k P
size=strlen(tmp)+1;7 f, N2 X' Y) k$ ^0 p8 y+ b
str=new char[size];
2 Y% P( t* ^) ~8 D) [' O9 `1 u8 Z" P if(str==0), P7 n- Z5 Z% M6 e0 l' H2 h
 throw "error";
+ p. D1 @% }* r4 U9 C strcpy(str,tmp);
8 c( z8 x6 K7 } return size-1;- n/ T$ F9 N/ C; R
}
! _# V V& ?$ w Z$ d+ x6 B<>void String::get(int *p)//将字符串改成整型数组
3 L* q3 p; W' u* j1 `{ _; h4 T2 T3 w6 Q
int i,j;& k8 d6 Q* c, Y& Z
for(i=0,j=size-2;j>=0;i++,j--)
; K' z) G$ k9 s* d if(str[j]>='0'&&str[j]<='9')
4 f0 |3 C5 d" _* K- a8 U$ E) j6 n& u p=str[j]-48;7 G& [ Z d4 f5 O7 K
 else7 ^5 a! P. j& }: }
 {1 H6 Q- y& E( X K6 Y6 E
switch(str[j])
# \: Q" v2 M' v. v; _ {
8 _, P5 W$ M ?) z% J8 f. r2 ]& g: G case 'A': p=10; break;
# Y8 u7 g4 r5 z- [. ^ case 'B': p=11; break;& Y0 \; T6 y7 R, n4 M
case 'C': p=12; break;
/ D' t3 Z) S7 A! r( Q1 j case 'D': p=13; break;
! q* h3 [$ {9 ]: n# i. Q$ a case 'E': p=14; break;
5 e( ~2 M; T8 U3 H& I+ Z case 'F': p=15; break;
0 D) H. f' \$ T- t }) r. c& p( W4 F' d" u
 }
0 O: U ], d0 y7 g' I} W' N, b' `9 I! b1 j
<>void add(int *p,int &m,int *c,int k)//将一个数同其倒置数相加" u& r r1 k0 M
{
4 Z. T& w5 q8 B& U5 P1 { int i,j,a=0;+ r; t7 s8 n3 I' c
for(j=m-1,i=0;j>=0 && i<m;j--,i++)
+ ^, P/ W# m: X4 ^% N# ?! N6 ?% M {
3 k9 @; U0 R: A- A. f5 L& M c=p+p[j]+a;9 u/ Y6 y- B1 A) S
 a=0;
- G. ?( a6 b1 K$ U4 L0 J if(c>=k)
4 P, j) v$ g3 F2 M' G. O {& N4 V y7 V1 P9 G, X& _- S* I! D
a=c/k;
6 m2 c `# \2 Q: _ c=c%k;" [- E1 V, e2 z
 }7 T7 U& f1 I) r: a
}
6 p; e# ?9 l+ ]1 m/ ~# W if(a!=0)
; I& H. K1 y% ~2 b$ [% R0 C* {' K8 H {
- F' e: Z0 F" R" S6 e5 U, y# L. G c=a;
1 D6 O, i u0 ], g: ^) I" C1 R m++;
# W {% w; Q% S7 F2 u( @ }( ?0 b7 i4 a7 R B
}
7 }: ~, ?2 [5 I, r0 u5 D3 n+ S<>bool match(int *a,int n)//判断是否为回文数
% n f& E$ ]- p% X p{
! k* p( \& ^" k% P8 U int i,j,h=0;
9 n: [5 \& d( F for(i=0,j=n-1;i<=n/2 && j>=n/2;i++,j--)
% y9 {. Q3 K' v( I+ @! P$ ~ {
1 t# C" x. a6 E' o1 b7 w% n if(a==a[j])5 ?% s' g& G: o2 E% j' b
continue;
, H& a: W. H |/ } h=1;! o/ N' A9 b9 U# \4 p6 u
 break;5 V: Y# x9 u( W$ ~$ U8 |7 w( o4 I- p* g, Q
}
6 L* Q9 C: Z+ d2 J: h4 { if(h==0)3 l' k( o, r3 L( Q/ o9 k' T
 return true;
7 C0 ~, e2 W6 m4 N* n$ X0 ?/ I else
 J; z o) a9 J2 T* B- b- K return false;
$ J" Z1 o, {' r+ v7 U2 Y4 J}
2 ]) K1 e9 e2 k//clock_t start,finish;
, ?- ^6 q) T4 C! ]- P/ @+ rint main()
1 W. y: w/ B! a; r$ u{//start=clock();8 K. B' y. D$ ]: F
if(in.fail())3 Z' O: e$ |" v `9 I8 `6 I
{; y2 A5 u6 R0 r0 M0 o, U
 cout<<"the input.txt is not exist!";" @1 r! S0 u% d4 i/ r. ~# b: f; G
 exit(1);
4 o, |' N5 a! W6 Z } p3 _7 w; f; Q& ] s0 Y
String s,s1;
$ ?' H: k1 ^ _, @7 i int n,g,k,*a,*c,m,h=0;5 J! X5 z; c2 k2 [( ]
in>>k>>g; 6 T& z0 t. P* |1 W& G3 a
s.get();
$ b& j2 K: _5 G* v
$ K( C# Y L9 ^ S. a n=s.length();+ i" N7 N, f) `' F+ {
m=n+g+1;
8 |" L6 C/ j* F a=new int[m];1 g0 J: w( \& t$ y
c=new int[m];
" H: h/ w& [- ^+ [) M s.get(a);3 U1 f/ }0 v) g- @+ J% f6 n) F, d" p
if(match(a,n))
) O; @, V! y# P/ G5 L+ O5 z {' t! H o P4 D8 x
 out<<0<<endl;, N# y% `" A7 {0 f+ m; d
 s.display();
! k7 t! A' d, l0 a return 1;
( \0 b; w/ Y3 K. q) h }8 N! J5 f) B4 E; a3 C8 ?- d, y
do
2 }6 O+ \5 U$ p1 ^% |8 m {
$ I9 ^% F1 I" q7 A& E6 b. [7 I if(h%2==0)7 l* t. @* R. H. e; L/ C: i
 add(a,n,c,k);
+ [3 M5 H" t ?/ C! K7 |$ y else
- R' `4 I# n$ |8 N- s! H add(c,n,a,k);
# { Z8 C8 W% E' \ h++;
: ^9 ]/ O0 V9 I; w% s9 ?% O if(h>g)3 c5 Y7 t* y2 E- X& J' k7 T3 ?
break;" w5 w! ?. S2 Q3 ]. h8 l$ A
}! m. Z, l2 p1 o8 X$ D: k8 M) B
while(!match(a,n)&&!match(c,n));
( O4 Y9 Q- B9 x0 ?. [* {7 H if(h>g)
& C$ E% `0 G+ _ out<<"No Solution!"<<endl;
: D9 _1 l9 v. r6 a; x; N else
' w7 ~7 G: d9 D# T5 f* X6 r5 ]' @9 Q1 V {
/ s$ g7 N& J9 Z* ~ out<<h<<endl;
- H5 S/ O: Q u7 p4 c if(h%2==0)
9 Z4 E5 j% H/ E# e# w' y% S0 r s1.change(a,n);% L- x8 S! r1 I" E
 else, i. v7 s- T6 B. P, w; x0 f% [8 \
 s1.change(c,n);
! `9 n# b" k: o4 _3 b4 C1 y% u s1.display();/ ]& v; i: @ g5 ]+ }9 g0 M7 c7 u3 v
}
4 I$ ?- j8 w z B* d- r delete[] a;
2 I, c0 T* y( T4 W8 X1 S delete[] c;1 F2 r& K. H: h' |" ]4 ]. N: G
// finish=clock();
9 s" e v( A+ c' N. S/ N// cout<<finish-start<<endl;9 ?, Q5 V; k1 ]2 @4 f
return 1;
/ q% y {* q2 I6 D}