回文问题（用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)
8 D1 r* r7 r- G/ m: x6 K str=p+48;
- M$ |3 D" n# p5 Q3 C else
/ t; K5 j, V( P6 k/ P9 @, X switch(p)
8 c+ L$ j. i+ v8 P4 [8 M6 `* U" F {! z5 e! J6 d3 S2 t5 r
 case 10: str='A'; break;
! _1 ?9 l( `5 ?* E; y case 11: str='B'; break;
" y; ^9 H5 N. M9 F+ a- T! i3 ^ case 12: str='C'; break;2 X2 c: a8 \( p: S* b7 d
 case 13: str='D'; break;' l; l8 j( Y& f, g" v2 S& T
case 14: str='E'; break;
3 l0 X" M! y8 A, n: n7 z case 15: str='F'; break;
2 H8 s* M) X7 ?" B }- Z9 s; T1 T8 o' W$ {" e
 str[n]='\0';' b) a/ y- h' I8 }- N8 G9 j$ I
 return *this;) t& U, N8 g: Z. W" P: I
}1 {( K0 ^4 a' }4 A) r0 v( M. r; s
int String::get()//输入一个字符串1 \4 _: ]% v9 N' k
{
& V3 k3 X7 ?" G2 a char tmp[40000];
% r+ \9 u z9 {3 y in>>tmp;
; B( T6 |* e7 }. R K7 Y6 F3 P* g delete[] str; n, B' H9 `& H" P4 B! k T
size=strlen(tmp)+1;
4 a/ u9 J X' u1 K+ Z1 m! y str=new char[size];& {5 d7 i* b% o: ~ c1 J
if(str==0), V! ?1 f) `1 }0 C7 X6 ]% D
 throw "error";
+ A6 @7 i P6 Z5 X strcpy(str,tmp);( j4 I8 C/ T( d
return size-1;
0 _" F) A6 w, f0 {}1 \9 r u0 z4 {$ R6 J/ E1 p7 B
<>void String::get(int *p)//将字符串改成整型数组6 P3 B, E9 { ^1 o
{
- g) c; P- o h5 `7 \- Z1 l2 c int i,j;
8 U/ k& ?9 h: ?! g: } for(i=0,j=size-2;j>=0;i++,j--)) K1 ~) t% `- q% d
 if(str[j]>='0'&&str[j]<='9')% G7 P u# Z9 X9 ^5 }/ i
 p=str[j]-48;
' R1 {, e" P6 e0 B6 X a3 f! f else
! r4 v. S( ^' O7 T2 ] {
/ @; }- o6 Z! L+ A5 ^! V switch(str[j])
+ m; R c6 [6 }4 E* ` {
# \7 S( g8 a+ m, m0 n case 'A': p=10; break;+ N4 i8 r# o7 S2 I2 e3 n
case 'B': p=11; break;
( Z% q' g2 `6 { case 'C': p=12; break;! m) `3 Q8 [# s+ T+ o8 V
 case 'D': p=13; break;
case 'E': p=14; break;
 | Q0 F. G. B/ ` case 'F': p=15; break;
# F2 ?1 J/ G* i1 H4 ]+ Z }
' D) q/ F. G2 {9 s9 J- ?( |2 N }# U7 x$ I& i* }. O3 ^) t7 O
}& f3 C0 Q, W) m3 z0 P1 W+ U
<>void add(int *p,int &m,int *c,int k)//将一个数同其倒置数相加
8 p5 h& W T# p' Z& H' J1 Q{
$ l4 [! Q* Y5 H/ Q# c) [8 } int i,j,a=0;+ ?, \4 R! h& w1 s6 ^+ V
for(j=m-1,i=0;j>=0 && i<m;j--,i++). x B5 L/ B y1 @' g8 F
{
1 ~- J: e" z0 u$ s c=p+p[j]+a;2 T( `4 Q# [+ E
 a=0;
% P. {' k. P& J# B4 ~. c if(c>=k)+ ^6 z. u! T2 |7 y+ S$ s
 {, U* i9 P; |! w" j* X
a=c/k;& p. P2 E4 L! ]. k6 L
c=c%k;9 z7 y, P& K5 @/ ~7 x* M! L R3 t
 }. Q+ d4 u% z8 i% Y3 \) @. h
}
1 l$ I8 \+ l7 u4 K4 e8 S if(a!=0)
4 h% H7 u* J0 x {
5 }4 z |6 G1 Q1 ]5 t# j; i c=a;# `% Z( l! l4 E9 X# {
 m++;# K9 Y+ P3 @2 ]
}
1 y9 I2 t/ z5 i, Q8 n: L}: j- n) j, f( l. R
<>bool match(int *a,int n)//判断是否为回文数
. F R, J2 O1 ^/ V{
! x% ^ D% d* A# o int i,j,h=0; d* Z& V3 D+ R
for(i=0,j=n-1;i<=n/2 && j>=n/2;i++,j--)
{
/ L8 `) t' |" x& G# P if(a==a[j])
# O6 h& E c7 a+ M continue;
. a* z% b+ ^$ c0 R9 s h=1;% Q. Z5 f# p9 W7 ]. k
 break;
4 ?2 Y* X5 |6 H7 U6 k }" Z2 y7 W% a* p- r2 p8 p. q3 M
if(h==0)7 b: D. @' h# k0 R! P
 return true;3 p4 s8 F0 N( S P7 s
else 8 z" o* [1 m( F% F/ F7 e
 return false;
8 R. I X( v7 ?, w* J}) J) e4 V$ J- |9 y
//clock_t start,finish;4 { ]' P% h' q0 V7 Y/ D i
int main()
& \, N' J8 z! L: Z( B5 V{//start=clock();
9 E `; ]& d* X8 w if(in.fail())
9 o& r# ?7 p3 d6 I8 Y( V {+ o& b4 Z. u8 Q. h) c& R' s
 cout<<"the input.txt is not exist!";
/ l! K L" b' c/ {& Q# z exit(1);, c% C) h$ G4 ^. z! f X
} `7 r/ n5 ~0 {1 V+ Q( h
String s,s1;
7 P# @4 Y9 |# t: \ int n,g,k,*a,*c,m,h=0;: f# p. k' Y: j e0 H& L+ s
in>>k>>g;
- ~6 Y# {. d1 s" i s.get();
# x6 H9 G" ` G9 V1 G# f: d% K ; {! i/ Y4 E' G7 [
n=s.length(); N4 d* v6 S* T1 K0 s4 G' q
m=n+g+1;' y% X" K: U0 T# m& H
a=new int[m];
! r' D, E* b7 ]6 d' K5 V c=new int[m]; m, w. K( x1 b' \ z
s.get(a);
' K H8 }4 B: s if(match(a,n))
2 ?) L {9 p/ q" K# o2 q {4 G1 J9 v5 C9 u# X8 p- Q# x
 out<<0<<endl;
# A% u2 M) A \; `1 L# S s.display();6 h7 Q( O- p) G1 Z' u3 F
 return 1;
0 u2 P' f0 H6 E3 v6 k# i6 r' g }
- Q9 H6 K7 _0 z: I3 B$ B do; s, c0 G9 s z- y O3 a
{
* ~ h) Q' e8 ~: n, _ if(h%2==0)
 }; ?! K, \ b! ] add(a,n,c,k);% T* `" c- z5 }2 g9 o- F
 else
' p$ w+ R; `+ @+ u+ N M0 R add(c,n,a,k);
$ x9 B4 O- Y& V0 X2 Z% F2 P9 J# ? h++;' R. P- v) S* a, Y5 |# L/ N9 D
 if(h>g)
