Maintenance script: Repair pages found by live-compare batch 0001

2026-03-26T14:46:17Z

Repair pages found by live-compare batch 0001

← Older revision		Revision as of 14:46, 26 March 2026
Line 20:		Line 20:
	count = 1		count = 1
	while(aNumber != 1):		while(aNumber != 1):
	if(IsInRange(aMin, aMax, aNumber) and aBinaryMap[aNumber-aMin]):		if(IsInRange(aMin, aMax, aNumber) and aBinaryMap[aNumber-aMin]):
	aBinaryMap[aNumber-aMin] = False		aBinaryMap[aNumber-aMin] = False
	if(aNumber%2 == 0):		if(aNumber%2 == 0):
	aNumber = aNumber/2		aNumber = aNumber/2
Line 39:		Line 39:
	binaryMap = range(rangeOfMap)		binaryMap = range(rangeOfMap)
	for i in range(rangeOfMap):		for i in range(rangeOfMap):
	binaryMap[i] = True		binaryMap[i] = True
	return binaryMap		return binaryMap

Line 45:		Line 45:
	maxCycleLength = 0		maxCycleLength = 0
	for i in range(aMin, aMax+1):		for i in range(aMin, aMax+1):
	if(aBinaryMap[i-aMin]):		if(aBinaryMap[i-aMin]):
	cycleLength = TreeNPlusOne(i, aMin, aMax, aBinaryMap)		cycleLength = TreeNPlusOne(i, aMin, aMax, aBinaryMap)
	if(maxCycleLength < cycleLength):		if(maxCycleLength < cycleLength):
Line 64:		Line 64:
	tempI = i		tempI = i
	while(IsInRange(aMin, aMax, 2*tempI)):		while(IsInRange(aMin, aMax, 2*tempI)):
	aBinaryMap[tempI-aMin] = False		aBinaryMap[tempI-aMin] = False
	tempI = 2*tempI		tempI = 2*tempI

Line 81:		Line 81:
	----		----
	[[3N+1Problem]]		[[3N+1Problem]]

imported>Unknown at 05:22, 7 February 2021

2021-02-07T05:22:16Z

New page

== 파이선 ==
파이선으로 재귀호출을 한번 구현해보았으나, 엄청 느리다.
def TreeNPlusOne(aNumber):
print aNumber,
if aNumber == 1:
return
elif aNumber%2 == 0:
aNumber /= 2
else:
aNumber = 3*aNumber+1
TreeNPlusOne(aNumber)

=== 알고리즘 ===
# 22의 경우 22, 11, 34...이렇게 되는데 22의 싸이클 안에 11, 34등의 싸이클도 포함되니 최대값에서 그들을 배제하는 것이 가능하다.
# 범위 안에 어떤수의 2의 배수가 있는 경우(또는 (x - 1)/3이 있는 경우) 1과 같은 이유로 그 수는 최대값에서 배제한다.
----
범위(Range)를 인위적으로 줄여야한다는 결론에 도달.
=== 소스 ===
def TreeNPlusOne(aNumber, aMin, aMax, aBinaryMap):
count = 1
while(aNumber != 1):
if(IsInRange(aMin, aMax, aNumber) and aBinaryMap[aNumber-aMin]):
aBinaryMap[aNumber-aMin] = False
if(aNumber%2 == 0):
aNumber = aNumber/2
else:
aNumber = aNumber*3+1
count = count + 1
return count

def InputRange():
min, max = input('최소, 최대: ')
while IsCorrectInput(min, max) == False:
min, max = input('최소, 최대: ')
return min, max

def MakeBinaryMap(aMin, aMax):
rangeOfMap = aMax - aMin + 1
binaryMap = range(rangeOfMap)
for i in range(rangeOfMap):
binaryMap[i] = True
return binaryMap

def FindMaxCycleLength(aMin, aMax, aBinaryMap):
maxCycleLength = 0
for i in range(aMin, aMax+1):
if(aBinaryMap[i-aMin]):
cycleLength = TreeNPlusOne(i, aMin, aMax, aBinaryMap)
if(maxCycleLength < cycleLength):
maxCycleLength = cycleLength
return maxCycleLength

def OutputResult(aMin, aMax, aMaxCycleLength):
print aMin, aMax, aMaxCycleLength

def IsInRange(aMin, aMax, aNumber):
if(aMin <= aNumber and aMax >= aNumber):
return True
else:
return False

def PreInspection(aMin, aMax, aBinaryMap):
for i in range(aMin, aMax/2+1):
tempI = i
while(IsInRange(aMin, aMax, 2*tempI)):
aBinaryMap[tempI-aMin] = False
tempI = 2*tempI

def IsCorrectInput(aMin, aMax):
if(aMin > 0 and aMax < 1000000 and aMin < aMax):
return True
else:
print 'Not Accept'
return False

if __name__ == '__main__':
min, max = InputRange()
binaryMap = MakeBinaryMap(min, max)
PreInspection(min, max, binaryMap)
OutputResult(min, max, FindMaxCycleLength(min, max, binaryMap))
----
[[3N+1Problem]]

3N+1Problem/강희경 - Revision history

Maintenance script: Repair pages found by live-compare batch 0001

imported>Unknown at 05:22, 7 February 2021