回文问题（用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)
$ l" O2 T0 w& p0 ^ str=p+48;0 W& l) l0 q6 ` n9 q7 k8 q
 else. i: w2 c }* d2 h/ f
switch(p)9 p# n) T) n5 D; b& T+ E
{
# x' X0 b( t/ M# Q5 k case 10: str='A'; break;8 }* Q( i+ `# u8 f1 N. B
case 11: str='B'; break;. B! [" S* x5 S9 g7 R3 J0 m
case 12: str='C'; break;3 i q9 S0 q9 V U+ k# E" l
 case 13: str='D'; break;
7 ?# L! j. T( `, Z8 p case 14: str='E'; break;- ^3 r! A' _7 w) B9 h6 E4 f, ^
case 15: str='F'; break;) |! g4 {; h$ c- ? Z6 C* @
}
& ]0 U8 R8 m. b! Z& n# i, K str[n]='\0';
( \0 S) Q+ S d; y. T return *this;2 m& g0 u. G0 x7 K1 Z( l) l' g& u, ~
}
& r3 l3 r& n- S: {3 U' Hint String::get()//输入一个字符串
( _' G9 J) n9 p1 h7 S1 w2 J{" d: Q/ T4 i1 ~0 v
char tmp[40000];$ \% @% A! P) R7 r/ T6 y, J2 ~
in>>tmp;% ` s+ c7 J3 D) U& |; p, }! y; h
delete[] str; }6 A( b3 \' m' J' L
size=strlen(tmp)+1;
" @% i; y- }0 s# ~ str=new char[size]; v3 u; u$ w9 @! t( P
if(str==0)
+ w, M0 }* z* y& y$ Z% d1 c6 } throw "error";
" C1 Z' L4 b# _- H6 P strcpy(str,tmp);
" Y% S) q f, G; N! u/ g8 Q return size-1;
% m; ]* b: E+ J. O6 Q' Z}4 G2 L' `0 s+ n" j3 |7 X! R/ c8 L s; ~
<>void String::get(int *p)//将字符串改成整型数组( }0 Q& ]4 H5 C1 Y5 i" m5 X/ q; |
{% E1 U, P% S! H) ]( I% I7 p
int i,j;1 q0 l/ |! i4 e: Q w; W" q/ J
for(i=0,j=size-2;j>=0;i++,j--)" \) `) x% k1 ?, _7 G; b2 c
 if(str[j]>='0'&&str[j]<='9')7 z( @" v4 x; y+ w
 p=str[j]-48;1 |. a8 J' V1 g* C8 T4 E8 K
 else
, l( S8 A5 u; U4 q8 G. i/ ] {
& t* o: x9 F; _$ x' j+ h switch(str[j])" h0 v# U e! F: e: b3 `, c
{
/ K T% D0 x( U" K! V case 'A': p=10; break;
. C' b3 G2 W4 K" z- G case 'B': p=11; break;) {2 h% Q0 B! ~3 U
case 'C': p=12; break;* X7 E$ U( L# U) p) Y
 case 'D': p=13; break;) t7 |6 l/ X: p3 O9 n; C
case 'E': p=14; break;6 M4 Y9 t# G" K& \0 H, U
case 'F': p=15; break;: r/ ], @: S9 ?% ~ m
}
/ k4 F1 {# @( t4 ?& y }, U" j- e/ V P5 C N4 d, }* N
}
9 Y, x% |7 n! B M<>void add(int *p,int &m,int *c,int k)//将一个数同其倒置数相加. d$ A$ c: q$ u8 G& w# Z; }3 T, n
{
int i,j,a=0;/ O* v4 }. D$ ?6 P9 F
for(j=m-1,i=0;j>=0 && i<m;j--,i++)
. f1 a! `. d" v$ W* p {( n* C1 O2 r# ^" n0 d2 y
 c=p+p[j]+a;! x0 \& B" }& K3 I9 r, I% ^' p6 a/ v
 a=0;
* M! h2 H5 W- v0 T9 u/ q: E if(c>=k)
( u( s, k- {: m- w" p {
% q9 S# K( C3 ]) I$ M! ] a=c/k;0 M3 o" K& o4 \4 v
c=c%k;1 W2 W8 N: i+ K
 }
8 X. O8 h: R+ P: j, L6 k }
8 N5 g2 g" ?+ d: L+ E4 p; x if(a!=0)9 x, h0 P$ X( K; Z" ^$ O1 q
{0 ~* u, e( \& r* {# O
 c=a;
9 b, \2 S( j8 |% [ m++;/ @7 b4 a5 I& N U2 k
}
& \! R9 {3 m6 k4 b; l+ |: b}
% O) Q( T6 K$ g( J<>bool match(int *a,int n)//判断是否为回文数* t! u$ d/ b7 U& p6 _- r
{ q0 c8 ]+ m& T+ t1 u
int i,j,h=0;
: q2 k! f3 n o$ m for(i=0,j=n-1;i<=n/2 && j>=n/2;i++,j--)
) k e) F: S* }" H* K {" b1 z/ v. G0 t4 Q( q2 M8 o" r
 if(a==a[j]); x/ I8 D- a. \' {6 k
continue;- f' ^; w7 A3 n8 W$ e# C6 e& q
 h=1;
 @6 E4 m/ Z7 ]8 d3 a break;5 N1 a, T) w( a: s2 X
}
* b( G$ B e2 Q3 b if(h==0)
5 j! h: L* J! ~& [1 N return true;
+ L( g! y3 W; i+ T else
; f1 c7 s9 T2 i! w& u8 @9 J. |# d return false;
/ b- M; y5 b% i# E% k' G}1 } d* b$ a: W# p+ G. d3 V
//clock_t start,finish;4 Q. f; E( V) e. M# n
int main()1 K& D* \& ?- M0 [. a
{//start=clock();
. B Z. p; @& K* `6 | if(in.fail())& @; `- R$ I/ z3 D" f/ [7 r( ~
{
/ o8 s* B W5 |6 }) M2 }% I cout<<"the input.txt is not exist!";
; a0 A5 S1 ]9 {' l- S exit(1);
* V$ @, N T# P! J% a' W }$ O/ }% D4 j6 C3 d" ~# C) V/ Z
String s,s1;2 c1 }& G* w. i/ c9 ^
int n,g,k,*a,*c,m,h=0;
* G9 f* p2 g( m/ d% u in>>k>>g;
5 U! c+ N" F' \, h s.get();- {5 ~: X+ t2 Z+ p+ A. g
" D# i+ T0 m V
n=s.length();
7 E9 ~- K6 R( ~: a( k; m m=n+g+1;
$ O* ?( o8 U) Z$ |4 D a=new int[m];' v: ]+ N n9 a9 A1 H7 O$ ?2 n
c=new int[m];
5 Z. B6 a" Y4 G2 U8 ~" X s.get(a);
0 K5 }; s. |7 y0 W$ c if(match(a,n)) l, b6 d% ]- V0 z- b' Q0 G
{- A( N; ]) I/ g
 out<<0<<endl;
' B$ \3 m; |- Q, f s.display();
, s+ `9 p1 m# @8 M& X! b, Q return 1;
" [3 \ r( D: g }
; v/ v& U" Y- _/ ^9 P1 @ do
: H: n% e# V; W7 v {
9 f# Z& q" J" o' Q- ~) @$ M if(h%2==0)
8 S5 Y0 }4 j+ X* w D0 w& T+ D9 [# m add(a,n,c,k);3 b: k1 L& d" Z X- S5 \
 else
/ z* l% @* M; t: [' M( \9 ^ add(c,n,a,k);
% T0 O: ?5 J1 M3 \! m4 g h++;1 s8 G% p3 q, ?' b7 L' }" V3 h, g) i
 if(h>g)
( k% E8 u) Q9 D9 R3 W( g3 s- n; I break;/ b" Y: v7 k2 T8 p- v: l
}
 z, N: l3 f$ S while(!match(a,n)&&!match(c,n)); j7 u0 Q( o# c7 I
if(h>g)" r- p. F& a. B& L# _. x$ }. m9 |7 \
 out<<"No Solution!"<<endl;9 J& u' R3 |& P N% r; t% n: j
else" G* J) v! l) i) s% c1 _& Z
{& r! g- X5 S6 r! W7 k; ^; H3 \
 out<<h<<endl;
( k9 n: v* A5 d6 G' ^ h. P if(h%2==0)
$ P1 D& f* R& y8 W& G: z s1.change(a,n);
3 S$ G7 n* i' [) ~) c [ F else
, z$ Y/ w) c( C" h( y. @' A s1.change(c,n);* G: Y& E! H3 A) b" i5 \
 s1.display();+ b# \ G* H1 G: B- n" @5 N
}/ r$ K% H U* o; T" l% G9 H
delete[] a;3 Y6 A9 x" A# O' J
delete[] c;
, D3 v% S& ~. t5 ^// finish=clock();! Z, _4 a3 w' W4 \, S
// cout<<finish-start<<endl;5 `9 e( @' j1 z! Q6 D+ Z
return 1;9 d. Q, f3 _; A
}