数学建模社区-数学中国

标题: 回文问题（用c++编写） [打印本页]

作者: lynnyan 时间: 2005-4-22 01:27
标题: 回文问题（用c++编写）
<

>#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)9 N' y; r6 o" }/ s
str=p+48;+ k! J3 q5 K- h& r3 x3 V8 M
 else
5 @& `8 H0 Z, l. I7 i4 B switch(p)
3 ^! z; x' R, a# E F6 P) D" [ {
6 P3 v# n0 c6 ?$ w case 10: str='A'; break;
5 y v' W, R( p! L9 Q case 11: str='B'; break;
# ^- Q3 i( ]# O case 12: str='C'; break;
# G: C0 a B }1 V case 13: str='D'; break;# ]% j/ i0 I4 D: V9 N" J# a! {
case 14: str='E'; break;) e$ \4 z0 ]/ v7 O; F
case 15: str='F'; break;
 A1 E7 y( A" o0 {6 H }% M! u# a6 R0 `+ O- x* p3 z" ^
 str[n]='\0';9 J# y& P7 n9 j/ ^
 return *this;
" [2 U# P8 R+ Y/ G7 X- ]7 N}( h& K+ Z% O2 p; Y; w! y) a
int String::get()//输入一个字符串
: C: f+ p+ F6 l( X{' D$ @% n1 Y" n6 u* n: r
char tmp[40000];
" R" {7 d) T5 d" V* F! D2 T# J in>>tmp;3 v2 i) D7 |0 i; K/ O
delete[] str;
( s: z4 n* G& v2 Z8 t B size=strlen(tmp)+1;
: g7 |* `0 ?3 g: F5 ]$ I2 N$ ~! s str=new char[size];
* U9 ~& z. t Z' p. b2 }# P1 B7 S if(str==0): ]! f) J" [: R) [1 [9 y
 throw "error";
6 I' I$ u" g9 y strcpy(str,tmp);
! @3 [, b8 M I3 m# a& [ return size-1;# l% O" p+ F: G8 Y3 {9 D2 g
}3 H# ?' q# W' N- _
<>void String::get(int *p)//将字符串改成整型数组9 T& P* i: ^; x( T. |2 } @
{
/ l) e' \2 u3 E int i,j;
" \. X5 j9 \$ P/ j# [& R& W for(i=0,j=size-2;j>=0;i++,j--)5 V! A: Z- v' v9 c9 J
 if(str[j]>='0'&&str[j]<='9')" i% q; v% s* L, F
 p=str[j]-48;. b" _! y( S; \$ ]% y& r, K& k9 R
 else% f* ~* Z; f0 ~5 h: n- b: M& ]
 {- Y" o7 X7 b8 f; P
switch(str[j])
 y+ S. m' U$ Z, w {1 U* Q# H+ r: X$ N0 Z2 {
 case 'A': p=10; break;6 @+ R- N- H3 w# V' O2 l9 s# Q
case 'B': p=11; break;4 ~2 q" A# i' ^' t
case 'C': p=12; break;
; S7 ~: g5 h- b. ]+ ^ case 'D': p=13; break;- P n2 T& H$ R7 r9 k+ L
case 'E': p=14; break;" \& @ x8 }% U2 D. T( |% @$ X: W
case 'F': p=15; break;
( {4 Q/ j2 ] A5 J% {/ l8 t }
$ F; e; h+ T( e% f$ v }- y; ]( J$ C/ t* S. B
}
! {$ Y! F4 \& i4 M9 J<>void add(int *p,int &m,int *c,int k)//将一个数同其倒置数相加9 I+ d3 H& J1 D" O% h( S# y
{4 y, o/ Z2 l5 l& S: @
int i,j,a=0;
9 ]7 d6 s- E. J for(j=m-1,i=0;j>=0 && i<m;j--,i++)
; e6 X6 z9 h1 G/ v/ u$ P7 I {
# N# G& N- k4 j- a7 L8 x c=p+p[j]+a;
8 E0 j( y9 f$ W+ s! r" P a=0;
) k9 O" x+ x' @2 G7 T if(c>=k)
: P9 d% J5 |# F6 p! c {5 A, z0 ~2 f! ~# ]
a=c/k;
' d0 z7 \: a/ a! }9 s- G c=c%k;/ m. Z2 @' y, q# V
 }
4 C$ M M# r- W9 [ g }
2 ^/ p( D+ {, ~1 _8 J% U if(a!=0)" t# s* N- d- d: P! f: R
{1 ^- P* c- V% C
 c=a;, i. ^* U) i2 h0 J8 p$ x' G! a
 m++;: f. t8 p) c$ v3 A. L% v
}8 N$ S$ M, l4 k& y7 j
}
. Y( ?8 `/ Y# W6 {1 R* t' v<>bool match(int *a,int n)//判断是否为回文数
# u7 Q7 b% f: j+ J5 _$ e{! f% Z6 i0 q( R4 _
int i,j,h=0;9 v- e) t0 s" u# I8 p+ H p
for(i=0,j=n-1;i<=n/2 && j>=n/2;i++,j--)
9 n$ \) I5 P. f3 j {# a3 P3 K o2 i' p
 if(a==a[j])# F/ W* e/ b. i6 K1 p9 m6 x
continue;% x7 n% ]2 B( e* @' Q+ ^
 h=1;5 z7 m& g1 ]9 s4 h) |. C& K: D
 break;
