回文问题（用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)
# T, f* W: H. a str=p+48;
7 j" \' e* T* v4 i; h+ C else
+ f+ J- e9 u) j4 A) P# e2 Y, G8 L switch(p)
: `+ ?; r7 C* ?1 R- K; f {, s' \4 e1 m, Q& k* C' N" t6 \* v
 case 10: str='A'; break;
) _3 @# s1 j- R F) d7 y$ w case 11: str='B'; break;* {* F | c. T
case 12: str='C'; break;2 Q5 W M( O" }# u
 case 13: str='D'; break;: g* r$ w9 g2 E# N& M. s7 |
case 14: str='E'; break;
6 }! k! ]) p3 n6 n+ |+ v& [ case 15: str='F'; break;
9 e: m3 a; [. B f: Y }
5 ^ p9 U( o9 Y str[n]='\0';
5 H2 I/ U1 B/ _/ m return *this;2 @1 }: T2 i, `( c+ p, z9 T$ b5 g0 h
}
5 Z+ I4 K4 u4 C& j8 Z+ }( F+ Wint String::get()//输入一个字符串8 o. v2 C- P3 B
{
+ x' ^% c$ ^4 m( m6 a char tmp[40000];
 |/ }8 g+ _0 \ D$ ]; L in>>tmp;
