惊悚算法计算给定长度的数字串是否有重复数字出现

作者: twd2 日期: 2013 年 08 月 25 日被围观 233 次发表评论 (0) 查看评论

(传说RDTSC计时会不准确)

#include<iostream>
using namespace std;
unsigned long long RDTSC()
{
    __asm("RDTSC");
}
bool algorithm1(unsigned long long a, int length=10) //惊悚算法
{
    int map[]={2,3,5,7,11,13,17,19,23,29};
    unsigned long long foo=1;
    if(a>9876543210) return false;
    for(int i=0;i<length;++i)
    {
        if(foo % map[a%10] ==0)
        {
            return false;
        }
        foo*=map[a%10];
        a/=10;
    }
    return true;
}
bool algorithm2(unsigned long long a, int length=10)
{
    bool hash[10]={0};
    if(a>9876543210) return false;
    for(int i=0;i<length;++i)
    {
        if(hash[a%10])
            return false;
        hash[a%10]=true;
        a/=10;
    }
    return true;
}
int main()
{
    unsigned long long n;
    cin>>n;
    bool a,b;
    unsigned long long t1,t2,t3,t4;
    t1=RDTSC();
    t2=RDTSC();
    a=algorithm1(n,5);
    t3=RDTSC();
    b=algorithm2(n,5);
    t4=RDTSC();
    cout<<"algorithm1: "<<a<<" "<< t3-t2-(t2-t1) <<endl;
    cout<<"algorithm2: "<<b<<" "<< t4-t3-(t2-t1) <<endl;
    return 0;
}