awesq123的部落格

找出每個數字的cycle_length 再找出 start 和 end之間cycle_length的最大值

網址:

https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=3&page=show_problem&problem=36

-------------------------------------------------------

#include <stdio.h>

int main()
{
    int start, end, num, cycle_length, max, temp;

    while(scanf("%d%d", &start, &end) == 2)
    {
        printf("%d %d ", start, end);
        if(start > end)
        {
            temp = start;
            start = end;
            end = temp;
        }
        for(max = 0; start <= end; start++) /* From start to end */
        {
            num = start;
            for(cycle_length = 0; num > 1; cycle_length++) /* Process a certain number. */
            {
                if(num & 1) /* odd */
                    num = 3 * num + 1;
                else /* even */
                    num /= 2;
            }
            if(max < cycle_length)
                max = cycle_length;
        }
        printf("%d\n", max+1);
    }

    return 0;
}
 

-2017-05-22----------------------------------------------------

import java.util.*;

public class main {

    public static void main(String[] args) {
        int stepsPerNum[] = new int[1010000];
        Arrays.fill(stepsPerNum, 0);
        try {
            int numA, numB;
            Scanner in = new Scanner(System.in);
            while (in.hasNextInt()) {
                numA = in.nextInt();
                numB = in.nextInt();
                System.out.print("" + numA + " " + numB + " ");
                if (numA > numB) {
                    int temp = numA;
                    numA = numB;
                    numB = temp;
                }

                // Calculate from numA to numB(inclusive)
                for (int i = numA; i <= numB; i++) {
                    if (stepsPerNum[i] == 0) {
                        stepsPerNum[i] = do3nPlus1(i);
                    }
                }
                System.out.println("" + findMax(stepsPerNum, numA, numB));
            }
            in.close();
        } catch (Exception e) {
            System.out.println("Input error!");
        }
    }

    private static int do3nPlus1(int val) {
        int times = 1; // Count frome 1
        for (; val > 1; times++) {
            // odd
            if (val % 2 != 0) {
                val = 3 * val + 1;
            } else {
                // even
                val /= 2;
            }
        }
        return times;
    }

    // endIdx: inclusive
    private static int findMax(int[] arr, int statrIdx, int endIdx) {
        int max = Integer.MIN_VALUE;
        for (int i = statrIdx; i <= endIdx; i++) {
            if (max < arr[i]) {
                max = arr[i];
            }
        }
        return max;
    }
}