! A1 f6 D3 \3 U+ b1 M8 | delete[] str;& \9 v3 C( m- e/ Y2 X: r3 q, ]
size=strlen(tmp)+1;
5 w* U3 {. U( K5 ~7 P str=new char[size];6 P1 G6 P# _3 j2 _- T
if(str==0)
1 u) Q- b! N2 \ throw "error";; Y |" }8 G# \4 \( H' s
strcpy(str,tmp);
7 \ V& Q& s% `$ R9 V1 R5 t* n, B return size-1;
8 ~) {* e6 }9 K9 k1 L2 N}( q* n, G: @( y/ e9 _
<>void String::get(int *p)//将字符串改成整型数组
7 V: J+ E. C- x& U{
+ ? c7 ]$ a, w) N7 m1 k2 _ int i,j;
, C; j- V/ T% e/ }! m for(i=0,j=size-2;j>=0;i++,j--)
" \( l" R/ r8 I6 }* G# d5 C/ ? if(str[j]>='0'&&str[j]<='9')
1 }' _' ^9 n( U( v! N( _0 y p=str[j]-48;
) ]" \( p+ ]: T3 g2 f1 P else
5 u% y* t( F1 T' L t1 |; u {
( a( k' ?' r/ ~# F switch(str[j])
8 _2 B, R1 V/ w5 L0 N6 j1 ~2 [ {! e" |2 b* ]3 _9 D A& ~' ?7 _
 case 'A': p=10; break;
: M% y, m6 B4 g) c9 | case 'B': p=11; break;
/ b% i: `6 W2 H, k case 'C': p=12; break;
% t4 t1 c" w, x8 {4 \* u; O case 'D': p=13; break;
6 k" p8 M2 M8 F case 'E': p=14; break;; S; O, T% S) Z2 o
case 'F': p=15; break;" c( R/ m4 G! t( W
}
: X* E$ ]$ p0 Z }
$ O6 a$ R+ i$ K$ x! Z" A' J}
) G/ S6 s5 M% H& o. Z" X<>void add(int *p,int &m,int *c,int k)//将一个数同其倒置数相加
' I7 L$ C/ l* U1 l2 [5 n$ u{7 W8 t9 v' z4 C
int i,j,a=0;
& t _* _1 `; b& `& z; D) J for(j=m-1,i=0;j>=0 && i<m;j--,i++)3 h& Y* m i& r+ A! o* |. D- e
{
* M8 l( N( [* q- R: U; c c=p+p[j]+a; n$ j. a9 j D1 x% l
 a=0;
- n( x" ]/ Y. X- a4 \ if(c>=k)
7 t' f: P0 J" k; Q {) N$ N1 i! P. P5 x1 P2 A! d
a=c/k;5 E4 j0 h2 Z2 s9 J& W* I
c=c%k;. e V/ j6 a% m. G8 d( [2 }
 }7 G& |. _0 `" ]' `
} " d/ I5 x$ `" V8 i
if(a!=0)
- ~# f) B; W# J. ]% N( d: I; ` {
* T6 s) x2 F( _ c=a;
 F/ ]% H6 l3 H( x m++;
5 f) {0 U: U8 a% n0 G& T! I }
, l# \8 Q. H. k! b& ]}8 d0 E6 e/ |3 h% ]
<>bool match(int *a,int n)//判断是否为回文数
" k K+ r" b/ t2 o- T{" b9 w$ u# O9 s7 ?. i4 F) `/ `, g
int i,j,h=0;+ f7 v8 A$ t7 \; A& m0 n& H2 p/ x: J
for(i=0,j=n-1;i<=n/2 && j>=n/2;i++,j--) q' b" H. z# f' T
{# K- W" M$ y' h- F' O% V& {
 if(a==a[j])
& U. X% T2 U9 M- X6 b continue;4 s& V/ A/ Z! _# T
 h=1;0 j4 P, | j8 j6 H- L
 break;
( a/ N& l9 x+ ? }6 w% k' }% T5 S' V2 k
if(h==0)
' e/ b7 V/ ~- B/ O' I return true;
& j1 M& z5 g( \1 X; t2 Q0 K( C else
7 z. g. s6 o: _4 c8 q& i! [ return false;
 _. A& H: m% @% C- W* E4 g}
& f2 G" ]8 s! }& D//clock_t start,finish;
% V. O2 ?9 D$ r% s: V8 s5 k" Zint main()
# y7 f+ `& q+ Q. I$ M1 ^{//start=clock();
/ O/ i, N& j5 z4 S0 q4 @: k if(in.fail())
3 M" ?) K+ V4 t {
7 B3 g& D: O6 I* T0 R! F) ^ cout<<"the input.txt is not exist!";7 q4 N# t2 R6 Y8 n- G
 exit(1);- f% u1 L: [* F* ]5 \
}
" I* T# V C$ c+ L String s,s1;
& k$ H' p3 T0 C8 k, M! L/ ~: H! l. q int n,g,k,*a,*c,m,h=0;9 U |) _' S0 O9 Z
in>>k>>g;
: |* L& t8 ]+ H s! } s.get();
: _/ {+ H3 f) t" g
3 K4 l* V/ v6 A7 N9 ~5 e n=s.length();6 _4 {% W, s# O$ u6 U0 o
m=n+g+1;
. C+ [# I1 v5 l6 u. c8 g a=new int[m];
: R/ Y4 g+ x, e0 S9 x c=new int[m];( h6 x0 d, u' \ q: A. \3 r
s.get(a);
. |; Y2 T; t8 i* j if(match(a,n))
2 O$ y, c# o! z! l* l- x {$ L0 _+ v+ O2 | o5 ^
 out<<0<<endl;6 ]' R6 z5 g9 ]8 r/ c. D
 s.display();: e. b6 ]# h+ V6 B1 R9 d, M) p
 return 1;
" H* ?- [; z) p+ i }
; I3 k6 K& s. l7 F8 P5 [ do
/ a- y. U% h/ o, l {2 q9 x0 @- D- J2 ?
 if(h%2==0), Z6 e% U- U/ j5 p2 V( Z
 add(a,n,c,k);
/ U8 t8 z9 X& H else2 U O& Z( Z; }. l
add(c,n,a,k);
/ [( F: N8 g* Y2 Q& X h++;! a) J# p6 d8 B+ ?5 ~
 if(h>g)5 k0 L _; i7 l- `6 i) v$ u
break;
: ^* H/ j2 J6 p6 s }) J8 D0 A0 P# L+ Y/ t
while(!match(a,n)&&!match(c,n));6 a5 d+ I' D- ~
if(h>g)
+ f& z' K4 A1 v& Z& b out<<"No Solution!"<<endl;# O- \) n- Z+ i. r5 t0 q
else: A3 c! j' g+ h. s3 {
{
: \' X" P& ?- p! @ out<<h<<endl;! g9 f/ F2 f& L: `/ V, U
 if(h%2==0)
- p8 G* B4 Q: | s1.change(a,n);; |$ B' l3 j' \5 [8 J* a+ b
 else
* D& K, [6 y f5 d2 o s1.change(c,n);' @ i5 Y4 | X$ i7 E
 s1.display();
* i% ?" d/ D& q ^! O0 C }: I" d0 w7 R5 b9 l* u$ [* v) e+ K
delete[] a;
8 m7 K" l: K. m5 N delete[] c;
' q0 H! b& t( N4 W# C5 M// finish=clock();
2 w8 N& p1 a& e, z' e4 r// cout<<finish-start<<endl;
7 Y* m7 U$ J8 c8 A! T return 1;" ^, I: x/ Z/ r. \
}