回文问题（用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)
6 y, w6 u& `; |) b3 H R% r str=p+48;5 m/ G {; G! N9 ?, T+ U
 else/ x. W# k+ t! y; L8 `) j
switch(p)8 {1 h) |' m" W& F: R+ e+ x
{2 r- u5 ~5 C, b# ~
 case 10: str='A'; break;' y# P) W& G) X$ }) U7 z+ x" i
case 11: str='B'; break;' D+ O3 O# u1 |/ m; L/ h0 ~9 s }; I
case 12: str='C'; break;3 ?% f' T& Y a6 F- d- t2 u* m
 case 13: str='D'; break;
3 N& B% Y, q: t% ? case 14: str='E'; break;
- A' m5 J4 d. G; [ case 15: str='F'; break;& _' B; P6 u$ i, q ]. `9 o8 o
} q2 h+ g" o; r# `
 str[n]='\0';
2 @' { n) ?" d4 f. ]1 B return *this;/ g; q% A* e4 z7 d
}
, G- T5 b. }! g% |int String::get()//输入一个字符串
0 N1 j y6 E1 t{3 ~7 ?# w4 `/ T( ^: U$ p( D
char tmp[40000];' F2 `, z6 z2 H; K
in>>tmp;
3 V& R& ` G3 i+ B3 ]" | delete[] str;. g$ V+ C8 e: b/ x8 r3 [8 ?" a
size=strlen(tmp)+1;
, @. ~$ T; j5 [6 \ str=new char[size];" h( R" Y' ?' R* N# r
if(str==0)
, R( E- ?6 r. I+ E/ V" } throw "error";
( T1 f7 a) V$ m! o" o9 Z# v9 D# g3 h strcpy(str,tmp);7 n1 a- f' {% a7 o9 Z5 _
return size-1;
1 n: {4 g+ A- N8 e4 r; R1 J' Z* {}
/ [, L( O: E6 _/ j5 L8 x<>void String::get(int *p)//将字符串改成整型数组
 K. B7 G+ C/ J$ T{$ H8 c& S, r* C8 U5 ^7 g
int i,j;
for(i=0,j=size-2;j>=0;i++,j--)
- ?! Z. D( @; {. ~/ V1 K if(str[j]>='0'&&str[j]<='9')
- q/ }6 \3 k2 x p=str[j]-48;/ t4 q5 U3 j5 b" [0 P( m) k
 else
 A- i9 f& n2 m) I3 L( q {
( S* O: X# E4 ~: `3 u. b4 E switch(str[j]), J4 r `; y( v
{- b, c! B0 g' S& O/ c* {
 case 'A': p=10; break;8 M* a+ |' p* L& Z, I! K+ I n W% Z
case 'B': p=11; break;
$ v% J( U8 m1 e2 z0 `+ u case 'C': p=12; break;
* A0 O6 c0 V( Z& e3 p' V0 P, o case 'D': p=13; break;, G, E: C5 H2 u( [
case 'E': p=14; break;! N8 d% ^: ?" k; k3 R' o
case 'F': p=15; break;
" P! w- D$ B. v+ L' ]9 n }7 q# u7 v( P6 C2 L# k$ b
 }: _, v1 E$ Y1 o& L; ^
}$ i* F* r, ~6 a: _
<>void add(int *p,int &m,int *c,int k)//将一个数同其倒置数相加9 v' Z& x8 X! z9 s
{, m# b3 f, C& S* W8 L- N+ C' N
int i,j,a=0;
 G# Y2 k* ~" h+ w# C for(j=m-1,i=0;j>=0 && i<m;j--,i++)/ `1 _: n- k; K; X
{
. w) g5 I; {) s( ^+ R2 r: @ c=p+p[j]+a;/ _, P& _0 Q( m
 a=0;
2 R$ M h. Z ^+ s8 H if(c>=k)9 U$ C* S) [5 C+ {' P
 {
! w) {/ f4 f3 B1 t a=c/k;
2 ?2 J g" \! F1 A# d" g c=c%k;& ?, M% S4 G, b6 R. u
 }
: o( _! r$ C8 o p' i } 8 ^* ` i. z9 [7 ~% M$ V
if(a!=0)& ]2 M; p& V K; b- @( ?3 A
{
, B7 R, m4 X6 J7 T# {) [ c=a;
$ I- G6 e5 I8 F4 c2 u( A- ~7 i m++;
! t1 w V" ?& S }
$ F; O2 l' l" o& q" Q$ w}4 t2 q. {2 y& `' r
<>bool match(int *a,int n)//判断是否为回文数
$ s- U: \5 ]3 M0 b. v( m{/ }( o, p; o( c. f; e
int i,j,h=0;
) m& L' b0 Z; `2 A for(i=0,j=n-1;i<=n/2 && j>=n/2;i++,j--)' z. M. J+ |: t6 e c1 K
{7 k4 O/ G- _/ i: M6 z6 T0 z/ b/ M9 `
 if(a==a[j])' a& V2 T7 n, D/ U
continue;" c6 v6 n9 u# W w& F/ z0 F
 h=1;
( Z0 W2 K0 x w+ P break;0 S/ D2 q% _) e
}$ L3 q4 W+ J; Z* Q
if(h==0)
$ o0 p, H: u/ _" s" I) L return true;
1 n; a/ K# H+ Y0 \ U6 i% e else 2 S! o9 k4 h* l0 K/ u- T7 w$ P
 return false;3 U7 P7 r5 e% ?( @" T
}
- m8 x8 R+ m& R# ^% ^1 m//clock_t start,finish;; o$ Y' j# E- X
int main()
+ ]5 e: ~& z) j$ U" l2 b* @{//start=clock();& k' B6 X v% F1 H% x# q
if(in.fail()). c0 f# W2 {: p0 {
{
/ a G1 r3 J1 m1 i$ `4 t% ?+ m cout<<"the input.txt is not exist!";! V) m# B" o3 d) W" e
 exit(1);
9 J$ t. x) H) j" D* {2 ?6 S0 ]1 j! ~ }1 h" \! M5 j7 |$ h" {& {& E, B1 I2 z3 u
String s,s1;) U% A m3 a! t2 ~
int n,g,k,*a,*c,m,h=0;
 j3 E$ q+ e- L in>>k>>g; 6 y' C' R/ Q4 ]6 w- V6 A. u5 X
s.get();
, }$ B9 w* U! L {
: @) g1 J7 S" C' C7 y# C! x n=s.length();! x9 [$ R* h7 K7 b7 u) L3 R4 d
m=n+g+1;
 X/ \" |1 s; U9 n- E. t a=new int[m];( L5 g3 Z& N# \% ~
c=new int[m];! u9 B1 p& d+ r( p
s.get(a);9 J Z }- P% \% y% q: y/ F
if(match(a,n)). ?& m7 z1 K, d, Y
{
9 s- V( O5 ? Z7 B# O3 l7 I: P out<<0<<endl;
- K+ R- O( V) U1 ~& w s.display();
5 M m- S1 R8 i4 o o return 1;1 }1 Q3 p$ _! s0 [* F3 s. U
}
" M; f9 l! ~8 m do& q+ ?, R% b6 _8 F( H1 w; ?
{0 g. b4 ?! `) |4 z8 J) r' i/ q
 if(h%2==0)
1 h/ S* l% G8 a% \% M8 K add(a,n,c,k);7 u: m1 \& ]( Z8 m" ~- S! v$ F
 else
" E# c* ^' A, W$ \8 a! B add(c,n,a,k);* |) p( c3 ?, z" J' B# E, B5 [ @
 h++;% @2 D" p1 C3 T5 `
 if(h>g)8 [. o/ m; |7 x1 h- c& C" C, _
break;
 u4 @* a/ l4 [8 @ }4 n; A" o/ q) [ b8 b1 r. v; J- d
while(!match(a,n)&&!match(c,n));3 ^# c9 N% C5 |4 z( _
if(h>g)
) e$ [, l J* G8 k out<<"No Solution!"<<endl;8 `! C3 P; U5 q. p/ _: r0 x+ `
else* P# G& ~" ?% V& B
{
: u2 X+ c% I$ D6 q5 f out<<h<<endl;
% t3 W# X; d1 U: a% r% N if(h%2==0)
) M* I& ~% m, o" R1 N2 g% w s1.change(a,n); Z* g0 E6 V8 a0 S; C! |
 else
) W" Z2 U# m& {$ o% y) @4 j0 r s1.change(c,n);
$ z/ F( E$ Q6 n2 o s1.display();) }8 g$ s+ b! H" A8 B7 Y
}5 |2 \1 Z2 x2 Q( o
delete[] a;7 G( U+ {3 |; q" g% d% X
delete[] c;
% A; [2 J x( `& x, k# f$ w// finish=clock();, R. ~$ ?3 j2 q; ?5 N y
// cout<<finish-start<<endl;
; A7 [4 Q4 j5 {6 [ return 1;/ K. m- Q9 O/ B4 j! z
}