注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

Hao的博客

I'm on my way……

 
 
 

日志

 
 
 
 

POJ1047字符串处理  

2009-03-27 16:03:08|  分类: Algorithm discov |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

 Round and Round We Go
Time Limit: 1000MS  Memory Limit: 10000K
Total Submissions: 5558  Accepted: 2529

Description

A cyclic number is an integer n digits in length which, when multiplied by any integer from 1 to n, yields a"cycle"of the digits of the original number. That is, if you consider the number after the last digit to "wrap around"back to the first digit, the sequence of digits in both numbers will be the same, though they may start at different positions.For example, the number 142857 is cyclic, as illustrated by the following table:
142857 *1 = 142857
142857 *2 = 285714
142857 *3 = 428571
142857 *4 = 571428
142857 *5 = 714285
142857 *6 = 857142

Input

Write a program which will determine whether or not numbers are cyclic. The input file is a list of integers from 2 to 60 digits in length. (Note that preceding zeros should not be removed, they are considered part of the number and count in determining n. Thus, "01"is a two-digit number, distinct from "1" which is a one-digit number.)
Output

For each input integer, write a line in the output indicating whether or not it is cyclic.
Sample Input

142857
142856
142858
01
0588235294117647

Sample Output

142857 is cyclic
142856 is not cyclic
142858 is not cyclic
01 is not cyclic
0588235294117647 is cyclic

Source

Greater New York 2001

 

题目大意:一个N位的整数digit,如果满足:digit分别与整数1~N相乘后的乘积形成一个digit的循环,如样例,则说digit是一个循环数。现在给定一个整数,要求判断它是否为循环数。

主要思想:输入的整数最大为60位,所以选择字符串接收。首先要解决的问题是怎么降低字符串乘法的复杂度,这里digit从1乘到N,所以可以用字符串加法代替乘法,通过N次循环将digit自增。接下来要解决的问题是如何判断当前得到的字符串是否为digit移位得到的,比较简单的方法就是将两个digit连接为exDigit,然后判断得到的字符串是否为exDigit的子串即可。

代码如下:

#include<iostream>
#include<string>
#define MAX 70
using namespace std;
//实现dig1和dig2的字符串加法,结果更新dig1
//返回true运算成功,返回false说明得到的字符串长度大于len
bool AddSelfOnce(char dig1[],char dig2[],int len);
char digit[MAX];
char exDigit[MAX*2];
char temp[MAX];
int main(){
    int i,len;
    while(cin>>digit){
        len=strlen(digit);
        for(i=0;i<2*len;i++){         //初始化temp和exDigit
            exDigit[i]=digit[i%len];
            if(i<len)temp[i]=digit[i];
            else if(i==len)temp[i]=NULL;
        }
        exDigit[i]=NULL;
        for(i=2;i<=len;i++){
            if(!AddSelfOnce(temp,digit,len)){
                cout<<digit<<" is not cyclic"<<endl;
                break;
            }
            if(strstr(exDigit,temp)==NULL){   //如果temp不是exDigit的子串
                cout<<digit<<" is not cyclic"<<endl;
                break;
            }
        }
        if(i>len)cout<<digit<<" is cyclic"<<endl;
    }
    return 0;
}
bool AddSelfOnce(char dig1[],char dig2[],int len){
    int i,carry=0;
    for(i=len-1;i>=0;i--){
        dig1[i]+=(dig2[i]+carry-48);
        if(dig1[i]>'9'){
            if(0==i)return false;
            dig1[i]-=10;
            carry=1;
        }
        else carry=0;
    }
    return true;
}

后记:

1.strstr(const char *s1,const char *s2)函数,如果s2不是s1的子串就返回NULL。

2.这里用了扩展digit的方法判断循环数免去了不少移位的麻烦。

3.有的时候用乘法代替加法不仅可以降低算法的时间复杂度,还可以降低实现的难度。何乐而不为呢~~~~

  评论这张
 
阅读(862)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017