PAT 线上测试赛 2020-05-01
今天的PAT线上测试赛，报名今年六月份比赛的自动获得参赛资格，题目一共三道都是水题
7-1 Knuth洗牌法 (20分)Knuth 洗牌法是生成 { 1, 2, …, n } 的一个随机重排列的算法。与每次反复随机生成一个数字，直到获得一个不重复的新数字的算法不同，Knuth 洗牌法从原始序列 { 1, 2, …, n } 开始，逐次洗牌。洗牌的方法是从左到右，每轮从没确定的数字中随机抽取一个数，把它放到确定的位置上。
例如令 n 等于 4。我们从 { 1, 2, 3, 4 } 开始。记 i 到 N 之间的随机抽牌数为 random(i,N)。假设我们生成的随机数序列 random(i,4) (i=1, 2, 3, 4) 为 { 2, 4, 3, 4 }。则 Knuth 洗牌法是这样执行的：
• random(1,4) = 2; 将位置 1 与位置 2 的数字交换，得到 { 2, 1, 3, 4 }
• random(2,4) = 4; 将位置 2 与位置 4 的数字交换，得到 { 2, 4, 3, 1 }
• random(3,4) = 3; 将位置 3 与位置 3 的数字交换，得到 { 2, 4, 3, 1 }
• random(4,4) = 4; 将位置 4 与位置 4 的数字交换，得到 { 2, 4, 3, 1 }
现给定随机抽牌数字序列，请你输出 Knuth 洗牌法的结果序列。
输入格式：
输入在第一行中给出一个正整数 N（≤ 1000）。随后一行给出 N 个随机抽牌数字，数字间以空格分隔。题目保证第 i 个数在 i 到 N 之间。
输出格式：
在第一行中输出 Knuth 洗牌法的结果序列。数字间必须以 1 个空格分隔，行首尾不得有多余空格。
输入样例：
10
7 4 4 5 10 6 9 9 10 10
输出样例：
7 4 2 5 10 6 9 1 3 8
AC代码：
#include//Author:Summer
#include
int a[1010],ran[1010];
int main()
{
int n;
scanf("%d",&n);
for(int i=1;i<=n;++i)
{
scanf("%d",&ran[i]);
a[i]=i;
}
for(int i=1;i<=n;++i)
std::swap(a[ran[i]],a[i]);
for(int i=1;i<=n;++i)
printf(i==1?"%d":" %d",a[i]);
return 0;
}
7-2 三阶幸福数 (20分)
对一个十进制数的各位数字做一次立方和，称作一次迭代。如果一个十进制数能通过 h 次迭代得到 1，就称该数为三阶幸福数，迭代的次数 h 称为幸福度。例如 1579 经过 1 次迭代得到 1198，2 次迭代后得到 1243，3 次迭代后得到 100，最后得到 1。则 1579 是幸福数，其幸福度为 4。
另一方面，如果一个大于1的数字经过数次迭代后进入了死循环，那这个数就不幸福。例如 97 迭代得到 1072、352、160、217、352、…… 可见 352 到 217 形成了死循环，所以 97 就不幸福，而 352 就是它最早遇到的循环点。
本题就要求你编写程序，判断一个给定的数字是否有三阶幸福。
输入格式：
输入在第一行给出一个不超过 100 的正整数 N，随后 N 行，每行给出一个不超过 104 的正整数。
输出格式：
对于每一个输入的数字，如果其是三阶幸福数，则在一行中输出它的幸福度；否则输出最早遇到的循环点。
**输入样例：**
3
1579
97
1
**输出样例：**
4
352
0
这个题有点小坑，好多人都是卡在这道题上的，可以看到排名那里一大堆都是58分，就是如果第一个数本身就是一个循环的起点 那么应该输出它，所以应该一开始就对n做标记，AC代码：
#include//Author:Summer
#include
int vis[10000];
void fun(int n)
{
memset(vis,0,sizeof(vis));
vis[n]=1;
long long int x=n,cou=0;
while(x!=1)
{
long long int sum=0;
while(x)
{
sum+=(x%10)*(x%10)*(x%10);
x/=10;
}
if(vis[sum])
{
printf("%lld\n",sum);
return;
}
vis[sum]=1;
cou++;
x=sum;
}
printf("%lld\n",cou);
}
int main()
{
int n,temp;
scanf("%d",&n);
for(int i=0;i<n;++i)
{
scanf("%d",&temp);
fun(temp);
}
return 0;
}
**
7-3 垃圾分类 (20分)
原创文章 23获赞 5访问量 8479
关注
私信
展开阅读全文
作者：summer_shell
