回文问题（用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)
4 d6 p: e$ z1 B8 V; X$ x) w str=p+48;
" I# B2 j& x: B, H F) T( H" ` else
* a* X. D# G z( h u3 c switch(p)
( f0 k4 y, \- c$ i/ s4 @2 G; |( w9 K- y {' } h$ y/ ?" x/ O9 O0 }
 case 10: str='A'; break;
; z! h N+ A) b+ u! K! x1 x case 11: str='B'; break;6 `; _6 Q; n$ ?( q7 V! T/ N6 L1 w# w
case 12: str='C'; break;" t: J, g7 b. t5 J; j% J# D
 case 13: str='D'; break;! E; i9 ~8 a; I# Y9 |# K
case 14: str='E'; break;0 k# W7 R- T2 E/ ?; I) ]8 P' m( B1 q
case 15: str='F'; break;# K, Y/ ^2 ~" b- K7 D. y
}5 T, x3 _% w: | N
 str[n]='\0';# ?+ d! v3 n; Z2 ~6 B) w
 return *this;
/ a% E2 m* T9 R) n* M. j& N4 `}9 {3 y% D3 e& c2 d: G( k" A
int String::get()//输入一个字符串8 n9 Q/ H- Y: W
{# o0 b5 n' F8 r0 j6 _7 U5 i# |8 R9 c
char tmp[40000];+ g* `9 f3 W6 k3 y1 Y1 x
in>>tmp;1 \, a0 s* l" B9 B) L8 b
delete[] str;
7 |- o' Q2 s" `" y5 o size=strlen(tmp)+1;$ n2 o: Y- l. v7 t- Z
str=new char[size];# Y1 s0 Q" `, N8 E1 T, c% X! z
if(str==0)* m0 S, R+ Q& i, E, |$ R
 throw "error";
" g z, U1 ~) ?0 f& v; m strcpy(str,tmp);
5 R9 ]$ f$ F+ u6 k9 L0 S return size-1;& Q% a: i' _$ K# W
}$ t/ E$ O* Z8 a" G
<>void String::get(int *p)//将字符串改成整型数组
3 V5 G) L- S+ \ l2 w' R1 Z8 ~9 O{4 \; |) I# l& a) p8 x+ e4 C
int i,j;5 [ `" ?( g$ G! D9 @. B3 ]
for(i=0,j=size-2;j>=0;i++,j--)
 ~% U: L Z2 d& C8 W if(str[j]>='0'&&str[j]<='9')" _" C- K. [1 r- T1 |8 C+ R" \
 p=str[j]-48;
9 |9 Q y( M, E4 g6 P- q. x/ j else& W+ l/ U, L0 @9 a4 ~
 {
6 O5 o: j; Q5 }6 B3 H switch(str[j])' v& K! M. a2 _% i
{
% f( w' z' Y" Y, y case 'A': p=10; break;: T7 V2 B: t- y
case 'B': p=11; break;- O3 _4 Y; U G8 j l. @( H& w5 M4 P
case 'C': p=12; break;$ M/ a1 T/ G8 Q# O" i0 ]
 case 'D': p=13; break;+ \& f' e' ^: u# n2 b
case 'E': p=14; break;% J# `8 F. C7 @
case 'F': p=15; break;
8 q& ?$ Q" x9 b. V% p }4 B6 t$ j# c' ]* K& i1 q; `
 }
