The 3n + 1 problem

From Progteam

Jump to: navigation, search
Checkmark.jpg This problem has been solved by mlc413.
Checkmark.jpg This problem has been solved by kerry.


The 3n+1 Problem
Problem Number 1207
Sorter: mlc413
Source: Programming Challenges
Link: http://acm.pku.edu.cn/JudgeOnline/problem?id=1207



The 3n+1 Problem is problem number 1207 on the Peking University ACM site.

This is also one of the sample problems from the Programming Challenges book (Problem 1.6.1 page 15).




import java.util.*;

public class Main{

    public static Scanner in;
 
    public static void main(String[] args){
        in=new Scanner(System.in);

        doStuff();
    }

    public static void doStuff(){
        while(in.hasNext()){
	    int x = in.nextInt();
	    int y = in.nextInt();
	    System.out.print(x + " " + y + " ");
	    solve(Math.min(x, y), Math.max(x, y));
      
	}
    }

    public static void solve(int i, int j){
	int max = 0;
	for (int m = i; m <= j; m++){
	    max = Math.max(max, getCycle(m));
	}
	
	System.out.print(max + "\n");
    }
    
    public static int getCycle(int m){
	int cycles = 1;
	int tmp = m;
	while(tmp  != 1){
	    cycles++;
	    if(tmp%2  != 0)
		tmp = 3*tmp + 1;
	    else
		tmp = tmp/2;
	}
	return cycles;
    }
}



Kerry answer in C


#include <stdio.h>
#include <stdlib.h>
#include <string.h>
int total;
int pathlen(int, int);

int main() {
int i, j, tmpi, tmpj, x, stop, max;

max=0;
stop=0;

while (!stop) {
        scanf("%d %d", &i, &j );

        if (j<i) {
                tmpi = j;
                tmpj =i;
        }
        else {
                tmpi=i;
                tmpj=j;
        }

        max=0;
        for (x=tmpi;x<=tmpj;x++) {
                total=0;
                pathlen(x, 0);
                if (total > max) max = total;
        }
        if (getchar()!= '\n') return;
        printf("%d %d %d\n", i, j, max);
        }
}

int pathlen( int x, int currlen) {
total = currlen;

        if (x==1) {
                total++;
                return;
        }
        else if (x%2 == 1) {
                x=(3*x+1);
                total++;
                pathlen(x, total);
        }
        else {
                x=(x/2);
                total++;
                pathlen(x, total);
        }
}

Personal tools