# 3N+1 Problem/황재선

1. C++
2. Python
3. Python
4. 쓰레드

## 1. C++ ¶

```~cpp
#include <iostream>
using namespace std;

void input();
int process();
int findMaxCycle(int aNum, int aCount);
void output(int aMaxCycle);

int inputNum[2];

int main()
{
input();
int max = process();
output(max);
return 0;
}

void input()
{
cout << "<< ";
cin >> inputNum[0] >> inputNum[1];
}

int process()
{
int interNum = inputNum[0];
int maxCycle;
int temp;
int count = 1;

while (interNum <= inputNum[1])
{
count = 1;
temp = findMaxCycle(interNum, count);
if (maxCycle < temp)
maxCycle = temp;
interNum++;
}
return maxCycle;
}

int findMaxCycle(int aNum, int aCount)
{
if (aNum == 1)
return aCount;
if (aNum % 2)
aNum = 3 * aNum + 1;
else
aNum = aNum / 2;
aCount++;
findMaxCycle(aNum, aCount);
}

void output(int aMaxCycle)
{
cout << aMaxCycle << endl;
}
```

## 2. Python ¶

2005.1.9
```~cpp
import unittest
import psyco

class ThreeNPlusOne:
def __init__(self):
self.cycleLength = 0
self.cycleDic = {}

def compute(self, num):
self.cycleLength = 0
while (num != 1):
self.cycleLength += 1

if num % 2:
num = 3 * num + 1
else:
num /= 2
if str(num) in self.cycleDic:
return self.cycleLength + self.cycleDic[str(num)]

self.cycleLength += 1

return self.cycleLength

def computeAll(self, num1, num2):

maxLength = 0

for n in range(num1, num2+1):
length = self.compute(n)
self.cycleDic[str(n)] = length

if length > maxLength:
maxLength = length

return maxLength

class ThreeNPlusOneTest(unittest.TestCase):
def setUp(self):
self.u = ThreeNPlusOne()

def testOneCal(self):
num = 22
expected = 16
self.assertEquals(expected, self.u.compute(num))

def testTwoCal(self):
self.assertEquals(20, self.u.computeAll(1,10))
self.assertEquals(125, self.u.computeAll(100, 200))
self.assertEquals(89, self.u.computeAll(201, 210))
self.assertEquals(174, self.u.computeAll(900, 1000))
self.assertEquals(525, self.u.computeAll(1, 999999))

def main():
n = raw_input()
n1, n2 = n.split()
o = ThreeNPlusOne()
result = o.computeAll(int(n1), int(n2))
print n1, n2, result

if __name__ == '__main__':
psyco.full()
unittest.main(argv=('','-v'))
#main()
```

## 3. Python ¶

2005.1.13
```~cpp
import unittest
import psyco

cycleDic = dict()
def compute(num):
cycleLength = 1
while (num != 1):
num = (num %2 and 3 * num + 1) or num / 2
if num in cycleDic:
return cycleLength + cycleDic[num]
cycleLength += 1
return cycleLength

def computeAll(num1, num2):
maxLength = 0
for n in range(num1, num2+1):
length = compute(n)
cycleDic[n] = length
if length > maxLength:
maxLength = length
return maxLength

class ThreeNPlusOneTest(unittest.TestCase):
def testOneCal(self):
num = 22
expected = 16
self.assertEquals(expected, compute(num))

def testTwoCal(self):
self.assertEquals(20, computeAll(1,10))
self.assertEquals(125, computeAll(100, 200))
self.assertEquals(89, computeAll(201, 210))
self.assertEquals(174, computeAll(900, 1000))
self.assertEquals(525, computeAll(1, 999999))

def main():
n = raw_input()
n1, n2 = n.split()
result = computeAll(int(n1), int(n2))
print n1, n2, result

if __name__ == '__main__':
psyco.full()
unittest.main(argv=('','-v'))
#main()
```

## 4. 쓰레드 ¶

입력은 0과 1000000 사이의 값을 갖는 한 쌍의 정수이다. 1과 999999를 입력한 경우 몇 초 이내에 답이 나올까. Python으로 4초 이내를 목표로 구현했다. 하지만 만족할 만한 결과가 나오지 않았다. 안타깝게도 더이상 최적화할 묘안이 떠오르지 않는다 -- 재선

http://bioinfo.sarang.net/wiki/AlgorithmQuiz_2f3Plus1 에서 yong27님의 소스코드를 보았다. 소스가 정말 깔끔했다. 실행속도가 빨라서 그 원인을 분석해가며 지난번 작성했던 코드를 수정했다. 나의 목적은 0.001초라도 빠르게 결과를 출력하는 것이었다. 실행시간을 최소화하기위해 클래스마저 없앴다. 특히 두 부분을 수정하니 실행시간이 현저히 줄었다. 하나는 클래스 멤버변수를 제거하고 지역변수화한 경우인데 왜 그런지 모르겠다. 둘째는 사전형 타입인 cycleDic 에서 key를 문자열에서 숫자로 바꾼 부분이었다. 지난번 구현시 무엇때문에 수치형을 문자열로 변환하여 key로 만들었는지 모르겠다. -- 재선

멋진 코드
```~cpp
num = (num %2 and 3 * num + 1) or num / 2
```
```~cpp
i,j = map(int,raw_input().split())
```
둘다 무슨 의미인지 정확히 모르겠다. -- 재선