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

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

新老客户大回馈,云服务器低至5折

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

 

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

出租

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

一时间网上一片求救声,急问这个怎么破。其实这段代码很简单,index数组就是arr数组的下标,index[0]=2 对应 arr[2]=1index[1]=0 对应 arr[0]=8index[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≤ 10),随后N行,每行给出一个小于2?31??的需要判断的正整数。

输出格式:

对每个需要判断的正整数,如果它是素数,则在一行中输出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
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有

上一篇:#leetcode刷题之路17-电话号码的字母组合

下一篇:关于类的几点说明