3 f/ }" Z! S5 \1 B7 J }
: f& w1 K$ } k, A3 J if(h==0)
. d& E, H( A6 W5 T/ `- g8 M return true;1 s8 ?5 D! S; B- G2 ?3 H5 Q( k
else
7 B6 H9 Y* V4 d0 \. g" B4 k9 A return false;
/ a( W+ I, J/ ~# X; W, E}
9 n5 x2 K5 Z2 J9 i//clock_t start,finish;% N+ b: Z( g% L/ Z; ? B& d; E
int main()+ q6 u: g5 N" F
{//start=clock();/ n" J. x' P3 E; v* a
if(in.fail())
9 w0 ]0 w1 x3 y! ?& Z {
9 S0 M" }2 Q7 E+ W; k: T0 a cout<<"the input.txt is not exist!";
/ w5 H: C0 F x. M2 ]5 w7 X exit(1);
3 I3 v3 d0 j) y }
6 r U# @! }, A; h: b; y String s,s1;& T5 Z# x4 u# ~) `
int n,g,k,*a,*c,m,h=0;
! h) E) S' q2 i/ p" u in>>k>>g;
' n4 p! T \% i# @! d5 F s.get();) p% X2 I4 ?5 F& C& B! g s# B

. C7 f- n, M; S. p! o' ?8 g n=s.length();
% }# n# L& C- I- g3 u+ ^; l2 u m=n+g+1;' q+ Y; f2 a0 i8 u. v+ [7 r3 f; e
a=new int[m];& Q$ b2 l+ ^4 ^/ k/ o4 q& h g
c=new int[m];! p& R0 R% f! J5 E/ X5 W
s.get(a);
! S8 ?$ V3 U$ _ if(match(a,n)). i9 N ] A3 S3 D
{
/ ~+ ?+ y( h2 r: c out<<0<<endl;5 Q% }5 H* ]2 y2 P( B4 J
 s.display();$ |. s3 O3 ^5 V, D
 return 1;6 `6 B0 p9 `- o) z
}
0 A" e7 E2 [/ n5 v& U do$ d! a% w( {& w! R4 H. d d
{% C: ^. o6 L" n8 b
 if(h%2==0), X; {( ?2 @4 S5 s
 add(a,n,c,k);
7 G) W6 @! T1 N Q/ E else
) F' J- P8 B0 v0 Z0 x5 ?$ E add(c,n,a,k);3 o" }3 [1 O4 v
 h++;; {, D9 z# D9 u' l' _6 M; J- J2 o
 if(h>g)0 m+ o4 E- p9 C7 V( X
break;
- o( b& p! o; T* X" o8 [; T }
6 ?+ ]% t, O6 d5 p$ Z while(!match(a,n)&&!match(c,n));
# @7 `& q1 s l if(h>g)" l t" P' [8 G" X! z6 {
 out<<"No Solution!"<<endl;6 }, b- d2 D: K% ?$ \" K3 J
else! o/ f' n6 o$ p
{
( z2 u7 n1 j! l2 i0 l# N7 | out<<h<<endl;
 q1 q; P, L# y. s if(h%2==0)
2 c/ u3 P6 I/ y/ v s1.change(a,n);
! e/ V6 A! H1 J/ L) ?, C, c# ^& p else; V- Q3 O P/ J' y. P5 t
 s1.change(c,n);
: Z; V) v% D; M9 y( o s1.display();6 x `8 B/ j# O+ y
}- b; k( B$ u0 Q% K( D2 Z! j) V
delete[] a;8 ~# s. S2 e) N7 M) m+ u
delete[] c;
 G5 f3 V* T; v; z* q// finish=clock();
3 A+ i' s# L2 s. f5 \// cout<<finish-start<<endl;
# ^! ?$ e* y' d( F9 v7 g. S return 1;0 u0 B% s0 B, f' k, N. E
}
作者: txj66 时间: 2005-8-22 02:00
<>谢谢
作者: zxl_lucky 时间: 2005-8-24 17:02
<>谢谢啊啊 
作者: sabbanji 时间: 2006-11-21 04:52
　　一个指针从头向尾走，一个指针从尾向头走，至多走到两个指针相遇或相错，就可以检查出是否为回文了。上面的代码怎么弄得这么复杂？
作者: darkghost 时间: 2006-12-11 01:57
我觉得用堆栈也可以实现吧，先将各元素压栈，然后将其中的元素复制到另外一个栈中，再出栈比较。 呵呵，可能还要麻烦，没做过。。。 
作者: mustpeter 时间: 2006-12-12 16:42
回文是什么意思？
作者: zhuph 时间: 2006-12-26 09:11
有没有汇编写的？
作者: hero1632 时间: 2007-1-2 18:08
不错，正在找
作者: friendfb 时间: 2007-1-6 09:09
设计算法的时候，应该充分考虑时间效率和空间效率！但是两者往往也是互相矛盾的。一个好的算法可以应该权衡这两个方面；或者更加特定的需求来设计算法。在我的记忆中，回文是需要考虑标点符号的吧
作者: zhaoyunfei1126 时间: 2007-4-7 11:50
什么啊？？？
作者: seashell7 时间: 2007-4-12 17:39
3Q~ ~
作者: hanyeyu2009 时间: 2010-12-5 11:01
看看是什么
作者: zengshengda 时间: 2011-1-30 21:52
很强大！！！！！！

欢迎光临数学建模社区-数学中国 (http://www.madio.net/) Powered by Discuz! X2.5