回文问题（用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)
3 O* [7 S5 K" ~' E# T str=p+48;# o5 A( o" }+ {) q8 I
 else. G3 W0 D. D- U) ^( ~( \
switch(p)
 y) } d. V d }& R1 u# C {
. j- g; H9 u7 A: v case 10: str='A'; break;% ^: a; J& E2 D0 k8 ^
case 11: str='B'; break;
! K# d& W7 r4 D case 12: str='C'; break;, V a% L1 u5 g4 v, {/ s8 G+ W1 P
 case 13: str='D'; break;
1 E" [$ O1 L1 _$ I case 14: str='E'; break;6 d' ]$ [6 ~1 r& X0 S$ d/ \2 x
case 15: str='F'; break;
1 o2 g6 z: K" ` q' v }& Z1 `* K6 J1 {# {! a+ `2 |
 str[n]='\0';% g1 {4 C' |/ V: j9 i3 O
 return *this;
$ ], O. R) _7 u( y# y+ q}$ ^- f. D; F* Z
int String::get()//输入一个字符串0 u. O& ~8 ?1 e" p
{; b' }6 J3 G0 B& I2 y; h" H7 i
char tmp[40000];
3 l$ o$ k% o' E5 h# I in>>tmp;1 \ }: r- u( m" p# X$ O
delete[] str;
: p1 z' u5 r5 k3 W" Y size=strlen(tmp)+1;
 c# p! t3 g9 r Y+ l, T str=new char[size];
1 f) y9 O! B3 u! ]3 F6 B/ t if(str==0)' D- L7 V( n! p* q5 T" a
 throw "error";
