QQ登录

只需要一步,快速开始

 注册地址  找回密码
查看: 6505|回复: 12
打印 上一主题 下一主题

回文问题(用c++编写)

[复制链接]
字体大小: 正常 放大
lynnyan        

2

主题

2

听众

26

积分

升级  22.11%

该用户从未签到

新人进步奖

跳转到指定楼层
1#
发表于 2005-4-22 01:27 |只看该作者 |倒序浏览
|招呼Ta 关注Ta
<>
游客,如果您要查看本帖隐藏内容请回复
#include&lt;iostream&gt;
; c- _) C4 g% ?& ]. x. k: O* ~/ I#include&lt;fstream&gt;
/ |  Z- L5 A% H+ r5 I$ P3 R  j#include"string.h"
$ B# J( e  }3 A0 l8 M//#include"time.h"! Z3 W/ V, Y* {0 P" _' E
using namespace std;8 x+ ]7 ?) I% D% o$ z
ifstream in("input.txt");0 s. d5 |1 K9 k% ?0 Y6 c8 W
ofstream out("output.txt"); " C+ X* U) q' O$ w
class String
4 x* |+ `' R4 ^% h{
; |8 n9 N) P/ o2 Epublic:
0 [) O; Y& R- j. X. t( C String(char *s="");& {& I4 ^/ [1 V" x( R; ?$ E
String(const String&amp; s);
6 C3 q4 O( \5 T* k0 u ~String() {delete[] str; delete[] pre;}
& u9 _9 G# C* I9 m: G# E String&amp; operator=(const String&amp; s);
, K$ ]# K2 w" A' Q+ f int length()const {return size-1;}
4 O* O4 M; k, k$ Y int get();
. ~: N  l' T% b8 y& `2 d String&amp; change(int *p,int n);6 @7 W5 y, M# j7 a" P
void get(int *p);* ~# H% f" A8 [
void display(){out&lt;&lt;str&lt;&lt;endl;}
; ?! [' O7 |1 y2 U, Rprivate:
5 C, y' i* a" X& p char *str;
. H( c& ]6 H( I$ X/ g1 V    int  *pre;
; ?  D% z7 _+ f4 o) A: g0 x int  size;
1 j# @' a; U. ]7 p};</P>
* m6 T6 d$ d; }9 ]# i! a<>String::String(char *s)
& w. C: H4 _- Z# g{% R8 b+ n3 S2 B8 o/ [" y
size=strlen(s)+1;8 \  n; e3 p: V% c8 f# {. F
str=new char[size];
# }2 U, h1 W. d" ~3 `$ Y' h; h& Z5 `. ~) q if(str==0)  throw "error";
9 k: ?, V+ ~% e7 k3 x, _ strcpy(str,s);
$ ]  c7 N/ u1 \; i. x pre=new int[size];
; G2 R! F9 i, o- z; n if(pre==0)  throw "error";- _6 J' k/ ~# e6 E' v: F
}</P>
+ t8 B" M" P# P6 V/ T' G$ b<>String::String(const String&amp;s)
. Y! T0 [! `8 i  G! C1 ]$ Q" i{
/ c" a+ Z& ]" S! N4 i size=s.size;  x  h3 d' Z: ]2 s5 E+ y2 R' A
str=new char[size];* m* q( c$ N9 @! s9 F" k) L7 b
if(str==0) throw "error";1 z5 m& b7 c8 @- [- i, e
strcpy(str,s.str);9 b7 t* h; `2 B
pre=new int[size];
, W$ i3 s+ {2 m4 t if(pre==0) throw "error";5 ]' Z# w$ h! D# s; d
}</P>, ~& A# T: x4 C/ G4 X0 C8 x
<>String&amp; String:perator=(const String&amp; s)
5 P' a$ o8 q- ]5 W% s! E4 \{
1 Y. l; c) a/ S! {; L. @7 T5 ]" @ if(s.size!=size)
) `: K3 H6 F2 n) ~ {1 `+ g3 a+ r2 N$ Q  h6 a1 Z
  delete[] str;( b" n. f3 }, y: b. L* R5 d4 N+ B
  str=new char[s.size];
# q3 j2 d. k5 K, _1 ]8 e  if(str==0)1 `, Z( l2 P3 |4 G( k
   throw "error";( e5 [6 l' Y6 E& w/ E6 I' m0 m
  size=s.size;3 N5 E$ e0 E. E  \  t
}9 K5 e* w$ Q! A  ?  E- \4 b; ?& J7 k
strcpy(str,s.str);# x6 U  c9 T6 i" b7 s
return *this;
4 ^! {; u# D! L4 X  `( Q/ H$ X}</P>
% Z, J2 h9 H' G* D" T<>String&amp; String::change(int *p,int n)//将整型数组改成字符串
! I+ R0 @4 Q2 f) z# Z+ W% X) K4 z{4 m6 A+ q- o/ o! v/ y4 b1 _
int i;5 W& V& @+ j$ U1 k1 G: Q" I1 h7 ^
delete[] str;3 \2 _1 [* O& K
str=new char[n+1];
+ u4 K1 n; O! k# S, e+ Q# U# Q1 f for(i=0;i&lt;n;i++)9 m4 L2 [! h; I* G/ ]& n
  if(p&gt;=0&amp;&amp;p&lt;=9)
8 D1 r* r7 r- G/ m: x6 K   str=p+48;
- M$ |3 D" n# p5 Q3 C  else
/ t; K5 j, V( P6 k/ P9 @, X   switch(p)
8 c+ L$ j. i+ v8 P4 [8 M6 `* U" F   {! z5 e! J6 d3 S2 t5 r
       case 10: str='A'; break;
! _1 ?9 l( `5 ?* E; y    case 11: str='B'; break;
" y; ^9 H5 N. M9 F+ a- T! i3 ^    case 12: str='C'; break;2 X2 c: a8 \( p: S* b7 d
       case 13: str='D'; break;' l; l8 j( Y& f, g" v2 S& T
    case 14: str='E'; break;
3 l0 X" M! y8 A, n: n7 z    case 15: str='F'; break;
2 H8 s* M) X7 ?" B   }- Z9 s; T1 T8 o' W$ {" e
  str[n]='\0';' b) a/ y- h' I8 }- N8 G9 j$ I
  return *this;) t& U, N8 g: Z. W" P: I
}1 {( K0 ^4 a' }4 A) r0 v( M. r; s
int String::get()//输入一个字符串1 \4 _: ]% v9 N' k
{
& V3 k3 X7 ?" G2 a char tmp[40000];
% r+ \9 u  z9 {3 y in&gt;&gt;tmp;
; B( T6 |* e7 }. R  K7 Y6 F3 P* g delete[] str;  n, B' H9 `& H" P4 B! k  T
size=strlen(tmp)+1;
4 a/ u9 J  X' u1 K+ Z1 m! y str=new char[size];& {5 d7 i* b% o: ~  c1 J
if(str==0), V! ?1 f) `1 }0 C7 X6 ]% D
  throw "error";
+ A6 @7 i  P6 Z5 X strcpy(str,tmp);( j4 I8 C/ T( d
return size-1;
0 _" F) A6 w, f0 {}</P>1 \9 r  u0 z4 {$ R6 J/ E1 p7 B
<>void String::get(int *p)//将字符串改成整型数组6 P3 B, E9 {  ^1 o
{
- g) c; P- o  h5 `7 \- Z1 l2 c int i,j;
8 U/ k& ?9 h: ?! g: } for(i=0,j=size-2;j&gt;=0;i++,j--)) K1 ~) t% `- q% d
  if(str[j]&gt;='0'&amp;&amp;str[j]&lt;='9')% G7 P  u# Z9 X9 ^5 }/ i
      p=str[j]-48;
' R1 {, e" P6 e0 B6 X  a3 f! f  else
! r4 v. S( ^' O7 T2 ]  {
/ @; }- o6 Z! L+ A5 ^! V   switch(str[j])
+ m; R  c6 [6 }4 E* `   {
# \7 S( g8 a+ m, m0 n       case 'A': p=10; break;+ N4 i8 r# o7 S2 I2 e3 n
    case 'B': p=11; break;
( Z% q' g2 `6 {    case 'C': p=12; break;! m) `3 Q8 [# s+ T+ o8 V
       case 'D': p=13; break;
* L" U  o2 {% h* H/ s) a, a/ C! z) t/ W    case 'E': p=14; break;
  |  Q0 F. G. B/ `    case 'F': p=15; break;
# F2 ?1 J/ G* i1 H4 ]+ Z   }
' D) q/ F. G2 {9 s9 J- ?( |2 N  }# U7 x$ I& i* }. O3 ^) t7 O
}</P>& f3 C0 Q, W) m3 z0 P1 W+ U
<>void add(int *p,int &amp;m,int *c,int k)//将一个数同其倒置数相加
8 p5 h& W  T# p' Z& H' J1 Q{
$ l4 [! Q* Y5 H/ Q# c) [8 } int i,j,a=0;+ ?, \4 R! h& w1 s6 ^+ V
    for(j=m-1,i=0;j&gt;=0 &amp;&amp; i&lt;m;j--,i++). x  B5 L/ B  y1 @' g8 F
{
1 ~- J: e" z0 u$ s     c=p+p[j]+a;2 T( `4 Q# [+ E
  a=0;
% P. {' k. P& J# B4 ~. c  if(c&gt;=k)+ ^6 z. u! T2 |7 y+ S$ s
  {, U* i9 P; |! w" j* X
   a=c/k;& p. P2 E4 L! ]. k6 L
   c=c%k;9 z7 y, P& K5 @/ ~7 x* M! L  R3 t
  }. Q+ d4 u% z8 i% Y3 \) @. h
}
1 l$ I8 \+ l7 u4 K4 e8 S if(a!=0)
4 h% H7 u* J0 x {
5 }4 z  |6 G1 Q1 ]5 t# j; i  c=a;# `% Z( l! l4 E9 X# {
  m++;# K9 Y+ P3 @2 ]
}
1 y9 I2 t/ z5 i, Q8 n: L}</P>: j- n) j, f( l. R
<>bool match(int *a,int n)//判断是否为回文数
. F  R, J2 O1 ^/ V{
! x% ^  D% d* A# o int i,j,h=0;  d* Z& V3 D+ R
for(i=0,j=n-1;i&lt;=n/2 &amp;&amp; j&gt;=n/2;i++,j--)
- s: U: N- o- \% Q8 n- G9 C+ [  Z$ V9 I {
/ L8 `) t' |" x& G# P  if(a==a[j])
# O6 h& E  c7 a+ M   continue;
. a* z% b+ ^$ c0 R9 s        h=1;% Q. Z5 f# p9 W7 ]. k
  break;
4 ?2 Y* X5 |6 H7 U6 k }" Z2 y7 W% a* p- r2 p8 p. q3 M
if(h==0)7 b: D. @' h# k0 R! P
  return true;3 p4 s8 F0 N( S  P7 s
else 8 z" o* [1 m( F% F/ F7 e
  return false;
8 R. I  X( v7 ?, w* J}) J) e4 V$ J- |9 y
//clock_t start,finish;4 {  ]' P% h' q0 V7 Y/ D  i
int main()
& \, N' J8 z! L: Z( B5 V{//start=clock();
9 E  `; ]& d* X8 w if(in.fail())
9 o& r# ?7 p3 d6 I8 Y( V {+ o& b4 Z. u8 Q. h) c& R' s
  cout&lt;&lt;"the input.txt is not exist!";
/ l! K  L" b' c/ {& Q# z  exit(1);, c% C) h$ G4 ^. z! f  X
}  `7 r/ n5 ~0 {1 V+ Q( h
String s,s1;
7 P# @4 Y9 |# t: \ int n,g,k,*a,*c,m,h=0;: f# p. k' Y: j  e0 H& L+ s
    in&gt;&gt;k&gt;&gt;g;
- ~6 Y# {. d1 s" i    s.get();
# x6 H9 G" `  G9 V1 G# f: d% K ; {! i/ Y4 E' G7 [
    n=s.length();  N4 d* v6 S* T1 K0 s4 G' q
m=n+g+1;' y% X" K: U0 T# m& H
a=new int[m];
! r' D, E* b7 ]6 d' K5 V c=new int[m];  m, w. K( x1 b' \  z
s.get(a);
' K  H8 }4 B: s if(match(a,n))
2 ?) L  {9 p/ q" K# o2 q {4 G1 J9 v5 C9 u# X8 p- Q# x
  out&lt;&lt;0&lt;&lt;endl;
# A% u2 M) A  \; `1 L# S  s.display();6 h7 Q( O- p) G1 Z' u3 F
  return 1;
0 u2 P' f0 H6 E3 v6 k# i6 r' g }
- Q9 H6 K7 _0 z: I3 B$ B do; s, c0 G9 s  z- y  O3 a
{
* ~  h) Q' e8 ~: n, _     if(h%2==0)
  }; ?! K, \  b! ]      add(a,n,c,k);% T* `" c- z5 }2 g9 o- F
  else
' p$ w+ R; `+ @+ u+ N  M0 R   add(c,n,a,k);
$ x9 B4 O- Y& V0 X2 Z% F2 P9 J# ?  h++;' R. P- v) S* a, Y5 |# L/ N9 D
  if(h&gt;g)
