回文问题（用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)
% w: J7 B1 [4 b- ]. {% s str=p+48;
3 V- N4 G4 L% U; P& ~; X4 o else
& T. {$ x7 H1 q: F% L3 G switch(p)& Z% s+ o9 ^7 d% c$ d# w
{
 y ~4 e- C7 L+ l% g5 A0 ? case 10: str='A'; break;
- f9 _0 k& p$ ~5 b$ @; @! S case 11: str='B'; break;
% M: \1 u9 [! ]( D7 U case 12: str='C'; break;) J# t: X. m0 J0 ?2 Q) z
 case 13: str='D'; break;
) M: h) i1 a' q+ T5 c* t- v case 14: str='E'; break;. H& g2 T v% U; W. o: `3 w% n1 S% u
case 15: str='F'; break;! `! j& G( y, ]! z$ V
}: `( H& O# _1 C) _2 V
 str[n]='\0';+ u* G/ U, l6 [$ w7 x* S% i/ D
 return *this;4 g1 ], J) D' R8 n1 c
}
$ O4 d7 [' l' S9 e( {+ x: Qint String::get()//输入一个字符串; L" X( c+ t# k( [$ I1 [0 B- `- n3 f
{
% i( \4 D5 H2 \8 ` char tmp[40000];
0 T& X# j. v' a1 y7 x in>>tmp;
 D- f: h/ d( w8 M delete[] str;( P3 ` M7 l, R; p( z% f- E( D
size=strlen(tmp)+1;
8 |+ h' l( [; A _! n str=new char[size];
! l% P) T7 y& X& ]' z1 i0 K, j if(str==0)& `9 l! @& {, K& g, G$ L
 throw "error";3 j6 x I2 L# |% S! o
strcpy(str,tmp);* M. I4 @" t p$ m+ t+ E8 [# N
return size-1;
' o) m5 d# `! }, {! S. F" e* J/ |}1 k) o5 ]2 I0 l1 X ]( s
<>void String::get(int *p)//将字符串改成整型数组
" S8 W5 U' O3 e{
& V/ E. C6 r- O" X2 L; | int i,j;
2 E; f) A) H7 c. m2 e for(i=0,j=size-2;j>=0;i++,j--)
* a1 j A( M8 T4 E6 b- S if(str[j]>='0'&&str[j]<='9')1 j* y9 A6 M" h+ ?4 W5 L& ~
 p=str[j]-48;
$ k' Y% y S) |) q/ }/ ~: e3 J2 T else' `- W! Q. m \/ C9 h
 {
* G4 c8 G: s) B0 G8 N# d switch(str[j])/ T3 Z9 O! _/ G. B, a2 }
{) f$ S* L) N q+ V+ x
 case 'A': p=10; break;
2 T( c: U E; |' o4 f3 k; l case 'B': p=11; break;; C) a8 W7 k$ a) I+ ?6 w
case 'C': p=12; break;) Z+ b. Y& `* p; u- K
 case 'D': p=13; break;
6 b& o& \& F3 C case 'E': p=14; break;
3 {( k8 e' w- a" q3 k( l& g! n case 'F': p=15; break;
 i% B& D7 ?2 P: G z# U }
1 i/ c6 p: C( X* g5 r. J }
* r. e( c8 h X l2 Z$ ^}$ J8 ^( ]$ Q9 ?8 h# V
<>void add(int *p,int &m,int *c,int k)//将一个数同其倒置数相加6 J6 h3 U* t3 g* D, I( s. e
{. f, S4 h( q4 |
int i,j,a=0;
$ k4 j/ l3 ]: ]- A- J9 y; C for(j=m-1,i=0;j>=0 && i<m;j--,i++)3 k) b( ~0 K' y7 c% i! E
{
2 t2 ?" r! d( M# M, f! H' C7 ]2 j c=p+p[j]+a;& C! u7 q% w b/ v1 ^3 r+ w
 a=0;
2 x. d7 y! G A if(c>=k)
8 n% [; A& F3 K, e5 C0 T9 o8 e, M {- E V% }) P3 B( T& c- O- d
a=c/k;
2 D- o/ q# V# \/ b c=c%k;
- Y, T n0 C0 v5 b0 K. [. C }
 {# P8 | [" I) |; [ } : e4 j! j9 X; o5 }
if(a!=0)
7 e, L5 }0 p5 {: j2 m {$ o1 S1 m; x, y. A8 F
 c=a;1 r) x, Q, A; ?6 l
 m++;
7 F1 \8 e+ y. \/ f! P( V, h$ h }4 A& c: |4 b7 W
}1 U% }9 R' K% L
<>bool match(int *a,int n)//判断是否为回文数; M8 c+ e6 W/ R4 }/ z
{
0 t5 K5 R% |) r8 C: ?/ \; e int i,j,h=0;! K" n6 a3 T, `* P: M" O4 i
for(i=0,j=n-1;i<=n/2 && j>=n/2;i++,j--)
" F- ]* `2 T: l {
0 p! U; W! H( [' n( U; @! L if(a==a[j])
* s# i6 F! g$ t& h$ |2 C7 o continue;; Y: P+ z9 _, d5 E/ N
 h=1;
2 g8 k0 W+ ^: u break;
/ S. d- V' C# G% I4 @5 \* m7 S, I }
' E! j, Z3 s# b5 b if(h==0)
/ o) [9 C( d: ~% _/ J5 t- v return true;$ Q: V2 `) Q X1 ?
else
0 Z5 Z. W, D( E4 [7 J9 b i0 ~ return false;4 G* Y/ s! e1 N# k0 F
}
+ G2 y# e1 |4 q6 N1 I//clock_t start,finish;* p. ~6 }5 A5 K1 c. ?
int main()8 t6 L) |- |- Z8 x% T" k# ?: D
{//start=clock();
, w9 w+ Z' a! l* i8 G- p if(in.fail())
 z; I, R( I8 L& h6 @' ` {% f- f8 J( x2 ?
 cout<<"the input.txt is not exist!";+ E" ^: u/ [" `
 exit(1);
( x) T$ b7 q/ I }! K/ I# w# F% [# ?: _8 C
String s,s1;/ n" ~7 E) n! B6 ^
int n,g,k,*a,*c,m,h=0;
, e; m6 r, I- A" ^ in>>k>>g; 7 {- {& C( \( R5 _$ u* b' v7 c
s.get();
" P9 @- m& B9 D9 M
) r f+ ?. S6 T% d) a* a. U, E; [ n=s.length();5 I2 \ f& v7 U' R
m=n+g+1;. R; W( J7 Z/ G5 W
a=new int[m];
2 e( {+ \8 U$ X; `; L c=new int[m];. v9 S2 @! e0 t5 |) k
s.get(a);& ^3 [6 j5 a8 z7 W. R
if(match(a,n))
/ F& q+ Z6 Q$ [; c7 l {6 J1 p; e j7 ~- K, t
 out<<0<<endl;* e. D W/ h9 M" Y) ^- T J* m
 s.display();% M0 Q( l5 b- I+ L
 return 1;
' j: D+ N0 n! h0 @/ e3 T }4 B: r* e0 S) X" `
do
- [& z4 T. g, ]- e/ U {* ~4 h' e( ^3 j7 R6 \
 if(h%2==0)- A9 Y/ i* G: j* h' I
 add(a,n,c,k);( P. f) k: A4 `2 D$ W8 I
 else
7 ] S7 i* ]! n5 ]7 R- d add(c,n,a,k);
( F/ |8 k4 Y( X5 V' }+ r; c h++;
' ^$ N$ J+ l2 A7 [3 N& _4 ] if(h>g); M4 t1 k6 K1 d4 T" ~7 Z
break;( v: |5 Y2 W/ `
}
2 G+ T2 r" Z6 V while(!match(a,n)&&!match(c,n));
2 e* W# R3 x, F( ~: R if(h>g)0 x0 a/ L8 b& b: N
 out<<"No Solution!"<<endl;
( S& p2 q8 f" _9 `; C3 } else
2 u. G( @5 R& T6 N7 @ {
' ~( @- N& N A. E% H# X. g out<<h<<endl;- S: ~" L: _. W. p# I! R
 if(h%2==0)) x7 b: t, |8 u$ q* L7 _
 s1.change(a,n);
& W( F2 O; r1 i# u else" @. l) M; N/ d! h$ b5 V
 s1.change(c,n);9 F- o& g" U# J
 s1.display();1 |7 O5 C7 D: E0 M* n+ p* C( c
}& ~2 }7 w! }6 A! R( g
delete[] a;) F9 n% ?. }* z' a6 X o
delete[] c;: u B$ T( K# Y" [
// finish=clock();
( m/ D9 B7 v! {( T, e5 o, Q// cout<<finish-start<<endl;
# A8 U: ^+ s3 R. |; y1 B. W( W$ c9 T return 1;
/ W( K# c- I5 {6 F' ?. c& L9 Q}