[C语言-PTA]特立独行的幸福—–一点也不幸福

文章目录[隐藏]

前言
题目
思路

前言

呀，看着PTA没几个人做，就试试，其实思路清晰了，也就那么回事儿，就是中间一点小插曲有点多。
第一次让我在C语言上用“分块测试”的方法，还是那么好用 #(受虐滑稽) （之前都是在PHP上用的 #(泪) ）。

题目

对一个十进制数的各位数字做一次平方和，称作一次迭代。如果一个十进制数能通过若干次迭代得到 1，就称该数为幸福数。1 是一个幸福数。此外，例如 19 经过 1 次迭代得到 82，2 次迭代后得到 68，3 次迭代后得到 100，最后得到 1。则 19 就是幸福数。显然，在一个幸福数迭代到 1 的过程中经过的数字都是幸福数，它们的幸福是依附于初始数字的。例如 82、68、100 的幸福是依附于 19 的。而一个特立独行的幸福数，是在一个有限的区间内不依附于任何其它数字的；其独立性就是依附于它的的幸福数的个数。如果这个数还是个素数，则其独立性加倍。例如 19 在区间[1, 100] 内就是一个特立独行的幸福数，其独立性为 $2 \times 4 = 8$ 。

另一方面，如果一个大于1的数字经过数次迭代后进入了死循环，那这个数就不幸福。例如 29 迭代得到 85、89、145、42、20、4、16、37、58、89、…… 可见 89 到 58 形成了死循环，所以 29 就不幸福。

本题就要求你编写程序，列出给定区间内的所有特立独行的幸福数和它的独立性。

输入格式：

输入在第一行给出闭区间的两个端点： $1 < A < B \leq 1 0^{^4 }$ 。

输出格式：

按递增顺序列出给定闭区间 $[A, B]$ 内的所有特立独行的幸福数和它的独立性。每对数字占一行，数字间以 1 个空格分隔。

如果区间内没有幸福数，则在一行中输出 SAD。

输入样例 1：

10 40

输出样例 1：

注意：样例中，10、13 也都是幸福数，但它们分别依附于其他数字（如 23、31 等等），所以不输出。其它数字虽然其实也依附于其它幸福数，但因为那些数字不在给定区间 [10, 40] 内，所以它们在给定区间内是特立独行的幸福数。

输入样例 2：

110 120

输出样例 2：

SAD

思路

判断是不是幸福数
计算迭代次数
判断是不是素数
是的话迭代次数加倍
判断是不是独立幸福数
是的话就输出

1.判断是不是幸福数

根据题目描述，很容易想到递归求解，因为每次执行的操作都是一样的。

相同操作为“各位数字做一次平方和”，直到结果为1。

于是可以写成

//判断是否幸福，返回值为正整数是为幸福独立性，返回-1为非幸福数
int is_happy(int num)
{
    int sum = 0;
    int temp = num;
    int res;

    while (temp > 0)
    {
        sum = sum + (temp % 10) *(temp % 10);
        temp /= 10;
    }

    //1是幸福数
    if(sum == 1)
        return 1;

    res = is_happy(sum);

    if(res > 0)
        return 1 + res;
    else
        return -1;
}

但是，像29这种数字会出现死循环怎么办？

点我查看方法

可以定义一个宏来限定递归调用次数，全局变量来记录次数

//递归最大调用次数
#define _LOOP 20
//递归调用计数
int count = 0;

函数改为：

//判断是否幸福，返回值为正整数是为幸福独立性，返回-1为非幸福数
int is_happy(int num)
{
    //递归调用次数加一
    count++;
    int sum = 0;
    int temp = num;
    int res;

    while (temp > 0)
    {
        sum = sum + (temp % 10) *(temp % 10);
        temp /= 10;
    }

    //1是幸福数
    if(sum == 1)
        return 1;

    //超出递归次数返回-1，表示不幸福
    if(count > _LOOP)
        return -1;
    
    res = is_happy(sum);

    if(res > 0)
        return 1 + res;
    else
        return -1;
}

2.判断素数过于简单。。。 #(cos滑稽)

3.判断是不是独立幸福数

粗暴的方法：
这里把幸福数的子数称为儿子 #(流汗滑稽)

把幸福数的所有儿子都存在一个数组中
现在试图输出一个幸福数
在所有的其它的幸福数的儿子中，寻找这个幸福数
找不到就输出这个数，否则就尝试下一个

