回文问题（用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)
 P0 A# X) p* F0 p* @0 t str=p+48;
% _7 A) [! f; e. e else* `+ l4 Z Z- ^
switch(p)6 Q# A& v7 _2 h1 U
{
- o+ T7 P* z, v8 d6 U K7 S case 10: str='A'; break;
1 o* L" E6 h7 B case 11: str='B'; break;
" Y8 W$ e3 I3 ? f1 o. p; G Q case 12: str='C'; break;
) V/ K$ F, S8 X% M case 13: str='D'; break;
0 [7 |% `5 y$ u; Z, v6 o3 p" ?5 c0 c case 14: str='E'; break;
& Z8 Z& z6 G! V% s case 15: str='F'; break;# U6 c0 d1 N- d1 q6 w% T- C
}
% _6 e7 j$ |/ E# o str[n]='\0';1 K- R( r. V- u+ O+ e3 I7 J; \
 return *this;( V+ H% C) Y5 Q: z9 p
}) ?3 E/ U- e5 M, L: p
int String::get()//输入一个字符串' d8 a+ Y' k5 a) }
{
# ?2 y, `- o. p+ _7 q7 p char tmp[40000];( R; C+ T9 ^- m
in>>tmp;( A( t( G3 \8 v3 L) L; ^" \. y
delete[] str;
( v& _8 F1 N5 f, m; x, \ size=strlen(tmp)+1;
& J6 H7 l* x- M% b$ m& _" f str=new char[size];+ Q1 R- Q: Y: n4 ^+ z- q
if(str==0)
0 {: S3 f {5 q throw "error";
- W5 r1 o: z9 F8 Q" |3 Z' j: h strcpy(str,tmp);
% s4 K/ C8 }) Z6 A: ^+ d return size-1;; x. w2 _8 a. m5 e" ~
}3 m7 ^/ p4 \4 @) ~
<>void String::get(int *p)//将字符串改成整型数组
( O4 `2 v, ]! U, m. d; h{, s U, Y$ b0 X& P
int i,j;: e" Z7 V; i$ B& y9 B& u7 \2 a3 F
for(i=0,j=size-2;j>=0;i++,j--)
7 _! Y1 k! N6 {5 z. l; l. d" D if(str[j]>='0'&&str[j]<='9') t3 t0 P6 e5 U% r2 J3 P3 d8 X& E
 p=str[j]-48;
* q+ v; t8 |- `* z) u8 A else
! z( `5 r C' L/ q/ l% l {2 w2 P3 k# F' r( ]
switch(str[j])3 }% W% V) H2 V& E# A- N% ]/ v6 }# g
{0 H' o' x8 d' P& x! G$ h
 case 'A': p=10; break; f/ T; k! X! A; r+ ^2 u& C
case 'B': p=11; break;
4 M7 t7 U; N( _, G" y& @- W" d. y case 'C': p=12; break;' j& j- y# a3 x- J, X
 case 'D': p=13; break;
4 i. D# \9 [- j' z; u# K case 'E': p=14; break;
0 ]+ n% ]! Y% D* E" D) U9 p7 P case 'F': p=15; break;
, N" N* R3 c/ L( Y% C }
$ P! @. Q! G; m: @' a }) l9 i1 |5 G6 N# k8 ]
}
, }! Z5 j9 @, @' Q<>void add(int *p,int &m,int *c,int k)//将一个数同其倒置数相加$ }* [7 b# x4 s5 O. G/ y
{7 H7 _# U5 G/ O, T( E4 a
int i,j,a=0;
2 r% J. l& [' F( E8 X for(j=m-1,i=0;j>=0 && i<m;j--,i++)$ f! L+ q9 Z( J
{
/ l; M. v( u8 S( x% t c=p+p[j]+a;
 |, K3 L: j) G2 p m8 Q/ ` a=0;
- m* d; P( P% S: ^6 E if(c>=k). U6 \; L& q: o X, X, p3 l
 {. C) _3 C+ l; c( n. ^/ O# p
a=c/k; K1 a& Q. l7 y
c=c%k;
+ G- K0 Y9 D7 E' T! p, { }
, c3 g1 J$ @* c' v4 x }
* e; Z% t# b/ c& G if(a!=0)
 ]# X0 @. y/ v2 g$ I& s7 Y {# O: Y* ~2 \3 E
 c=a;2 }1 K5 P: Q( a; `+ l
 m++;
3 x' D4 @! Y* J }6 I7 F1 L( V8 n" i5 v& ~
}6 P! H* A: K+ a5 x( Y
<>bool match(int *a,int n)//判断是否为回文数
4 ]/ }; H! _ D7 q0 R{6 |1 l& i1 I# {$ a f
int i,j,h=0;* x: O, ]) q, M6 I+ S# T9 m' L* W1 X
for(i=0,j=n-1;i<=n/2 && j>=n/2;i++,j--)7 K3 @' e: W+ C/ b) x
{
/ W1 B) i! L" p8 ^& l+ y- P if(a==a[j])
* Y. M% h6 h. T) P0 j4 ^7 x* l9 V continue;8 t: j4 ^+ f: D
 h=1;. U+ y9 |4 m0 y& Q/ B: K
 break;9 n7 g4 W) ]# h/ B' a! m' |" y7 W2 R
}5 |& o$ W6 F1 c6 e
if(h==0)
) _% x: m( R2 y4 j; O return true;
8 L+ U7 i5 D# h) T5 ~. r+ z else
1 F0 g0 }! o) p- B i return false;
) O. B( B& t7 s: f6 ~4 n2 m}
3 p8 N8 z8 X" W o$ G5 x+ G//clock_t start,finish;+ Z: |% k: F' S) {# \
int main()* x0 {* q: S$ F; W3 Y5 W
{//start=clock();
1 z% W5 _- Y3 v if(in.fail())
4 I! E" c S2 e! k {. F+ N3 a6 x) c
 cout<<"the input.txt is not exist!";
+ n, p! B7 r# J( J3 k exit(1);
- Y5 g+ U+ z6 k) J, a5 a/ L }4 N) U6 d# ^7 C$ {
String s,s1;
" C: s6 U! J# _: R2 U int n,g,k,*a,*c,m,h=0;8 E* v. z) f1 _- h, Z) ?! @
in>>k>>g; - i, h; K$ \- Z$ i; c5 D, U# M: o, \
s.get();
: r( G% Q' H" b" @; p! a1 K# K2 h, l, @
6 n+ D$ H+ b* ` n=s.length();
: F/ ?3 T( p9 R3 O/ A8 k/ j+ _0 v m=n+g+1;
9 l+ o6 N3 P1 p' b a=new int[m];
; i9 m1 `$ R. ?# e c=new int[m];
4 I& S+ A2 \9 E4 ? s.get(a);+ E2 ?+ T' N" ? W
if(match(a,n))
4 c! H6 K) v: }( @( H. } {) y4 B# w& f, X
 out<<0<<endl;
; @! d# B% d7 H$ e" Y s.display();2 w9 a/ _9 M- X
 return 1;- i) K/ t; Z5 F: a
}
4 z6 i2 E# V7 I; P0 z do% ~! @5 E* ?: ?$ X9 j
{
7 d' H4 |) T3 ` if(h%2==0): J# p0 L) x$ \, V* f
 add(a,n,c,k);
0 p" e) |( V6 \' I) D else
% V0 s( Y+ ?5 @" b' C$ Y2 `7 M add(c,n,a,k);
3 Z( D+ A1 r* q/ [6 ]! S: e& I h++;
( h! k/ i8 ~0 [/ E# K: v ~9 B if(h>g)
& {7 K. w; W( i0 s break;1 u7 O. H8 W2 k
}
- P3 b/ X% x9 X: u8 r while(!match(a,n)&&!match(c,n));2 R+ l0 r, m' K( U+ W' `& D
if(h>g)1 F" _9 Q5 P( D( n4 X& L
 out<<"No Solution!"<<endl;' Z& v% p. J. K0 r' U- E5 ^
else
5 I: n; F6 \8 h# a& ` {3 E- v$ I w' p+ [; m. Y, @8 ^
 out<<h<<endl;1 X8 g1 v& R& W3 ^
 if(h%2==0)
9 U; v9 r1 ]- J Y, y, g! }8 p s1.change(a,n);/ V! _! r4 i) W0 n) O/ L
 else" e6 c* q- R) m; Z9 ~: F
 s1.change(c,n);
7 j- D* p$ F. R s1.display();
, f* e4 G& X" |3 E* j" P. B _- M! V }, u- a. V0 R6 G! @9 I
delete[] a;! M/ S; H2 w% q
delete[] c;
2 r4 L, t1 F# o// finish=clock();7 l: X* e$ F$ y7 e, Z. A0 C
// cout<<finish-start<<endl;
2 Z# ^/ f: @8 u6 J" F return 1; E/ y# ?; C9 w- u; @/ S. @
}