回文问题（用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) S: e* z, a: H5 Y L7 s4 m& T
str=p+48;
) Q$ I# b$ @! l }8 J8 F else
7 q- k! Q9 b& Z6 B% A3 i+ c' @* @9 s switch(p)
0 g2 D4 C. R9 J {
5 r% W5 m) Z& i O( a5 B! W3 J; [ case 10: str='A'; break;3 z# D2 \2 |/ {
case 11: str='B'; break;/ L0 b5 H; w, ]' R b/ z* }& O
case 12: str='C'; break;
! r# j" M- U1 x6 Y0 [* d& \; t" N case 13: str='D'; break;
# H3 C9 a) e$ j: R$ M- n case 14: str='E'; break;
& y' \: u% V9 A9 R9 w0 W case 15: str='F'; break;
/ Z5 G1 J1 d! x }
+ |6 r1 X8 q9 x' {3 D. X4 X str[n]='\0';
* p- `# t. s0 m5 S Y2 U- k w' o return *this;9 L% W+ Z" a# T4 c/ k! b
}
9 v n2 n6 K# Wint String::get()//输入一个字符串
! l4 @* ?! S y0 B- ~{
; y2 R b4 X: V# J/ r' h: Q5 S char tmp[40000];
1 s& u3 M( r: z9 g2 u5 _) ?7 u; R in>>tmp;1 Q; Y0 K5 c9 Q+ W0 Y- a! e
delete[] str;: t) t3 ]4 M& w: _6 U
size=strlen(tmp)+1;; B2 {2 k2 F. j: c$ O8 N' G C
str=new char[size];' b! D1 [1 _3 W) g$ O3 N
if(str==0)
7 T8 x. W8 g9 G! e5 a/ r2 L throw "error";
. L5 G3 V" U- N( n* q \9 y strcpy(str,tmp);
) X- I# b2 j" J, J return size-1;
9 U" ~0 g. X' T7 z- k. H}; S$ m+ I- E- O; J# W
<>void String::get(int *p)//将字符串改成整型数组; M1 g# V. u/ l7 V9 ?9 W
{7 b5 {5 w5 ~7 x4 y
int i,j;- u$ Q1 c- i9 z: V( \6 W5 n
for(i=0,j=size-2;j>=0;i++,j--)
3 |' ~" r, l: B9 g if(str[j]>='0'&&str[j]<='9'), K# `) w s! T9 x4 l0 a
 p=str[j]-48;
; N7 B% a8 o- j3 P8 Z0 V else- g7 m) d# ?1 ~, q; s
 {2 }2 @5 o' H; B- r8 g' ^
