『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
(≤ 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",×); 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
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
下一篇:关于类的几点说明
- C++ 转换函数搭配友元函数 2020-06-10
- C++ 自动转换和强制类型转换(用户自定义类类型) 2020-06-10
- C++ rand函数 2020-06-10
- C++ 友元函数 2020-06-10
- C++ 运算符重载 2020-06-10
IDC资讯: 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营: 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程: Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术: Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧: 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作: FrontPages Dreamweaver Javascript css photoshop fireworks Flash