回文问题（用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)5 ?' O8 N/ p4 x. ]1 H
str=p+48;# z; G' t/ x$ C0 K6 p( ^
 else
) X4 p; ?$ ]0 r$ I) I" j switch(p)! }' s5 {! D! f, p
{
, o! i6 y, ]9 v2 s" H case 10: str='A'; break;
1 v. P# F2 K0 o! V' v; d) B case 11: str='B'; break;
& n9 O! W, K0 U1 T9 ~! E8 p$ R& V1 _* l case 12: str='C'; break;
$ u. P T) V6 R k) i, Y case 13: str='D'; break;
$ A; @ A5 G( {; @0 S2 X$ I% j- k case 14: str='E'; break;
& v0 Y0 w1 j- v case 15: str='F'; break;% t0 K3 n; \/ b2 N8 P. _' Q4 I
}8 D3 Y! b) O5 {0 G5 a) G
 str[n]='\0';
. u, e& F; N, g1 z( ] return *this;
1 ]/ o7 w( _+ e7 S}
' _ y+ C$ n2 n6 s$ u7 L1 sint String::get()//输入一个字符串5 D- F4 |- I7 }
{
 P$ x' |% k: n; N* }# `, [ char tmp[40000];6 t0 K+ |5 h2 j$ D" d, y) m) e# `
in>>tmp;
7 G+ V. e( L2 t2 U delete[] str;
* o' ?7 O4 L! h( E size=strlen(tmp)+1;
, K0 s! `0 h- f: {( } str=new char[size];6 b& c7 z) z: Q/ n: |9 H3 d
if(str==0)
- r7 s; M* F$ n4 m throw "error";, U) m; z3 w+ q8 E7 ]9 e8 r; q
strcpy(str,tmp);9 o) s7 Q7 M+ f3 Z
return size-1;: }% y4 f; c# C$ T% K" N# y
}
! G+ ~8 T- a9 }" h- J! j$ p<>void String::get(int *p)//将字符串改成整型数组
# H) T9 u, P- {0 `; L{: @0 [. L5 M& l" p6 M
int i,j;5 J, M4 n# D& B
for(i=0,j=size-2;j>=0;i++,j--)
4 ~& u3 k' f5 N7 A if(str[j]>='0'&&str[j]<='9')
/ z6 q- I. B% C, h p=str[j]-48;
6 K( o5 n: z' k j else; q. j3 | m4 {3 m2 K# E
 {+ a: ^7 n- E% l$ l7 k4 ~( `
switch(str[j])0 \5 L) o1 E7 I# N& P
{
& u. s7 `) x8 z0 B! z5 y" i4 R" ^3 s case 'A': p=10; break;3 l5 g( `9 W1 e5 q3 [: `. N8 Y
case 'B': p=11; break;) k" b8 d9 x% f) Z# G
case 'C': p=12; break;
9 E; \! k5 k+ f q# ?: f case 'D': p=13; break;
/ A5 d2 N" B2 n" _' Q8 } case 'E': p=14; break;
- u3 p1 W* [+ h* O case 'F': p=15; break;
/ m$ m4 n' s4 E5 [- d3 d }
0 e5 U4 r5 f* R) ]6 c8 h3 w1 I }
; ~5 J2 | q% R- r1 B' s0 |+ R; t}
" w& ?2 n/ ?! y) P z' `# l+ s) D<>void add(int *p,int &m,int *c,int k)//将一个数同其倒置数相加
0 M) Y6 Q ?6 o E, j/ r{
* b. V' d( `/ D# n) r& W1 \ int i,j,a=0;
3 a2 L& b, I" c6 e5 P# w0 o for(j=m-1,i=0;j>=0 && i<m;j--,i++)
 L1 h( W7 }9 q( o! @- } {8 s( `% m7 N6 K% Z
 c=p+p[j]+a;( T. T4 y4 C: d A
 a=0;
2 b7 J: y+ q Y& p# U+ \ if(c>=k)
1 Y$ m7 t2 u2 ] k2 ~& Q- C {
 v4 L4 e5 o& Q! R a=c/k;
! W$ G- W2 U1 w! U- g5 ? c=c%k;+ N, O+ R& N& _) j
 }9 |2 x. z1 m! p0 y3 J' q
} $ M- w b; F! D$ Q5 K0 }" p
if(a!=0)7 G) w' k/ i9 q3 H% c: \' e r3 @+ J
{" X+ \7 b. | k
 c=a;
! ?& b! P. @8 c X: N) {2 H, m- Z m++;& n6 w, [; r* g7 l1 {
}
3 M$ E8 v3 F; P5 o}
 l% t5 x' F5 O<>bool match(int *a,int n)//判断是否为回文数
8 [: f, `5 ]+ I{2 Z! o+ }- [+ c( S9 `
int i,j,h=0;) K3 X# N$ s+ g2 X Y$ C* ?
for(i=0,j=n-1;i<=n/2 && j>=n/2;i++,j--)
, L; i: ]1 i1 b6 a) L) B$ T {. T% R9 U. C# O% ]) y- O
 if(a==a[j])8 P- T Y/ B! g/ X6 [- C
continue;3 B& ~ Q- \+ K1 y. ?
 h=1;
2 k" D8 d( `2 N M5 q: P" X break;; X$ T9 ?- C. P
}5 J; ]1 o$ c6 A" g+ @6 C& ~( }+ }
if(h==0)
 Q v5 r5 o% T2 i* [' N return true;
8 y" |5 n' u \( b" [+ z* e else
: {6 w; G' _$ @$ P return false;
1 F' j- H( R) w2 k) ~$ U}
, v. H# R* Q( u" \, j2 {( I//clock_t start,finish;
: n: \ j; C5 n/ _int main()* B; y% ~$ G' U6 @" F& ?" a
{//start=clock();* f2 X( A& {: i8 G
if(in.fail())
+ r; R0 k3 @3 ?0 J2 Y- g* ` {. [2 {; A7 s/ q
 cout<<"the input.txt is not exist!";
3 t W- L! V5 d2 j5 q+ h4 f exit(1);
; a- N4 I% D% c/ p8 q; h: Z! L. | }. n+ O/ a& V# ?7 @5 j/ j! ?
String s,s1;
0 d8 P: _" t& L$ l int n,g,k,*a,*c,m,h=0;
4 V( S! i, @: B: V# l7 C) h+ G in>>k>>g; ' S+ {+ P2 ? f$ }, v- K
s.get();
; }" t2 p4 M7 g9 T, ]$ [. O . N, K7 b( @9 G: O9 g" U
n=s.length();9 w# {! B/ o% ]
m=n+g+1;/ v* \. d) t1 y1 q+ K
a=new int[m];3 {0 e# {0 n0 v6 E K( d) s( }
c=new int[m];4 C7 m; N2 k. w+ h7 e
s.get(a);
/ w4 {, f1 l- T& ~ if(match(a,n)); h) ?$ t% m# Q- P, ]
{4 h8 |! j5 j6 ]* T3 q2 w) i7 C6 ^
 out<<0<<endl;4 l2 t; o" a" [" G- r$ {
 s.display();& a# b8 s j2 I
 return 1;' e/ |9 v, r: E7 q8 ^5 d. ^0 M6 W
}8 m$ W0 \- r" N/ d) c: D" [
do i! S1 M7 M$ e9 \' G9 C O& q
{
6 U O% o# d( Y/ J if(h%2==0)# A( |9 q' L9 q0 N# w
 add(a,n,c,k);9 i6 k5 P' O: ]* Y
 else" l7 U/ { M% G* h- K- k
add(c,n,a,k);
1 x J C6 m% c+ B# D h h++;
 y) m) y+ P3 a9 J8 f if(h>g)" ^) C* L* @' Q6 ? r2 N/ T
break;
9 H4 z* X% W' k0 f" N }. S' I. Z' w- o; Z
while(!match(a,n)&&!match(c,n));
0 o& x5 e: c$ T" h) f. ^6 w if(h>g)3 Q( q/ z0 v7 F
 out<<"No Solution!"<<endl;
$ r. W" s( c! W else
* h/ Q. a. O1 n, M( I w# `' R7 f {
1 M8 L& l5 F7 g; \! }4 X0 f out<<h<<endl;
- K4 m8 o/ ?! g m if(h%2==0)) b5 Y7 k5 z' w
 s1.change(a,n);7 N7 j# a M8 R c7 e0 j" O
 else
7 y4 z; ~( n% T6 z s1.change(c,n);
: ]2 S4 x. _! w* Q; Z) A& r9 Q5 h s1.display();
, i& Q- H. V7 s4 o/ n }, j. t! j. G4 F9 A) U2 E6 c' o/ y
delete[] a;) ~1 _" G9 F# A! o
delete[] c;4 g( J4 k) q7 V' C9 k) x# e
// finish=clock();8 a3 q- ~( p: n# v, x
// cout<<finish-start<<endl;$ L# [# v: a4 G
return 1;
' ?# X9 H. q" N# b5 `8 P: n}