# t& N9 i9 K7 r% f& m2 G" Q2 w break;$ h( D4 V4 z8 \- L& u, w. ^0 S7 ~, ]0 r
}
& L! G8 g- E' e while(!match(a,n)&&!match(c,n));
. s a2 w c1 p, M; h if(h>g)
, w! V) i8 T+ Q- d1 g, N out<<"No Solution!"<<endl;
/ w9 C8 g% x5 I# ~+ b else+ F2 Y( ]7 `5 D1 F9 J& I% @
{; |* d4 x1 k- D
 out<<h<<endl;
- n! q0 ]% i0 y; Y) Q if(h%2==0)
4 W+ G+ Y& b+ ^9 \! e0 M/ x2 \: G s1.change(a,n);9 E/ H( V" |, I, r2 K
 else
- {9 e+ s' l3 h5 f, X- e s1.change(c,n);6 Z2 M o! F, X
 s1.display();
+ y9 g N+ A+ _" L }! W1 X3 ]$ D; S; X! P
delete[] a;
; T/ v- `1 |- r9 \5 r delete[] c;
& M) `7 s9 D. J% E. e# a// finish=clock();
7 B! v5 E# O( z3 |) y, z// cout<<finish-start<<endl; t& e( L7 }4 ^4 M1 \
return 1;
' ?* J/ |9 q# Y2 r% D}