回文问题（用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)
+ N1 r! v1 H7 j0 H7 H: x str=p+48;/ e8 r3 k7 M+ P! A; m3 `
 else! ^( z2 J% U8 K9 C# S0 |* f- \
switch(p). A! n. |4 j6 r+ m
{
9 D! |6 `) i+ L/ w1 I( U- }5 u case 10: str='A'; break;0 w, \7 M8 U: J/ k, G
case 11: str='B'; break;
1 j0 G" H6 r6 o! t8 O0 `+ i case 12: str='C'; break;0 k4 m9 ^! l& l% N
 case 13: str='D'; break;
3 c9 W- K" R; O8 ^ case 14: str='E'; break;
0 J: F: N: A$ n% J% E5 M case 15: str='F'; break;
! b9 ^! L( K q6 Y7 f }6 U3 b, n s' F9 R5 p4 l
 str[n]='\0';
, A% U( f& k; P, h1 d% i: N return *this;
; u/ N6 [/ P2 F9 C: P. s: f1 }* A; p}
' p& l. O, Y2 xint String::get()//输入一个字符串
3 k+ v% Q" _( y" T) _: T$ T{+ n' X* W5 f- m
char tmp[40000];
2 C4 S3 P2 w1 a: s/ N in>>tmp;2 V/ ~' x$ ~, Q* D( I
delete[] str;
# F! g' ^- e# U) e. T; x: C% E2 o size=strlen(tmp)+1;5 h+ m8 P9 K/ k0 `3 e: k' e& t _ P
str=new char[size];' K+ B& D$ g7 C2 q3 @# F/ T
if(str==0)
5 Q! }2 h, I' F- Q. y1 [2 b throw "error";
7 `% ]9 |5 c9 F: o S strcpy(str,tmp);& _% g3 t6 P# p+ }) r7 w
return size-1;
" j% F% C# r* s' J5 B}8 j- L/ ~3 J" B% ~, \" S7 S
<>void String::get(int *p)//将字符串改成整型数组
& C% A, F* P1 P$ {{
! Q, A7 l5 C! [& @ int i,j;
2 y% b6 `0 E1 f3 N8 `& \1 n1 D5 ^ for(i=0,j=size-2;j>=0;i++,j--)* j, v: P& a* O3 q3 s2 c( Y- u
 if(str[j]>='0'&&str[j]<='9')5 v5 D/ y" w9 @( z+ Y
 p=str[j]-48;. t" @$ e/ O# l) t$ s
 else6 v, t. b9 G( t. b: ?5 z
 {
+ o* Y' ]. p( j* R switch(str[j])
 N2 F& z: ]4 J6 R9 m- n3 N' @* w {
* Q5 o0 u, t( z3 Y7 ~ case 'A': p=10; break;
( S6 K# A: F( q case 'B': p=11; break;
4 b' k; l* Z( s. Z& J" C9 D case 'C': p=12; break;6 W9 D/ R/ s; ?; X
 case 'D': p=13; break;
& H: M' ~: W' _; t. {2 E/ I) { case 'E': p=14; break;
9 ]% |$ S) J* o( f9 \! S case 'F': p=15; break;
3 D* K% w- P- t }9 c) b _0 E( @8 t2 t* u: L6 }: a
 }
2 B- t0 F( x, y6 l$ N, B}) F: _3 {" F& c+ m6 g
<>void add(int *p,int &m,int *c,int k)//将一个数同其倒置数相加* |7 ^1 ^# P2 t( z X
{
/ W; i4 W, l1 p t' R" h int i,j,a=0;2 D6 K0 C# C% h1 `( G
for(j=m-1,i=0;j>=0 && i<m;j--,i++)
" t* n) k) g% i) {) ^" [ {
9 Q5 B! e! ^/ \0 u- } W! y M1 T c=p+p[j]+a;
; U7 h; j& B% y( i0 y) f9 {+ S a=0;
4 D) A2 U9 {5 f$ P; R if(c>=k)
2 l6 B7 L1 R# r4 Y% d$ `3 u {
+ m! a. d, f: H6 q4 N; j+ i+ K a=c/k;
* }3 ~. f7 P. _ c=c%k;& l0 s8 m! N5 ~- o9 p1 R
 }8 b1 G( ~- o: B! ]5 y5 A) c
}
# _3 i( |/ S+ S9 m/ k# o if(a!=0)
, s+ ~- O% j l& H/ U% Q8 m {
! H. a0 I$ _/ w2 C8 w c=a;
4 M8 C& z4 f" M* u. }9 h m++;
6 O; h+ }$ P4 w e* ? }2 d. Y( V. d# V: ^( f0 N8 Z8 l s
}
7 o7 ?# w* |4 j<>bool match(int *a,int n)//判断是否为回文数9 L( o! r# J2 }/ h! L, v
{! q( q& d1 p9 {, |# h1 X7 H
int i,j,h=0;+ ?" B) B* h" a* ~% I
for(i=0,j=n-1;i<=n/2 && j>=n/2;i++,j--)
4 H' S, p; H8 D# Q {' F+ N. [2 \/ \$ u
 if(a==a[j])& f3 |' D4 E9 X0 L8 ]
continue;: I( T+ b8 g. n( x3 U1 _6 V! {: \
 h=1;
% S, |% [+ T% g4 H" f break;
) P: E& n O6 Q. J8 _ }: [2 f& H7 f+ ]; W( G. f Q4 h
if(h==0)
0 K$ j- n0 L) J return true;
8 T: o9 ~3 l: J5 d else
$ h( t0 C4 W3 [ return false;! w* C" F" [2 H* a7 `6 k
}
# T+ T# ]* c5 n6 ]& s4 O- l. V//clock_t start,finish;
9 s; [& \- c$ cint main()
* k9 }4 ^5 T8 y- \" Z{//start=clock();* }3 k9 Z- e: F& H
if(in.fail())
6 I6 Y) Y2 K/ j {# Y8 l0 z( P' q- V& o* C" A' g
 cout<<"the input.txt is not exist!";5 s' K% v0 S: g% j( w% J4 M
 exit(1);& U6 C5 M; z5 j$ [6 R- X! ]
}7 z" _; F; X' K* p) L3 b |
String s,s1;! U* L! D! R& j5 ]2 D1 X
int n,g,k,*a,*c,m,h=0;
1 _8 _: B- q( [; Z+ ^. L in>>k>>g;
" O, x% l/ ]0 B8 [, i! q! P6 o s.get();
2 f0 L% i0 h( v6 J( f % x) o+ k3 j) c, n4 Q- @) l/ S
n=s.length();
6 w( g6 A, {: e4 A m=n+g+1;
7 U/ f5 t4 Y2 q/ o$ R5 _+ v a=new int[m];
 S6 t4 o4 w2 Q, f: d) b8 N c=new int[m];
) m. B' g. b7 c s.get(a);2 v( q* M8 _3 T, Z2 X
if(match(a,n))
" N* r; h6 G- D, ?6 Y) Y {
3 |( ^; L# E; P& u/ ] out<<0<<endl;% n0 [" S9 ?) p! p }
 s.display();2 `: w5 M. v$ E& w C
 return 1;+ z' _8 ^0 w6 g' A- s# C
}% M& r6 `+ J" o! |6 `: @
do
9 f T; |5 b$ L" ^# O' z( z {
2 c% w; [" y" L if(h%2==0)6 v+ Q! i/ B& a# b. N. n
 add(a,n,c,k);" l I( l4 l' e# |8 f
 else3 a! T/ k2 S; ~) Q( \% b6 j
add(c,n,a,k);
' c+ E& R* N8 `, F h++;
- K: o2 H# e4 h( g' v( T4 P if(h>g)
( J5 |' e6 F! L, x8 X: o+ B break;* h. ^$ ]; y& R2 j# A# h
}1 P& r3 y$ b- P9 h! F
while(!match(a,n)&&!match(c,n));
4 N4 W+ {% c5 x* M if(h>g)2 ?5 v- C/ K& }$ A& G2 F
 out<<"No Solution!"<<endl;" g0 K1 M7 a9 @
else. [, z8 M6 Z/ I7 {/ n9 V* D
{
2 _, M) t- I& P6 X/ f out<<h<<endl;
5 w9 D' N' @9 q7 T3 g3 M! {, U; a if(h%2==0)/ a7 c# s5 y' p6 [; T* }
 s1.change(a,n);
. g3 N$ Q- ?9 C else
- g6 `6 s: y( w- _6 c7 D1 P s1.change(c,n);8 O& Y' H: R% y( Y Y4 T! D( G0 x
 s1.display();" [$ U& X) s2 ?
}
* t, p& K5 {6 J9 e( H' E delete[] a;
 G0 a$ o. `& v( I- q delete[] c; f. M- ~6 @, Y8 V
// finish=clock();+ x( T9 m" h! P& C
// cout<<finish-start<<endl;
5 G4 q. c7 t1 G2 ~2 [ u1 Y. k return 1;
, b/ X' X& x3 m* N- c6 ~3 r/ z}