数学建模社区-数学中国

标题: 回文问题（用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)
( W, E1 ~5 y) J7 k% o. q) l/ M str=p+48;
3 R! J" _# w P* D1 r else+ }8 j$ |* c3 q4 ]8 w
switch(p)
" h9 d9 j( y& O! E" x7 a+ x {2 `4 Z8 ?9 V5 M5 W9 M0 u
 case 10: str='A'; break;/ l. A1 w- @) {9 ?- `! j7 N( J& V4 }
case 11: str='B'; break;( |+ U0 I7 Q |; Q) S, P' w
case 12: str='C'; break;
5 C8 H' ], [0 P9 z+ { case 13: str='D'; break;6 t1 A1 e1 d( G" X/ ]
case 14: str='E'; break;
8 j q& ]! y! e. e1 g6 H! D case 15: str='F'; break;! p$ U, _0 O& K( Q; C
}8 s8 W" N( g+ i# k2 w
 str[n]='\0';5 T. P8 q; h2 z8 u* s5 T" C
 return *this;$ z9 X. E- F$ F# a, `
}% f" f/ E! ^' x1 M8 L
int String::get()//输入一个字符串
% X W6 H3 [0 @+ \{1 V" Z; B, }$ c
char tmp[40000];
: [* Q5 t+ t7 [ in>>tmp;
5 L7 X3 {2 ?4 p, N# r" }& q v delete[] str;1 M, J2 F2 G$ r0 ~) s+ H
size=strlen(tmp)+1;6 o& M3 a, K9 t% J7 _# m* F
str=new char[size];
4 i) P/ [5 N' ]" N if(str==0)
1 T, z* s" X- h9 r/ v throw "error";4 E' a: E" _ e. p) @
strcpy(str,tmp);
7 B- y" ^* e. W* H return size-1;
2 i- v/ W3 I+ e+ s}
6 T; A _5 o$ `6 b* g3 Y<>void String::get(int *p)//将字符串改成整型数组+ E a9 ^+ E9 o3 l2 N1 G5 _
{
4 _& }$ M1 z2 R int i,j;. z3 g, F: s! m1 B1 Y- N) d
for(i=0,j=size-2;j>=0;i++,j--); h4 \! N. o4 s% C
 if(str[j]>='0'&&str[j]<='9')
6 ~5 n' d1 Q9 M9 | p=str[j]-48;9 I: y, B, J- p' F5 S! r6 g6 s5 [8 |
 else) `, r" ~' W4 p* Z t4 {$ q
 {" F: E: N y1 `$ Z$ n% u+ D$ [
switch(str[j])
' T+ s; z; k, E( P' M3 S {
! `1 v4 F# e/ e9 Q l$ r case 'A': p=10; break; S5 c9 @7 H/ }/ Z4 S9 H4 T4 K
case 'B': p=11; break;
' X7 x( W+ |! M$ y3 I case 'C': p=12; break;6 H9 x, J/ A; P. r. i! F$ H
 case 'D': p=13; break;; J7 @- i4 M+ R9 L/ S) k$ ]' C
case 'E': p=14; break;: B7 e9 K. b# m0 A
case 'F': p=15; break;
- t& t$ T$ O7 T8 i- v5 q }
8 h8 d% Z- z3 z; Z }
* V( s' n# c& N" O l}* M! O0 E9 s' \
<>void add(int *p,int &m,int *c,int k)//将一个数同其倒置数相加
6 l3 l1 {2 W, ?{: s. y: c4 ^+ h7 k+ p5 P
int i,j,a=0;
; o6 g. z" Y3 x* ]# r: l for(j=m-1,i=0;j>=0 && i<m;j--,i++)
) _ T- x% S9 B: Q& a {
% H' }) I! w6 @- N1 F; M c=p+p[j]+a;
0 ], S2 t: j( e: N a=0;
9 a5 B$ u: D& \9 t; f4 _! [( b% e if(c>=k)* `8 {6 I0 r% e$ P3 K" M0 }
 {, }7 m5 }# q [9 u- h
a=c/k;" q2 d0 D; ~: ^4 t' Z
c=c%k;1 ^7 n" E5 M4 J1 q, n2 s1 Y
 }8 U h: @% \: E4 w6 `! }
} , w1 Z1 \8 ^3 t" f. f
if(a!=0)8 }& e/ V; @: Q' ]; f; p
{
 l4 z0 M5 N7 {9 }! @ c=a;7 |& x% h* F3 i6 }
 m++;
+ o f# v$ y7 \3 a @ }" I, q: b: w7 E* \) E
}/ w4 a( h8 i% z; w4 l+ v
<>bool match(int *a,int n)//判断是否为回文数9 p- ^5 D c I% e T8 e
{
) {0 ]: @8 m# ?, B+ i int i,j,h=0;& k2 M, i) |# h, H
for(i=0,j=n-1;i<=n/2 && j>=n/2;i++,j--)
& p, W6 Q5 J7 [9 m { g- K. t$ s2 M/ ]3 O
 if(a==a[j])2 ?" v- ~) |/ C9 G7 X4 s3 h2 X
continue;) O7 I5 P. z+ C/ r2 A4 J
 h=1;5 d7 c/ Z( J! E2 @' P& e# i2 m, Y
 break;/ |9 A1 f% W1 }; C
}. r0 \# C; C& a M/ J7 R
if(h==0)3 o# B2 u' ^: F$ x0 A1 @* I% T
 return true;3 Z5 u' |. l7 p/ s/ @
else 3 \3 }' @; B% `" p) E3 ?. \
 return false;: q; b f2 B" H
}, M- {+ t {2 |& a
//clock_t start,finish;% H* j) }4 l4 q9 F, h1 T6 G
int main()
' \) E: I! E/ O% q7 I{//start=clock();
; v9 P" e/ U' `' p3 o7 L# m if(in.fail())
; _5 c- O$ E7 A5 b6 S. b {0 x( q6 ^/ z' k9 v u* `! A/ i( @
 cout<<"the input.txt is not exist!";
8 W4 v$ ]- d+ `3 t) V) a7 h* E8 c F exit(1);7 x5 d; |! `" L& A# T
}, H5 O+ Z( ]: p C
String s,s1;
+ S% l6 d. a2 j# q @' ~ int n,g,k,*a,*c,m,h=0;
; L C& A! C" ^ in>>k>>g; $ U: }" a5 z Q1 R* N* L$ U7 ^- o
s.get();
- b- K; V$ x4 R+ ?: i) f9 L 9 ?5 y7 ~) c( B
n=s.length();9 s$ f' J( k6 m
m=n+g+1;
7 W* C* z. n8 m3 T) q c a=new int[m];
, ^& }* i7 G H. ^; C8 ]5 M c=new int[m];6 l" u. v" P. a& F) w! y. K1 Y
s.get(a);
* {/ Z# X0 D% X! C- g' k$ y% {* I if(match(a,n))! M# a4 D& O& G2 J( e
{
2 y" d; h+ G& D out<<0<<endl;
6 s3 t! N I$ E, b s.display();
, Q0 D: q! Q2 P' c! w! B return 1;
3 H/ E1 b/ a: ^$ w. r4 { }; Q+ i7 I7 j# n* E! D7 q: B
do
) `# W9 X% d4 m- \' B$ ^ {3 `, s% Z. T: r0 t0 ]% N+ r
 if(h%2==0)
