yzoi1109&&viojs1042最小步数的一点看法——回文数

Description - 问题描述

        有一天,雄霸传授本人风神腿法第一式:捕风捉影..............的步法(弟子一:堂主,你大喘气呀。风:你给我闭嘴。)捕风捉影的关键是换气(换不好就会大喘气...)。

        使用捕风捉影这一招时并不是每一步都喘气,而是在特定的步数喘气。一般来说功力越高,喘气越稀疏。喘气的步数符合特定规律:第一要是SUSHU(弟子二:哇塞!堂主,你还会鸟语,我好好崇拜你呦!可是SUSHU是什么意思呢?风:笨蛋,那是汉语拼音!)第二要是一个回文数,回文数就是正反念一样的数,如:123321,121,5211314(弟子三:堂主,最后一个好象不是...风:废话,当然不是了,我是考察一下你们的纠错能力!)现在给出两个数M,N(5< =M< N< =100,000,000),你要算出M,N之间需要换气的都有哪几步。(包括M,N)。算出来的可以提升为本堂一级弟子,月薪(1000000000000000000000000000000000000000000  MOD  10  )元。

 

  可能在众位神犇看来这是一道水的不能再水的题目,但我认为还是有必要提一提的。首先,这是一道判断素数+回文数的题,对于回文数,百度的定义是如下的:

“回文”是指正读反读都能读通的句子,它是古今中外都有的一种修辞方式和文字游戏,如“我为人人,人人为我”等。在数学中也有这样一类数字有这样的特征,成为回文数(palindrome number)。 
设n是一任意自然数。若将n的各位数字反向排列所得自然数n1与n相等,则称n为一回文数。例如,若n=1234321,则称n为一回文数;但若n=1234567,则n不是回文数。
  另外,他给出的c++判定代码如下:
 1 #include<iostream>
 2 using namespace std;
 3 bool symm(long m)
 4 {
 5 long temp = m,n=0;
 6 while (temp)
 7 {
 8 n = n*10+temp%10;
 9 temp = temp/10;
10 }
11 return (m == n);
12 }
13 int main(int argc, _TCHAR* argv[])
14 {
15 long m;
16 cout<<"请输入一个整数:";
17 cin>>m;
18 cout<<"输入了"<<symm(m)<<"个回文数!";
19 return 0;
20 }

  个人认为,对于回文数的判断基本可用该法进行。但同时亦可以string读入,用s.size()判断是奇是偶,后再从中向左向右搜索即可。


 

  我的代码:

 1 #include<iostream>
 2 #include<cmath>
 3 using namespace std;
 4 const int maxn=3000000;
 5 //int p[maxn];
 6 int m,n;
 7 //int sum=0;
 8 //void make()
 9 //{
10 //  p[1]=1;
11 //  for(int i=2;i<=sqrt(maxn);i++)
12 //      if(p[i]==0)
13 //          for(int j=2;j<=sqrt(maxn)/i;j++)
14 //              p[i*j]=1;
15 //}
16 bool pd_1(int m)
17 {
18     int temp=m,n=0;
19     while(temp)
20     {
21         n=n*10+temp%10;
22         temp/=10;
23     }
24     return (m==n);
25 }
26 //bool pd_2(int m)
27 //{
28 //  if(p[m])
29 //      return false;
30 //  else
31 //      return true;
32 //}
33 bool pd_2(int m)
34 {
35     for(int i=2;i<=sqrt(m);i++)
36     {
37         if(m%i==0)
38             return false;
39     }
40     return true;
41 }
42 bool pd_3(int m)
43 {
44     int k=m%10;
45     if((k==2||k==4||k==5||k==6||k==8||k==0)&&(m/10>=1))
46         return false;
47     else
48         return true;
49 }
50 int main()
51 {
52 //  make();
53     cin>>m>>n;
54     if (n>10000000)
55        n=10000000;
56     for(int i=m;i<=n;i++)
57     {
58         if(pd_1(i)&&pd_3(i))
59             if(pd_2(i))
60                 cout<<i<<endl;      
61     }
62     return 0;
63 }
64 /**************************************************************
65     Problem: 1109
66     User: lwq
67     Language: C++
68     Result: Accepted
69     Time:559 ms
70     Memory:1320 kb
71 ****************************************************************/

 

 

郑重声明:本站内容如果来自互联网及其他传播媒体,其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享,并不代表本站赞同其观点和对其真实性负责,也不构成任何其他建议。