ZeroJudge B553: Collatz Problem

The Collatz problem (also known as the "3N + 1" problem) begins with a positive integer N greater than 1, and follows these transformation rules:

  • If N is even (i.e., divisible by 2), then divide N by 2, i.e., N becomes N÷2.
  • If N is an odd number greater than 1 (i.e., not divisible by 2), then multiply N by 3 and add 1, i.e., N becomes 3N+1.
  • If N is 1, then stop.

For example, starting from 5, the transformation steps are as follows: 5→5×3+1=16→16÷2=8→8÷2=4→4÷2=2→2÷2=1.

Starting from 7, we get the following sequence:
7→22 →11 →34 →17 →52 →26 →13 →40 →20 →10 →5→16 →8→4→2→1
This time it's a bit more complex. There were a total of 16 transformations, but we eventually stopped at 1.

Now, I'd like you to write a program to determine the number of transformations.

Sample Inputs/Outputs

Sample Input(s)Sample Output(s)
The test data consists of 1 to 10 lines terminated by EOF. Each line contains a positive integer N, with values ranging from 2 to 30,000.For each input line, the output data is a positive integer representing how many transformations are needed for N to reach 1.
3
5
7		7
5
16

Thought Process

You can declare a function that returns two integers, one representing the current number being operated on and the other representing the number of operations performed so far.

Each time you evaluate the Collatz problem (3N + 1), you should return the value of the number being operated on, and remember to increment the operation count by 1. If the computed number is 1, then return the operation count.

Sample Code－ZeroJudge B553: Collatz Problem

#include <iostream>
using namespace std;

int calc(int N, int count)
{
    if (N == 1) return count;
    if (N % 2 == 1) return calc((3*N)+1, count+1);
    return calc(N/2, count+1);
}

int main() {
    cin.sync_with_stdio(0);
    cin.tie(0);
    int N;
    while (cin >> N)
    {
        cout << calc(N, 0) << "\n";
    }
}

//ZeroJudge B553
//Dr. SeanXD
Tags

Related Posts

Comments