回文问题（用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)3 X& ]; ]: e' b
str=p+48;
6 N( s9 }( A$ b- Q6 x+ P else. d, |7 d6 S7 U9 M# `
switch(p)2 z0 @* `4 _0 y
{
& V' B" j! I( F- Y case 10: str='A'; break;. y0 V8 C5 v- u! g
case 11: str='B'; break;
- {% g/ F7 ]* K2 ~ i& E case 12: str='C'; break;+ T* a+ Y6 o$ E5 w5 \9 Y5 g
 case 13: str='D'; break;
8 S2 Z5 ]. c/ X3 H, p- F case 14: str='E'; break;
9 @8 ~0 v& w, U4 z, g( l) O, f" } case 15: str='F'; break;' k/ j& C+ G }0 y! O3 v9 E, H
}6 {; F' V# @4 n6 c+ a0 ~( ]
 str[n]='\0';5 s/ m' I. e3 T, y
 return *this;" W% S( g9 E3 e5 ?4 r
}
) Q$ b% V7 _) v# `6 G+ Aint String::get()//输入一个字符串; O; w9 ]; t7 z; O/ w% i! P2 @5 M
{
) [3 U* W1 A- Q# V3 _1 F: ]5 K6 J char tmp[40000];" |3 Y% B9 |6 l! m! S
in>>tmp;
5 _' x$ b& ?9 U% f V delete[] str;
3 u$ Z6 a" O2 o' } size=strlen(tmp)+1;
2 \6 r" s. _& c; i str=new char[size];
+ T1 K/ q* w% t" i1 u. } ^; f if(str==0)8 z2 z, V% ~7 \2 h& Z* k
 throw "error";
6 \4 u3 T: d, X strcpy(str,tmp);" Q x; j) V7 }3 r. M: Y4 j
return size-1;+ k* L/ a$ Z$ @4 y/ _2 Y
}0 x& n: J( j+ |8 b% z) ?
<>void String::get(int *p)//将字符串改成整型数组7 u+ H) A% i% {
{
4 [- G8 n* X8 W( q# e+ T int i,j;
/ y+ s g8 e9 H( U! n for(i=0,j=size-2;j>=0;i++,j--)
2 E" h% i& ^0 x9 H! W ` if(str[j]>='0'&&str[j]<='9')
* O1 s( @( J: Z6 O8 j1 U7 k p=str[j]-48;+ l m- |$ z$ _" U5 h
 else
' B! _ M" K0 a& I. q) I {8 r b, g9 Y* _; G
switch(str[j])
9 k6 \+ { i+ n6 j. v3 {/ k {
) \, d. D% t% y7 A( y case 'A': p=10; break;: w: I% N) A2 v- o0 z+ X1 ]% Q& R
case 'B': p=11; break;$ E1 C, B M/ X) Z
case 'C': p=12; break;
+ w/ ]% D' I: C7 ^8 s2 A1 b! l case 'D': p=13; break;) _0 S. _- E% P: D% X4 j
case 'E': p=14; break;
0 _* D1 \- R6 c" G& p case 'F': p=15; break;$ k' b( {0 O$ a/ u
}& d: F3 p8 R3 o4 b) P
 }
" V# F+ h) |: R q* ?}3 D* h$ @/ f ^+ U! b4 ?4 V
<>void add(int *p,int &m,int *c,int k)//将一个数同其倒置数相加1 J! q$ m; ^/ K/ P. f* S! `
{
* k' T9 F) j$ Y, ~ int i,j,a=0;
/ O* s9 F: H" q for(j=m-1,i=0;j>=0 && i<m;j--,i++)2 n, W. ^- A% i
{7 `# |5 A- t2 c( v' v# h }5 i
 c=p+p[j]+a;5 w+ A; p# g- k9 l4 Y9 \/ }
 a=0;
3 u# {; z; j& I if(c>=k)
0 J8 o! T W2 f& Q4 ] {
0 r8 b5 x( J" a" S L( R a=c/k;
, G& Q/ f0 O, J5 ? c=c%k;$ H, s5 L. x, W$ v& c) i( f
 }
1 L% U6 v3 [1 T* a c8 \" X! k } # }* x% I3 B2 n9 R( g
if(a!=0)6 U- X' \* Z3 v, `; y
{
, e3 l! e9 s+ s c=a;
 c5 ?* r" H/ {0 J4 m m++;1 k8 {0 K7 K! B) h' T
}
9 u: t. o5 I4 m k" j* k7 k% S}
$ w* R. _6 ?2 ]$ E0 m" n8 s0 X9 s<>bool match(int *a,int n)//判断是否为回文数
0 l! x4 X8 i# i- o& Z" o2 T{
. `) Q$ k- X; l9 l. R7 b int i,j,h=0;4 M. t# B5 a p3 I! ^5 G7 m
for(i=0,j=n-1;i<=n/2 && j>=n/2;i++,j--)
# n' F9 A" B: P/ b, X, |( Y7 _ {# F3 h0 D& \: F0 T3 p
 if(a==a[j])
continue;
4 F: L8 i! v1 l h=1;2 u& Q! F [: r9 I
 break;2 y: B$ v; v7 \% T9 E9 ]4 h
}+ h! `' y( W# `# S% a! J @
if(h==0)
2 [3 q5 Q* k E) Q& j- d. ] return true;8 g! C' r: U( ^2 X
else ' k+ k) |, t4 G& f# l( Z% h
 return false;
6 c* y- v3 ^; y; s; _8 x}
/ h, a% }1 s* c$ V6 e8 |//clock_t start,finish;
1 ~# E2 m K! |* O& B- dint main()
/ X% q" x; D- R' n; N{//start=clock();( k" p! }/ y, }. r# v6 {5 ]0 ~( ?
if(in.fail())
1 d# C% V& ^4 B' F L* u {. z$ ]. `* R% f7 N& k- n) W- b0 y
 cout<<"the input.txt is not exist!";( A* V. {8 l! P
 exit(1);1 ~8 A% q( `) g% B
}; k" C ]1 }) P4 ]
String s,s1;* L e* E7 N5 L* a* n
int n,g,k,*a,*c,m,h=0;
1 Y' ~9 O3 [7 g4 G" d" i7 \. h in>>k>>g;
& W; L2 K x! C- _7 N9 ?& N s.get();

3 }% S# q/ [ g n=s.length();
; k* y3 ~& M! f4 g+ L0 a m=n+g+1;
. ?2 U/ R6 F4 ^ a=new int[m];$ Z3 E T, l! Y1 @% P6 x, q
c=new int[m];' m8 b) C: j/ f( X( L% z0 F
s.get(a);
( x1 Z4 }* R$ a6 j0 j. m9 g if(match(a,n))/ e2 S9 X N9 C/ Z3 D
{4 ~0 l4 ^0 B- x. C6 a
 out<<0<<endl;
$ e# ~$ q; ]; c6 k s.display();' A! Q3 a2 W' S7 A F8 h9 f
 return 1;
( U) M$ l3 f* m }; U1 L6 H1 z* _: P7 i; f' S7 m# m
do
3 j9 ~- f0 v6 ^6 V4 h q {
/ \: a) f9 x0 y if(h%2==0)
: g. I% E) C o7 J7 g add(a,n,c,k);
$ u) `8 I2 y$ J, E else
' h m7 u0 b: {: o6 [ add(c,n,a,k);4 D f. ~- G4 r% U+ U' x% z1 D
 h++;
( S* Z' \% ^8 ] if(h>g)4 E! c1 \# B- ~3 o( a6 T. D. {
break;, R2 V7 E) w) e( s* f- G5 L% {
}9 V: P, K/ _( N2 h8 Y' z
while(!match(a,n)&&!match(c,n));, g2 X. N$ O/ |: r( {
if(h>g)( _, W5 l: ], |% |
 out<<"No Solution!"<<endl;
8 S; q1 c% ?4 j1 p7 b else
( _$ x( y; v3 j$ U1 Z9 G {
3 O- i) j. u5 v$ @- F7 K3 J" |! V' K out<<h<<endl;$ J1 h( r9 z: [! j! S6 b/ V
 if(h%2==0)
8 C3 W5 g; `5 w2 `4 b s1.change(a,n);5 a6 o9 V1 V" q( ~' p9 v
 else
8 }) p: I' b" E s1.change(c,n);6 Z% h5 B. a5 E! M
 s1.display();
) {! M3 \' M, X/ Z, F }
1 y4 S! K o$ M" n delete[] a;
" d. M% P' q6 @3 \( X7 z5 _9 l delete[] c;
) Q3 ^# C: I J% @7 y// finish=clock();
& {) {, C- K0 a4 o// cout<<finish-start<<endl; A* } x0 m# V: g+ I) `# s
return 1;
( ?! Z0 M# j8 L}