0 c0 k& I/ {6 |4 g}
. [0 w' n9 m! d# l<>void add(int *p,int &m,int *c,int k)//将一个数同其倒置数相加
/ N9 z/ F9 p5 L$ i* E. F{; m. D; [' b3 l4 f5 h
int i,j,a=0;3 W8 Q( D/ }9 y* s1 t1 k9 [9 y. K
for(j=m-1,i=0;j>=0 && i<m;j--,i++)
: O5 Q' k- \2 r# S {8 F. j! ~8 g1 B7 k+ W @9 o4 U+ O# U5 Q
 c=p+p[j]+a;
) `) l5 q& M0 C& X. F- Z6 ^) k5 u a=0;
 L# T$ i, A) L if(c>=k)
3 m# L, O0 c) ` {
& E z( {0 \, p2 F& N7 X a=c/k;; X; R7 k" k6 t! t) v/ {& E
c=c%k;1 _0 c { U5 V0 H; n
 }
- x" Y6 X8 R* F9 x Q. m# T } ; a, z1 b! ~: ^
if(a!=0)
* k" i) A; ~; u: V3 [ V- T {/ y# J" `3 U: O8 g, U
 c=a;0 s3 @! n3 j Y5 X" t5 g4 E
 m++;
& T0 N8 O+ ^8 u9 W& R& { }
% M% G# ]5 B) F q' c# x}/ y1 `) n x0 i+ p: U
<>bool match(int *a,int n)//判断是否为回文数
# }! a5 d1 b; [/ ^7 k{$ `( [1 i" @- v
int i,j,h=0;0 J) n; U! n+ r' S* m( B
for(i=0,j=n-1;i<=n/2 && j>=n/2;i++,j--); z. y _$ @1 d! T# O
{" @2 u; N& K2 N- ^) ~$ v L
 if(a==a[j])
" X6 h5 y* R3 N/ n! u) G# l. L continue;
. `- A; g, z* ^7 n+ @7 y7 q h=1;' h% q, D) R ]. E3 D; R# w: i4 F
 break;# Q2 ?: Q( l0 f
}2 W# W- ]% b0 }: i1 H7 e6 e
if(h==0)
; F7 V: A# L/ Y2 K$ @+ A+ f) B) J return true;2 |+ n; J* U( ~4 [. L) I/ I
else 5 ?& U' j. b5 [/ E6 `
 return false;3 A2 u) W% |' v) [
} R6 g" k: }3 q$ k3 V# u" y
//clock_t start,finish;) n2 v! x0 X& d. |8 b! P% K; o
int main()( \, Q' W7 e9 k8 f4 x+ K2 [
{//start=clock();+ x1 A9 z/ u; c' `
if(in.fail())/ Y: J( w* [, i# N9 y+ k
{- z7 l+ `$ ^' _' g$ b
 cout<<"the input.txt is not exist!";+ H) z2 S# Q# \3 Q
 exit(1);
% x( Q5 P% ~. U: k }
& Y) E" u0 }! A2 u- q String s,s1;3 [$ X0 O* I# l+ j; A6 Z7 z- O
int n,g,k,*a,*c,m,h=0;
) |3 r2 ]- O! M5 u/ b in>>k>>g; 5 M) j4 U4 b/ u0 X9 g
s.get();
: N% r; g+ {7 ]$ ~$ i, w
) y- k, H) E9 U) E( L) O ]7 O4 m. O n=s.length();7 W. n$ P( z6 ~( a
m=n+g+1; {' o' ^3 A# \
a=new int[m];7 B6 Y. b: y5 o$ i% H9 G, g8 ?; N
c=new int[m];
1 O/ W9 f3 J4 p0 L8 O' E+ O s.get(a);
$ R- I$ j/ h! p/ S- G( | O* m if(match(a,n))2 o! g4 L* ]! O2 L2 p% ^" U4 Y: z+ Y8 ^
{9 e2 N. z" E- C3 W* i# V
 out<<0<<endl;: ^$ ~! \1 j2 ?
 s.display();
; @9 |4 K- g: C$ d, ^) Z return 1;) l8 T4 o( }5 Y2 o
}
: {% Z; l. O' B" c, @# F5 k" P+ A; f7 N do. s4 U5 w- q% J
{/ y! i9 p( Q/ A) N1 G4 |
 if(h%2==0)+ h( v' U% c, k! |' H; N
 add(a,n,c,k);& Z; E- T! B* }- }
 else
' N5 }% |$ @4 F @ add(c,n,a,k);
" n! m0 l5 d' p5 ~5 X h++;
: B! w }' i: s& @ if(h>g)
" z" w2 c1 w3 J8 b1 y" g break;; H9 a. |# F2 e$ w, K* U8 y0 E% c8 N7 H
}9 h$ @/ i0 W: @& J+ \- |$ o+ `
while(!match(a,n)&&!match(c,n));
' T6 L2 z a1 u$ r0 z* ~ if(h>g)
4 A% Z5 |6 F1 p$ |* r3 Z out<<"No Solution!"<<endl;
. ~" v/ D0 A E/ ?2 L else) ~! g# n5 H$ V) R8 @5 S7 j
{
: B" P2 _2 s) v) ^ out<<h<<endl;& k3 `7 H) u3 N* K* v0 J' @
 if(h%2==0)5 f h1 q4 k7 g8 F
 s1.change(a,n);9 t0 c; H1 A6 X8 ~$ \
 else
" g1 j) \& [( X s1.change(c,n);
6 R+ N0 k( r( k, @' u1 p; X* _0 ] s1.display();, _( W) G9 D1 P' R' Z d4 N2 M+ y
}
( X: }/ V. n- G z# E8 @3 o- A delete[] a;
2 T% w/ i8 Z: Q; P0 v; } delete[] c;# M# n3 P* F% u0 r; D0 ?
// finish=clock();
% C" ?7 P! r8 O" s7 h% C// cout<<finish-start<<endl;
7 P( l! ^ b) I return 1;
; m7 _: |& I- p) R; v8 a}