# t& N9 i9 K7 r% f& m2 G" Q2 w   break;$ h( D4 V4 z8 \- L& u, w. ^0 S7 ~, ]0 r
}
& L! G8 g- E' e while(!match(a,n)&amp;&amp;!match(c,n));
. s  a2 w  c1 p, M; h if(h&gt;g)
, w! V) i8 T+ Q- d1 g, N     out&lt;&lt;"No Solution!"&lt;&lt;endl;
/ w9 C8 g% x5 I# ~+ b else+ F2 Y( ]7 `5 D1 F9 J& I% @
{; |* d4 x1 k- D
      out&lt;&lt;h&lt;&lt;endl;
- n! q0 ]% i0 y; Y) Q     if(h%2==0)
4 W+ G+ Y& b+ ^9 \! e0 M/ x2 \: G      s1.change(a,n);9 E/ H( V" |, I, r2 K
     else
- {9 e+ s' l3 h5 f, X- e      s1.change(c,n);6 Z2 M  o! F, X
     s1.display();
+ y9 g  N+ A+ _" L }! W1 X3 ]$ D; S; X! P
delete[] a;
; T/ v- `1 |- r9 \5 r delete[] c;
& M) `7 s9 D. J% E. e# a// finish=clock();
7 B! v5 E# O( z3 |) y, z// cout&lt;&lt;finish-start&lt;&lt;endl;  t& e( L7 }4 ^4 M1 \
return 1;
' ?* J/ |9 q# Y2 r% D}</P>
zan
转播转播0 分享淘帖0 分享分享0 收藏收藏0 支持支持0 反对反对0 微信微信
我相信今天的埋头苦读是明天的出人头地
txj66        

2

主题

2

听众

42

积分

升级  38.95%

该用户从未签到

新人进步奖

回复

使用道具 举报

zxl_lucky        

15

主题

2

听众

66

积分

小木屋

升级  64.21%

该用户从未签到

新人进步奖

回复

使用道具 举报

sabbanji        

0

主题

3

听众

21

积分

升级  16.84%

该用户从未签到

新人进步奖

  一个指针从头向尾走,一个指针从尾向头走,至多走到两个指针相遇或相错,就可以检查出是否为回文了。上面的代码怎么弄得这么复杂?
回复

使用道具 举报

darkghost        

0

主题

3

听众

22

积分

升级  17.89%

该用户从未签到

新人进步奖

我觉得用堆栈也可以实现吧,先将各元素压栈,然后将其中的元素复制到另外一个栈中,再出栈比较。<br/>呵呵,可能还要麻烦,没做过。。。<br/>
回复

使用道具 举报

mustpeter        

0

主题

3

听众

23

积分

升级  18.95%

该用户从未签到

新人进步奖

回复

使用道具 举报

zhuph        

0

主题

3

听众

21

积分

升级  16.84%

该用户从未签到

新人进步奖

回复

使用道具 举报

hero1632        

0

主题

0

听众

17

积分

升级  12.63%

该用户从未签到

新人进步奖

回复

使用道具 举报

friendfb        

0

主题

3

听众

21

积分

升级  16.84%

该用户从未签到

新人进步奖

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

使用道具 举报

0

主题

3

听众

72

积分

升级  70.53%

该用户从未签到

新人进步奖

回复

使用道具 举报

您需要登录后才可以回帖 登录 | 注册地址

qq
收缩
  • 电话咨询

  • 04714969085
fastpost

关于我们| 联系我们| 诚征英才| 对外合作| 产品服务| QQ

手机版|Archiver| |繁體中文 手机客户端  

蒙公网安备 15010502000194号

Powered by Discuz! X2.5   © 2001-2013 数学建模网-数学中国 ( 蒙ICP备14002410号-3 蒙BBS备-0002号 )     论坛法律顾问:王兆丰

GMT+8, 2026-7-19 16:06 , Processed in 0.569229 second(s), 109 queries .

回顶部