回文问题（用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); m) B# g! T8 L* b( ?
str=p+48;& X t' P+ {; e( R
 else% |) J, v! K/ j+ U( P6 v l" @
switch(p)! D1 R0 h5 j, d2 w7 T
{. Y, a) _3 H3 R9 l
 case 10: str='A'; break;
1 u' R6 ~+ J2 d4 x% K case 11: str='B'; break;3 C' {) ?; k5 z
case 12: str='C'; break;
, {# d7 E4 T2 J" C case 13: str='D'; break;. i$ _% z/ `7 Q' O' [. S2 O3 {4 A
case 14: str='E'; break;" D1 d7 Y' v0 [2 o: q9 z
case 15: str='F'; break;
) j( ]& o( _4 g* q }
: m* G1 { Z6 O" t* S/ b str[n]='\0';
2 X9 ?! s! v* M8 p T4 g8 j# e return *this;
6 i* O9 e( G7 B- ?2 E}
6 d0 M6 R% \8 tint String::get()//输入一个字符串7 R( X* b2 R, w: [7 p1 ~5 R
{+ |% Q" g4 E; s( D4 ~# v: B% J
char tmp[40000];
' k0 B2 w4 o7 ?' c in>>tmp;) p6 l. s Q, _% f7 @, S, U$ Y8 q
delete[] str;: P* H3 |: y5 W( z# x
size=strlen(tmp)+1;
' E- m! M6 `, B2 R5 L& }1 \ str=new char[size];, F' a, j/ v( v( \% z% m+ z e
if(str==0)
9 G* P5 u) S- W' m1 r throw "error";0 i* o, n8 z" T7 n0 o
strcpy(str,tmp); [/ a# M! n6 Y9 v
return size-1;$ m8 Q# ]& c8 I; [' |% |: B
}
$ h; z( f8 F$ a7 E/ \<>void String::get(int *p)//将字符串改成整型数组 e) u+ Z4 a1 @% ]6 f, J
{
0 z6 ^6 r! r5 s! s int i,j;# t9 P: s- ]! i. `3 j. }5 U* P* E+ X# x
for(i=0,j=size-2;j>=0;i++,j--)
 }* F# Y8 ~3 z' _4 v) X" t$ [3 S if(str[j]>='0'&&str[j]<='9'): Q! t" e8 V+ o
 p=str[j]-48;% T, p9 U K3 W' y7 D
 else
 `0 y# B0 P( O {
* t4 C8 I7 q. f switch(str[j])& ], {* Q" w/ j8 [; [& j
{! E# S6 \; m F/ [
 case 'A': p=10; break;' G5 F- A/ P" K, Q2 ?8 d, f
case 'B': p=11; break;* B$ k* j0 m: k/ |- `
case 'C': p=12; break;, ?# i j$ B8 H
 case 'D': p=13; break;
" ]: p( R7 `- \4 S: H' K case 'E': p=14; break;$ [' g& t8 V9 A5 `
case 'F': p=15; break;& _; u3 c/ D4 }3 P, |2 K
}
% t/ c o, _% m& y. z# ^4 a }
- i8 i* I+ I# g% D5 K# {4 ~}& X( d3 p6 e9 W/ V
<>void add(int *p,int &m,int *c,int k)//将一个数同其倒置数相加
& M1 r, ]# U# j: `{
. K( k5 g3 G: v. W4 y0 V9 b9 l int i,j,a=0;" A1 q+ {3 P8 z( H
for(j=m-1,i=0;j>=0 && i<m;j--,i++)
, C" x1 M- l% T. l j {
& S$ ]: P+ \' _" K- H4 U4 F1 n7 X c=p+p[j]+a;
$ T% }! v$ g" Y% ^2 c( \ a=0;8 M2 X5 p& Y) a/ f3 F. `( H* h. q
 if(c>=k)
! G4 a" Z. u! `( f% ^ {
0 \% O0 G" I) }. T; g4 [+ ~ a=c/k;
/ x! T. D) J2 k% N% R% l c=c%k;$ ^- l- d* Y2 C7 c& m2 B' _
 }& C# W) S" v- F$ `6 o. Z+ V
}
4 o6 ^. ^0 Z; \$ O" _ if(a!=0)* k. O% W5 k! o
{
) G" l9 P2 ^ m c=a;' e" N! l) T5 i0 H' S- T M
 m++;
