[C语言-PTA]特立独行的幸福—–一点也不幸福 | 祭夜の咖啡馆
  • 公告

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

C/C++ 祭夜 10个月前 (12-20) 454次浏览 已收录 0个评论 扫描二维码
文章目录[隐藏]

前言

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

题目

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

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

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

输入格式:

输入在第一行给出闭区间的两个端点:

输出格式:

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

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

输入样例 1:

10 40

输出样例 1:

19 8
23 6
28 3
31 4
32 3

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

输入样例 2:

110 120

输出样例 2:

SAD

思路

  1. 判断是不是幸福数
  2. 计算迭代次数
  3. 判断是不是素数
  4. 是的话迭代次数加倍
  5. 判断是不是独立幸福数
  6. 是的话就输出

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这种数字会出现死循环怎么办?

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

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

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

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

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

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

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


祭夜の咖啡馆 , 版权所有丨如未注明 , 均为原创丨本网站采用BY-NC-SA协议进行授权
转载请注明原文链接:[C语言-PTA]特立独行的幸福—–一点也不幸福
喜欢 (2)
[1690127128@qq.com]
分享 (0)
发表我的评论
取消评论
OwO表情
贴图 加粗 删除线 居中 斜体 签到

Hi,您需要填写昵称和邮箱!

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址