; r) b/ P2 K4 v0 F strcpy(str,tmp);* s% |2 \# ], `) W5 W- d
return size-1;, e4 @* V: M9 H7 x1 j
}
1 y7 x$ [: ~: X6 Y2 C. Q0 J" S<>void String::get(int *p)//将字符串改成整型数组" J( H. v5 F% F1 h: {
{
8 @) R- F9 X! D/ L, ~$ ~% x int i,j;) H- P* u; Z, M& Q7 m- z
for(i=0,j=size-2;j>=0;i++,j--)! T& b3 W* A+ k! u8 C% F( d$ G. ~* Z( `
 if(str[j]>='0'&&str[j]<='9')& [: u& B& R) v, T# r1 i2 K
 p=str[j]-48;
( S+ Y. ~2 `, _4 w ^2 U. m3 t else
4 A4 b) b0 f+ L- B7 l {7 O8 `7 Q* `6 J4 L. }, }/ }
switch(str[j])/ Q4 e: J3 y u3 I2 O( }
{
% _6 v' a# X7 j3 N case 'A': p=10; break;, c) w; B1 z# E. p- i
case 'B': p=11; break;
6 R6 G. J+ \) x# v% X% N1 G case 'C': p=12; break;
" @# f' K2 L0 D0 j case 'D': p=13; break;* H+ K# P( W' P" {
case 'E': p=14; break;; M3 y. ~7 v0 ]& _( I0 ~' ~; n
case 'F': p=15; break;6 D, [& l. f9 n% j# `. ?% g8 O
}
2 q1 ^0 k1 X5 c L' G" J% v& K- C" l }4 w& Q7 V) B9 t$ J9 i
}
% @9 x' `. T6 l& x* `<>void add(int *p,int &m,int *c,int k)//将一个数同其倒置数相加
& O. F% A i5 v{
' `1 p: ^: R9 E; ^7 B int i,j,a=0;8 I4 r0 ^" W) `3 W/ G3 ]! A
for(j=m-1,i=0;j>=0 && i<m;j--,i++)5 D* J* B' {- J( g* e% l0 F8 D& a
{
) a% P) O! h. m C0 \ c=p+p[j]+a;# b& z( W2 Q. a, h! T& Y
 a=0;
3 i& B0 z! G4 o" Z7 a' x' w4 O' v if(c>=k)
% Z6 c3 W# f$ |- q" |1 b# F8 b) q {
. U' w/ g$ D5 S5 A" j a=c/k;* |6 A: @0 d: p8 b) P
c=c%k;
2 {+ `- z2 A p6 ^ }
# v: v* g# N4 R! {& c3 h }
+ }* \8 I6 i& [. S$ n+ q: H if(a!=0)
$ G. c. V9 X! P9 Y6 K/ q: C, ^ {
4 Z* F/ F0 Z" ^ c=a;7 R: ~/ e7 _. X) D5 C
 m++;
( d, W9 o9 }4 E }, ?$ Y9 e1 w- g
}2 u$ V: K7 n8 K. w
<>bool match(int *a,int n)//判断是否为回文数7 _5 ~7 v& ?% W& ^# e7 X# g
{6 v7 e; a9 i$ `! i9 H! T
int i,j,h=0;
6 v2 f! r/ l3 t3 s3 k5 v& u for(i=0,j=n-1;i<=n/2 && j>=n/2;i++,j--)7 ]- ~! |) {, v# m L, a
{, r/ A) h3 r, w+ f0 s. a+ p
 if(a==a[j])8 {/ m5 X/ I% S9 m, m) w: |, Y
continue;& [4 w4 y0 t' O8 V& m" j# P
 h=1;
8 y/ ?3 I( V% y% x break;) P: Q6 r- I) n" a# R
}
8 F- G8 A$ G0 L# o* |; j if(h==0)
0 R7 W, V+ E3 ~ return true;
; w; L% @, O' a+ R- C( [5 y else ' Z( H5 D6 r) q! w& {# A
 return false;
9 h8 C. [& \0 [) P! W. q2 s}
% \$ U( \7 r1 n" S//clock_t start,finish;
3 C+ u! V0 |/ Cint main()8 Y! p6 V8 W% o# k
{//start=clock();
3 u- W- j/ d/ m. ~ if(in.fail())* L- D8 s$ X2 {2 |6 J, @4 }, s
{
8 v' m) V3 y: `3 {3 n* {3 U' l cout<<"the input.txt is not exist!";; ]8 l; Z# ?* D2 t$ N! d" G
 exit(1);
; e! b+ ]- _! x1 b. }$ z# v6 T }
& h( U+ ?$ |: d3 ~: b String s,s1;* H; S @/ X. Q; H0 I
int n,g,k,*a,*c,m,h=0; X$ I* a+ c! A3 g w$ C1 A: r) t+ v
in>>k>>g;
9 B n6 {) _' b- M- J- Z! F- Y s.get();
. C; O! z2 o0 d& p/ T
, V) \6 v* x6 n' A n=s.length();
. N" {8 Z4 Z, D9 D# m" ]% H+ P. ] m=n+g+1; f# a. m7 L5 C2 t( ]+ m
a=new int[m];3 _0 L; ^ x' a5 w3 _. R
c=new int[m];0 L- @0 _" O( ]! t/ j
s.get(a);4 W" k4 `4 K3 c: u4 l/ a& H
if(match(a,n)): c% e+ ~5 z8 D5 h% E
{
* y$ l. b. k. ]8 d9 M0 D: C out<<0<<endl;
1 _' ^7 a* D5 v. ?# o7 ? s.display();
$ o5 F: Z' _+ i" _" s return 1;
0 S% C, k2 F% g+ n }9 Q# S' e# N( U: l
do# k$ V# J. E4 }4 X2 w: J
{
! M* C- O1 m/ J9 ?* M3 i9 F2 l9 { if(h%2==0)
6 v; L6 ?7 d4 M3 u V5 y, A- N3 T add(a,n,c,k);
" _9 u0 K* p/ J8 s5 p s* h else
% d ^: r# t1 _ add(c,n,a,k);' t; }- I3 K% J8 [/ D8 `& T
 h++;
' \3 g0 l+ Y3 y# d( U( q6 t5 P if(h>g)' g* w/ Q0 O! N8 j
break;
) Z( ^2 I0 m6 a) \' b# k( V( C }/ Z8 U9 V, n# \, u& ^
while(!match(a,n)&&!match(c,n));
% g# c" A9 v! v( w" ] if(h>g)
1 c2 Y! @- C% f: X out<<"No Solution!"<<endl;
7 Q; S. ^3 J* F# v0 v8 Z9 g6 r# h else
9 W2 F* t0 i% o" D) J {
2 D* p/ a+ A5 q# }( q! J out<<h<<endl;
& A6 ?# h) G3 L% w1 C, l j# m- e; b if(h%2==0)
) a n1 e2 [8 z$ g% [: P% y" ^ s1.change(a,n);9 R' D+ k+ K, R3 R! \
 else
: D. `* U7 o* b9 ` Y! H" M( ] s1.change(c,n);6 s+ [1 D' h3 S; l& d" X
 s1.display();0 h/ P i3 V8 q6 S, k# v* f4 E
}
 _7 }& k% P/ q& ~: U- { delete[] a;
* B) x& X9 P3 q, T! u delete[] c;
7 D0 i) K- f _4 }3 i// finish=clock();
% |* j j+ {; g& q// cout<<finish-start<<endl;
/ D, L: A8 \, H( U( ?" A/ E return 1;; B, O1 `. _" ~9 L. {9 ^+ `' L
}