首页 > 试题广场 >

继续(3n+1)猜想 (25)

[编程题]继续(3n+1)猜想 (25)
  • 热度指数：4020 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 32M，其他语言64M
  • 算法知识视频讲解
卡拉兹(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个空格隔开，但一行中最后一个数字后没有空格。
示例1

输入

6<br/> 3 5 6 7 8 11

输出

7 6<br/>
算法知识视频讲解
添加回答
C/C++
Myhui头像 Myhui 
#include <algorithm>
#include <iostream>
using namespace std;

int main(){
    int hash[10000]={0};           //数组开大一点，不然会数组越界段错误（如n为95时可以达到485）
    int x,n,a[110],num=0;
    cin>>x;
    for(int i=0;i<x;i++){
        cin>>a[i];
        n=a[i];
        if(hash[n]==1)            //如在前面过程中已经出现覆盖过一次，直接跳过这个数（不可能合格）
            continue;
        while(n>1){
            if(n%2==0)
                n/=2;
            else n=(3*n+1)/2;
            hash[n]=1;
        }
    }
    sort(a,a+x);                  //默认从小到大排序，之后的循环从大到小输出
    for(int i=x-1;i>=0;i--){
        if(hash[a[i]]==0){
            num++;
            if(num>1) cout<<" ";  //非第一个合格的数时，先输出空格再输出数字
            cout<<a[i];
        }
    }
    return 0;
}

发表于 2018-01-26 00:23:28 回复(0)
DauBotue头像 DauBotue 
//func函数返回每次卡拉兹的中间变量
//findvalue函数查找中间变量，并从vector中删除 中间变量
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int func(int a)
{
    if (a % 2)
        return (3*a+1)/2;
    return a/2;
}

void findvalue(int a, vector<int> &vec)
{
    vector<int>::iterator it;
    for (it=vec.begin(); it!=vec.end(); it++)
    {
        if (*it == a)
        {
            it = vec.erase(it);
            break;
        }
    }
}

int main()
{
    int k;
    vector<int> vec;
    int n[100];
    cin>>k;
    for (int i=0; i<k; i++)
    {
        cin>>n[i];
        vec.push_back(n[i]);
    }
    for (int i=0; i<k; i++)
    {
        int x = n[i];
        while (x != 1)
        {
            x = func(x);
            findvalue(x, vec);
        }
    }
    sort(vec.begin(), vec.end());
    int j;
    for (j=vec.size()-1; j>0; j--)
        cout<<vec.at(j)<<' ';
    cout<<vec.at(j)<<endl;

    system("pause");
    return 0;
}

发表于 2018-01-22 18:05:47 回复(1)
Python
HelLeong-葉头像 HelLeong-葉 
def callatz(n):
    # 卡兹拉猜想的递归，偶数返回n的一半，奇数返回3n+1的一半
    if n % 2 == 0:
        return n/2
    else:
        return (3*n+1)/2


k = int(input())
input_number = input().split()
# 用list和map函数返回一个保存值类型为int的列表
input_number = list(map(int, input_number))
output_number = input_number[:]

# 去除输入列表中已被覆盖的值，剩下的即关键数
for num in input_number:
    while num != 1:
        num = callatz(num)
        if num in output_number:
            output_number.remove(num)

# 对关键数列表进行倒序，从大到小排列
output_number.sort(reverse=True)
number = ''
for i in range(len(output_number)):
    number = number + ' ' + str(output_number[i])
# 删除两端的空格并且输入结果
print(number.strip())

发表于 2017-09-25 11:16:50 回复(0)
啥头像 啥
贴个python版的 
def nextCallatz(n):
    if n%2 == 0:
        return n/2
    else:
        return (3*n+1)/2

n = input()
data = raw_input().split()
data = map(int, data)
rlt = data[:]
for num in data:
    while num != 1:
        num = nextCallatz(num)
        if num in rlt:
            rlt.remove(num)
rlt.sort(reverse = True)
rlt = map(str, rlt)
print(' '.join(rlt))


发表于 2016-01-17 19:38:26 回复(0)
刷牛客的三文鱼很爱吃肉头像 刷牛客的三文鱼很爱吃肉
PTA死活过不了                                                                         
n = io.read("*n")
local nums = {}
for i = 1, n do
    cur = io.read("*n")
    nums[cur] = false;
end
function Callatz(num)
    if(nums[num]) then
        return
    end 
    while(num ~= 1) do
        --3 --> 5 -->
        if(num % 2 == 0) then
            num = num / 2 
        else 
            num = (3 * num + 1) / 2 
        end 
        if(not nums[num]) then                                                              
            nums[num] = true
        else
            return;
        end 
    end 
    nums[num] = true
end
for k, v in pairs(nums) do
    Callatz(k)
end
ans = {}
for k, v in pairs(nums) do
    if(not v) then
        ans[#ans + 1] = k 
    end 
end

table.sort(ans, function(num1, num2)
    return num1 > num2
end)
if(#ans > 0) then
    io.write(ans[1])
end
for k = 2, #ans do
    io.write(" "..ans[k])
end
print()                                                                                     n = io.read("*n")
                                                                               

编辑于 2021-03-19 16:28:12 回复(0)
Java
奋斗201906192227359头像 奋斗201906192227359 
import java.util.ArrayList;
import java.util.Collections;
import java.util.Scanner;

public class Main
{
	public static void main(String[] args)
	{
		Scanner in = new Scanner(System.in);
		int num = in.nextInt();
		ArrayList<Integer> list = new ArrayList<>();
		for (int i = 0; i < num; i++)
			list.add(in.nextInt());
		removeDuplicated(list);
		Collections.sort(list);
		Collections.reverse(list);
		printList(list);
	}

	private static void removeDuplicated(ArrayList<Integer> list)
	{
		ArrayList<Integer> temp = new ArrayList<>(list);
		for (int i = 0; i < temp.size(); i++)
		{
			int number = temp.get(i);
			while (number != 1)
			{
				if (number % 2 == 0)
					number /= 2;
				else
					number = (3 * number + 1) / 2;
				if (list.contains(number))
					list.remove((Integer) number);
			}
		}
	}

	private static void printList(ArrayList<Integer> list)
	{
		for (int i = 0; i < list.size(); i++)
		{
			System.out.print(list.get(i));
			if (i != list.size() - 1)
				System.out.print(' ');
		}
	}
}

发表于 2020-02-19 14:22:46 回复(0)
C/C++
练习时长两年半的Java练习生头像 练习时长两年半的Java练习生 
#include<stdio.h>
#include<string.h>
int main (){//the shorter,the better.
    int n,i,t,cnt,h[10000];
    for(;~scanf("%d",&n);){
       for (memset(h,0,sizeof(h)),i = 0; i < n&&~scanf("%d",&t);i++)
            if(h[t]==0)for(h[t]=1;t!=1;t=(t%2?3*t+1:t)/2,h[t]=-1);
        for (cnt=0,i=0;i<101;h[i]<=0?:++cnt,++i);
       for (i = 100; i > 0;h[i]<=0?:printf(--cnt==0?"%d\n":"%d ",i),--i);
    }
}

发表于 2018-02-03 15:38:00 回复(1)
Mr.Husky头像 Mr.Husky 
import java.util.ArrayList;
import java.util.Collections;
import java.util.Scanner;

public class Main {
    public static void main(String[] a) {
        Scanner sc = new Scanner(System.in);
  
        while (sc.hasNext()) {
            int N = sc.nextInt();
            ArrayList<Integer> List = new ArrayList<Integer>();
            for (int i = 0; i < N; i++) {
                List.add(sc.nextInt());
            }
            ArrayList<Integer> cloneList = new ArrayList<Integer>();
            cloneList.addAll(List);
         
            for (int i = 0; i < cloneList.size(); i++) {
                int k = cloneList.get(i);
                while (k > 1) {
                    if (k % 2 == 0) {
                        k = k / 2;
                    } else {
                        k = (3 * k + 1) / 2;
                    }
                    if (List.contains(k)) {
                        List.remove((Integer) k);
                    }
                }
            }
            
            Collections.sort(List);
            Collections.reverse(List);
            
            for(int i = 0;i<List.size()-1;i++){
                System.out.print(List.get(i)+" ");
            }
            System.out.print(List.get(List.size()-1));
        }
    }
}

发表于 2017-10-02 19:31:04 回复(1)
猫猫猫1头像 猫猫猫1 
#include<bits/stdc++.h>
using namespace std;

bool hashtable[10010];

int main() {
	int n;
	cin>>n;
	int a[n];
	for(int i=0; i<n; i++) {
		cin>>a[i];
		if(hashtable[a[i]]) {
			continue;
		} else {
			int b=a[i];
			while(b!=1) {
				if(b%2==1) {
					b=(3*b+1)/2;
					hashtable[b]=1;
				} else {
					b/=2;
					hashtable[b]=1;
				}
			}
		}
	}
	vector<int> answer;
	for(int i=0; i<n; i++) {
		if(hashtable[a[i]]) {
			continue;
		}
		answer.emplace_back(a[i]);
	}
	sort(answer.rbegin(),answer.rend());
	for(int i=0;i<answer.size();i++){
		cout<<answer[i];
		if(i<answer.size()-1) cout<<" ";
	}
	cout<<endl;
	return 0;
}

发表于 2022-11-11 11:15:53 回复(0)
LeslieYoung头像 LeslieYoung 
/*继续3n+1猜想*/
#include<cstdio>
(802)#include<iostream>
#include<algorithm>
using namespace std;
const int maxn = 100000;

bool cmp(int a, int b)
{
    return a>b;
}
int main()
{
    bool hashTable[maxn] = {false};
    int n,m;
    int a[110];
    cin>>n;
    for(int i = 0; i<n; i++)
    {
        cin>>a[i];
        m = a[i];
        //对m进行3n+1猜想
        while(m!=1)
        {
            if(m%2==1)
            {
                m = (3*m+1)/2;
            }
            else
            {
                m = m/2;
            }
            hashTable[m] = true;    //将被覆盖的值置为true
        }
    }
    int count = 0;     //count用于控制输出的格式
    for(int i = 0; i<n; i++)
    {
        if(hashTable[a[i]] == false)
        {
            count++;
        }
    }
    
    sort(a,a+n, cmp);
    for(int i = 0; i<n; i++)
    {
        if(hashTable[a[i]] == false)
        {
            printf("%d", a[i]);
             count--;
            if(count > 0)
            {
                cout<<" ";
            }
        }
       
       
    }
    return 0;
    
}

发表于 2020-04-20 16:02:13 回复(0)
hestyle头像 hestyle


在前面一篇博客 PAT乙级(Basic Level)练习题 害死人不偿命的(3n+1)猜想 (15)，我们验证了一些数据是否能符合猜想，根据题意，我们不难发现我们做了很多重复的工作。此题的意思让我们减少重复工作，并且找出不能被覆盖的数。

解题前，我们需要明确“覆盖”、”被覆盖“的概念，验证n = 3时，依次计算3、5、8、4、2、1，我们只说3覆盖了5、8、4、2、1，或者说5、8、4、2、1被3覆盖。==注意，并没有说3覆盖了3自己！！！==

题目要求我们找出==没有被数组中其它数字覆盖的数字==，我们当然是把数组中各个数字验证3 * n + 1猜想所覆盖的数字，那么谁被覆盖了、没有被覆盖不就一目了然么。

#include <iostream>
(720)#include <cstring>
using namespace std;

int main() {
    int k = 0, numbers[101] = {0};
    //coveredTable[i]=true记录i被某个数的3n + 1计算覆盖了
    bool coveredTable[400] = {false};
    scanf("%d", &k);
    //获取输入的k个数
    for (int i = 0; i < k; ++i) {
        scanf("%d", numbers + i);
        //如果被覆盖了，不用再次计算
        if (coveredTable[numbers[i]]) {
            continue;
        }
        int number = numbers[i];
        //对于number,我们把它能覆盖的全部标记到coveredTable表中
        //注意，对于numbers[i]本身我们并不覆盖！！！
        while (number > 1) {
            if (number % 2 == 0) {
                number /= 2;
            } else {
                number = (number * 3 + 1) / 2;
            }
            //如果number已经被其它数覆盖过了，停止计算
            if (coveredTable[number]) {
                break;
            }
            //否则标记覆盖
            coveredTable[number] = true;
        }
    }
    //希尔排序，进行升序排序，d是步长
    int d = k / 2, temp;
    while (d > 0) {
        for (int i = d, j = 0; i < k; ++i, j = i) {
            while (j >= d && numbers[j] < numbers[j - d]) {
                //出现逆序，交换
                temp = numbers[j - d];
                numbers[j - d] = numbers[j];
                numbers[j] = temp;
                j -= d;
            }
        }
        d /= 2;//逐渐缩小步长
    }
    bool firstFlag = true;
    //输出所有没有被覆盖的number
    for (int i = k - 1; i >= 0; --i) {
        if (coveredTable[numbers[i]] == false) {
            if (firstFlag == false) {
                //注意输出格式，对于第一个输出的数字我们不输出空格，后面的需要先输出空格
                printf(" ");
            }
            firstFlag = false;
            printf("%d", numbers[i]);
        }
    }
    printf("\n");
    return 0;
}
————————————————
版权声明：本文为CSDN博主「hestyle」的原创文章，遵循 CC 4.0 BY 版权协议，转载请附上原文出处链接及本声明。
原文链接：https://hestyle.blog.csdn.net/article/details/104756772
发表于 2020-03-09 17:30:18 回复(0)
C/C++
不偷不抢安度因_头像 不偷不抢安度因_ 
#include <stdio.h>
(737)#include <stdlib.h>
 
int cmp(const void* a, const void* b)
{
    return (*(int *)b - *(int *)a);
}
 
int main()
{
    int n;
    scanf("%d", &n);
    int waiting[100] = {-1};
    //int ensure[100] = {-1};
    for(int i = 0; i < n; i++)
    {
        scanf("%d", (waiting + i));
        //ensure[i] = waiting[i];
    }
    qsort(waiting, n, sizeof(waiting[0]), cmp);
 
    int i = 0;
    while(i < n)
    {
        int temp = waiting[i];
        if(temp == -1)
        {
            i++;
            continue;
        }
        while(temp != 1)
        {
            if(temp % 2)
                temp = (temp * 3 + 1) / 2;
            else
                temp /= 2;
            for(int j = 0; j < n; j++)
            {
                if(temp == waiting[j])
                {
                    waiting[j] = -1;
                }
            }
 
        }
        i++;
    }
    //qsort(ensure, n, sizeof(ensure[0]), cmp);
    qsort(waiting, n, sizeof(waiting[0]), cmp);
    for(i = 0; i < n; i++)
    {
        if(i == 0)
            printf("%d", waiting[i]);
        else if(waiting[i] != -1)
            printf(" %d", waiting[i]);
    }
    printf("\n");
    return 0;
}

发表于 2020-03-04 20:11:20 回复(0)
C/C++
CodePanda头像 CodePanda 
#include<bits/stdc++.h>
using namespace std;
int main(){
	int k;cin>>k;
	bool hash1[101]={false};
	vector<bool> hash2(200,true);	
	for(int i=0;i<k;i++){
		int t;cin>>t;
		hash1[t]=true;
		while(t!=1){			
			if(t%2==0) t=t/2;
			else t=(3*t+1)/2;
			hash2[t]=false;
		}
	}
	int num=0;
	for(int i=100;i>1;i--){
		if(hash1[i]&&hash2[i]){
			num++;
			if(num>1) printf(" %d",i);
			else printf("%d",i);
		}
	}
	return 0;
} 

发表于 2020-01-15 10:57:56 回复(0)
平头哥，冲呀~头像 平头哥，冲呀~
超级简单的C++代码 
#include <iostream>
#include <vector>
using namespace std;

int main()
{     int k, n, num[10000] = {0}, a, tmp, max = 0;     cin >> k;     //建立num数组，待验证的数字就是数组的下标，数组的值为1,num数组初始值为0.      for(int i = 0; i < k; ++i){         cin >> a;         max = (a > max) ? a : max;          num[a]++;         tmp = a;         do{             if(tmp%2){                 tmp = (3*tmp+1)/2;                 num[tmp] -= 2;             }else{                 tmp /= 2;                 num[tmp] -= 2;             }         }while(tmp != 1);     }     int cnt = 0;     for(int i = max; i >= 0; --i){         if(num[i] == 1 && cnt == 0){             cnt++;             cout << i;         }             else if(num[i] == 1)             cout << " " << i;      }     return 0;
}

发表于 2019-04-01 20:25:49 回复(0)
C/C++
hanjiangxue头像 hanjiangxue 
//欢迎参观鄙人的博客https://blog.csdn.net/qq_33375598
#include<cstdio>
#include<algorithm>
using namespace std;

int A[110];
bool hashTable[10000] = {false};

bool cmp(int a, int b){
  return a > b;         //从大到小
} 

int main(int argc, char const *argv[])
{
  int n;
  scanf("%d", &n);
  for (int i = 0; i < n; ++i)
  {
    scanf("%d", &A[i]);
  int m = A[i];
  while(m != 1){            //将被覆盖数flag设置为true
      if(m % 2 == 0){
        m /= 2;
      }else{
        m = (m * 3 + 1) / 2;
      }
       hashTable[m] = true;
    }
  }

sort(A, A + n , cmp);   //排序

int count = 0;
for (int i = 0; i < n; ++i)   //统计关键字个数
{
  if(hashTable[A[i]] == false) count++;
}

for (int i = 0; i < n; ++i)
{
  if(hashTable[A[i]] == false){
    printf("%d", A[i]);
    count--;
    if(count > 0) printf(" ");//控制输出格式
  }
}

  return 0;
}
发表于 2019-03-02 08:51:54 回复(0)
C/C++
romanten头像 romanten 
//稍显复杂
//1037.继续(3n+1)猜想
#include <iostream>
#include <string>
#include <algorithm> //std::sort
using namespace std;
int main() 
{
    int n,fg[200]={0},a[100]={0};
    cin>>n;
    for(int j=0;j<n;++j){ //算出每个数字覆盖的
        cin>>a[j];
        int t=a[j];
        while(t!=1){
            if(t%2==0) t=t/2;
            else t=(t*3+1)/2;
            for(int i=0;i<200;++i){
                if(fg[i]==t) break;
                else if(t!=1&&fg[i]!=t&&fg[i]==0) {fg[i]=t; break;}
            }
        }
    }
    int ans[100],num=0;
    for(int i=0;i<n;++i){ //是否处于覆盖数组中
        int f=1;
        for(int j=0;j<200;++j){
            if(fg[j]==0) break;
            if(fg[j]==a[i]) {f=0; break;}
        }
        if(f==1){
            ans[num]=a[i]; num++;
        }
    }
    sort(ans,ans+num); //默认升序，降序需要自己写函数
    for(int i=num-1;i>0;--i){
        cout<<ans[i]<<" ";
    }
    cout<<ans[0]<<endl;
    return 0;
}
发表于 2019-02-14 17:24:31 回复(0)
vcjmhg头像 vcjmhg 
//继续3n+1猜想
#include <iostream>
#include <stdio.h>
#define maxsize 10000
void process(int num);   //处理数字的函数

int count[maxsize]; //统计数字出现的频数
int main(){
    int K,temp;
    int flags[maxsize];
    for (int i = 0; i < maxsize; i++) {
        count[i] = 0;
        flags[i] = false;
    }
    scanf("%d", &K);
    for (int i = 0; i < K; i++){
        scanf("%d", &temp);
        flags[temp] = true;
        process(temp);
    }
    //输出结果
    bool formatFlag = false; //判断输出的第一个数前边没有空格
    for (int i = maxsize; i >= 1; i--){
        if (count[i] == 1&&flags[i]&&formatFlag){
            printf(" %d", i);
        }
        else if (count[i] == 1 && flags[i] && !formatFlag){
            printf("%d", i);
            formatFlag = true;
        }
    }
    //system("pause");
}
void process(int num){
    while (num != 1)
    {
        count[num]++;
        if (num % 2 == 0) num /= 2;
        else
        {
            num = (3 * num + 1) / 2;
        }
    }
}
发表于 2018-12-29 10:47:02 回复(0)
Disconnect头像 Disconnect 
def find(a):
    while a>1:
        if a%2==0:
            a = a//2
            res.append(a)
        else:
            a = (3*a+1)//2
            res.append(a)      
def c(t):
  te = []
  for j in t:
        if res.count(j)>0:
            te.append(j)
  if te:
      return te
    
n = input()
n = int(n)
res,out,temp = [],[],[]
lst = list(map(int,input().split()))
if n>1:
    for i in range(0,n):
        find(lst[i])
        tem = lst[:i]+lst[i+1:]
        if c(tem):
            temp.extend(c(tem))
        res = []
    out = sorted(set(lst)-set(temp))
    out.reverse()
    out  = list(map(str,out))
    print(" ".join(out))
else:
    print(lst[0])     

发表于 2018-12-01 00:01:37 回复(0)
SupritYoung头像 SupritYoung
详细题解
发表于 2018-11-24 10:45:03 回复(0)
C/C++
Caffeine头像 Caffeine 
思路：对应数据如果被计算到标记，然后统计那些没有被标记到的数据。
题目意思：就是找出没有被因为其他的计算顺便计算出来的数据，他给了我，他给了我们一堆测试数据。
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

void Callatz(int n, vector<int> v, int *p)
{
    for (int i = 0; i < n; i++)
    {
        while (v[i] != 1)
        {
            if (v[i] % 2 == 0)
            {
                v[i] = v[i] / 2;
                
            }
            else
            {
                v[i] = (3 * v[i] + 1) / 2;
            }
            p[v[i]]++;
        }
    }
}

bool Cmp(int & a, int & b)
{
    return a > b;
}

int main()

{
    int k;
    while (cin >> k)
    {
        int v[10000] = {0};
        int temp;
        vector<int> vv(k);
        for (int i = 0; i < k; i++)
        {
            cin >> vv[i];
        }
        Callatz(k, vv, v);
        vector<int> rlt;
        for (int i = k-1; i >= 0; i--)
        {
            if (v[vv[i]] == 0)
            {
                rlt.push_back(vv[i]);
            }
        }
        sort(rlt.begin(), rlt.end(), Cmp);
        for (auto c : rlt)
        {
            if (c != rlt[rlt.size() - 1])
                cout << c << " ";
            else
                cout << c << endl;
        }

    }
}

发表于 2018-08-14 15:54:44 回复(0)
提交观点

问题信息

难度：
29条回答 15645浏览

热门推荐

通过挑战的用户

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号