回文问题（用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)9 @5 ]: N; t- E. p, C
str=p+48;
# ~8 _4 B: L8 h2 U7 d" Z- }$ [ else
1 N1 I/ p; J7 F7 _+ U) _ switch(p)
( _. }) U8 W3 H3 K2 i: q3 \( h3 \ {
; _/ _% S' J r: Q. q, F) m6 K case 10: str='A'; break;% v1 x& f) Q7 Y( L# P2 C6 q
case 11: str='B'; break;0 I O- x% P! O6 y: C. u- e! K
case 12: str='C'; break; A( q6 t+ _) O
 case 13: str='D'; break;. ^3 ~- L" i7 T0 S% @
case 14: str='E'; break;+ o$ A: j5 ?7 `9 s
case 15: str='F'; break;
8 a3 t9 v5 m8 ^0 I* n }
# k2 U( I% V3 K1 I. B str[n]='\0';6 `( D+ t+ H, X3 _
 return *this;
: P/ P. J2 ^4 e% s}
6 [9 {$ G9 l+ i6 E) k3 Nint String::get()//输入一个字符串1 Z% j- P6 e& Q8 I
{+ B0 ]# e2 T. Q, m
char tmp[40000];% g2 Y- z7 T( S% B7 p
in>>tmp;
5 ?( ^+ B& k3 B% Z; ~" a* S) F3 e- \ delete[] str;
2 G% i" [4 T8 Q5 i% G/ O& U8 k: } size=strlen(tmp)+1;
. D8 H1 H) V2 L# F str=new char[size];2 B# s; T# x. V" \5 T7 c2 t2 C; F; y% M
if(str==0)
; Y: V$ n" n% y2 Y: s throw "error";
! ]; Q0 S i! {' s( H strcpy(str,tmp);' |9 e# ^8 g4 J8 s* t0 R$ G3 u
return size-1;" {- j2 ^" W% `+ z
}
, B( K( _9 c# `<>void String::get(int *p)//将字符串改成整型数组/ p( i6 d( N: J: e
{
# n9 }2 _$ n+ J* V' P int i,j;
* x0 L4 y r& N& c; q for(i=0,j=size-2;j>=0;i++,j--)
 t M+ U: t2 g$ Q# f if(str[j]>='0'&&str[j]<='9')7 _( b) T; x8 R) v& m- [
 p=str[j]-48; c" g7 E; N2 g: a; y6 {6 @ {
 else" n/ o& {! Z+ t$ `0 D) R
 {
# v! c3 P* [4 z switch(str[j])
3 t& S. o. V) [7 z- u2 | { H( ~$ o# c/ @ m% ^7 b3 O
 case 'A': p=10; break;3 |- q: `9 t% r$ h A( h
case 'B': p=11; break;, R* ~5 x7 D$ j" _6 l: g$ Z
case 'C': p=12; break;9 F9 N# P: g' q& \% E
 case 'D': p=13; break;4 U. w6 F7 }9 y- r9 H
case 'E': p=14; break;
) s. G1 G: E+ i. _- \ case 'F': p=15; break;- k1 v" @5 e Q s
}
7 J' o2 P; ?+ a% e+ z9 t3 j4 U }
$ [8 U/ b, O3 k4 c}
" R. v% ?5 D( M<>void add(int *p,int &m,int *c,int k)//将一个数同其倒置数相加
* e# [! g" F( I4 [2 i{: n8 b6 U, Y! v
int i,j,a=0;
. b, q$ `. L- B$ W for(j=m-1,i=0;j>=0 && i<m;j--,i++)) R4 V+ V. A2 y7 W! C( K* A4 N
{. G1 g5 r: q3 J4 H
 c=p+p[j]+a;2 R0 Z0 v3 e% r# m
 a=0;8 t8 }- Q$ r1 w
 if(c>=k), A5 Z6 \5 q9 t" I! h9 B
 {; r0 q5 e# `- S. }
a=c/k;4 z& n4 w& v& o8 f1 S( D Q3 O
c=c%k;
# m! K9 `7 l1 i* D' w }
1 e" |' T3 i1 \+ ]& } } 9 T& P: r( L& l+ X1 P4 f2 U' j
if(a!=0)7 j1 X$ y6 H, Q. K2 R9 `8 W. z$ H
{
2 x. M" L$ a% N6 G! t- w c=a;
5 z7 C& o3 a) z: o m++;
4 F5 P1 s2 S& X- x }5 p7 L' Y |% V! m! Y
}: g5 d1 t7 A$ | e
<>bool match(int *a,int n)//判断是否为回文数
% f3 K3 q1 t3 C4 W& j{
5 _4 P* k0 _+ x+ D int i,j,h=0;: E3 i) O% s5 a$ H R" I: D h0 X% @6 c
for(i=0,j=n-1;i<=n/2 && j>=n/2;i++,j--)
" e5 m5 X2 n; |, `. U8 g {
" I7 K" @* U8 J1 }- C3 [ if(a==a[j]). s1 d- U: S9 h
continue; t5 ]5 K2 z6 k: ?6 [; F7 e
 h=1;$ V+ t( t* @8 d# j
 break;6 `$ L: ~# `, S; Z( g0 m8 U5 K
}
* P; t9 f6 O d; @( T! y if(h==0)
7 \0 O2 B8 |2 Y; j, W$ P return true;
" L- [) A# h6 N& l# m% ~3 n/ Q else
 F# V1 \# x( C# C/ S6 W* H) { return false;
$ ~1 j0 l' q9 L0 p5 r& {}* W1 m) M+ Q J* b+ J
//clock_t start,finish;
$ P0 C" g, v- I ?( H* Q- xint main()( a- U& G1 ^- W& G
{//start=clock();9 O! S4 }' y: y! ]/ L+ A) H1 B3 a
if(in.fail())7 {4 N! g7 z& e7 B! c% R2 ~
{
% }9 ]5 m$ M' y1 J$ T& `* o5 y cout<<"the input.txt is not exist!";
1 W4 e) u r0 i- W: i exit(1);! m# u+ H3 c$ |
}/ `7 M( j5 i/ y- |
String s,s1;
5 F. U( F D ^( G4 U5 c0 r+ ~: a int n,g,k,*a,*c,m,h=0;/ K/ X* |$ [% g( I+ [6 f5 ?) v
in>>k>>g; " K0 ?9 }# M+ u/ W. Z3 _ e$ [
s.get();6 g8 r" |4 N2 ^

9 z& s# ^6 I0 M# H7 f8 r b- O n=s.length();
. ^0 `& |; c8 m m=n+g+1;
4 c, U/ c2 C8 r% ?& F a=new int[m];
, P, B0 D, a% I% E! i8 } c=new int[m];* c( {2 |0 U3 M0 b
s.get(a);
4 Y( S1 O; ~, ^ ?$ p5 M if(match(a,n))
7 b9 |/ y8 h+ o" M {2 @+ e- r2 l# M' g0 E
 out<<0<<endl;
2 |2 W( P& K5 ^+ u( b" y s.display();
# f, Y0 {" C* ?0 e return 1;, K" L: z0 w |0 P# h7 c
}( M1 t; |2 T3 u/ g8 r5 g
do1 }0 w& k! W3 `$ t/ j& ^: q
{
' h) I. u. t2 t* o+ L; ? k4 v if(h%2==0)
' }$ O% D2 W( O+ s$ i9 N3 n3 g add(a,n,c,k);+ e5 Z$ f) j+ J& X; N; i/ ]+ U3 M
 else
, @/ Q- g1 K. } n, I3 G. d add(c,n,a,k);% W0 l. E; t6 Q) z% N3 w
 h++;4 @7 G! O9 J' P# F
 if(h>g)
3 Z: b% D8 l2 { break;
! X/ p! J4 ^) j }
, r9 s3 s. N5 v, }2 F2 O while(!match(a,n)&&!match(c,n));8 t1 F2 s# } J! M$ s/ ~
if(h>g)0 H% O! l0 {+ s3 i5 f4 R6 A4 J
 out<<"No Solution!"<<endl;
' {2 Q8 @# A+ H6 [ else4 d0 N/ _$ W6 ~
{2 ~% R3 T4 F" c0 J1 O
 out<<h<<endl;
5 I8 _4 U4 P% l- T if(h%2==0)# Y0 e( R6 h" _% y
 s1.change(a,n);$ X' m( I4 r2 c" ]
 else
8 j/ E: H3 `* b7 |: Q0 T7 o3 Y8 B) y s1.change(c,n);
" ^4 X4 Q1 L/ p$ x- ~ s1.display();, S6 r- Q9 J5 v. _: C6 R6 |, h# D
}+ `) \9 `- I: ` N0 m
delete[] a;
 {. P3 R- V/ i3 y delete[] c;
/ t" V3 e, w; |- t// finish=clock();9 s D. i* w5 l1 _- I
// cout<<finish-start<<endl;) p! G, ^' E8 n; I; Y8 s" Z
return 1;
% A9 @/ Z5 ~% V7 |}