回文问题（用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)
4 ^* q- [# {' ]% { str=p+48;) v! H% B5 D" V, A( G
 else
( @! V5 Y2 }$ j" L* h switch(p)
& {3 {* C+ A) |% i, j2 T- ^/ W {
: U( R" R2 ]8 S, M) I6 {$ U1 q3 p case 10: str='A'; break;
- ^4 Q, e) P& p2 X+ r1 l case 11: str='B'; break;4 p2 M* c: a6 j7 E' N- \
case 12: str='C'; break;7 D- C: R G6 X
 case 13: str='D'; break;( V$ @: a- m( C- W& P( J: U
case 14: str='E'; break;
4 j2 ]$ [6 H! o/ R case 15: str='F'; break;* W$ P& N3 B, @; Z
}
9 e$ Q' D' u1 p: D& g* C4 d- G9 L; p str[n]='\0';7 z: O8 c9 O: D4 Z
 return *this;5 }; r. p& M% Z4 h9 }+ f
}
7 t, y0 n5 o) `0 |8 e+ U `/ L" w& yint String::get()//输入一个字符串
/ p4 ^4 s2 U+ w- [: a+ s{
; p `. n( _3 o- Z& n char tmp[40000];
' m7 S; v+ I- ?& R9 ? in>>tmp;
' X x, g( G8 |+ i6 R delete[] str;) {7 p/ H; l2 L( [: ?: c. d J
size=strlen(tmp)+1;
/ F0 E% _% [9 S str=new char[size];7 L+ j& b* p" g6 c9 {: N
if(str==0)
( g3 ?: t6 D' Q0 E8 j throw "error";1 ~9 E3 v% M9 A* Q9 Q& r
strcpy(str,tmp);
! t3 s7 B( u' b1 A return size-1;
 z2 B8 n' J4 v3 W( i}9 L/ b. ~7 ?# _1 u3 V
<>void String::get(int *p)//将字符串改成整型数组
# } T4 n& H0 i$ w* e5 s, o{
6 s, ^& n1 @7 T, Z( }: C- | int i,j;
9 k+ ^' {6 ~; p" H for(i=0,j=size-2;j>=0;i++,j--)" Y5 y- ^$ n p2 k- d
 if(str[j]>='0'&&str[j]<='9')2 R1 a: b# s7 w% m2 }
 p=str[j]-48;
- s- Q R. a: h# `' n else' ^ \) u$ i: m
 {
9 a/ a% D" L" Z: _5 @, i' `9 r$ u: m switch(str[j])& s; C! ?* I7 k9 z; K) s4 x
{
6 j, n, p; u$ K/ f; o$ m8 K case 'A': p=10; break;/ X, h+ u& L) e- ?, a
case 'B': p=11; break;1 W6 @* c+ _7 G {3 {
case 'C': p=12; break;& w1 S' i6 M' r6 Y* O2 |
 case 'D': p=13; break;# Y J- D( o, w/ T3 ~- ~
case 'E': p=14; break;- }/ H. A9 S9 q& B6 ^
case 'F': p=15; break;
" t ]/ n# v7 u! Y1 q } m8 b3 ~' Z x3 ~: D t! F" p
 }
9 `% g. v0 a# t}" B# m$ I5 A1 J
<>void add(int *p,int &m,int *c,int k)//将一个数同其倒置数相加: j; H# Q, l# L# Y: {4 h
{1 U1 b6 l) G1 \/ Y
int i,j,a=0;# u6 T. X$ V1 Y
for(j=m-1,i=0;j>=0 && i<m;j--,i++)
3 j" D) Y8 M0 W# M4 J$ I; }2 _ {
7 K, N# t4 t: x, w! w c=p+p[j]+a;
7 F) k0 c5 v1 H# |4 u* k$ J a=0;# @/ t+ l# Q" Q
 if(c>=k)
# Z$ l; [! R. \* V {% ?1 P# s! H: ~- K" J
a=c/k;6 U3 o7 o! q' D
c=c%k;
8 N5 A' Y. s6 w }
5 O5 D: @ U1 p } . `6 E3 C. |7 |$ U; K
if(a!=0), _, {7 `& u: `+ i* v
{
' H: L$ [$ M6 c' R7 a8 {% p c=a;/ n5 l" R8 x; P" K/ L
 m++;
, O" l7 K6 w: b/ l; i }( C9 h3 g8 I" p0 ?* V7 h
} l. H3 Z$ Q$ Z' W) n
<>bool match(int *a,int n)//判断是否为回文数
* u* [1 n+ W( D# L* _8 T{
; S5 x$ p% I: u/ P; d3 w8 G int i,j,h=0;
! s3 I: o" @$ g for(i=0,j=n-1;i<=n/2 && j>=n/2;i++,j--)
' g; t& ~# \$ {1 ~* g, f2 ` {+ K4 g/ U1 J& [# E; C! b
 if(a==a[j])9 ~) k/ x1 b0 L q( H* {
continue;
( F* o% U [* R) q" ?0 \ h=1;% Y. }& B+ A7 w; [# p1 d% n+ I
 break;. i1 g; z2 D5 [# | C9 D/ E
}
8 V% Z5 {- _$ r, `( j6 Q, ~9 H' g8 } if(h==0)
% p! u$ C& K7 A- G, [) P return true;
5 [ S0 ^* K! g2 m* O else 8 C0 G6 J' C% J. X
 return false;
. ~: C) L% @" E' m L! Y}
//clock_t start,finish;* H! x% R' x% f) V% g2 J" ]" ]/ I
int main(), J: B" Y, q& _6 q8 {2 I3 L
{//start=clock();
0 f2 b1 v% ]" N; ?. ^ if(in.fail())2 h$ F$ K# ^0 Q* D8 ~) L4 O
{$ _+ ]& t0 x7 [, O6 w
 cout<<"the input.txt is not exist!";
; G2 X: ^; O- _' s$ y exit(1);
1 q6 p0 G, E W8 I- @% P }
( J$ p- w8 e) `: o# m" i String s,s1;4 l0 T" X. l2 m# }: k F+ m
int n,g,k,*a,*c,m,h=0;
) L8 q9 B8 P( P' R' B; V4 n in>>k>>g;
/ Q" j1 C3 |8 _5 B2 e% m- g s.get();$ B% m1 w% x* V7 |) P& n, d
0 Y8 [" P3 T/ M
n=s.length();
6 c1 F: ]2 P0 }" t2 ? m=n+g+1;
9 R5 v5 m- ~% L/ T" V a=new int[m];
' y O% j8 O6 O0 }! b: w$ F3 `% l- L c=new int[m];
5 i, Q3 \ ?. V s.get(a);
' l0 [ M1 z: Q0 ^4 m if(match(a,n))
6 w; {% _) a" w0 J {( Q0 l0 q) Y; e6 n5 T' \% k
 out<<0<<endl;
$ ^9 b+ k1 Y$ n; }& \ s.display();
2 G; ?9 d5 J- y1 C! D( t return 1;
) f6 L5 I6 t* _# g+ S# _; m }, ?1 |5 ]- @/ F! f5 w6 `
do
% g$ K3 q9 \! ?8 \( a- g B+ D {; d2 L* f2 H% q" i$ C
 if(h%2==0)
2 S L/ f6 P. M( w! S2 e( e add(a,n,c,k);# N5 K8 B) l; M t2 R1 Y
 else$ H; a; W# x: l9 V7 M* f6 U. B
add(c,n,a,k);
/ N. w9 i% f$ B# f% ^8 A h++;; K! l/ g# o( g) E$ ~: O$ z0 C/ E4 V$ I
 if(h>g): w$ V4 A# R6 ~, e6 D6 X& b* O
break;
; F a% c" B+ f2 H% q6 t5 Z }7 X. [2 @9 i4 T8 S
while(!match(a,n)&&!match(c,n));! I- R: W' \7 A7 Y
if(h>g)
8 H0 B) a% @2 V& U' m: l0 h) T# | out<<"No Solution!"<<endl;
3 h5 e( {* @! x1 w- n/ G else
) o( F& r8 U) D8 S8 B' K {' p" H K, N5 [, q
 out<<h<<endl;
8 l8 r8 D% a& F- e; s if(h%2==0)5 H! g7 f$ `. V5 m/ Z: ^
 s1.change(a,n);$ I+ M3 h( h; L+ S7 q
 else' f* r0 S7 t* }# s
 s1.change(c,n);) U) i# G2 J+ R! y/ L
 s1.display();
/ a5 w5 s0 l$ _9 a$ j }
1 j% [- b% i; F5 f+ h6 z1 N delete[] a;
: M& W- L6 N5 e! _# a( V delete[] c;
" ?% q: i+ z8 v: t4 o// finish=clock();
 _9 Y( s* f2 t% O// cout<<finish-start<<endl;; _$ p2 m. g& R( e
return 1;
8 R R/ o# H7 K% M5 k% D}