' ^5 e" E$ U: _$ Q. `. C add(a,n,c,k); p# c+ R( p$ f6 z6 x3 s9 B
 else& l( N6 q4 @# j* O" o2 X
add(c,n,a,k);
, b5 F6 L: M" K, y" z" S8 F Z h++;5 a$ g: k1 C' n) y: C& g E6 h
 if(h>g), ~2 W5 I' @* y! {
break;
- ? p' i7 R2 ^5 T }
5 b8 \& L1 Q8 Q4 a3 x5 c+ E" i0 e while(!match(a,n)&&!match(c,n));& i* F1 M0 y S8 M5 I% @; w
if(h>g)' y; J. n" }8 b; O# d
 out<<"No Solution!"<<endl;/ _: v" M) h2 O/ i1 o
else
- D5 J v1 e) Z p5 b { H, O. S/ _4 e% B0 m
 out<<h<<endl;: G- F% E6 ^1 N3 D! K7 l
 if(h%2==0)
% L) c* X& w v/ j) ^ s1.change(a,n);
7 H( s: Z3 j8 H% D* \7 s( u6 l else
+ ?0 y4 z7 G6 b% V2 H% f# F s1.change(c,n);6 Y$ ?4 W+ ?9 u0 A$ h" L0 i9 m# u
 s1.display();
2 u& ]" [/ H. n- s0 ^8 A. X# t }
5 R( B; Q2 b" X3 C6 u- I delete[] a;9 Y/ S( n6 U9 `) P
delete[] c;8 R& n" I* r5 A
// finish=clock();
0 i6 F( C; \( e: U5 e- I// cout<<finish-start<<endl;
% d6 S1 P+ t" R1 e6 ^1 a return 1;
5 F2 Z) f: ?) X2 i* e4 [5 ?}
作者: 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