“程序星编程之路”第二次作业题解

“程序星编程之路”第二次作业题解

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 的约瑟夫环