首页 > > 程序设计 > C/C++ >

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

2019-03-13 23:29:57来源：博客园阅读 ()

　　死亡周二，今天去看惊奇队长了！！！真的很佩服国外的后期特效大片技术，要是我们国内也能实现这样的技术能力就好了~ 羡慕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中的数字必须按递减顺序给出。

输入样例：

18013820100

输出样例：

int[] arr = new int[]{8,3,2,1,0};
int[] index = new int[]{3,0,4,3,1,0,2,4,3,4,4};

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

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

#include<stdio.h>
#include<algorithm>
using namespace std;
char number[11];
int Match[10];
int length,ans,c;
int main()
{
    c = 0;
    for(int i = 0;i<11;i++)
    {
        scanf("%c",&number[i]);
        int temp;
        temp = number[i] - '0';
        if(Match[temp] == 0) 
        {
            Match[temp]++;
            length++;
        }
    }
    printf("int[] arr = new int[]{");
    ans = length;
    for(int i = 9;i>=0;i--) 
    {
        if(Match[i] == 0) continue;
        Match[i] = c;
        c++;
        printf("%d",i);
        if(length != 1) printf(",");
        length--;
    }
    printf("};\n");
    printf("int[] index = new int[]{");
    for(int i = 0;i<11;i++)
    {
        if(i == 0) printf("%d",Match[number[i]-'0']);
        else printf(",%d",Match[number[i]-'0']);
    }
    printf("};");
    return 0;
}

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

判断素数

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

输入格式：

输入在第一行给出一个正整数N（

输出格式：

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

输入样例：

2
11
111

输出样例：

Yes
No

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

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

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

bool Sushu( int num )
{
    int tmp =num- 1;
    for(int i= 2;i <=tmp; i++)
      if(num %i== 0)
         return 0 ;
    return 1 ;
}

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

#include<stdio.h>
#include<math.h>

long long int times;
bool Sushu(long long int num)
{
    long long int sqrtO,test = 0;
    sqrtO = sqrt(num);
    for(long long int i = 2;i<=sqrtO;i++)
    {
        if(num%i==0) break;
        else test++;
    }
    if(test == (sqrtO -1)) return 1;
    else return 0;
}
bool YES[10];
int counter;
long long int temp;
int main()
{
    scanf("%d",&times);
    while(times--)
    {
        scanf("%lld",&temp);
        if(temp == 1)
        {
            YES[counter] = 0;
            counter++;
            continue;
        }
        if(Sushu(temp) == 1 || temp == 2) 
        {
            YES[counter] = 1;
            counter++;
        }
        else
        {
            YES[counter] = 0;
            counter++;
        }
    }
    for(int i = 0;i<counter;i++)
    {
        if(YES[i] == 1) printf("Yes\n");
        else printf("No\n");
    }
    return 0;
}

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

bool Sushu( int num )
{
    if(num % 2 == 0) return 0;
    int tmp =num- 1;
    for(int i= 1;i <=sqrt(tmp); i=i+2)
      if(num %i== 0)
         return 0 ;
    return 1 ;
}

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

int Sushu(long long num)  
{  
    if(num<=1) return 0;
    if(num==2||num==3) return 1;//两个较小数另外处理 
    if(num%6!=1&&num%6!=5) return 0;//不在6的倍数两侧的一定不是质数   
    //在6的倍数两侧的也可能不是质数  
    for(long long i=5;i*i<=num;i+=6)
        if(num%i==0||num%(i+2)==0) return 0;
    return 1;//排除所有，剩余的是质数 
}

证明：

　　令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

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

原文链接:https://www.cnblogs.com/winniy/p/10520422.html
如有疑问请与原作者联系

标签：

版权申明：本站文章部分自网络，如有侵权，请联系：west999com@outlook.com
特别注意：本站所有转载文章言论不代表本站观点，本站所提供的摄影照片，插画，设计作品，如需使用，请与原作者联系，版权归原作者所有