回文问题（用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)
7 ~) J! `' d! a' h( m6 v8 ~ str=p+48;
2 _0 p. n+ F9 X! P7 E else
) s/ T2 N6 ~ k: h2 O% U* W; l7 q switch(p)4 ^! Y. p9 w9 y) F+ K; | H+ [( D
{- C( U$ g, H& c5 u% a7 |; U, B. a
 case 10: str='A'; break;
. Q3 c8 W- a* Y case 11: str='B'; break;
* i; J% j9 h- l+ ~ case 12: str='C'; break;2 j% x+ V4 y3 q% M' k; K- ?" k
 case 13: str='D'; break;8 D2 F) v1 \( k; e4 D8 F
case 14: str='E'; break;
& p7 u: Z m9 P+ E case 15: str='F'; break;
3 z% ~* h2 K# v* t3 Z! z }
. X8 k8 q* a5 y1 h str[n]='\0';
" x! L V; g, V$ U, q; B return *this;9 Q3 u4 ?# x1 z( I# `
}0 |" R/ x7 F c; i9 x) T9 e
int String::get()//输入一个字符串$ C" r0 a$ {0 _2 o
{
1 G9 m! e! B7 V/ Q% F7 W- {2 g char tmp[40000];
' G8 W, S5 z( ~% |$ B in>>tmp;& z! x8 O4 R: z% x0 ~
delete[] str;
, y9 g+ E7 z) Y, P size=strlen(tmp)+1;
# K0 j l% S1 t2 w& p0 `% T str=new char[size];! d3 h( i) g8 N3 S, j" z7 D8 s. x) a, @
if(str==0)
6 O: t3 i# a$ P throw "error";
% s5 o8 d; N. \7 M' b strcpy(str,tmp);
' g9 U, V+ R$ S# _1 a5 {+ C: s return size-1;( R, b( {% b3 K( a' w* Z7 y
}* n2 b5 a' `. d) ?8 @5 E6 v4 q4 t
<>void String::get(int *p)//将字符串改成整型数组& V/ S9 h. q% G( ^+ X; T
{
' v" ?8 i& I7 C6 n9 X% m int i,j;; }3 j4 z( R4 h5 N
for(i=0,j=size-2;j>=0;i++,j--)
$ d2 f8 X5 }* K; E5 x. P4 _- J+ Q7 n if(str[j]>='0'&&str[j]<='9')& _5 N" h/ S: F
 p=str[j]-48;
' ]+ R4 X# {8 R' l) m else k, P$ Q! W2 `! N4 o
 {
6 w4 i! L: E# `, w2 b; A switch(str[j])
( Q) k# u! r H" P" G {* P# q; F% {% ]7 v' ?
 case 'A': p=10; break;
9 {1 \9 ^4 ^0 J8 h case 'B': p=11; break;
' D6 @8 z6 Q9 V, R case 'C': p=12; break;
 x% x8 c% }6 D! B1 M# _ case 'D': p=13; break;, N# q5 J2 K, ]( X3 R
case 'E': p=14; break;/ U$ J4 s% E: m0 A+ j
case 'F': p=15; break;
" d7 x- e/ [ O- b }5 x- j' G r5 D# {; J3 g
 }
