　　死亡周二，今天去看惊奇队长了！！！真的很佩服国外的后期特效大片技术，要是我们国内也能实现这样的技术能力就好了~ 羡慕max

------------------------------------------------L1-027----------------------------------------------------------

出租

下面是新浪微博上曾经很火的一张图：

一时间网上一片求救声，急问这个怎么破。其实这段代码很简单，index数组就是arr数组的下标，index[0]=2 对应 arr[2]=1，index[1]=0 对应 arr[0]=8，index[2]=3 对应 arr[3]=0，以此类推…… 很容易得到电话号码是18013820100。

本题要求你编写一个程序，为任何一个电话号码生成这段代码 —— 事实上，只要生成最前面两行就可以了，后面内容是不变的。

输入格式：

输入在一行中给出一个由11位数字组成的手机号码。

输出格式：

为输入的号码生成代码的前两行，其中arr中的数字必须按递减顺序给出。

输入样例：

输出样例：

int[] arr = new int[]{,,,,};

int[] index = new int[]{,,,,,,,,,,};

------------------------------------------------L1-027----------------------------------------------------------

注：思路还是很清晰的，没有遇到什么坑点，直接贴AC代码

#include<stdio.h>

#include<algorithm>

using namespace std;

char number[];

int Match[];

int length,ans,c;

int main()

{

    c = ;

    for(int i = ;i<;i++)

    {

        scanf("%c",&number[i]);

        int temp;

        temp = number[i] - '';

        if(Match[temp] == )

        {

            Match[temp]++;

            length++;

        }

    }

    printf("int[] arr = new int[]{");

    ans = length;

    for(int i = ;i>=;i--)

    {

        if(Match[i] == ) continue;

        Match[i] = c;

        c++;

        printf("%d",i);

        if(length != ) printf(",");

        length--;

    }

    printf("};\n");

    printf("int[] index = new int[]{");

    for(int i = ;i<;i++)

    {

        if(i == ) printf("%d",Match[number[i]-'']);

        else printf(",%d",Match[number[i]-'']);

    }

    printf("};");

    return ;

}

------------------------------------------------L1-028----------------------------------------------------------

判断素数

本题的目标很简单，就是判断一个给定的正整数是否素数。

输入格式：

输入在第一行给出一个正整数N（≤ 10），随后N行，每行给出一个小于231的需要判断的正整数。

输出格式：

对每个需要判断的正整数，如果它是素数，则在一行中输出Yes，否则输出No。

输入样例：

输出样例：

Yes

No

------------------------------------------------L1-028----------------------------------------------------------

注：通过这道理学到了几种判断素数的方法：

第一种：超低配版 · 从1到n每一个单独判定：

bool Sushu( int num )

{

    int tmp =num- ;

    for(int i= ;i <=tmp; i++)

      if(num %i== )

         return  ;

    return  ;

}

第二种：低配版 · 从1到sqrt（n）每一个单独判断：注意坑点：1不是素数，要单独判断！！不然过不了测试点.

#include<stdio.h>

#include<math.h>

long long int times;

bool Sushu(long long int num)

{

    long long int sqrtO,test = ;

    sqrtO = sqrt(num);

    for(long long int i = ;i<=sqrtO;i++)

    {

        if(num%i==) break;

        else test++;

    }

    if(test == (sqrtO -)) return ;

    else return ;

}

bool YES[];

int counter;

long long int temp;

int main()

{

    scanf("%d",&times);

    while(times--)

    {

        scanf("%lld",&temp);

        if(temp == )

        {

            YES[counter] = ;

            counter++;

            continue;

        }

        if(Sushu(temp) ==  || temp == )

        {

            YES[counter] = ;

            counter++;

        }

        else

        {

            YES[counter] = ;

            counter++;

        }

    }

    for(int i = ;i<counter;i++)

    {

        if(YES[i] == ) printf("Yes\n");

        else printf("No\n");

    }

    return ;

}

第三种：中配版，判断2之后只需要判断从3到sqrt(n)之间的奇数了，无需再判断之间的偶数。时间复杂度O(sqrt(n)/2)

bool Sushu( int num )

{

    if(num %  == ) return ;

    int tmp =num- ;

    for(int i= ;i <=sqrt(tmp); i=i+)

      if(num %i== )

         return  ;

    return  ;

}

第四种：牛逼版，素数要出现只可能出现在6x的相邻两侧。因此在5到sqrt(n)中每6个数只判断2个，时间复杂度O(sqrt(n)/3)。

int Sushu(long long num)  

{  

    if(num<=) return ;

    if(num==||num==) return ;//两个较小数另外处理 

    if(num%!=&&num%!=) return ;//不在6的倍数两侧的一定不是质数   

    //在6的倍数两侧的也可能不是质数  

    for(long long i=;i*i<=num;i+=)

        if(num%i==||num%(i+)==) return ;

    return ;//排除所有，剩余的是质数 

}

证明：

　　令x≥1，将大于等于5的自然数表示如下：
　　······ 6x-1，6x，6x+1，6x+2，6x+3，6x+4，6x+5，6(x+1），6(x+1)+1 ······
　　可以看到，不在6的倍数两侧，即6x两侧的数为6x+2，6x+3，6x+4，由于2(3x+1)，3(2x+1)，2(3x+2)，所以它们一定不是素数，再除去6x本身，显然，素数要出现只可能出现在6x的相邻两侧。
参考：https://blog.csdn.net/huang_miao_xin/article/details/51331710

注：如果有更好的解法，真心希望您能够评论留言贴上您的代码呢~互相帮助互相鼓励才能成长鸭~~

巴特西

『ACM C++』 PTA 天梯赛练习集L1 | 027-028

出租

输入格式：

输出格式：

输入样例：

输出样例：

判断素数

输入格式：

输出格式：

输入样例：

输出样例：

最新文章

热门文章