回文问题（用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)- I/ ^) O; _6 l) d$ P
str=p+48;- z5 D/ f- L. F6 M3 E$ q9 ]
 else6 d1 u- ]3 l6 E5 k. \4 |" k/ D2 Q
switch(p)& d8 l6 [7 M8 |+ ]& A
{- Z3 r/ R# k7 V% L& ^ H- M
 case 10: str='A'; break;
, C; h4 I. f, J8 [* e case 11: str='B'; break;
3 s1 s6 I3 x/ t, M) t, b, M case 12: str='C'; break;' r2 O$ B% E+ Z! \* v( E. \$ ?3 o
 case 13: str='D'; break;
/ n. X7 h6 t Z, d case 14: str='E'; break;! [' c1 w, l( h' y+ k3 \8 o
case 15: str='F'; break;
9 B5 G8 h; U4 U5 {+ q9 q }/ B' y' U' x" x) W6 ^0 e4 {
 str[n]='\0';
% _8 \/ P; v" G6 l2 ~ return *this;: \' Q3 c& m3 V, N% G
}
6 ~5 y% J/ q/ j7 J) k0 t) s: Dint String::get()//输入一个字符串# L9 c0 D/ _1 _; I
{* _0 c" w* d. s6 Y- w
char tmp[40000];
0 j$ J3 `# g3 Z) H in>>tmp;: ~$ Y% u8 S: \( P8 b& c' k1 s
delete[] str;) F2 A" Q1 _0 C) o) m. y9 }3 C4 W
size=strlen(tmp)+1;
( `9 V/ `( A0 j- ?4 ?3 }$ I' z# X str=new char[size];1 G m! N) u) Y5 r
if(str==0)
8 Q, l% h+ ^; p" M9 `# J$ H! O throw "error";, m& m/ M% U9 \0 I' }8 o* g
strcpy(str,tmp);3 o& Q6 V1 G6 V# b
return size-1;& P, d1 z, t7 I
}1 C9 U2 N7 B% M7 s8 r) Q
<>void String::get(int *p)//将字符串改成整型数组; f) |; x. U [6 H
{" n) ^1 D3 ^9 Y4 D
int i,j;
1 m- ?2 w& ]: D! t for(i=0,j=size-2;j>=0;i++,j--)
# c# C. }2 Q: s1 J if(str[j]>='0'&&str[j]<='9')
, R' q7 j; `) d) V& k- N p=str[j]-48;- h4 Q# X. u( S4 m* B. ]. v) W6 _
 else# O3 {( D! p0 W/ R1 f! p4 c
 {
* k% b0 S( j/ \8 P- s8 A switch(str[j])
5 g y4 r- \" q {
0 C) K. Z5 W1 {% {; I9 j8 Z case 'A': p=10; break;, H6 ^0 x. s9 ?1 P% O& ~2 p
case 'B': p=11; break;
3 b. H$ Q, r, z6 Q* D" \; a$ v case 'C': p=12; break;5 c/ I7 D- C* S3 t6 W `7 @
 case 'D': p=13; break;
9 p% y/ ~/ H) M) @ case 'E': p=14; break;% t, v ~3 U% X @; ?9 g
case 'F': p=15; break;7 \" s* Q3 X1 C2 p. f; \
}
# R: y8 c, A9 T }
( o$ X: Q- S9 L}/ x0 c$ C# F* Z4 a; E8 W
<>void add(int *p,int &m,int *c,int k)//将一个数同其倒置数相加/ g0 U% h- a7 Z; \2 t8 |
{1 \ M" e2 T0 G# I3 }( t
int i,j,a=0;
* T3 {' \: Y$ U for(j=m-1,i=0;j>=0 && i<m;j--,i++)
' x- C4 z! U0 I# W# O" | O {
6 Y+ ~+ e! w7 g7 k+ }8 T c=p+p[j]+a;6 t* F9 W- h E0 _) s4 S
 a=0;
1 t& W! C h( }. U- O0 m8 Y if(c>=k)
3 j# d3 u" u$ ]1 p! E: X {
7 W, g ]2 d! {7 q5 o a=c/k;8 B4 v9 B+ ~5 z% G8 K' ] \4 j
c=c%k;
( }* R( H; I1 Z/ c8 R$ | }# I5 z, P2 K! _: H& r+ g
} 4 r# E. {6 l2 I# f" a3 j& G7 e' |( q$ B
if(a!=0)
, g: c0 F/ ^* f1 E% A3 Y/ v+ [ {
' {1 T! S* \1 J2 f; h/ e7 m* _1 Y c=a;2 S9 A1 v7 A8 I+ [2 C0 D# M
 m++;
1 d/ a! y, D; E+ `! o }
' z0 {' Z8 w7 p; K7 ~& C}: Q/ P& s7 ^- V# E1 f/ A) O
<>bool match(int *a,int n)//判断是否为回文数
2 w% P: Q* z, I) }: d5 X) t{
, M% y5 Z9 d3 D int i,j,h=0;5 n1 E7 s# `; Q3 c
for(i=0,j=n-1;i<=n/2 && j>=n/2;i++,j--)" Y3 H3 q, t5 X: f/ b/ |8 X
{
1 c$ e( p- ?/ e: m if(a==a[j])& a2 z' C! J3 x; B- |; i
continue;
# Z" F9 d: N% P% ~8 `" Q7 C h=1;5 O. k# y. M# ~& W) Z. M5 u- [! `0 b5 V
 break;6 c+ H- ^) s+ f/ y& |/ x Y+ G
}
! B5 ]8 M `/ I+ L$ R5 i if(h==0)
& B- k) C& Z! L9 }6 q return true;3 o$ J6 t5 m* _; R. W! q3 }
else
2 B% [, O* k# S% p6 m return false;9 S; ^' N$ i+ c
}1 ~5 w4 j5 s. G* G/ O/ ~
//clock_t start,finish;% n+ {) s+ ]4 S6 V
int main()
( y$ o% B- a) X) e% D{//start=clock();) |! T+ p2 D# o5 Y' {
if(in.fail())/ Q9 g1 g4 B! A& f& U
{5 c- X8 J; d- e7 d8 t: e8 ?" l& I
 cout<<"the input.txt is not exist!";3 @/ K1 R& C( n( s
 exit(1);
, o& U) x2 Y) X2 [. [ }& O, m6 I( m; \
String s,s1;
/ e# s* a/ l" _5 ?! G" f int n,g,k,*a,*c,m,h=0;4 S$ \! u8 C( Z3 e2 j
in>>k>>g; ' O! ]9 J) P1 p/ Q
s.get();, J* j9 d# G6 Z- b* G* Y
$ ~5 k; d0 J3 Q% G; n* `
n=s.length();+ Y$ X2 D) L8 Y2 T
m=n+g+1;
2 n" o$ L: }) ?3 f a=new int[m];
# s4 O }5 S$ S3 x c=new int[m];
 t% q% i- m6 y, i, e1 o3 | s.get(a);
