回文问题（用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), B# g3 T' a: @1 ^: l
str=p+48;
; E8 D& J6 z( p% B. W: n else Z' ~/ | h; Z( n) r
switch(p) W% T7 w0 V8 f* l7 {% V' d, w0 O
{
 Q8 L3 B8 X6 x6 ?+ J case 10: str='A'; break;
 c' j- t V6 v1 r; d: P: O case 11: str='B'; break;+ A. C# z$ q) g" ~* p, E3 I/ K& n, }, t
case 12: str='C'; break;$ u( ?6 u7 r6 u* t6 N+ m% N
 case 13: str='D'; break;& i7 m3 S" s! ^" d
case 14: str='E'; break;6 w/ M' m! i/ l8 d" z7 M6 u
case 15: str='F'; break;
# z; b4 W, h$ b }
0 X ~- p$ A2 _ str[n]='\0';
* h+ S" u! c$ H' t return *this;0 j, V4 W2 k0 d' p9 M
}: f; t5 a3 f/ e, b
int String::get()//输入一个字符串
6 U8 b8 m; i q{% v/ N6 ` T% j
char tmp[40000];& V/ E! P6 E% [8 @/ i. G/ T. W% N7 p$ d
in>>tmp;+ R, e) h: v6 L7 ~7 F) h, ]
delete[] str;1 R4 s7 X# E3 R+ I4 Y4 V( g' K O
size=strlen(tmp)+1;
; w7 E9 t& K6 \; p1 y1 [ str=new char[size];% A: X# G! q' b9 I) f
if(str==0)
( M8 h1 s; p' Q/ v3 M throw "error";
) T! R$ S) E+ c! i- P strcpy(str,tmp);
. v |% w2 E2 [* ] return size-1;
" K j7 r: T! j1 P8 L5 N}
7 Q' k. S! g5 U3 A<>void String::get(int *p)//将字符串改成整型数组7 g* {4 a- H5 _# z7 {
{( x% s' U8 w5 n
int i,j;$ H8 K2 h- ]( ~- N5 f. ?
for(i=0,j=size-2;j>=0;i++,j--)
7 |1 A7 I8 w ^& u% b if(str[j]>='0'&&str[j]<='9')* X5 Y9 F7 h& u4 z
 p=str[j]-48;
% h9 G* e6 J4 @- ^6 F else
' X$ g$ o' a4 h; p, r) z+ ]! I. d {/ ], Q/ n6 R$ U1 {
switch(str[j])8 C% z8 x( R; ~, ~: ^/ V X$ {
{* f# f; O( o" A4 a/ n2 ?$ W
 case 'A': p=10; break;
' J. D% E0 i1 `+ [) L9 o case 'B': p=11; break;# d* L" O1 j- d7 `. T! v; q
case 'C': p=12; break;, @; L+ P' I# g' h
 case 'D': p=13; break;
% b: {. O' L6 U# }; {& n case 'E': p=14; break;
# ^, t0 ?8 c; P# w- q case 'F': p=15; break;8 e* Y. T( e, j, R
}
8 O; U% |) ?2 V! |9 D/ w- c }
3 ?+ A2 g" C3 d- |}# ?* O, |0 q, [" Y3 f8 Y
<>void add(int *p,int &m,int *c,int k)//将一个数同其倒置数相加
7 y( h _: P L' u! D8 t" d{* f: j, y+ A# i/ [. M: S
int i,j,a=0;
 z, P) _3 T8 X4 {9 d9 \* P* c: d for(j=m-1,i=0;j>=0 && i<m;j--,i++)
! I6 J$ E O* X' H9 v9 W5 I: { {3 E% h7 G2 ?% Y4 T6 C3 `
 c=p+p[j]+a;) ?" H% X, L0 J4 R
 a=0;
9 ^! m/ `; ~5 ] w3 ]9 A if(c>=k)
& J$ g! S- v& v |, k& t {2 i6 h4 v% |9 y
a=c/k;
; D6 H6 Y9 {" a7 `" T+ W8 O c=c%k;
/ p7 m, Z% Z9 @- w% c" M }
; `8 _" e* R( x0 g }
9 F D" @ Y; z# Y3 b if(a!=0)
* r" u5 L& F3 q+ o4 u1 F/ E; }- [ {
$ {6 Z& \" f" v" L c=a;
: ]. s' F# \3 h6 A, K) S* c m++;
) c9 p0 E$ ~: `/ z' E" Q; u }- h8 ^4 T6 n: W+ q- a
}# H6 S, p5 L7 s. B: M
<>bool match(int *a,int n)//判断是否为回文数) T7 v2 B% x3 k T
{" O/ Z9 T1 f: {* B& l8 ^: R5 a
int i,j,h=0;
9 u( }0 g9 |/ n0 `. P, u# V3 S for(i=0,j=n-1;i<=n/2 && j>=n/2;i++,j--)
( C" P. q$ _; Z6 h {: R. Y2 y. J4 |9 L* j' {
 if(a==a[j])
" ~6 d. o ?3 u continue;1 {, u1 @$ J# P! }
 h=1;
' t9 R7 a( ] t$ y4 a( ^, w; Q break;
& v1 v4 d4 W* E: K4 O& N }, f1 P" z* v# N
if(h==0)( b$ D' J! W0 g/ ]3 i+ y- K
 return true;3 ^, {, P. O2 y0 I
else
' p3 }/ F3 z5 v return false;8 ~* L. g" P; \1 c- R0 w0 F; G
}' w& k4 G% T1 A: t( P1 ^
//clock_t start,finish;3 Q$ a! q2 v, {! b/ N
int main()! S) x+ Y W( M4 I+ T
{//start=clock();) j0 Q1 ~6 n4 c1 `7 i3 w+ Y
if(in.fail())/ E$ M+ {3 m1 i; i: ?4 A
{
$ ?* D* P( J- J! P* y- ~ cout<<"the input.txt is not exist!";
) j2 b; v! C. a; ~/ a) h! M exit(1);( \- x' ]( w( S9 H% q* V; C5 [
}3 o; o1 t1 g' f1 c8 l5 F6 O
String s,s1;
 s+ L: d2 G. [! _7 O; \) ?5 D+ E int n,g,k,*a,*c,m,h=0;
7 @, u4 A! F3 U: K0 j7 T$ w* T in>>k>>g;
$ L; s/ R6 K1 i s.get();
! j. G/ |; P0 u( K* x+ ^
! @* f: _0 I }3 P* ?$ I9 i$ `, | n=s.length();; E; K0 A }' o, W
m=n+g+1;
1 p5 g: \; e- q+ p" N% O- v a=new int[m];" p2 T3 e' a* I, M! Y3 t. ^# W( m& j
c=new int[m];
" N. j6 v" ^) T, d$ M# C3 x s.get(a);
4 n3 N9 x, i: v' H2 P3 x if(match(a,n))
6 A1 W- R3 r# T$ c5 a {% c( B: b) g- a; F
 out<<0<<endl;' Z: P1 ^# ~2 z9 q+ @
 s.display();
2 F h2 c' V4 h return 1;- @% s( \: e# H3 r
}" ?8 P' t7 C0 \: H$ P- q
do9 q; g1 u$ x; \% o
{
3 a. o& s' w; r( c' P" l if(h%2==0)
* S c4 w D& c# b1 @ add(a,n,c,k);
2 x4 H2 r5 p+ f! Y4 f* W else W9 V& g* ?8 X
add(c,n,a,k);
4 U; U0 Y7 N- } h++;
( k+ G% t# I- u7 b if(h>g)
9 t9 Q% ]7 h' ]" j5 j/ @) C3 A8 z# b break;
. E) Y/ H, B5 b+ { }
+ X6 }7 l: _* D, J# e while(!match(a,n)&&!match(c,n));
& a( p# y$ A8 Y. z/ y/ f4 f if(h>g)' @ x v+ [6 V
 out<<"No Solution!"<<endl;
) k& b# ^' q ^6 X+ h else4 p: V0 e8 F1 \ U' O( j; j& I
{- K7 Y5 y$ d9 h
 out<<h<<endl;
+ g1 G% P% k- p% {1 t+ g if(h%2==0)# u g/ ]& Q2 {0 H# \
 s1.change(a,n);
, O$ h* w' `# d- O' P else
/ D) c: T5 ^& J2 u- `7 _ s1.change(c,n);, H- D" ^% n. L% s, }) @
 s1.display();
7 ?, O* Q8 T+ X: h! {! g8 t }' y* f' \ W& m O! g
delete[] a;
& J7 \6 g8 [, q* y: x% k. s delete[] c; i+ L6 D% U. G) e" n: v
// finish=clock();' M% B9 O X, Z4 ^2 F
// cout<<finish-start<<endl;
. ^5 T' O4 y4 Y return 1;
7 Y$ a9 V8 S# [$ b}