浙大oj（basic level）1005_浙江大学oj

1005 继续(3n+1)猜想 

卡拉兹(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 个空格隔开，但一行中最后一个数字后没有空格。

个人思路：

这题主要是对1001的优化，当我们对一个数开始验证时，在计算过程中会产生中间的数，而其他输入与中间的数重复时，我们认为不需要重复计算，否则便认为是关键数，题目要求的就是关键数并降序排序.

我自己的想法是：

1.建立一个结构体，将每一个输入的数当作结构体的对象，用指针进行访问

2.将中间数（可以覆盖）全都存入结构体内，并记录中间数的个数

3.循环测试输入的数，与其他的输入的数的结构体内的中间数进行一一比较，若不相等，就存入新的数组；相等就舍去。

4.最后，降序排列。

前面两步已经实现，卡在第三步了，我发现要比较，就要套了好多层循环，比较复杂，就放弃了，觉得这不是最优方法。以下是我前两步代码，后面两步如果以后有想法，再来修改~

#include<iostream>
#include<stdio.h>
using namespace std;
struct Test
{
	int cov[100];
	int num;
};
int main()
{
	int n,temp;
	int i = 0;
	cin >> n;
	int t = n;//
	Test* p = new Test[n];
	int test[100];
	while (n--)
	{
		cin >> temp;
		test[n] = temp;
	}
	for (int s = 0; s < t; s++)
	{
		int count = 0;
		p[i].cov[count] = test[s];//将测试对象本身存入
		count++;
		while (test[s] != 1)
		{
			if (test[s] % 2 == 0)
			{
				test[s] = test[s] / 2;
				p[i].cov[count] = test[s];//存入中间过程数
			}
			else
			{
				test[s] = (3 * test[s] + 1) / 2;
				p[i].cov[count] = test[s];//存入中间过程数
			}
			count++;
		}
		p[i].num = count;//存入测试对象的覆盖数
		i++;
	}
}

最后看了大佬的代码，又学到了很多：

https://blog.csdn.net/weixin_43849505/article/details/114276305?ops_request_misc=%257B%2522request%255Fid%2522%253A%2522162882431316780265413833%2522%252C%2522scm%2522%253A%252220140713.130102334.pc%255Fall.%2522%257D&request_id=162882431316780265413833&biz_id=0&utm_medium=distribute.pc_search_result.none-task-blog-2~all~first_rank_v2~rank_v29-1-114276305.first_rank_v2_pc_rank_v29&utm_term=%E6%B5%99%E5%A4%A7oj%EF%BC%88basic+level%EF%BC%89&spm=1018.2226.3001.4187

1.使用函数递归，可以简化代码复杂度；

2.sort函数的使用：

头文件为#include<algorithm>；

void sort (RandomAccessIterator first, RandomAccessIterator last, Compare comp);

（1）第一个参数first：是要排序的数组的起始地址。

（2）第二个参数last：是结束的地址（最后一个数据的后一个数据的地址）

（3）第三个参数comp是排序的方法：可以是从升序也可是降序。如果第三个参数不写，则默认的排序方法是从小到大排序。

https://www.cnblogs.com/junbaobei/p/10776066.html

3.bool值的使用，将中间数转换为0-1变量，如中间数7，则数组m[7]=1；当我们输入一个数i，判断是不是关键数，if(m[I]==1)，如果不等，则是关键数        .