回文问题（用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)1 Q2 w* ?7 J$ [; n
str=p+48;1 K8 s5 E7 h- I0 Y1 {3 {# ^% Q
 else' D( s! [3 t4 h9 @# ]$ I0 l
switch(p)
& z8 _8 e4 n# G& J4 c# r8 [6 G5 d0 n {: Q% o' y& `8 Q3 x/ L) n8 L( N
 case 10: str='A'; break;
' h% K$ W& f4 G# M0 J3 S* f8 v ^ case 11: str='B'; break;2 B! Y6 r5 @# s. D- E
case 12: str='C'; break;
) W( z8 |% p, T& y4 g case 13: str='D'; break;
0 J* \' B# I; _- X case 14: str='E'; break;
: v6 d( n2 s3 E) h2 A5 O case 15: str='F'; break;
3 O0 p: A) O* i2 B9 C! G }9 V6 U% C/ I1 B# b
 str[n]='\0';5 F: x9 o. X" R, x3 D
 return *this;
/ |3 u5 t( Z2 b- y}
. _# y! r o" }int String::get()//输入一个字符串) Q1 ~3 Z9 e7 S& ?8 Q1 T" o# W
{
5 i& q$ M7 \" j) U9 m; v! S char tmp[40000];
1 i) C! h9 d+ I% i4 S5 s# i in>>tmp;
2 w9 R8 t$ i. t# s delete[] str;) \; ` O4 [/ x3 u+ X& D" C% a
size=strlen(tmp)+1;+ I/ T4 b3 C5 c, A
str=new char[size];% a1 p9 a5 h7 V, Y, r5 f" [7 i
if(str==0)( h1 m: K5 {& I) u$ K% J
 throw "error";( q7 i/ e/ ^' `* w6 ^& b1 f5 p
strcpy(str,tmp);, T' U6 I' r- b8 W8 m) {% d
return size-1;) d$ ?. P, l, T0 q% u
}2 ~% ?* b A# J- D5 {- R( l" `
<>void String::get(int *p)//将字符串改成整型数组
; ~ \5 T1 q# e u/ Q{& |+ B# D' o, t" q* A
int i,j;& x0 D" Q& t( c
for(i=0,j=size-2;j>=0;i++,j--)- m% l! t# ?: P& A# X
 if(str[j]>='0'&&str[j]<='9')2 c* v8 ^; [! h6 L/ B7 O- i. `: l
 p=str[j]-48;
( X& ?$ {2 d7 r2 z; @ else
" {) _7 K8 K, o! a( } {+ Z2 I# y7 F& J& e9 a
switch(str[j])) I" z- K- k& K
{; N/ Z+ \5 }6 f' C, e/ \
 case 'A': p=10; break;
- Y) h% o7 L7 P/ Y/ i( Q case 'B': p=11; break;9 e0 i/ p; y# P' {6 g& r$ w
case 'C': p=12; break;
5 ?) X! v; b7 V$ @8 q case 'D': p=13; break;' \) Y5 e' t! c) B% D; H/ ?- Y
case 'E': p=14; break;
0 l' y; B: ~" ^' v/ y$ C case 'F': p=15; break;
0 M$ o$ c# ]: S0 K/ d+ x }% d/ D# l# {5 B$ r: Q* A" y
 }6 z, C1 f6 d& w4 F4 z
}0 a5 a$ {1 j. q# R& ]% L
<>void add(int *p,int &m,int *c,int k)//将一个数同其倒置数相加7 _# b: R3 T2 h) o! ]
{
% E# E3 U& ~4 ~& {7 j# ~" Y- h5 C int i,j,a=0;
$ b# `3 W9 M* G6 I for(j=m-1,i=0;j>=0 && i<m;j--,i++)- S& d* S/ p2 Q
{3 [" m) c1 T- J1 Y* V. e! Y8 D" e
 c=p+p[j]+a;
7 U# A0 a! u& \+ z6 ^ a=0;
' r4 l: X6 V: j0 D) x1 ~) ~) C7 p4 m if(c>=k); y6 z2 I- Y6 X/ O. g
 {
8 S/ v4 G9 ]6 R( M* `' ^* r6 c' S a=c/k;
2 R+ @( }+ v* s2 c# o: A c=c%k;
8 P% c5 E; {& g }: q! d" q5 U4 C9 ?3 g8 w$ e$ s7 F& m
}
8 p' R. X* H( X* q if(a!=0)
. t4 F s T6 a1 b0 k {
5 j8 V$ j2 Q6 a/ L/ Q7 } c=a;
8 M# n8 K7 c9 }3 K7 t& l m++;; F0 u2 e. H1 f( w
}
" f5 r5 q0 p% p2 A+ x}+ B: h: V; Z5 e& T" Q* ]% X
<>bool match(int *a,int n)//判断是否为回文数% v2 w+ B! Q! Y l9 Z. G3 O7 M$ t3 G- T
{
 k6 W _) s% u5 L+ z int i,j,h=0;
3 j- R, c' C7 s9 G5 c: k8 k for(i=0,j=n-1;i<=n/2 && j>=n/2;i++,j--)5 R& S7 G2 o+ }
{8 @# H6 P7 ~" Q& `$ p5 F& T
 if(a==a[j])2 u& H6 X( h- M' @( L1 K' c
continue;
& w1 q2 _4 d* I& _+ O h=1;
' q3 D7 `, D! i6 [* w break;
 H# j; Z2 {! l* A! l }
* _3 Z/ b) _" r( @* a1 l9 D if(h==0) T$ x$ y$ @8 p
 return true;
5 ]6 s0 y6 x% L3 E7 k& @ else 1 W5 _8 Q4 z% \0 Y& Y& I3 @; w. |7 m
 return false;$ r0 S, j; s) T' f
}
; i2 E4 _- b6 _3 V& P3 s//clock_t start,finish; w5 ^- [' q2 d8 o+ I" p
int main()! l! Q& K4 r% I1 R. ^. z
{//start=clock();
1 C, [4 t+ D2 m j4 D. s if(in.fail()); G5 V. d& Z0 x
{6 T2 E7 m& z$ s% L
 cout<<"the input.txt is not exist!"; @6 `' G1 j4 c3 t/ x$ G& U
 exit(1);( G9 Q6 N; S4 w! a' e, X, ~1 c. ^
}8 B9 H" Q1 P. _/ B: L* x$ g- v
String s,s1;
; o$ s4 Z" p! {$ \4 ]4 ~" Y- f int n,g,k,*a,*c,m,h=0;
" y$ ^' A7 v6 |9 l2 Z in>>k>>g;
; E- @+ t! D0 @, x s.get();8 e+ ? x' ^& Z- y

% {- Q! Q) a* e; _: @9 o& J n=s.length();
2 }/ w4 [3 ~% e | m=n+g+1;
4 V `6 [, C- u7 L+ s/ b/ }. ]& B a=new int[m];
1 t# @, d8 w! Z c=new int[m];
, U) a5 V! M1 S8 e s.get(a);* ^" C. v- _' [- w
if(match(a,n))
$ {& f% X& e X8 l% q {
+ m6 ]5 n* p5 {* `+ A- y0 W out<<0<<endl; ]6 \4 S C/ P3 m0 c% B- M
 s.display();
- C# L7 U4 p; a3 M( i return 1;
& J- @: O6 E; w; E6 l5 x7 Y) I" d }+ }/ U/ r, l. r
do7 M8 p' ]5 D1 F. ^5 H$ I
{
0 u# v) V/ q" M |6 c if(h%2==0); a" t b+ W9 V: t0 |: {
 add(a,n,c,k);
' b2 p( Q+ M+ [. O1 Z2 M else
- u" j4 u/ ?8 a x3 W2 ]2 d add(c,n,a,k);4 _/ J ^ A: c5 t
 h++;% Y/ ?$ I3 w R& _+ T7 ` r
 if(h>g); k7 X5 V2 e4 J1 Q6 @
break;
7 ~: [+ A) M4 _" M/ y4 J }
: {+ \, h8 c- H while(!match(a,n)&&!match(c,n));
' m1 H6 t9 D+ E1 D! T: s2 G if(h>g)
: \; Y9 _$ j2 r' H# L# [# b out<<"No Solution!"<<endl;9 n- U( q. e; i: ]& w$ @
else
( P) G- K; X3 c8 G/ J {6 n& @! P0 s2 a4 m
 out<<h<<endl;& m$ g# Q5 o4 t5 s1 X8 X
 if(h%2==0)
. B/ m+ c. S1 s. G) n s1.change(a,n);9 {" b" J) J. r q3 O4 x
 else
( N$ p f' l$ R8 y9 a: |1 m" Z s1.change(c,n);
3 I# B) ~" J$ p0 @" n* i+ p* {( ^$ H s1.display();8 \" p( K9 `* C% L7 I
}# _! O. u# A# l; P1 W D
delete[] a;
3 Q" h5 c& K" B. F9 y0 c% W delete[] c;8 I0 X' u* H' o( ?- w( x0 v
// finish=clock();
# r# R, h: q( J" F' s( Y! Y4 R// cout<<finish-start<<endl;+ ?0 Q! X0 r5 A) X2 N" x; Q3 t
return 1;
& v1 |4 ]/ i L9 v9 `}