The 3n + 1 problem의 C#/Java 버전 풀이
두뇌를 말랑말랑하게 유지하려고 "알고리즘 트레이닝 북"을 구매했습니다. ^^
Programming Challenges - 알고리즘 트레이닝 북
; http://www.yes24.com/24/Goods/1396784?Acode=101
오일러도 88번까지 풀다가 문제가 더 출제되지 않아서 그만두고 있었는데,
일단... "Project Euler @kr" 88번까지 완료! ^^
; https://www.sysnet.pe.kr/0/0/427
오랜만에 방문해 보니 어느새 113번 문제까지 출제가 되었네요. ^^ 그래도, 책을 구매했으므로 이것 먼저 하고 오일러를 손대야 할 것 같습니다. ^^
우선 첫 번재 문제!
The 3n + 1 problem
; http://www.programming-challenges.com/pg.php?page=downloadproblem&probid=110101&format=html
C# 언어로 만들어 봤는데,
using System;
using System.Collections.Generic;
namespace ConsoleApplication1
{
class Program
{
Dictionary<long, int> _cycles = new Dictionary<long, int>();
List<long> _steps = new List<long>();
static void Main(string[] args)
{
Program my = new Program();
my.Run();
}
private void Run()
{
_cycles.Add(1, 1);
while (true)
{
string txt = Console.ReadLine();
if (string.IsNullOrEmpty(txt) == true)
{
break;
}
string[] numbers = txt.Split(' ');
long start = UInt32.Parse(numbers[0]);
long end = UInt32.Parse(numbers[1]);
if (start > end)
{
long temp = start;
start = end;
end = temp;
}
long ticks = Environment.TickCount;
int maxLength = GetMaxCycle(start, end);
long diff = Environment.TickCount - ticks;
Console.WriteLine(start + " " + end + " " + maxLength + ", elapsed: " + diff);
}
}
private int GetMaxCycle(long start, long end)
{
int maxLength = 0;
for (long i = start; i <= end; i++)
{
int cycleLength = GetCycleLength(i);
if (maxLength < cycleLength)
{
maxLength = cycleLength;
}
}
return maxLength;
}
private int GetCycleLength(long i)
{
_steps.Clear();
while (_cycles.ContainsKey(i) != true)
{
_steps.Add(i);
if (i % 2 == 0)
{
i /= 2;
}
else
{
i = i * 3 + 1;
}
}
int cycleLength = _cycles[i] + _steps.Count;
int result = cycleLength;
if (_steps.Count > 0)
{
foreach (long s in _steps)
{
_cycles[s] = cycleLength--;
}
}
return result;
}
}
}
아쉽게도 programming-challenges 공식 사이트에서는 C, C++, Java, Pascal 언어만 지원하기 때문에 자바로도 만들어 봤습니다.
import java.io.*;
import java.util.*;
class Main {
static String ReadLn(int maxLength) {
byte line[] = new byte[maxLength];
int length = 0;
int input = -1;
try {
while (length < maxLength) {
input = System.in.read();
if ((input < 0) || (input == '\n'))
break;
line[length++] += input;
}
if ((input < 0) && (length == 0))
return null;
return new String(line, 0, length);
} catch (IOException e) {
return null;
}
}
public static void main(String args[])
{
Main myWork = new Main();
myWork.run();
}
HashMap<Long, Integer> _cycles = new HashMap<Long, Integer>();
ArrayList<Long> _steps = new ArrayList<Long>();
public void run() {
String input;
StringTokenizer idata;
_cycles.put(1L, 1);
while ((input = Main.ReadLn(255)) != null) {
idata = new StringTokenizer(input);
long start = Long.parseLong(idata.nextToken());
long end = Long.parseLong(idata.nextToken());
if (start > end) {
long temp = start;
start = end;
end = temp;
}
long ticks = System.currentTimeMillis();
int maxLength = GetMaxCycle(start, end);
long diff = System.currentTimeMillis() - ticks;
System.out.println(start + " " + end + " " + maxLength
+ ", elapsed: " + diff);
}
}
public int GetMaxCycle(long start, long end) {
int maxLength = 0;
for (long i = start; i <= end; i++) {
int cycleLength = GetCycleLength(i);
if (maxLength < cycleLength) {
maxLength = cycleLength;
}
}
return maxLength;
}
private int GetCycleLength(long i) {
_steps.clear();
while (_cycles.containsKey(i) != true) {
_steps.add(i);
if (i % 2 == 0) {
i /= 2;
} else {
i = i * 3 + 1;
}
}
int cycleLength = _cycles.get(i) + _steps.size();
int result = cycleLength;
if (_steps.size() > 0)
{
for (long s : _steps) {
_cycles.put(s, cycleLength--);
}
}
return result;
}
}
입력 파일인 data.txt 파일을 다음과 같이 구성해서,
1 10
100 200
201 210
900 1000
1 1000000
C#, Java 버전의 코드를 실행하면 다음과 같은 실행 결과가 나옵니다.
D:>ConsoleApplication1.exe < i.txt
1 10 20, elapsed: 16
100 200 125, elapsed: 0
201 210 89, elapsed: 0
900 1000 174, elapsed: 0
1 1000000 525, elapsed: 406
D:>java -classpath . Main < i.txt
1 10 20, elapsed: 0
100 200 125, elapsed: 1
201 210 89, elapsed: 0
900 1000 174, elapsed: 2
1 1000000 525, elapsed: 1186
그나저나... 자바 버전으로 만든 소스코드에서 elapsed 측정을 제외시켜 다음과 같이 출력이 나오도록 변경한 다음,
D:>java -classpath . Main < i.txt
1 10 20
100 200 125
201 210 89
900 1000 174
1 1000000 525
"
http://www.programming-challenges.com" 웹 사이트에 제출하면 답이 틀렸다(Wrong answer)고 나옵니다. 웹을 검색해서 다른 사람들의 답과 비교해봐도 답이 틀린 것은 모르겠는데... 암튼 답이 틀렸다고 나옵니다. 혹시 어떤 기준으로 저런 판정이 났는지 아시는 분은 덧글 부탁드립니다. ^^
어쨌든 재미있군요. 가끔씩 심심할 때마다 풀어봐야겠습니다. ^^
참고로, C++ 버전도 추가.
#include <iostream>
#include <string>
#include <vector>
#include <cstring>
#include <algorithm>
#include <map>
using namespace std;
class Ch1_3n1
{
int _start;
int _end;
map<int, int> _cache;
public:
Ch1_3n1(int start, int end)
{
_start = start;
_end = end;
if (_start > _end)
{
swap(_start, _end);
}
}
int calc()
{
int result = 0;
for (int i = _start; i <= _end; i++)
{
result = max(result, calc3n1(i, 1));
}
return result;
}
int calc3n1(int n, int depth)
{
map<int, int>::iterator it = _cache.find(n);
if (it != _cache.end())
{
return it->second + depth;
}
if (n == 1)
{
return depth;
}
int totalDepth = 0;
if ((n % 2) == 0)
{
totalDepth = calc3n1(n / 2, depth + 1);
}
else
{
totalDepth = calc3n1(n * 3 + 1, depth + 1);
}
_cache.insert(pair<int, int>(n, totalDepth - depth));
return totalDepth;
}
};
// https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=29&page=show_problem&problem=36
int main()
{
while (true)
{
int start = -1;
int end = -1;
cin >> start;
cin >> end;
if (start == -1 && end == -1)
{
break;
}
Ch1_3n1 c(start, end);
cout << start << " " << end << " " << c.calc() << endl;
}
return 0;
}
[이 글에 대해서 여러분들과 의견을 공유하고 싶습니다. 틀리거나 미흡한 부분 또는 의문 사항이 있으시면 언제든 댓글 남겨주십시오.]