switch(str[j])
3 ?" g4 Y9 \: q. z {
. n* H$ F% g$ M) J1 v3 e1 g case 'A': p=10; break;
, a8 y* {6 ^6 W3 R8 P* z case 'B': p=11; break;
1 _! W0 Z# o. a. Y) T; c: e- t case 'C': p=12; break;
3 \+ o# q0 N6 n: k case 'D': p=13; break;
9 P; i2 F! N2 X. v case 'E': p=14; break;
 n3 R2 d4 h5 ^/ |6 M" I. g case 'F': p=15; break;
) G. P; B" [ x) j7 I& C, C }& j- H9 F! o/ h- l" K- ]
 } o* u0 g! j1 I; R( O! y
}
, i. S& @1 r6 Q, v- M h<>void add(int *p,int &m,int *c,int k)//将一个数同其倒置数相加# v% b& K3 _+ B. b2 O. i
{1 z U& ~3 f/ l
int i,j,a=0;
# c* o, O9 W1 |. C for(j=m-1,i=0;j>=0 && i<m;j--,i++)6 }/ I2 `- }3 O! `7 u. _6 l
{
' }1 x2 b" a/ s3 V9 P$ M c=p+p[j]+a;
& v1 `+ T1 i! C a=0;% M3 J" P# @& ^. f
 if(c>=k)& ~3 J; m1 Q; X$ C8 n8 }
 {9 Q& z8 H6 h! K5 G. k
a=c/k;
0 D; f* u' z8 ^$ ]1 x* b+ L c=c%k;, {9 G3 c7 v% i. [- g
 }- J% A0 Q% g( ^. v5 Q
}
' m: E/ y& y8 A$ j: K4 J if(a!=0)
2 W- x, y! a5 R& S7 \ {
0 c/ q; Y5 g+ `) U; m c=a;
1 q+ \3 _) n5 Z5 r! F m++;7 B: d8 a7 T5 B2 f
}; l+ A5 K; w% n i1 j8 ?
}, P3 G0 A7 e& x) u4 [7 A' F" _
<>bool match(int *a,int n)//判断是否为回文数" S3 v" y2 I1 Y+ g
{) Z C3 q" R$ K0 b8 X4 D
int i,j,h=0;
$ l+ F) ?$ M @& G+ C( y9 T for(i=0,j=n-1;i<=n/2 && j>=n/2;i++,j--)& I0 h9 [/ d3 q8 v: W0 f
{
2 B8 I) L% `9 @8 ] if(a==a[j])
' o9 J( t; I* ] U8 z- ?- q continue;
: B# W, ~! D% ~' y( H* n/ v h=1;
& h [. l- H* N9 m' _ break;, p) o/ v5 A1 b* _1 {, ~7 a: p, |
}# R; X. w8 b' N7 r1 e& ?
if(h==0)
/ i3 N( S: A8 p# l return true;
3 D, T; a. E' V% f& `: T0 v else ; C& j' K" ?5 G# ^. K) e
 return false;
' g# q( L5 `: o}
 f! T0 ^& `. r: V. U//clock_t start,finish;
; n: S' g: j% V4 p6 [int main()4 e) p8 Q2 Q' D( [
{//start=clock();; `% Z$ I3 m( c; E
if(in.fail())
. K; [1 r( |4 y( N7 n) M9 o' G {
- S$ w$ t% j3 \ cout<<"the input.txt is not exist!";1 Z3 F& o; x! x( g# R: q
 exit(1);9 K- ^8 o* |2 H& T: h i# a
}% ^" M) _; }# R
String s,s1;
% f5 z' ^* V3 E% b4 Q0 b5 H int n,g,k,*a,*c,m,h=0;6 S& s7 }5 a5 `
in>>k>>g; c6 Q1 ?- B! h- o) j0 {
s.get();
" T* G/ j' T& ?9 V n( O7 M+ `3 p
: p( A6 y7 y) b* w4 N n=s.length();
. I; B3 b6 K. c1 l$ _ m=n+g+1;6 t7 ~5 _- n. A( S+ e: T
a=new int[m];7 R$ ~) K9 Q6 h- v
c=new int[m];
. w4 `0 P5 l) e" g7 U1 `# Y* ^6 G s.get(a);3 |% x( n. j" z$ i/ A
if(match(a,n)) |, H. l" U1 C5 I l
{
 a( O. ~7 z3 ]4 y+ r out<<0<<endl;1 R1 G$ p" y a$ k
 s.display();7 F5 e; R F& L# A& t. m
 return 1;9 o7 C6 A+ ]- k4 t1 s4 ?
}# r! @/ r2 y8 K7 v* \: ~: B
do
/ m, C/ v7 E/ p4 [ {3 c+ [! ]( p/ ^% Q- j
 if(h%2==0)" w' [0 W, _, r6 |; @6 W
 add(a,n,c,k);
0 t* i, d( z" [& W. |! ? else7 S- M& F6 j8 \+ A/ L( |8 z. P _
add(c,n,a,k);$ i4 Q8 t7 Z) ?1 R8 U
 h++;
 ~# A# w. x# I6 x' T7 g8 d$ Q if(h>g)! D6 O4 O, R& F7 Q+ B" v; z) L
break;; S' N9 }9 {/ b# ?7 |' S. u
}/ [, b8 M0 g( N' A- N, I; H* J
while(!match(a,n)&&!match(c,n)); A( k; w- j6 ]
if(h>g), T5 j/ @# o2 e5 d: D' d
 out<<"No Solution!"<<endl;
' e2 d& y2 Q3 W# D; X: r else3 l! j, `& i/ q8 ~6 S1 P
{
1 H- `8 B3 j* t9 D0 U2 S out<<h<<endl;
 P9 |7 M& L: H5 ^ if(h%2==0)
 Y7 I4 ^0 f* l+ @' |" Y$ N! S s1.change(a,n);
2 a9 A# S5 j5 f else. w3 E3 C. h: _" V7 l# n, N. d! B
 s1.change(c,n);
0 H# Y" q7 b) `* c! T+ K0 _ s1.display();
1 @) H- z4 r2 {/ x }
+ w! D& e7 O1 i delete[] a;0 Z/ ^& }' \) ?2 ^% ?
delete[] c;6 H; G) f; E6 S$ c- ~* i9 p
// finish=clock();
( p; w, J9 l5 H4 I! G3 `. y4 b( E( U// cout<<finish-start<<endl;% q( ?* V- d0 Q! x% g; }
return 1;9 x" Z( k2 B7 ^; Q4 ^9 d
}