5 [/ o6 S' H: g; L8 T }0 r& E1 m5 M) `
}
' b6 F( H* s% H/ [; a- u- I<>bool match(int *a,int n)//判断是否为回文数1 r1 d7 n3 U* f) s
{
/ G% S* A) J3 y( }$ f2 n int i,j,h=0;! q( R/ K5 Y$ P& D4 U1 [
for(i=0,j=n-1;i<=n/2 && j>=n/2;i++,j--)1 @; l6 c( f, ^7 E0 A4 E
{7 J+ O4 \8 |# d) K
 if(a==a[j])
' f6 P8 D- |9 _; `: b continue; r% l) F9 O5 w1 o
 h=1;
0 Q, U z5 w* r3 z7 j* b break;
1 E& a% m) U/ P& C& z: B# G+ L }2 s5 w/ R x( ^* @5 |
if(h==0)8 j; O% T/ d. D2 r, }
 return true;; u! q. l) d2 z0 D8 \9 [
else $ P4 |8 F0 w" x8 e3 m* N
 return false;
# w# n- ?8 V2 i! ]' o7 Y}
! ?1 z# `* n2 s# X) V0 c! ?//clock_t start,finish;
# E+ B1 P( t- e; bint main()
/ f, W: {6 p1 j{//start=clock(); [+ c/ \* Q9 S2 _
if(in.fail())0 ?1 `3 e: ^( O5 c2 R0 b
{- r& H& n3 a& q( }% Q
 cout<<"the input.txt is not exist!";
# J L; `2 z1 @/ R# N exit(1);! H: \$ [! L+ t. K. S+ `
}6 M2 R, H% R) A+ b8 W8 y0 b
String s,s1;
7 h; R2 X# ?3 f, V* Z int n,g,k,*a,*c,m,h=0;# _7 q9 b+ a1 @" z/ {/ m4 Z4 P/ y
in>>k>>g;
) L+ i1 u3 `8 ] s.get();% t# P" x2 a1 O d2 i T1 J
$ Y% D3 m" ?0 ~4 b) v
n=s.length();9 x4 i/ d3 V6 J% i3 z7 w- h
m=n+g+1;
9 x$ b0 I0 Q* F; S- y a=new int[m];$ K$ _0 r9 m" d A2 M4 p# q& `
c=new int[m];
, V6 M* t' W/ b" r% V$ V' f s.get(a);4 C0 t1 C1 Q6 w/ T, Q
if(match(a,n))
0 M4 v. n4 @/ e2 t! p! O {" f, r" Z# E, {$ |7 ` @. o
 out<<0<<endl;; k3 H! a" L1 D; W7 ]
 s.display();& \. R1 J- l8 [2 s- S
 return 1;6 {, T* `: Y \( X- I) G6 }
}, a1 c5 B/ c1 t' B5 C4 [
do
% D2 M$ [+ L9 A7 @1 N; w- i* @ {
4 Y, a0 L# i. `! [+ v; h if(h%2==0)
$ n$ ?: e u0 s/ B5 S8 N+ `2 E4 v add(a,n,c,k);
4 e P$ U+ g, V9 N6 o, L/ _9 x A else
) o) K# r7 \; v' m add(c,n,a,k);9 c! V+ K- V# \3 P7 ?
 h++;5 a3 ~1 I" x; ?* Z, B0 g; H! Q6 k" D
 if(h>g)0 E; G( c7 E" p. V" P
break;& r* l% x) P2 I4 Z) O7 A
}
9 `6 j6 z X7 X8 A& D0 u3 d while(!match(a,n)&&!match(c,n));3 u3 T8 E- y7 o" L9 c' ^
if(h>g)% B- d+ T& ?5 N; |! x9 |# g2 B
 out<<"No Solution!"<<endl;
; u" y, Z Y' o else0 @1 C- h1 y, S- E" J9 k/ ], D
{
$ }' e6 M/ W5 r" B out<<h<<endl;
- v) O/ T7 X D( n6 c( r if(h%2==0)
/ t- N9 N) i1 }7 |& v3 B s1.change(a,n);& P8 t' g/ @0 l* T" Z5 H
 else
8 e/ }3 w, i8 m8 P& {+ T s1.change(c,n);' l6 {! j9 A; q' [: f
 s1.display();9 q: |& C/ M5 F' l: x; ~/ v
}
. Y, R9 ?2 v$ `/ T N/ W delete[] a;
" b. a& Y. V' U. E; |" t delete[] c;: E( y& V( a: p" ~
// finish=clock();$ a! q1 ]0 X* h" M I( ?
// cout<<finish-start<<endl;# y. M) p. F* k
return 1;: X( V0 U# d3 t+ b! B0 Y
}