[C++知识库]C语言PAT刷题 - 1005 继续(3n+1)猜想

作者的话：若有朋友复制代码去PAT试着运行遇到问题的：
1.可能是格式问题，可以先把从本站复制的代码复制到记事本，再把记事本里的代码复制，然后粘贴到PAT的代码区，提交本题回答，应该就可以了；
2.可能是注释原因，PAT有时候检测到注释会编译错误，所以可以先把注释删了，再进行提交回答。
3.可能是作者当初根据题目写出来的代码仍存在一些疏漏，而恰好当时的测试机制没那么完善，没检测出问题。后面测试机制有所更新，故出现问题，若有相关需要的可以评论区留言或私信作者，我看到的话会去再查一下疏漏之处，然后更新文章。

一、题目描述
卡拉兹(Callatz)猜想已经在1001中给出了描述。在这个题目里，情况稍微有些复杂。
当我们验证卡拉兹猜想的时候，为了避免重复计算，可以记录下递推过程中遇到的每一个数。例如对 n=3 进行验证的时候，我们需要计算 3、5、8、4、2、1，则当我们对 n=5、8、4、2 进行验证的时候，就可以直接判定卡拉兹猜想的真伪，而不需要重复计算，因为这 4 个数已经在验证3的时候遇到过了，我们称 5、8、4、2 是被 3“覆盖”的数。我们称一个数列中的某个数 n 为“关键数”，如果 n不能被数列中的其他数字所覆盖。
现在给定一系列待验证的数字，我们只需要验证其中的几个关键数，就可以不必再重复验证余下的数字。你的任务就是找出这些关键数字，并按从大到小的顺序输出它们。
输入格式：
每个测试输入包含 1 个测试用例，第 1 行给出一个正整数 K (<100)，第 2 行给出 K 个互不相同的待验证的正整数 n (1<n≤100)的值，数字间用空格隔开。
输出格式：
每个测试用例的输出占一行，按从大到小的顺序输出关键数字。数字间用 1 个空格隔开，但一行中最后一个数字后没有空格。
输入样例：
6
3 5 6 7 8 11
输出样例：
7 6

二、解题思路
读题：
这是1001卡拉兹猜想习题的后续，首先来回顾一下，卡拉兹猜想大概来说就是找一个正整数n，如果是偶数，对半来一刀，n=n/2；如果是奇数，乘以3再加上1，然后对半来一刀。就这样一刀刀砍下去，n最后总会变成1。
而对不同的数砍来砍去的时候，可能有个数字n1在砍另一个数n2的时候就已经遇到过了，也就是说n1重复出现了两次。如果这两个数(n1和n2)还恰好同在某一个数列里，那我们就说，在这个数列中，n1被n2覆盖了，即n1是覆盖数，n2是关键数。
这道题希望我们设计一个程序，从用户那里接收正整数K(这是要给的数列的元素个数)，然后接收K个1-100的数字，检测一下，在这个数列中，哪些数字是关键数(即没有被覆盖的数)，把这些数从大到小打印且每两个数字之间要加个空格。
思路：
1.定义需要用到的变量，接收正整数K(数列中元素的数量)；
2.设置循环，每一轮循环接收一个数字，将这个数字储存到临时变量temp中，然后将arr[temp]赋值为1，循环完成之后，所有的待验证数字所对应的的arr[i]都为1，arr的其他元素则为0(因为这些数字都要送去检测，每个数字在检测他们自身的时候都要被砍一遍，且第一刀砍的就是他们，现在直接赋值1，既可以将待检测数字和普通数字区分开来，在后面检测时也省的再记录第一刀砍的数字)；
3.设置循环，凡是下标在1-100之间且元素值为1(即数列中的数)的元素，对他们的元素下标进行检测，每一轮检测的第一刀由于前面已经计算过了，此轮循环不再重复计算，其它在检测过程中遇到的待验证数字直接被淘汰，可以直接赋值为0；
4.设置循环，从大到小，打印数列中的关键数，且两个数之间有空格。

三、具体实现
0.标准C源程序框架

#include <stdio.h>
int main()
{
    return 0;
}

1.定义需要用到的变量，接收正整数K(数列中元素的数量)；

	int K = 0;//待验证数字个数
	int i = 0;//接收各个待验证数字时要用到循环，i为循环变量
	int temp = 0;//每一轮循环接收一个待验证数字，储存在temp中，后面作为arr下标帮助指示待验证数字
	int arr[101] = { 0 };//用以指示哪些数字是关键数,又数组下标从0开始，为不混淆设置101个元素,下标即对应数字
	int j = 0;//后面对待验证数字进行检测的时候，不方便砍i，所以另设j，复制i的值来作为被砍的数字
	scanf("%d", &K);