: R- P0 P9 l% ]! k8 e4 O}3 L& B+ ?$ @4 A' [( \
<>void add(int *p,int &m,int *c,int k)//将一个数同其倒置数相加& A1 d5 E/ A0 _
{, \# B! g5 r& {9 |, {) @
int i,j,a=0;
9 r1 [; a v/ g4 X for(j=m-1,i=0;j>=0 && i<m;j--,i++)! L- y( E) M+ p* T
{
( M3 N9 I- r2 ~; c# D5 P c=p+p[j]+a;8 a/ j/ r3 ?# n/ M% S9 t
 a=0;6 p* b- I k" ?5 X
 if(c>=k)
2 n `# E/ p4 @8 r% Y2 e c5 @ {
* q! F7 i2 G- \ a=c/k;8 w& }/ [7 ?& n2 A& k- }
c=c%k;
, w$ S7 @0 i9 W( f }) n# f4 Z) Y z' B0 [- |( T
} , w, }& o4 U, k
if(a!=0)4 ~- H1 T' |! W: S1 v
{: A/ |% w6 K+ N4 r6 y
 c=a;% L: d0 W5 |1 V* v, X# P
 m++;
/ {' y. |/ O. G! y, l; C }
- \6 W# i; G# g}: ~0 R C( m. K, X4 d: Y& [
<>bool match(int *a,int n)//判断是否为回文数) I7 e# r1 X" ` @4 C& Z
{
. P$ }* j2 v# U. @ int i,j,h=0;4 l7 |" l! m4 V5 G* j7 J: m( [ [
for(i=0,j=n-1;i<=n/2 && j>=n/2;i++,j--)7 v- b) x$ P# y2 q" `( r
{+ z6 y/ f v6 p8 H0 [0 {1 |
 if(a==a[j]): k. H3 Y H5 L/ h/ O% S
continue;
( H6 C' f+ j& @" V h=1;& r, L2 g; z; ~+ U: ~
 break;- [# A3 w' d8 Z l. |2 Q
}
4 r& y/ l' V, q u/ E if(h==0)
$ h H- s, h3 {) j! @ return true;- J2 I. |+ L. {2 a2 K
else 4 i! O, Y" b$ M; Y
 return false;0 i0 Y: N' A2 a* _' H
}
% R5 m3 R8 | L+ Y5 ~- u//clock_t start,finish;9 Z- Q' u$ X' I7 B4 J
int main()% t+ ]4 D2 T2 O' Y6 G$ s
{//start=clock();
, a/ R |9 t+ G5 X& q+ @- K( F% h if(in.fail())
3 k% D" L$ ]4 M4 p {' \; h2 G! J& ?
 cout<<"the input.txt is not exist!";
7 x6 Y6 l N! n M exit(1);' f1 b) e4 g6 e
}
. i4 e! C0 Y+ t, g( E) W* e String s,s1;& a: w. b2 u% b4 b% a; J7 r
int n,g,k,*a,*c,m,h=0;
# j) I5 W8 y4 M9 R in>>k>>g;
' L) a5 E1 Y$ Y( w+ p9 D8 z, Q- L" T s.get();
0 b$ \( ?5 M9 e! G. h6 o7 i x
3 a) A0 f7 X* j2 k$ Z n=s.length();; O3 F0 }+ r0 S! i9 H! P8 K
m=n+g+1;
5 g5 x n$ f2 q& D3 w# K$ F, G8 b a=new int[m];2 l" k# S) v2 D
c=new int[m];
7 W7 A" m! d, W+ a0 F: A/ h/ c s.get(a);; w6 A: {8 L5 }
if(match(a,n))
# ^9 |# b0 p8 D6 R; Z0 K {
" F; _' M4 C% L! Z" c out<<0<<endl;
/ g" y, q& q2 ]: j) x) ?- W+ t s.display();
" ]1 p+ t( {/ I) E: g/ V% \ return 1;
3 H% u& B/ u. a% ] j1 A1 S7 M }5 |* ^+ k5 K% l' `( C! z( i
do% V; b, J' D$ j8 g' n% z( J' }
{! E. u% O( ^+ ^) w% \4 M
 if(h%2==0)
" h# M4 @1 D" w n' e7 c add(a,n,c,k);* M6 o' ?, V! U- I6 n0 Y
 else/ u' r% ^# m2 ]5 D \
add(c,n,a,k);
# y8 ?% p% X3 P D2 c h++;
3 I7 v9 U* g# S! v1 R if(h>g)- L& o6 Z8 @. m# n* u9 G- ? T
break;
$ w# ]( ?% j, ~1 V2 N+ g }" \( i* a8 n! o5 u& s* x
while(!match(a,n)&&!match(c,n));
$ }; X6 N, M4 X' _ if(h>g)
0 S8 M+ w8 j {2 T% I+ A) ~# ~6 {" G out<<"No Solution!"<<endl;* ?/ R# I3 j8 ^' ~. s3 Z
else
) O' O: l9 S4 Q4 Y8 E {
! T R+ s: g" [ out<<h<<endl;
1 V! U/ j0 \# z if(h%2==0)
" u2 B; [. }* W Q s1.change(a,n);5 a* m8 a! o& F7 P5 f+ x& u/ O" j4 K
 else" p/ J) L0 m* g" n
 s1.change(c,n);& w9 _2 D1 ~& ]& N
 s1.display();" F ^+ K, q+ d0 c+ x, L
}
) Q ]; c2 d# }& ]: t) i delete[] a;
- `3 [- O2 O a, i delete[] c;
: m* x# q/ W- }; d9 C$ r// finish=clock();
: q6 [) T2 f# ^) Y// cout<<finish-start<<endl; X. @( |: b% ]0 J$ E
return 1;
; _/ H7 f5 w$ ?! s* m- Y+ O}