G – SimpleCollatzSequence

发布于 2020-10-08  244 次阅读




SimpleCollatzSequence

The Simple Collatz Sequence (SCS) starting at an integer n, is defined by the formula:

S(k) = (k/2 if k is even, else (k+1))

The sequence is then n, S(n), S(S(n)), … until the value first reaches 1.
For example, starting at 11, we have:

11 -> 12 -> 6 -> 3 -> 4 -> 2 ->1

The sequence always ends at 1. (Fun Fact: The Hard Collatz Sequence sends odd k to 3*k+1. It is unknown whether that sequence always ends at 1.)
Let A(n) = number of steps in the SCS starting at n. For example, A(11) = 6. Write a program which computes A(n) for a given input n.

Input
Input consists of a single line which contains a positive decimal integer, n, which starts the sequence. n will fit in a 32-bit unsigned integer.

Output
The output consists of a single line that contains the value of A(n), the number of steps in the SCS starting at n.

Sample Input
11

Sample Output
6

Sample Input 2
123456789

Sample Output 2
39

题意:水题,判断当前数字为奇数还是偶数,奇数则n=n+1;偶数则n=n/w;计算该数字最终到达不可分割的最终步数输出即可。
思路:根据题意模拟即可。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main() {
	ll n;
	cin>>n;
	ll cnt=0;
	while(n!=1)
	{
		if(n%2==0)
			n/=2;
		else
			n+=1;
		cnt++;
	}
	cout<<cnt<<endl;
	return 0;
}