UVa # 100 The 3n + 1 problem - はじめてのUVa

登録してみた。

UVa Online Judge - Home

オイラーより断然むずそう。

言語がC/C++, Java, Pascalしかないってのが悲しいところですが、あんま使ったことのないC++の練習にしようかと。


問題は、入力aから入力bの範囲でコラッツのステップ数が最大になるものを答えよ。という問題。

類題はこのあたり→Problem 14 - コラッツ問題 - ボクノス


で、やってみると、Wrong answer出まくり。

合ってると思ったのに・・・なんでだろう・・・と思ってたら入力が逆になることがあるらしい。

20 1

↑こんな奴

やられた。修正してっと。

#include <iostream>
using namespace std;

int collats_count(int n)
{
    int count = 1;

    while (n > 1) {
        n = (n % 2 == 0) ? n / 2: 3 * n + 1 ;
        count++;
    }

    return count;
}

int search(int a , int b)
{
    int max = 0;

    for (int i = a; i <= b; i++) {
        int res = collats_count(i);
        if (max < res)
            max = res;
    }

    return max;
}

int main(void)
{
    int a, b;

    while (cin >> a >> b) {
        cout << a << " " << b << " ";
        cout << ((a > b) ? search(b,a): search(a,b)) << endl;
    }

    return 0;
}

断然早くなりそうなので考えてみる。それよりC++を覚えないとな・・・。