2.设置循环，每一轮循环接收一个数字，将这个数字储存到临时变量temp中，然后将arr[temp]赋值为1，循环完成之后，所有的待验证数字所对应的的arr[i]都为1，arr的其他元素则为0(因为这些数字都要送去检测，每个数字在检测他们自身的时候都要被砍一遍，且第一刀砍的就是他们，现在直接赋值1，既可以将待检测数字和普通数字区分开来，在后面检测时也省的再记录第一刀砍的数字)；

	for (i = 0; i < K; i++)//要接收K个待验证数字，自然要进行K轮循环
	{
		scanf("%d", &temp);//接收待验证数字存储到temp中
		arr[temp] = 1;//把待验证数字作为下标，对应的元素赋值为1
	}                 //即把所有待验证数字对应的元素先看做是关键数，后面发现重复遇见再淘汰，赋值为0

3.设置循环，凡是下标在1-100之间且元素值为1(即数列中的数)的元素，对他们的元素下标进行检测，每一轮检测的第一刀由于前面已经计算过了，此轮循环不再重复计算，其它在检测过程中遇到的待验证数字直接被淘汰，可以直接赋值为0；

	for (i = 1; i < 101; i++)
	{
		if (arr[i] == 1)//对1-100之间的待验证数字进行检测
		{
			for (j = i; j > 1;)   //此内层循环用来对一个数砍了又砍
			{
				if (j % 2 == 0)   //j为偶数，怎么砍
				{
					j /= 2;
				}
				else              //j为奇数，怎么砍
				{
					j = (j * 3 + 1) / 2;
				}
				if (j<101 && arr[j] == 1)//因为j砍的时候有时候会越砍越大，为避免arr[j]超出数组
				{                        //增设j<101这个条件，只有这个条件为真，才会去检测后面的条件
					arr[j] = 0;     //arr[j]置0，表示淘汰
					K--;            //每淘汰一个待验证数字，K就自减一次，循环最终结束时K的值就是关键数的数量
				}
			}
		}
	}//当所有的循环结束，元素值仍为1的元素说明没有被淘汰，即这些元素所对应的下标就是关键数

4.设置循环，从大到小，打印数列中的关键数，且两个数之间有空格。

	for (i = 100; i > 0; i--)
	{
		if (arr[i] == 1)//符合条件的元素所对应的下标就是关键数
		{
			printf("%d%c", i, --K ? ' ' : '\0');//先打印关键数，再把K先自减
		}//若K仍为真(非0)，说明当前关键数后面还有别的关键数，故打印空格；
	}    //反之，则打印'\0'，表示要输出的字符串在此结束，后面打印时会打印'\0'之前的内容，符合题意

四、全部代码

#include <stdio.h>
int main()
{
	int K = 0;//待验证数字个数
	int i = 0;//接收各个待验证数字时要用到循环，i为循环变量
	int temp = 0;//每一轮循环接收一个待验证数字，储存在temp中，后面作为arr下标帮助指示待验证数字
	int arr[101] = { 0 };//用以指示哪些数字是关键数,又数组下标从0开始，为不混淆设置101个元素,下标即对应数字
	int j = 0;//后面对待验证数字进行检测的时候，不方便砍i，所以另设j，复制i的值来作为被砍的数字
	scanf("%d", &K);
	for (i = 0; i < K; i++)//要接收K个待验证数字，自然要进行K轮循环
	{
		scanf("%d", &temp);//接收待验证数字存储到temp中
		arr[temp] = 1;//把待验证数字作为下标，对应的元素赋值为1
	}                 //即把所有待验证数字对应的元素先看做是关键数，后面发现重复遇见再淘汰，赋值为0
	for (i = 1; i < 101; i++)
	{
		if (arr[i] == 1)//对1-100之间的待验证数字进行检测
		{
			for (j = i; j > 1;)   //此内层循环用来对一个数砍了又砍
			{
				if (j % 2 == 0)   //j为偶数，怎么砍
				{
					j /= 2;
				}
				else              //j为奇数，怎么砍
				{
					j = (j * 3 + 1) / 2;
				}
				if (j<101 && arr[j] == 1)//因为j砍的时候有时候会越砍越大，为避免arr[j]超出数组
				{                        //增设j<101这个条件，只有这个条件为真，才会去检测后面的条件
					arr[j] = 0;     //arr[j]置0，表示淘汰
					K--;            //每淘汰一个待验证数字，K就自减一次，循环结束时K的值就是关键数的数量
				}
			}
		}
	}
	for (i = 100; i > 0; i--)
	{
		if (arr[i] == 1)
		{
			printf("%d%c", i, --K ? ' ' : '\0');
		}
	}
	return 0;
}