回文问题（用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)
" a2 Y) Q6 F1 _, g5 G5 o3 r str=p+48;) Z3 e; A- X0 `) [7 ~+ W4 M/ T
 else/ _" n5 \) s5 r+ ^
switch(p)
+ {3 Q. B1 g& t/ [2 t0 Z' [ {
; D; ]# C' x3 `, \) W$ n( m. G# r( \ case 10: str='A'; break;
6 X& `5 _4 |9 r case 11: str='B'; break;6 X- m. U" ^: \# r. Q, _# A! j, s
case 12: str='C'; break;) i) [; x/ B) q! z( Q3 S
 case 13: str='D'; break;
& G8 B5 j- K& B; k& P case 14: str='E'; break;1 B4 ~6 E2 r0 s ?
case 15: str='F'; break;
4 p$ |9 R' b7 X }* Z. s- U& c. Y# m4 E
 str[n]='\0';
: k9 j* W4 p" }) z8 M- B, M return *this;
# J9 @0 e" T$ M: [6 k}
4 u! d$ F0 b q) \7 n. F; vint String::get()//输入一个字符串5 F1 E5 X- g3 R
{
1 Z* \+ k2 _% q char tmp[40000];
+ s' k( I3 ?6 J in>>tmp;
. A. Z4 N# |2 A delete[] str;+ V1 w3 @& G2 b. w; L
size=strlen(tmp)+1;0 i* t: Z& H* p: l: e l
str=new char[size];9 O# j: }# z- |7 n4 @
if(str==0)" m5 Z3 h4 S, J, i, w: o* c d
 throw "error";3 _: }/ p" e6 K) R2 k. F
strcpy(str,tmp);
5 D( Z" x! w! {" e: \. V return size-1;
: Y/ W+ D& J. p/ Z! a}4 V Z. E: |! X1 f) r# Z3 ^
<>void String::get(int *p)//将字符串改成整型数组; L: K8 d: w3 l0 N n6 C
{/ B( m# _3 g( O1 O( F9 i
int i,j;
: u, M) S3 k2 w. D% ~' W9 k/ V for(i=0,j=size-2;j>=0;i++,j--)
/ _/ [% L% m1 A- R if(str[j]>='0'&&str[j]<='9')$ q1 ]2 N4 O* Y0 a. c) e
 p=str[j]-48;: N& H8 v7 h. ~/ a9 q
 else7 f$ Z7 [. J( u5 c0 }6 q, U% ~; T3 n
 {
8 F4 A, O5 x4 Z; ~ switch(str[j]), q4 q9 C6 K- ?
{
. Q. g/ B, h( _3 [8 P! J+ L7 g4 ^' v case 'A': p=10; break;
2 \" m% a) j7 s( f0 t9 v+ i case 'B': p=11; break;
1 l- l9 D1 f# @* }1 B$ l" V case 'C': p=12; break;) A! [, a8 }* L
 case 'D': p=13; break;
* z1 Y0 H: r0 T$ F case 'E': p=14; break;; s1 ]4 X, q7 k
case 'F': p=15; break;
3 \# x) s* F" U! Q0 Y0 L8 ] N }% X3 j |" _" }( Y" _. v$ X
 }3 y" y$ {+ D# G6 A2 o
}3 e3 b# o6 w1 p8 |2 p
<>void add(int *p,int &m,int *c,int k)//将一个数同其倒置数相加; a( [# `! u' H
{
$ p( h" z2 }& C( W" ^! k int i,j,a=0;
+ \) u+ @' [( q; o& E H$ S for(j=m-1,i=0;j>=0 && i<m;j--,i++); B( u( M7 L' O3 N) D9 N4 g
{% o4 K; [& C, {! e
 c=p+p[j]+a;% `9 Z/ [' _7 p5 H; L! M
 a=0;
2 N/ U/ l2 r' P5 {3 r- N if(c>=k)7 p5 T. y6 W$ A6 `2 j
 {# u$ G. @& G1 [2 c- R# a
a=c/k;3 m2 V; |8 i- A
c=c%k;5 H3 f/ D) O( K& D
 }
9 L& H8 O! t1 s/ V" F } 3 C& s4 a7 {% L7 n" d
if(a!=0) W2 E+ y" R9 p+ k6 ^0 t
{9 C* L# i1 j: b' d
 c=a;
, O" ^0 j, P u m++;* W: u/ L, }5 R
}
+ U! ^% A ?7 F4 j}2 N: F t2 Q6 H
<>bool match(int *a,int n)//判断是否为回文数
" p Y8 Y0 E- K3 [( S& @' q{3 _; r. J1 d/ s5 R8 E
int i,j,h=0;
8 W9 f( S# U" q% w% A( [/ _3 i% ^, C for(i=0,j=n-1;i<=n/2 && j>=n/2;i++,j--)
6 T/ `$ X' q% W% k% R {
) e$ g, y! w0 }/ l6 h5 B; _ if(a==a[j])
$ F% ~/ d8 z7 K continue;9 O c# @& F# G: t; F/ l( M9 o
 h=1;+ a$ L! ^! s* ^7 C0 R
 break;! V* c8 ]! n/ w4 { E3 B3 [' X
}
# \' q* F1 m6 e# j) Q4 L$ r% B+ m$ e: ~ if(h==0)# g9 s& g8 c3 p9 A) Z
 return true;/ U% |+ t- v) q
else 6 W2 i/ ?) Q, u2 H, u) [
 return false;8 P3 e1 ~8 F2 j9 n, _7 ^
}
% Y3 ?: p7 Y* b: L//clock_t start,finish;) S' M9 S8 W; s9 ^; O
int main()+ J) T$ x# m& |8 y+ M$ ~7 |- O
{//start=clock(); R5 P/ g, f) i: ]' h+ N* g
if(in.fail())
4 D8 P% v$ |: X) P U4 P# T {' M2 r: u/ w/ o# }5 P
 cout<<"the input.txt is not exist!";
# ]( k# C4 J+ Z7 y8 B- @4 b5 @ exit(1);
+ w2 e4 ?7 v5 }; { }9 b3 {3 f. h, `2 @$ `
String s,s1;% j9 ?# o* E2 l3 v- |2 u1 Y2 u2 g
int n,g,k,*a,*c,m,h=0;
+ G* o/ w, s& R! d, H, j in>>k>>g;
$ t/ n1 _- v4 Z2 }& s s.get();
 N. I& r' A( P8 h+ u" {& i) E, q 6 D% ?4 y+ K+ e' \
n=s.length();
6 u$ X) E. R" r m=n+g+1;
6 s6 x8 e+ R7 V/ p7 O* `* } a=new int[m];9 i7 e2 x0 I9 a% o! _
c=new int[m];
: ~; S' f- H c! ^ s.get(a);
% Y) B- S9 `" V/ `3 l( F6 @ if(match(a,n)): L2 a" Y% `9 z5 |6 l
{
! r$ S2 I& x8 i% o out<<0<<endl;
& w/ I# {! }0 K0 g* T; G- ` s.display();
! x N' P( _4 h4 d return 1;
/ F$ R. d# j& N4 b1 u# f5 p }' @0 X3 c4 H8 h. _
do. ]3 ?) f8 ~6 ~7 C* B+ O
{
7 g& r# G7 q) h5 ~) {: u if(h%2==0)
6 T+ w7 a& a/ n9 c add(a,n,c,k);
/ O$ m6 n: _) k3 r6 A( \% y1 e else
0 m% Q' B8 O2 o: e' U/ {' ] add(c,n,a,k);3 n- i( T$ S: u( `" T; b
 h++;
3 j, F: A: O+ d8 N if(h>g)) n; `- s: i1 K; |3 I( |; P
break;( T, g, I* R& Y; A
}% Z6 P9 Z0 J! y# }& q8 ]
while(!match(a,n)&&!match(c,n));
7 Q6 b! s! E G7 B6 s% w if(h>g)0 v- ^$ F" m' q; z6 U0 ~
 out<<"No Solution!"<<endl;
* {6 N7 V/ {8 s) C1 Q else7 U/ n9 v& v1 x, v) U# I
{
 B% ?8 x5 [% v# R) A% g9 T' V out<<h<<endl;
" }% O, d: _4 Q' |9 a( H6 I if(h%2==0); E& n% V! `% [6 e, n# R+ ?" r: D
 s1.change(a,n);
1 M7 j# I- }7 ?7 b/ ]8 h else; G; |! U9 G( P- S+ o, Q
 s1.change(c,n);: x4 ?1 i* S8 R3 r5 x
 s1.display();
5 g) ]$ B8 N. @; ^+ v2 O }4 ~3 x$ Q2 ]6 y( i2 y7 D) {7 T0 }
delete[] a;* F1 g7 X- k/ q
delete[] c;
9 G ]# x/ y' \: Q// finish=clock();
; M0 l9 K% x' F' @! ?// cout<<finish-start<<endl;/ S) P4 y) B7 d9 V! N+ N0 o; ^" b
return 1;
# x: E! C, J) C+ T7 o6 s}