8 E& y" D7 j% F: Y8 Z+ n if(match(a,n)); `2 F6 U; B7 b. y
{( b9 w7 K) v* g4 y
 out<<0<<endl;
; |2 [0 ]& r- ~0 o s.display();9 Z; r! S# p- i9 G
 return 1;
9 d/ u- x) S0 N# t" z }" E$ d- b" w9 P( T
do
) r! M2 c8 h& e: x" z1 e: G {2 a, v: Q0 F0 a' H! u' S
 if(h%2==0)8 n/ T& z: p5 K8 O1 x: w& b8 X4 @
 add(a,n,c,k);
% g4 c; B& |) |4 ~# D else
1 C, q$ p0 t9 c/ A5 w) I" C add(c,n,a,k);) r" j4 Y @. v: A2 a1 M
 h++;! n1 d, n2 E: a, T
 if(h>g)
' n/ n6 I4 X( o* \ q5 q" q8 n break;
- o2 L3 `% e3 e) X9 G }9 c+ ^& f* u1 ^
while(!match(a,n)&&!match(c,n));; s5 E5 q. Q2 g7 K( @8 Z2 P
if(h>g)
! ]) |6 V: b6 i out<<"No Solution!"<<endl;. z( J" w. l. c3 R* D
else9 c1 L& }, K) f
{: z9 V0 T" }1 }1 H: y! V: x) f
 out<<h<<endl;
& w1 q4 P% C* q. C, o4 @/ A if(h%2==0)/ {4 @ W9 ?7 r3 D9 c& `
 s1.change(a,n);
8 U5 Z/ p! w' x. B' a- q else
1 v4 g3 x/ J$ Y" q, E s1.change(c,n);) q" q, M, T2 c
 s1.display();- y, S( N2 p1 U5 |6 Q
}
) ]' ?( U: n+ |. w; g& C# }- y delete[] a;! T4 a3 c# D% ]5 S! S( E( B) |. L
delete[] c;5 Q# c5 G2 Y2 f) T% M
// finish=clock();
) q6 S- ?5 b2 e+ y0 z: `// cout<<finish-start<<endl;: Q4 e7 i5 k# B1 j/ O F2 v9 K* ?/ e
return 1; W, d) _* P( X- |# F& Y
}