回文问题（用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)( z3 R& r3 X! i- d0 F
str=p+48;
2 E0 u. Z( V5 X/ r else' e1 u6 k5 F1 L- v! O/ b
switch(p)4 v+ d! k# a, M: k! A0 ]
{
 Q w4 q1 Q6 u' {) a* P case 10: str='A'; break;
3 x+ I( t, \. a* E case 11: str='B'; break;+ c9 o$ \& G" @! E
case 12: str='C'; break;- w! m* E, `2 w+ T s% l" i, J
 case 13: str='D'; break;
2 a2 I' P& V: \1 n0 S case 14: str='E'; break;1 M* P) Q- t9 h
case 15: str='F'; break;$ i, I; F- E+ W) V( h( ?
}% I2 T" g/ e% O* b) y
 str[n]='\0';( O1 {# o+ L8 C$ z; b g2 n; \7 x3 r
 return *this;5 o# E2 M# F3 ?+ m. ?* [
}
: T0 Z$ E6 ^" @" Nint String::get()//输入一个字符串
) H8 B& x t5 K# @{ h" I# F; l p, V- v, O
char tmp[40000];6 s+ d3 H$ z* E b5 q9 u
in>>tmp;
: l: X9 q$ J% z* @2 b delete[] str;
* [/ \ T5 J6 C$ T$ D9 t5 I size=strlen(tmp)+1;4 |' Y: T' {2 @% L- d- @+ u5 F0 S
str=new char[size];
' _" N. v X$ y8 F) k if(str==0)* k1 K# l7 B0 A! n6 h: Z
 throw "error";8 q0 N/ ~3 @' ~8 ~& ~- f H
strcpy(str,tmp);2 ^- p+ Q9 A% l( N9 Q
return size-1; e Q' o6 `" R& G; D) O' Q- h
}
9 j9 H3 \$ f9 R* X# B3 C: a7 o<>void String::get(int *p)//将字符串改成整型数组
1 q+ o# ]/ y* J9 x( t% H) h{
! P; A1 w; g, _" E int i,j;& }0 R0 F5 d6 X5 e1 e
for(i=0,j=size-2;j>=0;i++,j--)1 S8 ~5 o2 c, x/ ]
 if(str[j]>='0'&&str[j]<='9')* c1 [1 w; y9 M0 w
 p=str[j]-48;+ y9 Q& R% X/ o4 {
 else1 q9 `3 B. V* _+ e! F
 {1 J: F+ ]' L5 }4 j: ^/ Q: N
switch(str[j]): M* K8 W( h3 H s/ ?# `
{
; q# A# H% @3 V6 P+ k! b, c case 'A': p=10; break;5 {( T% k( O3 D, A) ^& E& B
case 'B': p=11; break;
- w4 S" _5 m0 }9 _ case 'C': p=12; break;1 F x: Q; J- O- S2 J7 v
 case 'D': p=13; break;
- s) H6 }" R& ~, V! P' y! k& W case 'E': p=14; break;
( @0 H3 S8 V( |! P% n case 'F': p=15; break;
* V: o* h0 u- o/ m/ X }& ?/ z/ G/ e" e3 m' X# B# E6 e
 }
" U' j8 k- F. H: p v7 x}
' M' h! Z! |( X; b8 B& b6 Q& ?<>void add(int *p,int &m,int *c,int k)//将一个数同其倒置数相加4 ~' v" y0 ^! R- ]( Z, X
{
( C. H* S: ~/ C1 M# Y. I7 g' A$ D int i,j,a=0;8 O) y7 d! X7 _7 o$ H' S. ?# l( X
for(j=m-1,i=0;j>=0 && i<m;j--,i++)
' t' j4 y- n0 d' Q$ X {: s" G% {8 |; c& m
 c=p+p[j]+a;6 j, u. R- r) N; W( F3 p
 a=0;- u0 |3 f3 M! }6 T. M1 e
 if(c>=k)
& ^% s8 R* k9 _) y0 u {- Z' \. O3 N. [
a=c/k;
; C/ z: B. V* | M d6 f c=c%k;- c3 O D4 W# A0 K- X) y
 }
8 n2 Y; H4 G# [3 { }
7 q% v4 g7 x8 M8 w if(a!=0)
. U* W; z+ \, k% n' Z7 l {
4 z" b' G' E/ V& v6 A- j+ t& F7 O c=a;- _& w. V4 j) I. H% Z6 F4 L, A7 a6 y
 m++;: n' c, w' q2 n7 V6 [
}% h6 N. I0 [* R
}
$ q$ x1 N P5 Z/ @1 P4 w<>bool match(int *a,int n)//判断是否为回文数2 l, D' m- H6 F9 c$ l, f6 _. w) H
{ U5 x( e% [* S7 e4 e
int i,j,h=0;) Q/ |, Q. m7 x
for(i=0,j=n-1;i<=n/2 && j>=n/2;i++,j--)
; e( c2 d( I: W! G. W% H% y6 z0 E {# j- G, I% q, s- l) g" m' K
 if(a==a[j])) Z4 N6 I3 m1 i2 T& H
continue;# c( Z2 s) ?: [
 h=1;, A$ q) I# R K
 break;7 J1 H0 p p5 t5 U5 M
}
, [, S& ^0 u( ` l5 i$ Q( A7 q6 n if(h==0)
+ t* H$ }5 h9 t return true;
* [0 ~. G$ {$ _1 q6 b else , r" ^; ]& {% T
 return false;
1 Y8 ?4 K, J1 v; D}' b9 |& a; c9 T3 _2 i: {: u
//clock_t start,finish;0 u9 I$ t. W6 @1 _ U; ~
int main()
* d3 [# D* y C: P# T{//start=clock();
0 D& K" `- K. h7 W if(in.fail()): |; V, b; ]2 i6 H+ \
{% X9 i; r( d8 C; Z9 |
 cout<<"the input.txt is not exist!";
. s$ B" M* A2 P) }+ S6 E' a( } exit(1);' g1 r! ?% f5 c. U4 h
}
7 n' O* D I$ h7 |/ V- v* f) G String s,s1;, Q% m' `" P# n1 l1 i1 o
int n,g,k,*a,*c,m,h=0;4 V0 S. {" t. |7 ^
in>>k>>g;
2 @3 B! l) B6 z) n s.get();2 B0 r0 c v. v G8 R% c

! U; f9 W9 \3 [, c: [6 t* c n=s.length();% V4 R. G: ~1 a' r9 ^% X, w
m=n+g+1;) _5 E- u' g0 z9 b8 Z" I9 C# U
a=new int[m];1 w6 `" N5 e" J5 b3 ^. F& m
c=new int[m];$ G% {; p+ o5 [: v+ p
s.get(a);. v0 y+ }! b/ c
if(match(a,n))
0 J! o! `+ H6 }8 v- b* t/ ] {
$ R0 y! Z& m! k5 ~ out<<0<<endl;
$ ]# L! |" K& Q) R1 w e- s. P s.display();
+ e. e* y4 T$ c0 H: C, V! H0 e+ u7 Z return 1;
 o8 B4 w. l6 P( H5 ? }
7 J, _. S; e4 }- s do; H0 [7 u; M- }1 X' h2 S- C1 g
{% F+ K# h1 i1 d, u
 if(h%2==0)
- r, ~% s; r+ @* _9 E+ ~* ` add(a,n,c,k);
- N) X; `# T; A2 V: u else
& X2 @. ^$ T' M; w: x add(c,n,a,k);
( t1 s! ]8 ]; K h++;# X. R: K# d5 B; I/ r2 O+ ^- j
 if(h>g)
/ C$ p6 E7 J' l- ]; X$ }" o break;
- r& g& S7 j! _- n, Z r }) M8 H4 q7 v- |! \3 @6 c
while(!match(a,n)&&!match(c,n));: o9 o: {3 h4 o9 x
if(h>g), W, y8 u/ [: |9 q% ~2 ~
 out<<"No Solution!"<<endl;) K( R2 Y5 K6 U1 N
else
+ @4 ]' Z+ v% q& m# _- ] {
$ r3 a" |0 G: z; P/ t3 G$ L7 s out<<h<<endl;8 `% b+ S8 g8 b
 if(h%2==0)
3 k$ r) p' L: m# i, k- k% J/ j# l. [ s1.change(a,n);; M0 s% i) V5 n# ]5 u
 else& Y) @/ U4 X. L; Z" G
 s1.change(c,n);# {- v' }) s5 g2 Q2 }0 C
 s1.display();
0 W7 d) e8 L" k s8 G }
 X9 F' l) j- y9 y" o8 n( k, }) ]* O delete[] a;# {; w6 }9 ^+ ^4 ^8 Y0 k
delete[] c;
0 y$ @8 ~8 m8 a# r5 e$ r// finish=clock();% ]3 o$ s3 Q& e& G/ H: E8 o
// cout<<finish-start<<endl;2 G7 \( k8 _- [ U7 V4 s
return 1;
# G' m0 h; ^# i: k0 \' f}