当前位置:网站首页>1005 继续(3n+1)猜想 (25 分)
1005 继续(3n+1)猜想 (25 分)
2022-08-09 10:13:00 【Simonqwer】
1005 继续(3n+1)猜想 (25 分)
卡拉兹(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
#include<iostream>
using namespace std;
#include<iomanip>
#include<algorithm>
#include<string>
#include<queue>
#include<vector>
#include<map>
#include<cstring>
#include<cstdlib>
#include<cmath>
const int N=100;
int main()
{
ios_base::sync_with_stdio(0);
int n;
while( cin >>n )
{
int a[N],b[N],c[N],d[N],i,t=0;
for(i=0;i<n;i++)
{
cin >> a[i];
b[i]=a[i];
c[i]=1;
}
for(i=0;i<n;i++)
{
while( b[i]!=1 )
{
if( b[i]%2!=0 )
{
b[i]=(b[i]*3+1)/2;
}
else
{
b[i]/=2;
}
for(int j=0;j<n;j++)
{
if( a[j]==b[i] )
{
c[j]=0;
}
}
}
}
for(i=0;i<n;i++)
{
if(c[i]==1)
d[t++]=a[i];
}
sort(d,d+t);
for(i=t-1;i>0;i--)
{
cout << d[i] << ' ';
}
cout << d[0] << endl;
}
return 0;
}
边栏推荐
猜你喜欢
Attentional Feature Fusion
【MySQL】mysql因为字符集导致left join出现Using join buffer (Block Nested Loop)
【八大排序②】选择排序(选择排序,堆排序)
[ASM] Bytecode operation MethodVisitor case combat generation object
[贴装专题] 基于多目视觉的手眼标定
Practical skills: a key for image information in the Harbor, quick query image
MySQL执行过程及执行顺序
循环嵌套以及列表的基本操作
多行省略和选择器
3D printed this DuPont cable management artifact, and the desktop is no longer messy
随机推荐
[Machine Learning] Detailed explanation of web crawler combat
时间复杂度和空间复杂度
虚拟列表key复用问题
学长告诉我,大厂MySQL都是通过SSH连接的
元组 字典 集合
MySQL备份与恢复
分类预测 | MATLAB实现CNN-LSTM(卷积长短期记忆神经网络)多特征分类预测
京东物流与五菱将开发联名版定制产品
【MySQL】mysql因为字符集导致left join出现Using join buffer (Block Nested Loop)
面试官:MySQL 中 update 更新,数据与原数据相同时会执行吗?大部分人答不上来!
EndNote使用指南
好久没更新博客了
Master-slave postition changes cannot be locked_Slave_IO_Running shows No_Slave_Sql_Running shows No---Mysql master-slave replication synchronization 002
Attentional Feature Fusion
tuple dictionary collection
程序环境和预处理
今天做了手机播放器的均衡器
KMP& sunday
StratoVirt 中的虚拟网卡是如何实现的?
如何快速打通镜像发布流程?