回文问题（用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)
- u) }8 Q6 I! h+ i9 J# W str=p+48;4 Q% S) \& L: p% L% C6 v
 else
3 {) A) f1 I$ w( k& P7 E6 g switch(p)- e* W" i3 U! c6 v
{
' P6 q8 Q" o h( ]- E ~ case 10: str='A'; break;
/ [. k' H$ h7 A, D" \; j3 n9 D case 11: str='B'; break;
6 P+ u0 g4 c7 ^* |: w3 n case 12: str='C'; break;
' V$ L0 l/ _. e1 ? ^ case 13: str='D'; break;7 V" M+ Q% [* f- ?( {# X
case 14: str='E'; break;8 T( s6 b- Q/ p( d
case 15: str='F'; break;
9 x4 N" c3 }6 Y6 p }
4 X6 Y# f" d m& x6 w' A str[n]='\0';
2 O* ~4 e! g; [5 w1 q return *this;
! D" u: q5 n) y}
2 r; ~0 c# U: ?6 [( v: Z, _& pint String::get()//输入一个字符串
7 Q# b K3 n$ W9 ~{
$ Z. Z$ n; y [2 G char tmp[40000];. a; x; A9 l2 a- }! b) Q' T9 O
in>>tmp;( r1 [2 A9 c. k8 C5 X
delete[] str;
8 ^7 Q" E) { w7 t$ G size=strlen(tmp)+1;# V; P5 d! g" f6 p& u3 y9 Z4 g
str=new char[size];2 ]- j8 i" Q, f2 s& W) w7 K0 `% P3 y
if(str==0)3 V& _3 q/ h' p9 b& j3 U
 throw "error";
8 o/ `3 J0 ~2 h) M3 P- L strcpy(str,tmp);$ l, D3 [+ V. l/ w5 E$ z
return size-1;
3 {1 B0 z$ s6 S) q% } m}
! u2 C/ \0 L" q9 `<>void String::get(int *p)//将字符串改成整型数组
7 d9 T0 R5 Z2 d1 T# I{& Z+ @" [8 ~! j5 k7 D: [
int i,j;
/ V" ~7 v8 o- G i# M for(i=0,j=size-2;j>=0;i++,j--)
% O3 ?. Y- O( f, C- f+ s: J) e if(str[j]>='0'&&str[j]<='9')
! |. m: `# A; N5 g( I7 b4 \8 J1 V5 J- E p=str[j]-48;
" O. O- x% H8 f+ E0 Q4 N5 U else
& X5 f2 D- I! x$ i {
* w& e. k" p7 u0 R( h% R* d% N switch(str[j])5 F8 M( z$ s- x$ u% z
{' s1 q: u. o& `" l3 U2 U7 z
 case 'A': p=10; break;
% [# O8 O1 q, {9 Y' F case 'B': p=11; break;! Q/ \1 ]1 `/ v% z" b# @
case 'C': p=12; break;% Q' o P$ D. I
 case 'D': p=13; break;3 Q3 Z; N, W) ]* ~! ~4 a4 E
case 'E': p=14; break;: Z `9 @4 w B% p3 U
case 'F': p=15; break;
; f* w0 R s$ g- r }8 U7 V1 G6 \2 L5 X; y0 R4 x
 }6 S0 P; g& }5 ^1 Q( ?1 [
}* L1 O! l1 U/ d# A
<>void add(int *p,int &m,int *c,int k)//将一个数同其倒置数相加
- V' n3 i5 f' K{
- l/ K8 q# o" T) B4 O- y int i,j,a=0;
8 P0 M; V4 d# {* x( R for(j=m-1,i=0;j>=0 && i<m;j--,i++)
/ p, n& f0 x7 E# F {
& h8 \/ E& L8 e2 T# o0 x c=p+p[j]+a;1 T6 h( \- i$ [$ F0 S3 r6 T2 U
 a=0;
: C( R8 ^1 T! s, i if(c>=k)
9 f& n1 L2 G+ k- \ {- f" Y# y, Q6 t! x% j0 ~6 R/ T
a=c/k;
c=c%k;6 q& w" D5 |* H# ]1 d t" t
 }
; f. _9 A* Q2 ? }
9 E$ {3 j- c! [3 S, i7 w( P if(a!=0)
* z! S1 l9 e C8 k( H% W7 l; O {- Z3 E, ~7 _. o* G7 Z2 _
 c=a;' Q8 U) B2 m9 g+ g
 m++;/ P: S" b0 o& |* l3 ]; r; b* I( m- S
}8 Z- Z4 {. d Z* u
}) {( U( f' f+ K0 g& E" P7 L
<>bool match(int *a,int n)//判断是否为回文数$ X b r8 O) m# c! ~- w4 l
{8 X" d* k# j; Y$ k2 l
int i,j,h=0;
& O. b1 ?7 `/ _+ t for(i=0,j=n-1;i<=n/2 && j>=n/2;i++,j--)# _7 ?: T! m- L
{8 ^5 a& i( ?' U: O5 y* D! t
 if(a==a[j])
; r; b* M7 a: i% s t continue;% E: f Z4 C9 L
 h=1;
) H! j6 h$ {" Y6 t2 S9 I" Z break;! x( O) t3 H/ Z7 B5 @9 N
}
& k5 J9 {4 d3 y, L" m if(h==0)
4 l; J9 ~- p1 B( Q" k$ }$ m4 L8 B return true;
8 n# {1 W+ ~' v3 m$ `+ _! ?1 D else
' d+ g [) S! h. X* n return false;! ~2 A1 {" L4 Q! Z# o
}) a0 J% l u5 w) o) {/ ^% b
//clock_t start,finish;
& s" d) D- M3 W$ Gint main()
# @9 @& E% F- c$ s5 Z{//start=clock();
8 A( h( d) n N8 r5 U if(in.fail())
, { B5 r( l2 s- K" T {9 N4 @+ f/ x% T; t% j$ I$ V, H
 cout<<"the input.txt is not exist!";
0 \: a. ?/ _8 r% v3 I# J/ {* P exit(1);
. u% e8 b" B; a: e" u }0 [6 t( t. u/ w4 K- V* ?, A8 T
String s,s1;
2 A2 v' E& n7 y. c int n,g,k,*a,*c,m,h=0;7 Q) w x/ @4 }2 L8 y
in>>k>>g;
7 ^: N8 m. R$ j8 b3 W$ }" ^ s.get();: O5 W) x/ ~' R+ r; o
# [" Q% c& C8 ?7 G. O' K* [
n=s.length();: @6 c' f4 u! B* i' ~. f
m=n+g+1;
! D7 v0 ^! k% |9 Q/ ~8 @. v a=new int[m];
. ^. n. `* K$ R. B, u/ s c=new int[m];
 i+ x! P& y* I: i8 p# K W s.get(a);8 r/ D+ {" ^. e# [8 Q
if(match(a,n))7 _* q* l8 d) M/ n9 U) ~0 c
{; b# L) e; |" ~
 out<<0<<endl;4 t" L# E. t$ v8 @
 s.display();
: n9 G1 u' Y$ @, S0 P3 c3 R2 ] return 1; i8 j! a7 J P/ X5 h0 _; `/ ^5 @
}& u0 K* L2 D/ Y# t) [" C" p, a1 O
do7 \$ c& I9 l* x9 p
{. f9 d8 B4 N6 R+ i
 if(h%2==0)
% Z9 S3 K. g$ q0 \ add(a,n,c,k);8 z% V! k/ V# ]2 L3 b, @$ S
 else( S- N7 e/ Z) x* ~: `* Q
add(c,n,a,k);7 C, W& d" A2 L
 h++;
3 f* `" ^/ Z8 m4 e if(h>g)
2 f, }, |* w# n) S! R5 Y break;
6 U7 A8 }! E9 I2 a$ W( s2 P }
) ~5 h+ m. C8 P' {8 V0 ^ while(!match(a,n)&&!match(c,n));
1 n: f+ N6 Y9 W, k* [; D if(h>g)
3 f6 Q; c5 Q1 g/ ~ out<<"No Solution!"<<endl;! ~) |8 p% _- Q2 n$ j
else
, z4 z- E# X2 z# @3 O$ @) m {
! M+ {8 _- g, Y! O out<<h<<endl;7 J" q6 u: [5 l- @4 r7 g1 l
 if(h%2==0)
0 \+ M% m" T/ p3 L* l s1.change(a,n);- B, @( Z) z0 o
 else
) L) B# k! ^1 Q$ k s1.change(c,n);
* V9 s5 e6 k6 n4 \$ H; w s1.display();' g- c% l. u6 C8 {
}
! |; N' z6 s7 ~( b6 t! u' v delete[] a;
4 P3 V7 J# k, y4 b delete[] c;
' q" K6 B4 Q, W8 p1 q+ Z6 Z// finish=clock();% j" j9 d8 _% o+ z$ W4 A e0 G
// cout<<finish-start<<endl;
9 c0 i6 A* l+ ^1 X4 N$ S return 1;+ I7 L* J, r6 i# Z' l6 ]* f, H& D. ~
}