什么？你不知道怎么存儿子？

答案

4.注意存储所用的数组大小

我用2000大小的数组测试时，2 – 10000里面有1441个幸福数,好大 #(受虐滑稽)
设置1000的时候看着挺大，实际上比题目范围还是小了那么一点，改10000本地编译环境出现小问题。。。PTA倒是没问题。。。

我的最终答案

#include <stdio.h>
#include <math.h>
//递归最大调用次数
#define _LOOP 20
//幸福数个数
#define HAPPY_NUM 2000
//幸福数儿子个数
#define HAPPY_SON_NUM 200

int is_happy(int );
int is_prime(int );
int get_happy_son(int , int happy_son[][HAPPY_SON_NUM], int);

//递归调用计数
int count = 0;
//儿子的数量
int happy_son_son_count = 1;

int main(void)
{
    int m, n;

    //存储幸福数，happy[][0]为幸福数，happy[][1]为幸福数独立性
    int happy[HAPPY_NUM][2];

    //存储幸福数的儿子，happy_son[][0]存储儿子个数
    int happy_son[HAPPY_NUM][HAPPY_SON_NUM];

    //幸福数个数（顺序）
    int happy_count = 0;

    int i, j, k;
    int flag = 0;

    //临时独立性记录
    int temp;
    /*测试部分
    int test = 19;
    happy_son[0][0] = get_happy_son(test, happy_son, 0);
    for ( i = 1; i < happy_son[0][0]; i++)
    {
        printf("%d\n", happy_son[0][i]);
    }
    
    return 0;*/

    scanf("%d%d", &m, &n);

    for ( i = m; i <= n; i++)
    {
        count = 0;
        if((temp = is_happy(i)) != -1)
        {
            //这个数是幸福的

            //找幸福数的儿子
            happy_son_son_count = 1;
            happy_son[happy_count][0] = get_happy_son(i, happy_son, happy_count);

            //记录幸福数
            happy[happy_count][0] = i;

            //记录幸福数的独立性
            if(is_prime(i))
                temp *= 2;
            happy[happy_count++][1] = temp;

        }
    }
    
    for ( i = 0; i < happy_count; i++)
    {
        //判断当前幸福数是否存在于其它幸福数的儿子中
        for(j = 0; j < happy_count; j++)
        {
            for ( k = 1; k < happy_son[j][0]; k++)
            {
                //当前幸福数是别人的儿子，退出循环
                if(happy[i][0] == happy_son[j][k])
                    break;
            }

            //当前幸福数是别人的儿子，退出循环
            if(k < happy_son[j][0])
                break;
        }
        //当前幸福数不是别人的儿子，输出
        if(j == happy_count)
        {
            flag = 1;
            printf("%d %d\n", happy[i][0], happy[i][1]);

            //test
            /*
            for ( j = 1; j < happy_son[i][0]; j++)
            {
                printf("%d ", happy_son[i][j]);
            }
            printf("\n");
            */
            //test

        }
    
    }
    if(flag == 0)
        printf("SAD");
    return 0;
}

//判断是否幸福，返回值为正整数是为幸福独立性，返回-1为非幸福数
int is_happy(int num)
{
    //递归调用次数加一
    count++;
    int sum = 0;
    int temp = num;
    int res;

    while (temp > 0)
    {
        sum = sum + (temp % 10) *(temp % 10);
        temp /= 10;
    }

    //1是幸福数
    if(sum == 1)
        return 1;

    //超出递归次数返回-1，表示不幸福
    if(count > _LOOP)
        return -1;
    
    res = is_happy(sum);

    if(res > 0)
        return 1 + res;
    else
        return -1;
}

//判断素数
int is_prime(int num)
{
    int i;
    for ( i = 2; i <= sqrt(num); i++)
    {
        if(num % i == 0)
            return 0;
    }
    return 1;
}

//happy_son幸福数的儿子，n第几个幸福数的儿子，函数返回儿子个数
int get_happy_son(int num, int happy_son[][HAPPY_SON_NUM], int n)
{
    int sum = 0;
    int temp = num;
    int res;

    while (temp > 0)
    {
        sum = sum + (temp % 10) *(temp % 10);
        temp /= 10;
    }
    happy_son[n][happy_son_son_count++] = sum;
    //1是幸福数
    if(sum == 1)
        return happy_son_son_count;
    
    res = get_happy_son(sum, happy_son, n);

    return res;
}