回文问题（用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)
# \% { N2 R7 ~- R! d n1 R str=p+48;& ~. x, s' v& }' T, A
 else
6 N& {5 A2 i" }- D6 b switch(p)
1 N) C# v5 j2 t: Q) x; e+ @2 Q {. g) o3 Y3 C9 e8 Q+ g
 case 10: str='A'; break;
8 P8 ~* r( }; I8 }3 F$ j+ V case 11: str='B'; break;
" H( E x( ^9 }: @. p- t9 v B case 12: str='C'; break;5 [2 S/ T- R5 l/ f! J
 case 13: str='D'; break;4 u* ^0 S' R+ c0 ^
case 14: str='E'; break;% L- q9 L2 W6 r% ~
case 15: str='F'; break;
- m! Z9 X |2 R1 O0 [ }
# ~& N& T7 q6 _- y0 C3 M str[n]='\0';
6 S. Y7 d" {! |' ? return *this;
 H" \8 j- c: `5 S}
! U9 G- K+ \+ V" G2 wint String::get()//输入一个字符串
; ]5 ~! W' U6 w4 u# m; m" I0 ?{
4 p/ ^# q! m/ X* V2 U3 Q3 l char tmp[40000];% g3 K: J; ^: h: _5 J+ m
in>>tmp;& a( K/ e7 k. p7 p* M
delete[] str;7 k. K* `( t5 @ J. h5 N7 P6 p8 Q- O
size=strlen(tmp)+1;
$ L' `9 y* R& n/ a! Y' r str=new char[size];% V( j T, t5 O! T
if(str==0)
 P: _' ^6 F& Y4 M. `$ ^/ o8 M( ] throw "error";& X5 ^) q& U7 P5 }$ g" w
strcpy(str,tmp);
0 \% p- U3 Y% q2 ^3 q# G return size-1;2 H2 E- U, d: |2 G. j
}
5 v' f: t: B/ B7 M8 }<>void String::get(int *p)//将字符串改成整型数组
& g& [8 \+ j% @3 y- p, S{* d" K3 R0 b3 N7 v
int i,j;* m3 e. s& l- G9 B- ]4 Y
for(i=0,j=size-2;j>=0;i++,j--)2 e* t# s; \+ ^2 i! k
 if(str[j]>='0'&&str[j]<='9')
, E" Z0 u; f4 I6 |- X p=str[j]-48;6 D: J7 w/ w3 f0 b/ @& U& }* ^
 else! Z4 Y" j$ d) W! y& Z W
 {5 v8 Z# w+ z5 }0 P
switch(str[j])$ `- q9 W! r* k' v3 r# B
{
, ^3 E, t K9 a- J( q; \! k- @ case 'A': p=10; break;
1 D7 g6 ^4 D, `0 {. Q7 R K) z case 'B': p=11; break;
- t9 {3 V% ?* P! W( B% N* b case 'C': p=12; break;
2 E t7 z& \2 G case 'D': p=13; break;4 `. b- v: ~0 W A' z
case 'E': p=14; break;$ r" X$ o- M3 H/ @
case 'F': p=15; break;! n2 h2 Q E# j& _$ T
}/ @, @( C9 ^2 x/ A& _! V* h3 B
 }9 X) c$ i! M4 T' y, S- Z
}4 W& z( N9 w! M8 B
<>void add(int *p,int &m,int *c,int k)//将一个数同其倒置数相加
+ `4 j" z3 F5 D6 x' G8 Y) D% X5 I{5 s1 l2 k9 x* k8 c5 @
int i,j,a=0;7 ~% e2 E' S {" t
for(j=m-1,i=0;j>=0 && i<m;j--,i++)
6 m* q. i9 c) f/ n/ \ {
! q5 p9 W; ?. z9 t. \- Z c=p+p[j]+a;
/ h$ ~) c; C7 W E% ]% T a=0;
+ p* P) s2 g/ o1 G) o9 i! I if(c>=k)& |- V$ _& J# x( Q S$ k/ j
 {5 p9 M9 S& e9 T _- {. Y
a=c/k;
" g4 V2 i& H8 v c=c%k;- x# Y2 J- C2 R" Q. g, L1 K8 a* r& z
 }- `+ P h; {$ A
}
% j3 Q0 Z- i' |0 m if(a!=0)
: M T$ F$ Y' ]- Q; G4 B) }" Z {. ?5 j5 X9 a) ]; A) F, G: S" g
 c=a;$ L3 U# R7 Q2 y( L+ l$ m
 m++;
3 J9 H8 B/ d# e; R5 v0 T }0 e; f* h9 h8 z3 I0 ]. h
}
* x6 |/ k/ Z: ^, K1 x( J3 E<>bool match(int *a,int n)//判断是否为回文数, ?0 W2 \- O+ c T
{$ k2 H& O: u5 o8 p! l
int i,j,h=0;( A/ r& a6 ?* W: O _$ W n+ p
for(i=0,j=n-1;i<=n/2 && j>=n/2;i++,j--)! e, }: T4 K, y
{
# Z1 |1 J, o [7 J- ?; i if(a==a[j])+ a% k& d3 A7 ^8 y+ a0 C! S
continue;+ ^) o" w5 _/ ^6 J0 J& T
 h=1;$ W* \# F0 d0 f9 p. }
 break;/ b+ b4 F1 _/ W* A' w) h
}8 O6 J+ H R K7 }) [3 ^" m
if(h==0)
9 e9 }$ Z3 d2 x: g5 Z6 u, r return true;
# @: }4 d+ |: o3 I5 m$ h0 | else ' u0 O% f! @4 t' P4 d4 l1 {
 return false;
" z/ a- g [/ c e- z}1 w; b7 Z$ `" E& v
//clock_t start,finish;
. b1 u. a+ T. ^/ X1 q# \1 kint main()
% r/ d( v) q8 j1 H* G{//start=clock();
9 e7 I1 T" k$ m+ ?: K9 H; ` if(in.fail())
4 S, |* D3 k, V/ w4 z2 z {5 { ]) ?) t8 q- b1 F3 N; g
 cout<<"the input.txt is not exist!";6 G- P' X- c" a$ o
 exit(1);
4 i: x- d7 z7 |. G }
! l- M$ y9 H7 q M s" a String s,s1;
2 p: C- a4 N0 a3 O2 H9 B. } int n,g,k,*a,*c,m,h=0;
6 P( e4 u3 x+ J0 u. P7 e in>>k>>g; ) z9 [; B# i" w3 o: I0 ~" G
s.get();
7 P% b! y1 Y4 m( `) |( Y# ~( Y& g0 ~
2 A% [; s5 I) O/ ?5 K% a0 Z. r7 i n=s.length();
( a) [+ I$ q4 t5 G ^2 ` m=n+g+1;
0 c1 {. x0 ^+ c a=new int[m];
3 o. e' j5 ]: x5 f" k2 n( J" ~/ Y c=new int[m];
- u2 Q9 P2 p$ g/ \- E( t* p s.get(a);. o' \3 v& p) u+ \+ R
if(match(a,n))
8 ]. A' q; H* e4 l- \ {
3 d* a, ]& m' `& ?! y8 U- b out<<0<<endl;0 Y# o& L" ]7 @
 s.display();2 N& V0 T& q! B1 P/ ^7 R; f
 return 1;5 p8 b5 B1 J$ [1 H S
}6 i/ b2 M0 z" s( }: b
do
- o$ ~1 O; z2 \# B. Y$ u, k: o {
: a2 b# q( p' L! i if(h%2==0)
4 ?) q8 A" M& T# I) ~ add(a,n,c,k);
1 J, U7 m: E, d6 @( u; z8 D+ }# ? else
; i5 u) W7 P% |! f add(c,n,a,k);
3 N1 |, j, {- d) v/ | h++;
; {- q: Z6 I( O9 { H& d if(h>g)
6 A1 W$ ^6 W" f( F3 ]5 M break;
# r' L: S$ F# ] }
. j" j% ?0 u% \8 O& D( o6 U* L( i5 @ while(!match(a,n)&&!match(c,n));
4 L6 I8 N1 j4 z: V6 A if(h>g)! Y+ U/ u/ F7 v% S' e9 _7 ~5 V% V
 out<<"No Solution!"<<endl;
5 q' i& T3 U) q8 |; c* w; L else T$ F9 O G0 A" s8 i
{
1 S. F: Q4 j2 s" h3 t out<<h<<endl;
! b* k' W% P3 U; J& R5 a if(h%2==0)2 @$ N2 G7 ~& g2 Z3 R2 @
 s1.change(a,n);
 y3 n# g) v. M+ ` else
+ f- n* i7 ^) ?8 b4 V6 J' r s1.change(c,n);
/ }" C. L$ w; ~/ D. L; v1 h' n3 C" Z s1.display();2 ]4 P' W' G& J9 M3 ?2 G8 v* P; g
}* a/ Z& a" k% G8 Z. ]
delete[] a;
' |9 s7 l. l! R8 { delete[] c;
' j* r1 W/ r Y3 b8 i+ y// finish=clock();8 e1 R, Y& ^; V# h6 l2 F6 m
// cout<<finish-start<<endl;0 @# I& ?5 O& W6 O
return 1;. C- X7 Y$ f" U, Z1 S1 K0 C/ M
}