专栏首页程序员PAT(乙级)1005

PAT(乙级)1005

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

分析 :我们在1001的时候,给过卡拉兹猜想的描述的:即对任何一个自然数n,如果它是偶数,那么把它砍掉一半;如果它是奇数,那么把(3n+1)砍掉一半。这样一直反复砍下去,最后一定在某一步得到n=1。那么现在我们只需要将在砍掉的途中出现的重复数字标记出来就可以了。这样就能找到关键字了。

代码如下:

#include<stdio.h>
#include<stdlib.h>

void sort(int n, int *p);
void fun(int n, int *p);

int main()
{
	int n;
	scanf("%d",&n);
	int *p = (int *)malloc(sizeof(int)*n);
	for (int i = 0; i < n; i++)
	{
		scanf("%d",&p[i]);
	}

	fun(n, p);		//
	sort(n, p);		//排序
	printf("%d",p[0]);
	for (int i = 1; p[i] > 0; i++)
	{
		printf(" %d",p[i]);
	}

	return 0;
}
void fun(int n, int *p)
{
	int temp;
	for (int i = 0; i != n; i++)
	{
		temp = p[i];
		if (temp == 0)		//等于0,就进行下一次循环
			continue;
		while (1 != temp)	
		{
			if (0 == temp % 2)
			{
				temp /= 2;		//偶数砍掉一半
			}
			else
			{
				temp = (temp * 3 + 1) / 2;		//奇数砍掉3n+1的一半
			}
			for (int i = 0; i != n; i++)
			{
				if (temp == p[i])	//如果temp与数列中的其他数字相等,说明不是关键字,置0
				{
					p[i] = 0;
					break;
				}
			}
		}
	}
}

void sort(int n, int *p)
{
	for (int i = 0; i != n; i++)
	{
		for (int j = i+1; j != n; j++)
		{
			if (p[i] < p[j])
			{
				p[j] = p[j] ^ p[i];
				p[i] = p[j] ^ p[i];
				p[j] = p[j] ^ p[i];
			}
		}
	}
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • NOI接水问题

    15:接水问题 总时间限制: 1000ms 内存限制: 65536kB 描述 学校里有一个水房,水房里一共装有 m 个龙头可供同学们打开水,每个龙头每秒钟...

    zy010101
  • PAT(乙级)1013

    版权声明:本文为博主原创文章,转载请注明博客地址: https://blog.csdn.net/z...

    zy010101
  • PAT(乙级)1001

    对任何一个自然数n,如果它是偶数,那么把它砍掉一半;如果它是奇数,那么把(3n+1)砍掉一半。这样一直反复砍下去,最后一定在某一步得到n=1。卡拉兹在195...

    zy010101
  • 数论--康托展开与逆康托展开模板

    风骨散人Chiam
  • 2152 滑雪

    2152 滑雪  时间限制: 1 s  空间限制: 32000 KB  题目等级 : 黄金 Gold 题解  查看运行结果 题目描述 Description t...

    attack
  • 力扣 526.优美的排序(next_permutation?)

    链接:https://leetcode-cn.com/problems/beautiful-arrangement

    ACM算法日常
  • PTA 7-1 畅通工程之局部最小花费问题(35 分)

    7-1 畅通工程之局部最小花费问题(35 分) 某地区经过对城镇交通状况的调查,得到现有城镇间快速道路的统计数据,并提出“畅通工程”的目标:使整个地区任何两个城...

    Kindear
  • BZOJ1014: [JSOI2008]火星人prefix(splay 二分 hash)

    attack
  • 洛谷P1941 飞扬的小鸟(背包 dp)

    很显然的dp,设\(f[i][j]\)表示第\(i\)个位置,高度为\(j\)的最小步数

    attack
  • 水果Fruit(母函数) - HDU 2152

    转眼到了收获的季节,由于有TT的专业指导,Lele获得了大丰收。特别是水果,Lele一共种了N种水果,有苹果,梨子,香蕉,西瓜……不但味道好吃,样子更是好看。 ...

    ACM算法日常

扫码关注云+社区

领取腾讯云代金券