回文问题（用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)1 E" A2 N8 b7 j4 M0 U" ]$ ]0 D- q
str=p+48;
$ u. I4 y3 l/ s& _$ H$ o else
. _& H% e# c6 _( S9 e switch(p); `, |% w" x2 L$ Y7 |$ _+ q
{- [$ r: e! u6 E8 B4 h' Q
 case 10: str='A'; break;
& `) t" i- P7 g: ]$ } case 11: str='B'; break;5 d+ b" Y; Z! H. }" D, e* ^
case 12: str='C'; break;
# o4 ^* Z6 G$ R: E case 13: str='D'; break;: q/ v( x) d' d/ n) I
case 14: str='E'; break;4 z/ @ p3 B* _& L6 K2 u
case 15: str='F'; break;
/ X, n$ I. o2 h5 @( ` }
6 w2 c" E# q! E+ \) A str[n]='\0';
9 z3 ?& r8 g1 G$ m+ f- j return *this;
, w- z+ [! O- U& K}4 ^, A) K3 Y L1 u6 U% {
int String::get()//输入一个字符串5 K2 [: O/ P" J* ?0 P7 n, s
{7 t7 p5 @2 Z# S0 G+ K
char tmp[40000];
in>>tmp;" M/ f: U# U+ ^. I$ Y
delete[] str;+ d* {" g" @9 ]; l# }7 }2 R
size=strlen(tmp)+1;
# x0 L9 |. i+ w1 y str=new char[size];
6 A3 j# Q3 |/ x) V& ?6 z; J' u if(str==0). \% O1 |/ h/ E; Q5 Y6 h
 throw "error";
; \5 A' a& g2 C; H4 S; ]/ g strcpy(str,tmp);6 J K- M5 n% R1 \1 Z$ p# Y- {
return size-1;
 c3 j3 |9 _( S h2 j# @}' f- Q; v! O' G+ p' ]
<>void String::get(int *p)//将字符串改成整型数组2 V: S2 G0 L6 _6 k$ h1 [
{3 T0 c. H/ A" o( O4 a$ O
int i,j;6 |! J6 v7 Y1 N5 [6 M# [
for(i=0,j=size-2;j>=0;i++,j--)
& N$ U/ x* l7 ]# f3 ^& V5 j if(str[j]>='0'&&str[j]<='9')4 b2 y3 J6 o6 C
 p=str[j]-48;; G4 t, G% e" U+ `! S4 G
 else
+ i3 F' \$ Q" B2 R- P2 M+ u$ ~ {: ]$ K) U% C3 k
switch(str[j])
6 I8 y4 S, L- S. {7 C {
5 {, X4 p6 o6 a" E- A8 t case 'A': p=10; break;# s# s2 A; l: \+ W( Y% D& ?. t( f2 q
case 'B': p=11; break;
 a$ z u- G! P3 O, \ case 'C': p=12; break;
6 h+ P: d$ W2 W5 _& M% D& M case 'D': p=13; break;
& U! ]' M" `1 s) _& }9 N9 R case 'E': p=14; break;" @7 t7 Z, g' |. }
case 'F': p=15; break;. m2 ^8 V) o3 P1 K2 C1 N
}$ d7 p1 u6 o: A( o, F; ]
 }1 Y# l! e9 B0 o4 H( C: B. t% p2 y
}
, ]" `& J' w- l- {6 D. Z<>void add(int *p,int &m,int *c,int k)//将一个数同其倒置数相加: C* Q5 K7 C6 t2 [, J+ Q$ X7 R
{
 i" k s' ~8 a# y3 W" y int i,j,a=0;
4 I5 H2 \9 ~# M0 }( w for(j=m-1,i=0;j>=0 && i<m;j--,i++)
0 s& q7 U2 z1 a1 g" _ {
$ w# J+ _3 b% i2 u3 [0 W9 K4 e2 c c=p+p[j]+a;
$ T- I: z; v8 W$ Z) r$ }" v7 q a=0;
8 p( z3 J1 I: _+ z" ?' [0 t if(c>=k)
" Q6 q$ h' ?" o1 L8 T) i- X {! N- `8 S1 o$ Z
a=c/k;
( E _, `( t7 t9 j0 Z# K1 k c=c%k;
 O! u, n1 T6 j, T$ k }2 k7 t$ M/ r, D. ]
} . z. u! t* _2 Q# b# t2 u, A- q
if(a!=0)1 W3 w; s) D8 k0 |0 x, @
{/ `1 H+ R2 n* `7 p# Y$ C$ Q: Z
 c=a;
, G ?$ j" b7 M# B7 G1 n m++;
4 m+ h T P! s8 N U3 s' D }
7 ]/ ^, L2 _8 G; Y; m}
+ o+ J/ R; ]( E! ?6 u5 V; ^<>bool match(int *a,int n)//判断是否为回文数
# m4 B9 V2 g+ P& {0 }{
; q" n. ]+ }2 C# Y7 W6 U; M+ V int i,j,h=0;
: g& F8 X: v9 \% V% L for(i=0,j=n-1;i<=n/2 && j>=n/2;i++,j--)
* p' Q( T ~* q. f {
6 T4 V* o4 b3 N9 W1 E if(a==a[j])/ L" m% E, ~7 ^
continue;
# I! ^- v5 M( Y0 q& g4 H1 n# S h=1;, m9 B/ K$ B8 Y0 i
 break;
7 i) k: r% U5 Z9 G3 A }/ c; S, Y5 r) v
if(h==0)
$ B' m' [, z& o% J7 C* X0 H return true;
: C4 _+ ~; b1 F) e" c5 e3 b else
6 ?8 o' t0 ~. Y# i! t return false;
) B0 P7 e3 o# o- i}
# ~5 l4 p% n; ^5 x, d& ]//clock_t start,finish;' _% c' T9 }/ q0 O3 m# `$ A
int main()3 j4 f1 H0 a2 j5 c# a, d& p8 |" O
{//start=clock();# V) L) j- y4 v
if(in.fail())
8 n% G H1 i) s" q2 x, t {
8 Z! f) z/ [4 a cout<<"the input.txt is not exist!";+ p/ J* @& q1 \7 ~1 Y, ^ x
 exit(1);
5 }$ r* ~( T D }5 z+ Y/ p0 X* P. K: q4 N
String s,s1;- O% X3 Z3 M( N4 S9 Z0 I) B- O% v
int n,g,k,*a,*c,m,h=0;
- }0 q7 {! q0 n7 N- c( m7 F* v2 H3 r in>>k>>g;
9 [) S( h) l2 V; Y0 y' @7 A" F s.get();$ @# v: X: p, w0 [9 Y% I! c

7 \+ }* \) u. [8 ~7 u; I n=s.length();' D8 v$ c5 B$ w4 G
m=n+g+1;
1 }4 X4 M) W& F, X% _9 U a=new int[m];2 F! p7 f! o# Y- h* u; {1 O
c=new int[m];2 Q" {) I2 f8 }. k
s.get(a);/ e6 k& S D) k' P
if(match(a,n)) t; J8 a$ P4 p* h: F4 Q7 R" u( w7 H1 T
{* n% e" Y2 i1 H% }
 out<<0<<endl;% ^2 p3 _( @3 V% ?, F7 c3 A2 p a
 s.display();
# t P, u, u/ e: l' m" D; b return 1; H8 D$ c: [; D n
}/ i$ x, b2 c9 R: d5 m- x }( h; t
do
( ]# b4 X' x2 k4 V, t' j {
( Z* e5 j" ]" C0 t" e6 j# A$ m if(h%2==0)* p5 a* T3 u7 a" {
 add(a,n,c,k);
! _4 y8 z: t0 m6 C: e P1 r: V else
; w" h/ {' Y" v( C7 r* @& m add(c,n,a,k);
2 J+ f- z! T" V h++;; [8 z3 D+ b. [! r+ ^3 ~' M6 O- T
 if(h>g)2 {: R6 t1 r! L# o; f8 `! B
break;
8 w k5 h9 |! W) f( z5 f l }' U2 s$ }* l: o! v3 j( `; g
while(!match(a,n)&&!match(c,n));
6 C; u% }; k# W! h) |7 B3 ? if(h>g)% D: o& q- |$ W
 out<<"No Solution!"<<endl;# |) ^/ T O0 T! S0 A
else% ] s3 T I: e3 p! T
{$ m3 ]1 C) a4 y5 [8 q2 k0 q+ h
 out<<h<<endl;& b0 v" G# H: z
 if(h%2==0)6 f. m8 b$ O z; Z8 D& A
 s1.change(a,n);$ C# Z0 S/ p9 |! A/ h# I# u
 else
$ V7 Y% [5 k- ? u s1.change(c,n);, {) P( n* ]$ Z6 k0 @! D- e6 H, q
 s1.display();
: H# P- a a1 d2 {! ^" M. X6 U }
' I% a# ^# l2 q+ Y! P& ^ delete[] a;
3 c+ K |2 u: o* D delete[] c;) [: T" [% W2 S4 _! v4 Y
// finish=clock();
( h$ h' G3 U. ~" v' I( P// cout<<finish-start<<endl;. `" d* P6 x1 _5 P
return 1;
* ?+ E6 V W- J* g5 _# L}