1004 成绩排名
题目
卡拉兹(Callatz)猜想已经在1001中给出了描述。在这个题目里，情况稍微有些复杂。
当我们验证卡拉兹猜想的时候，为了避免重复计算，可以记录下递推过程中遇到的每一个数。例如对
n
=
3
n=3
n
=
3
进行验证的时候，我们需要计算
3
、
5
、
8
、
4
、
2
、
1
3、5、8、4、2、1
3
、
5
、
8
、
4
、
2
、
1
，则当我们对
n
=
5
、
8
、
4
、
2
n=5、8、4、2
n
=
5
、
8
、
4
、
2
进行验证的时候，就可以直接判定卡拉兹猜想的真伪，而不需要重复计算，因为这 4 个数已经在验证3的时候遇到过了，我们称
5
、
8
、
4
、
2
5、8、4、2
5
、
8
、
4
、
2
是被
3
3
3
“覆盖”的数。我们称一个数列中的某个数 n 为“
关键数
”，如果 n 不能被数列中的其他数字所覆盖。
现在给定一系列待验证的数字，我们只需要验证其中的几个关键数，就可以不必再重复验证余下的数字。你的任务就是找出这些关键数字，并按从大到小的顺序输出它们。
输入格式：
每个测试输入包含 1 个测试用例，第 1 行给出一个正整数
K
(
<
100
)
K (<100)
K
(
<
1
0
0
)
，第 2 行给出
K
K
K
个互不相同的待验证的正整数
n
(
1
<
n
≤
100
)
n (1<n≤100)
n
(
1
<
n
≤
1
0
0
)
的值，数字间用空格隔开。
输出格式：
每个测试用例的输出占一行，按从大到小的顺序输出关键数字。数字间用 1 个空格隔开，但一行中最后一个数字后没有空格。
输入样例：
6
3 5 6 7 8 11
输出样例：
7 6
思路&总结
应该有更好的方法存储输入数据，提高计算关键数字的效率，比如，动态规划，剪枝，我先去做饭，等我回来再搞搞。（2020-4-8 11:25:36）
真的是，中午菜搞的差不多了才想起，忘了煮饭。服气。
思路
：
例如对
n=
3
n=3
n
=
3
进行验证的时候，我们需要计算
3、
5
、
8
、
4
、
2
、
1
3、5、8、4、2、1
3
、
5
、
8
、
4
、
2
、
1
，则
3、
5
、
8
、
4
、
2
、
1
3、5、8、4、2、1
3
、
5
、
8
、
4
、
2
、
1
称为
递推数
。
1、把输入数据放在
numbers
里面。count存储
递推数
出现次数，类似键值对，最终
count[5]=2
表示
5
这个数字在整个程序运行过程中的在递推数中出现的次数是2。
2、迭代砍半过程，将
递推数
出现次数记录在
count[i]
中，比如递推
3
时，出现一个
5
，则
count[5]++
，然后出现一个
8
，则
count[8]++
，依次类推。
3、最后
i
从大到小判断
count[i]
中的值，如果不是1，则说明被覆盖过，不是关键数。
*由于不用计算覆盖次数，所以
count[i]
只要大于2，则说明被覆盖过，剩下的递推数也已经被覆盖过，可以直接跳出，提高效率。
上面答案1的问题主要是，忘了
3
n
+
1
3n+1
3
n
+
1
过程可能会超过给定数
n
n
n
的范围（
n
<
100
n<100
n
<
1
0
0
），使用下标记录被重复次数应该把大于100的给跳过记录，反正最后也不用输出。时间倒是没什么大问题，稍微做了一下剪枝，叫剪枝可能不太合适，因为是循环不是递归，将就一下吧。(我不会忘了这个题，它让我忘了煮饭！)（2020-4-8 13:42:36）
等下有空，百度一下dalao的做法。
答案（3正确2段错误 2020-4-8 11:22:01）
#include <stdio.h>
int count[100];
int numbers[100];//input integers
void toCover()
{
int i;
//iterate numbers , if the path of 3n+1 to 1 cover m,
//then count[m]++
for(i = 0; i < 100; i++ )
{
count[i]++;// for output convienently
int t = numbers[i];
if(t != 0)
while(t != 1)
{
if(t%2 == 0 )
{
t = t/2;
count[t]++;
}else{
t = 3 * t +1;
}
}
}
}
int isNumbersHasK(int k)
{
int i = 0;
for(i = 0; i < 100; i++ )
{
if(numbers[i] == k)
return 1;
}
return 0;
}
int main(int argc, char* argv[])
{
int i = 0;
for(i = 0; i < 100; i++ )
{
count[i] = 0;
numbers[i] = 0;
}
int n;
scanf("%d",&n);
for(i = 0; i < n; i++ )
scanf("%d",&numbers[i]);
toCover();
//the key num m is the count[m]=1
for(i = 100; i >= 1; i-- )
{
if(count[i] == 1 && isNumbersHasK(i) == 1)
{
printf("%d",i);
break;
}
}
--i;
for(; i >= 1; i-- )
{
if(count[i] == 1 && isNumbersHasK(i) == 1)
printf(" %d",i);
}
return 0;
}
答案2（2020-4-8 13:34:58）
#include <stdio.h>
int count[100];
int numbers[100];//input integers
void toCover(int n)// n is numbers length
{
int i;
//iterate numbers , if the path of 3n+1 to 1 cover m,then count[m]++
for(i = 0; i < n; i++ )
{
int t = numbers[i];
count[t]++;// for output convienently
if(t != 0)
while(t != 1)
{
if(t%2 == 0 )
{
t = t/2;
//version2.0 revise here
if(t <= 100)
{
if(count[t] > 1)
break;
count[t]++;
}
//revise done
}else{
t = 3 * t +1;
}
}
}
}
int isNumbersHasK(int k)
{
int i = 0;
for(i = 0; i < 100; i++ )
{
if(numbers[i] == k)
return 1;
}
return 0;
}
int main(int argc, char* argv[])
{
int i = 0;
for(i = 0; i < 100; i++ )
{
count[i] = 0;
numbers[i] = 0;
}
int n;
scanf("%d",&n);
for(i = 0; i < n; i++ )
scanf("%d",&numbers[i]);
toCover(n);
//the key num m is the count[m]=1
for(i = 100; i >= 1; i-- )
{
if(count[i] == 1 && isNumbersHasK(i) == 1)
{
printf("%d",i);
break;
}
}
--i;
for(; i >= 1; i-- )
{
if(count[i] == 1 && isNumbersHasK(i) == 1)
printf(" %d",i);
}
return 0;
}
思路2
百度dalao niubility。每次觉得自己做出来了题都很有成就感，一查百度总会发现自己是个弟中弟。
思路
：
例如对
n=
3
n=3
n
=
3
进行验证的时候，我们需要计算
3、
5
、
8
、
4
、
2
、
1
3、5、8、4、2、1
3
、
5
、
8
、
4
、
2
、
1
，则
3、
5
、
8
、
4
、
2
、
1
3、5、8、4、2、1
3
、
5
、
8
、
4
、
2
、
1
称为
递推数
。
1、把输入数据放在
numbers
里面，称为
输入数
。
2、迭代砍半过程，将所有在
递推数
中出现的
输入数
改成
1
。比如按输入样例输入
3 5 6 7 8 11
这些
输入数
，递推3时，出现
递推数
3、
5
、
8
、
4
、
2
、
1
3、5、8、4、2、1
3
、
5
、
8
、
4
、
2
、
1
，则把
输入数
更新为
3 1 6 7 1 11
。
3、排序一次，从大到小输出不是
1
的
输入数
。
*再说一遍niubility。由于
5
和
8
在递推
3
时已经被覆盖，可以把
5
和
8
看成
3
的子集，只要完整递推一遍
3
，则不需要再递推
5
和
8
，
5
和
8
也不可能是
关键数
，直接用
1
覆盖。最后剩下的
非1输入数
就是没被覆盖
输入数
，即
关键数
总结
sort(int a[],int a+n) 来自c++的
#include <algorithm> using namespace std;
c语言有个qsort()函数好像要自己写comp，下次再，学。
答案3（2020-4-8 14:58:23）
#include <stdio.h>
#include <algorithm>
using namespace std;
int numbers[100];//input integers
int main(int argc, char* argv[])
{
int i = 0;
int j = 0;
int x = 0;
for(i = 0; i < 100; i++ )
numbers[i] = 0;
int n;
scanf("%d",&n);
for(i = 0; i < n; i++ )
scanf("%d",&numbers[i]);
for(i = 0; i < n; i++ )
{
x = numbers[i];
while(x != 1)
{
if(x%2==0)
x /= 2;
else
x = (3 * x + 1) / 2;
for(j = 0; j < n ; j++)
{
if(numbers[j] == x)
{
numbers[j] = 1;
break;
}
}
}
}
sort(numbers, numbers + n);
for(i = n - 1; i >= 0; i-- )
{
//I don't know why here won't come out with
//IndexOutOfBoundsException errors or something
//it just print numbers[-1] = 0. !!!
//baidu say c program language won't test index
//unless the memory you visit isn't belong to this program
//printf("%d %d %d \n",i,numbers[i],numbers[i-1]);
if(numbers[i] != 1)
printf("%d",numbers[i]);
if(numbers[i-1] > 1)//may wrong,but i would'n reivse it
printf(" ");
}
return 0;
}