害死人不偿命的(3n+1)猜想【PAT(1/95)】题解

308 阅读 5 评论 0 点赞

[1001 害死人不偿命的(3n+1)猜想 (15 分)](https://pintia.cn/problem-sets/994805260223102976/problems/994805325918486528 "1001 害死人不偿命的(3n+1)猜想 (15 分)")

```
卡拉兹(Callatz)猜想：
对任何一个正整数 n，如果它是偶数，那么把它砍掉一半；如果它是奇数，那么把 (3n+1) 砍掉一半。这样一直反复砍下去，最后一定在某一步得到 n=1。卡拉兹在 1950 年的世界数学家大会上公布了这个猜想，传说当时耶鲁大学师生齐动员，拼命想证明这个貌似很傻很天真的命题，结果闹得学生们无心学业，一心只证 (3n+1)，以至于有人说这是一个阴谋，卡拉兹是在蓄意延缓美国数学界教学与科研的进展……
我们今天的题目不是证明卡拉兹猜想，而是对给定的任一不超过 1000 的正整数 n，简单地数一下，需要多少步（砍几下）才能得到 n=1？
```
```
输入格式：
每个测试输入包含 1 个测试用例，即给出正整数 n 的值。
```
```
输出格式：
输出从 n 计算到 1 需要的步数。
```
```
输入样例：
3
```
```
输出样例：
5
```
题解：
```
这是浙大PAT的第一题，题意比较简单。
算法如下：
1.算法开始。
2.如果n!=1，下一步。否则跳到第五步。
3.如果n是偶数，n/=2，step++，回到第二步。否则进行下一步。
4.如果n是奇数，n=（3n+1）/2，step++，回到第二步。
5.输出step。
6.算法结束。
```
C++代码
```
#include <iostream>
using namespace std;
int main()
{
    int n,step=0;
    cin>>n;
    while(1){
        if(n==1)break;
        else{
            if(n%2==0){
                n/=2;
                step++;
            }
            else {
                n=(3*n+1)/2;
                step++;
            }
        }
    }
    cout<<step<<endl;
    return 0;
}

```
其实代码可以更简洁，这样写思路会比较清晰，也说明我对C/C++不够深入。

0.0分

2 人评分

本文分类：文章列表
浏览次数：308 次浏览
发布日期：2019-07-31 21:32:34
本文链接：https://blog.dotcpp.com/a/61021

上一篇 > 二路归并，最简单的归并算法
下一篇 > 写出这个数【PAT(2/95)】题解

C语言网提供由在职研发工程师或ACM蓝桥杯竞赛优秀选手录制的视频教程，并配有习题和答疑，点击了解：

一点编程也不会写的：零基础C语言学练课程

解决困扰你多年的C语言疑难杂症特性的C语言进阶课程

从零到写出一个爬虫的Python编程课程

只会语法写不出代码？手把手带你写100个编程真题的编程百练课程

信息学奥赛或C++选手的必学C++课程

蓝桥杯ACM、信息学奥赛的必学课程：算法竞赛课入门课程

手把手讲解近五年真题的蓝桥杯辅导课程

评论列表共有 5 条评论

流离之人追逐幻影 5年前回复TA

@善良先生 哈哈哈

善良先生 5年前回复TA

if...if语句是互不干涉的，即每个语句都要执行，if和else是互斥的，即执行了if就不在执行else语句。。
我就栽在了这上面，，哭了。。

善良先生 5年前回复TA

@善良先生 哦哦哦，有错，哈哈哈我傻了，改对了

善良先生 5年前回复TA

#include <iostream>
using namespace std;
int main(){
	int n;
	cin>>n;
	int num = 0;
	while(1){
		if(n==1){
			break;
		}
		else{
			if(n%2==0){
				n = n/2;
				num++;
			}
			if(n%2==1){
				n = (3*n+1)/2;
				num++;
			}
		}
		
	}
	cout<<num<<endl;
	
	return 0;
}

善良先生 5年前回复TA

我也是同样的做法，超时啊0.0.。。。。

害死人不偿命的(3n+1)猜想 【PAT(1/95)】题解

数位dp#2491: 信息学奥赛一本通T1587-Windy 数(C++)

点进来你会后悔的

简简单单的循环

简单的回文数

评论列表 共有 5 条评论

发表评论 取消回复

害死人不偿命的(3n+1)猜想【PAT(1/95)】题解

评论列表共有 5 条评论

发表评论取消回复