数学建模社区-数学中国

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

---

作者: lynnyan    时间: 2005-4-22 01:27
标题: 回文问题（用c++编写）
<>#include&lt;iostream&gt;
#include&lt;fstream&gt;
#include"string.h"
//#include"time.h"
using namespace std;
ifstream in("input.txt");
2 h1 u' ]1 Y8 G0 P1 A9 gofstream out("output.txt");
class String
% i) p7 C+ n% |2 X$ P{
# l: |0 z1 g" ^8 Mpublic:
String(char *s="");
5 @: R# Y, I  c8 L String(const String&amp; s);
: |% @. P$ R3 `9 _+ P' z ~String() {delete[] str; delete[] pre;}
String&amp; operator=(const String&amp; s);
" X9 e- I/ d" [, f$ N- z, w+ W3 n int length()const {return size-1;}
3 G! g1 }1 z: Z$ Y& Y int get();
String&amp; change(int *p,int n);
8 ~9 ?9 @  |0 W# n5 G void get(int *p);
void display(){out&lt;&lt;str&lt;&lt;endl;}
5 O: s/ ~; \- Oprivate:
char *str;
    int  *pre;
: C6 q7 ?4 F6 b% E4 g* z% l" @ int  size;
};</P>
<>String::String(char *s)
5 h; M8 o+ K& q4 q4 `7 T3 i$ P{
' G8 C& c6 g* `+ R5 \ size=strlen(s)+1;
str=new char[size];
2 S: V- ^. z0 u$ M  S; a if(str==0)  throw "error";
strcpy(str,s);
pre=new int[size];
3 k! w: w( Z" p$ n+ R' C if(pre==0)  throw "error";
9 u; W1 a& b2 Q+ S}</P>
* |+ N: A1 T8 m5 E6 n5 E. t6 q<>String::String(const String&amp;s)
9 S/ I3 u) S% E9 e, H4 e0 I* r" p{
+ w/ f( f# r; q1 v  m size=s.size;
* h) ]* f, K3 P9 |/ x+ {, V; Z str=new char[size];
if(str==0) throw "error";
2 `7 t4 K7 T) j8 G& o strcpy(str,s.str);
2 D3 Y. `- [- ^- [6 a pre=new int[size];
& j8 A% p7 T" r5 s" L+ D/ e; \ if(pre==0) throw "error";
}</P>
<>String&amp; String:perator=(const String&amp; s)
{
* U, d2 s( i. B/ N% ] if(s.size!=size)
{
  delete[] str;
6 c4 O$ S7 C4 ]" A5 n  str=new char[s.size];
  if(str==0)
6 g  C. g( A5 {# \: }   throw "error";
  size=s.size;
}
strcpy(str,s.str);
return *this;
}</P>
<>String&amp; String::change(int *p,int n)//将整型数组改成字符串
, |6 k3 x$ ^- V) {2 h{
6 p  H- h+ N) u int i;
delete[] str;
str=new char[n+1];
for(i=0;i&lt;n;i++)
  if(p&gt;=0&amp;&amp;p&lt;=9)
   str=p+48;
# }9 N" `. W0 x. u  else
5 @. K" t  A2 u" {! b   switch(p)
   {
       case 10: str='A'; break;
$ ?! g4 B" b+ r6 J% n1 E1 w    case 11: str='B'; break;
    case 12: str='C'; break;
       case 13: str='D'; break;
    case 14: str='E'; break;
( j" t% M8 q5 o2 t( s* j    case 15: str='F'; break;
+ E2 e2 S8 E- u- X( ^% W   }
# r! [# c" Y: j! v0 ~  str[n]='\0';
  return *this;
: c6 o# f9 f: X+ e* V}
int String::get()//输入一个字符串
{
# E: {5 L$ |; G) ] char tmp[40000];
in&gt;&gt;tmp;
  {2 [4 L3 v8 N2 x7 v% L/ @ delete[] str;
size=strlen(tmp)+1;
str=new char[size];
if(str==0)
  throw "error";
strcpy(str,tmp);
$ ?- k. X9 _& M9 j0 b+ h; L return size-1;
  g* b- Q/ {9 B& K. J6 k3 p+ N}</P>
<>void String::get(int *p)//将字符串改成整型数组
1 J$ ^* A& T9 ]' ]6 B{
( B. `" t' P7 S/ Y' j int i,j;
4 Q% ?/ g: z8 J+ a for(i=0,j=size-2;j&gt;=0;i++,j--)
- B3 D, c* z8 s5 m8 Q" a8 |  if(str[j]&gt;='0'&amp;&amp;str[j]&lt;='9')
  X4 t3 M6 O+ B& Q      p=str[j]-48;
  else
  {
! X- X$ ~1 |9 @* f' K# x   switch(str[j])
   {
       case 'A': p=10; break;
- T  V& Y& G, O6 a) P! o3 d" [    case 'B': p=11; break;
+ a6 y3 z, n4 K! u/ J$ L8 Z4 @$ N    case 'C': p=12; break;
0 k+ l2 B3 ^7 v9 C0 h* |4 q9 g# [3 R+ @       case 'D': p=13; break;
5 z/ u) L* }2 d' d: s: U) V( A    case 'E': p=14; break;
    case 'F': p=15; break;
9 n% @+ H+ H3 c+ ~6 z   }
  }
}</P>
& k# y3 v; W  {1 |4 t, k( B<>void add(int *p,int &amp;m,int *c,int k)//将一个数同其倒置数相加
* N4 k' z& K: p% S0 i8 N{
+ m, X! j6 P7 m' [ int i,j,a=0;
% F0 n1 s2 }9 ?    for(j=m-1,i=0;j&gt;=0 &amp;&amp; i&lt;m;j--,i++)
{
     c=p+p[j]+a;
. }4 B# N& P; y4 b2 u1 m9 \  a=0;
3 S# D' b1 Z( D& ]* I6 q+ o  if(c&gt;=k)
% q) A: w! w6 K0 p9 B9 _+ ?  {
   a=c/k;
   c=c%k;
  }
}
5 S- c+ t) i( s) E if(a!=0)
{
0 r  A& {4 i) D- R9 K  c=a;
. n  v0 a* E7 k% v- e+ {# u  m++;
( L- L7 j5 r- k7 {4 }# C; E& _ }
/ w% l: V) G9 G7 X& B}</P>
% w% g  d3 H0 z0 Y- _2 S0 ]- V" D  M" P! A<>bool match(int *a,int n)//判断是否为回文数
{
# Y& @* I! \) q$ M6 i" Q int i,j,h=0;
3 O5 k4 O- X" ^( E, z$ ] for(i=0,j=n-1;i&lt;=n/2 &amp;&amp; j&gt;=n/2;i++,j--)
{
& s0 D: ?2 Z- Q6 g( x  if(a==a[j])
6 }2 N& }5 d3 W1 G0 e   continue;
        h=1;
  break;
. y; R6 n$ ~) T6 k9 E$ A }
+ Z4 U$ r# h; J: F; b; i if(h==0)
  return true;
else
  K, _( B3 c0 \2 n: r% w  return false;
- B4 i+ v6 Y) B}
2 b$ Q; E) J4 q' D, h//clock_t start,finish;
int main()
* L' b4 A$ ]  Q- U{//start=clock();
) \  ~$ ~8 L- ` if(in.fail())
{
  cout&lt;&lt;"the input.txt is not exist!";
% L9 y  Z# L0 {2 Q; i  exit(1);
% I9 U: s) B1 V* `0 d5 y }
String s,s1;
int n,g,k,*a,*c,m,h=0;
    in&gt;&gt;k&gt;&gt;g;
, [1 x6 A: s7 N8 h( l! a+ E( E    s.get();
) d6 l# f: Q; C" m4 B' v- p1 T4 O4 M: a( p
    n=s.length();
' t8 c0 W; U/ x' m" Z m=n+g+1;
; |+ x' x2 z/ \' c3 u$ L a=new int[m];
c=new int[m];
/ K" T: d2 r: y. J& f; ~! W7 A- t' Y s.get(a);
if(match(a,n))
{
  out&lt;&lt;0&lt;&lt;endl;
  s.display();
0 T/ ~% v+ r' _: X3 q" T7 K  return 1;
( I8 s  N0 W  }+ ~$ t  R1 a: F }
% @2 {; F& R0 Q. N do
{
. j7 v5 }: C2 L; M/ k     if(h%2==0)
      add(a,n,c,k);
0 _, S* D0 w1 [) D0 ^" u' a  else
   add(c,n,a,k);
  h++;
  if(h&gt;g)
% S+ L$ K5 \$ D' N; @) ~   break;
}
" C5 T: `! d8 Z; f3 L! ~ while(!match(a,n)&amp;&amp;!match(c,n));
- f8 a: I( _& H$ R" V0 X if(h&gt;g)
     out&lt;&lt;"No Solution!"&lt;&lt;endl;
7 X4 v7 [5 d5 W* P% W: A: G/ v else
{
      out&lt;&lt;h&lt;&lt;endl;
; @3 h/ J0 B( @& Y0 V1 _8 z     if(h%2==0)
      s1.change(a,n);
! U  u% H5 m+ c/ \, [     else
6 `2 F( k9 p1 w9 L- v) \, L      s1.change(c,n);
     s1.display();
- d* C6 ^5 B% [$ |: h }
6 N8 D  ^- F8 \' G delete[] a;
) [; @' U6 w9 f/ I delete[] c;
// finish=clock();
$ T  ~* p1 w7 y/ ~* m* @) Q// cout&lt;&lt;finish-start&lt;&lt;endl;
  n: J3 P% J* z: i return 1;
}</P>

---

作者: txj66    时间: 2005-8-22 02:00
<>谢谢</P>

---

作者: zxl_lucky    时间: 2005-8-24 17:02
<>谢谢 啊啊 </P>

---

作者: sabbanji    时间: 2006-11-21 04:52
　　一个指针从头向尾走，一个指针从尾向头走，至多走到两个指针相遇或相错，就可以检查出是否为回文了。上面的代码怎么弄得这么复杂？

---

作者: darkghost    时间: 2006-12-11 01:57
我觉得用堆栈也可以实现吧，先将各元素压栈，然后将其中的元素复制到另外一个栈中，再出栈比较。<br/>呵呵，可能还要麻烦，没做过。。。<br/>

---

作者: mustpeter    时间: 2006-12-12 16:42
<p>回文是什么意思？</p>

---

作者: zhuph    时间: 2006-12-26 09:11
有没有汇编写的？

---

作者: hero1632    时间: 2007-1-2 18:08
<p>不错，正在找</p>

---

作者: friendfb    时间: 2007-1-6 09:09
<p>设计算法的时候，应该充分考虑时间效率和空间效率！但是两者往往也是互相矛盾的。一个好的算法可以应该权衡这两个方面；或者更加特定的需求来设计算法。</p><p>在我的记忆中，回文是需要考虑标点符号的吧</p><p></p>

---

作者: zhaoyunfei1126    时间: 2007-4-7 11:50
什么啊？？？

---

作者: seashell7    时间: 2007-4-12 17:39
3Q~<br/>~

---

作者: hanyeyu2009    时间: 2010-12-5 11:01
看看是什么

---

作者: zengshengda    时间: 2011-1-30 21:52
很强大！！！！！！

---

欢迎光临 数学建模社区-数学中国 (http://www.madio.net/)

Powered by Discuz! X2.5