“程序星编程之路”第二次作业题解
A. Zs的回文质数
题目描述
读入一个整数 $n$ ，输出 $[1,n]$ 的所有回文质数，我们规定 $1\sim9$ 也是回文数。
思路
简单点说，回文数就是正着读反着读都是一样的，也就是对称的，形如 $abcba $ 或者 $123321$ 这样的。
质数的话，对于一个数 $n$ ，如果他是质数，那它除了 $1$ 和 $n$ 没有其他因子。例如 $2,3,5,7,11$ 这样的。
那么接下来我们考虑一下解决这个问题应该怎么做，首先我们看一下数据范围，$[1,100000]$ ，还是挺小的，我们可以考虑直接枚举每一个数来判断它是不是回文数，然后再判断一下是不是质数，如果两个都满足，我们就输出它。
判断回文数，我们可以考虑到 NOJ05 幸运数 一题的解题思路，也就是说我们把一个数倒置过来，好比一个数 $xyz$ 倒置成 $zyx$ ，然后判断是否 $xyz == zyx$ ，如果相等的话就是回文数，如果不相等就不是。
判断质数，我们可以在 $[2,\lfloor\sqrt{n}\rfloor]$ 枚举它的因子，这个的完备性我上课的时候证明过，不再赘述。这里需要注意 $1,2$ 需要特判一下。
代码
#include<stdio.h>
#include<math.h> //我们需要用到sqrt函数，因此需要引入数学库
int main()
{
int n;
bool flag = false; // 标记 i 是否满足条件
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
flag = true;
int p=i,j=0;
while(p) // 将 p 反转为 j
{
j=j*10+p%10;
p/=10;
}
if(j==i)
{
if(j==1) continue; // 特判 1
if(j==2) // 特判 2
{
printf("2\n");
continue;
}
int sqrtj = sqrt(j);
for(int k=2;k<=sqrtj;k++) // 枚举 [2,sqrt(n)]
{
if(j%k==0) // 如果能够整除(余数为0),那么是 j 的因子
{
flag = false;
break;
}
}
if(flag)
{
printf("%d\n",j);
}
}
}
}
其他
因为我们讲到这里的时候，我们没讲函数，但是这道题如果我们把判断是否为回文数，判断是否为质数，都另成一个函数模块，将使得程序变得更加简洁。我在这里也将函数版本的贴出来，有兴趣的可以看一下。
#include<stdio.h>
#include<math.h>
bool isprime(int k) //判断是否为质数，如果是质数返回true，如果不是返回false
{
if(k==1) return false;
if(k==2) return true;
for(int i=2;i<=sqrt(k);i++)
{
if(k%i==0) return false;
}
return true;
}
bool ishw(int k) //判断是否为回文数，如果是返回true，如果不是返回false
{
int ans=0;
int temp = k; //temp作为一个k的复制版，因为后续需要用到k，新定义一个作为备份
while(k)
{
ans = ans*10 + k%10;
k/=10;
}
if(temp == ans)
{
return true;
}
else return false;
}
int main()
{
int n;
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
if(isprime(i) && ishw(i)) //如果既是质数也是回文数
{
printf("%d\n",i);
}
}
}
B. Wcx的杨辉三角
题目描述
读入一个整数 $n$ ，输出杨辉三角的前 $n$ 行。
思路
首先这道题我们需要了解一下杨辉三角 ，大家小学到高中应该都了解过。
那么如何计算杨辉三角，首先我们可以知道的是杨辉三角的第 $i$ 行就是$C_i^0\sim C_i^i$ ，但是我们考虑一下如何计算组合数，是用阶乘对吧，但是阶乘就涉及到一个连乘，对于这个题，我数据范围写的是 $1\le n \le 40$ ，很明显，阶乘不可行。而且写起来挺麻烦的。
那么我们考虑一个组合数的性质 $$ C_n^i = C_{n-1}^i + C_{n-1}^{i-1} $$
看起来很高大上对吧，简单点说就是杨辉三角里面一个数的值等于两肩之和，那么基于这个性质，我们很容易想到，我们可以用一个二维数组，定义 $f[i][j]$ 为第 $i$ 行的第 $j$ 个数，那么可以得到
当 $j==1$ 或 $j==i$ ，则 $f[i][j] = 1$ ，也就是，当它为这一行的第一个或者最后一个，那么它就是 $1$
如果不是上述条件，则 $f[i][j] = f[i-1][j] + f[i-1][j-1]$ ，也就是等于两肩之和。
还有一个需要注意的问题就是，这个题的 $n$ 最大值是 40，这个时候已经超出了 $int$ 的范围，因此我们需要将二维数组定义为 $long: :long$ 。
代码
#include<stdio.h>
int main()
{
long long a[105][105] = {0}; //全都初始化为 0
int n = 0;
scanf("%d",&n);
for(int i=1;i<=n;i++) //这里我用的是 1~n 而不是 0~n-1
{
for(int j=1;j<=i;j++)
{
if(j==1 || j==i)
{
printf("%lld ",a[i][j]=1);
}
else
{
printf("%lld ",a[i][j]=a[i-1][j-1]+a[i-1][j]);
}
}
printf("\n");
}
}
其他
这道题主要是对二维数组的考察。
注意我们遇到第五个点过不去的时候，应该试一下最大的值 $40$ ，会发现有负数，显然是溢出问题，我们就能知道问题的解决办法了。
C. Zh的约瑟夫环问题
题目描述
有 $n$ 个人围成一圈，顺序排号，从第一个开始报数(从 $1$ 到 $m$ 报数)，凡报到 $m$ 的人退出圈子，问最后留下的是几号.
思路
约瑟夫问题是个很经典的问题，可能又叫什么猴子选大王什么的，特多变体。
这个题其实就是一个纯模拟题，主要是对数组的考察。我们可以考虑开一个布尔数组 vis 用来标记某个人是否出圈，如果出圈了我们给他设置为 true ，如果没有出圈就是 false 。
然后开一个报数到多少的变量cnt，开一个当前谁报数的变量pot，然后来模拟这个过程。如果 cnt 增长到了 m ，我们将 pot 出圈，也就是 vis[pot] = true ，然后在场的人数减一，当只剩下一人的时候，我们遍历 vis 数组中的每个元素，如果它的 vis 值为 false ，即没有出队，则将他输出。
还有一个要注意的问题就是这是一个环，那么我们只需要判断一下当 pot 为 $n+1$ 的时候将他置为 $1$ 即可，这就模拟了一个环的性质。
代码
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<iostream>
using namespace std;
int n,m;
int vis[1005]; //vis[i] = true 已经淘汰 vis[i] = false 未被淘汰
int main()
{
scanf("%d%d",&n,&m);
int cnt = 1; //报数到多少
int pot = 1; //当前是谁报数
int exist = n; //在场的人数
while(exist > 1)
{
cnt=0;
while(1)
{
if(!vis[pot]) //如果没有出圈
{
cnt++;
if(cnt==m)
{
vis[pot] = true;
exist--;
break;
}
}
pot++;
if(pot==n+1) pot=1; //模拟环
}
}
for(int i=1;i<=n;i++)
{
if(vis[i] == false) printf("%d",i);
}
return 0;
}
其他
上面的想法是比较好理解的形式。
我们考虑一下模拟环，也就是使得 pot 指针处在一定的范围内，如果超出了将他重新置到头部，那么我们可以联想到取模，在模拟环时使用取模来实现，大家可以下去自己尝试，这有点像魏辰旭第一节课讲的那个字符串的问题。
因为这道题只关心谁活了下来，所以还有一个比较简单的解法，我看在作业中也有几位同学给出了这个较简单的解法，如果理解了上述思想，看这个代码应该不难理解，大家可以对照代码自行思考。
#include<stdio.h>
int n,m;
int pot = 0;
int main()
{
scanf("%d%d",&n,&m);
for(int i=2;i<=n;i++)
{
pot = (pot+m)%i;
}
printf("%d",pot+1);
}
提示：n个人的约瑟夫环杀掉一个人后组成一个新的人数为 n-1 的约瑟夫环