import time
start = time.time()
cntlist = []
for i in range(2, 1000000):
numlist =
num = i
while num != 1:
if num % 2 == 0:
num /= 2
else:
num = num * 3 + 1
numlist.append(num)
if num in numlist:
cntlist.append(len(numlist))
print max(cntlist)
print time.time() - start
十分初级的版本。考虑优化点有2：
1、类似素数筛选法：已经算过的数的2的n次方倍数的数，计数直接+n，结束。
2、维护一个数的序列的表，如果出现某个数在列表内，则计数直接加上列表后面的长度，结束。
(837799, 524)
2.58100008965
优化了一下，速度提高了不少。不过最后的字典里取结果可能慢了。还有优化的空间。代码如下：
import time
def longestCollatz(n=1000001):
start = time.time()
collatzdict = {}#维护一个统一的collatz的统计字典，初始为
numlist = * (n - 1) #默认所有数都未被‘挖掉’, 从2 开始
for i in range(2, n):
count = 0
num = i
if numlist == True: #若一个数未被挖掉，计算数量
while num != 1:
num = num * 3 + 1 if num % 2 else num / 2
count += 1
if num in collatzdict: #若计算到某个步骤，产生了已经出现过的数，则直接加上该数的计数，计数结束
count += collatzdict
break
collatzdict = count
numlist = False
if i < n / 2: #以i为基数，挖掉i的2的j次方倍的所有的数
j = 1
while i * pow(2, j) < n:
if numlist == True:
numlist = False #挖掉第i个数2的j次方倍的数
collatzdict = collatzdict + j
j += 1
print list(sorted(collatzdict.items(), key=lambda x:x, reverse=True))
print time.time() - start
if __name__ == '__main__':
longestCollatz()
阿bang 发表于 2018-4-4 12:43
优化了一下，速度提高了不少。不过最后的字典里取结果可能慢了。还有优化的空间。代码如下：
import time
def longestCollatz(n=1000001):
start = time.time()
collatzdict = {}#维护一个统一的collatz的统计字典，初始为
numlist = * (n - 1) #默认所有数都未被‘挖掉’, 从2 开始
maxnum = 2
maxcnt = 2
for i in range(2, n):
count = 0
num = i
if numlist == True: #若一个数未被挖掉，计算数量
while num != 1:
num = num * 3 + 1 if num % 2 else num / 2
count += 1
if num in collatzdict: #若计算到某个步骤，产生了已经出现过的数，则直接加上该数的计数，计数结束
count += collatzdict
break
collatzdict = count
if count > maxcnt:
maxcnt = count
maxnum = i
numlist = False
if i < n / 2: #以i为基数，挖掉i的2的j次方倍的所有的数
j = 1
while i * pow(2, j) < n:
if numlist == True:
numlist = False #挖掉第i个数2的j次方倍的数
collatzdict = collatzdict + j
if collatzdict > maxcnt:
maxcnt = collatzdict
maxnum = i * pow(2, j)
j += 1
# print list(sorted(collatzdict.items(), key=lambda x:x, reverse=True))
print maxnum, maxcnt
print time.time() - start
if __name__ == '__main__':
longestCollatz()
再改了一下，只需要找最大的，不需要最后排序字典的话，会快一点
837799 524
1.69199991226
The answer is 837799
Its length is 525
Time is 136 ms
0.80s在此哦~~~~
#include <iostream>
using namespace std;
int main()
{
int longest = 0;
int terms = 0;
int i;
unsigned long j;
for (i = 1; i <= 1000000; i++)
{
j = i;
int this_terms = 1;
while (j != 1)
{
this_terms++;
if (this_terms > terms)
{
terms = this_terms;
longest = i;
}
if (j % 2 == 0)
{
j = j / 2;
}
else
{
j = 3 * j + 1;
}
}
}
cout << longest << endl << terms << endl;
system("pause");
return 0;
}
#include <iostream>
#include <cstring>
using namespace std;
int main()
{
bool dest;
long long maxtime=0,maxnum=0,time,num;
memset(dest,0,1000001);
dest=1;
for(int i=1;i<=1000000;++i)
{
if(dest==1)
continue;
num=i;
time=1;
while(num!=1)
{
++time;
if(num<=1000000)
dest=1;
if(num%2==0)
{
num/=2;
}
else
{
num=num*3+1;
}
}
if(time>maxtime)
{
maxtime=time;
maxnum=i;
}
}
cout<<"最长的序列数是："<<maxnum<<' '<<"总共有："<<maxtime<<"个元素";
}
不到1秒
def Collatz(n):
t = 0
while n != 1:
if n%2 == 0:
n = n/2
t += 1
else:
n = 3*n + 1
t += 1
return t
result = {}
for i in range(1, 1000000):
result = Collatz(i)
max(result, key = result.get)
837799
count1 = 1
num1 = 1
for n in range(1, 1000001):
count = 1
num = n
while 1:
if num % 2 == 0:
num //= 2
count += 1
else:
num = num * 3 + 1
count += 1
if num == 1:
break
if count >= count1:
count1 = count
num1 = n
print(num1)
837799
最大值：525
对应数值：837799
总用时：25.376614736835744
import time
def get_longer(num):
if num <= 1000000:
counter = 1
while num != 1:
if num % 2:
num = num*3 + 1
else:
num = num/2
counter += 1
return counter
else:
raise ValueError
t1 = time.clock()
num_list =
print("最大值：{} \n对应数值：{} \n总用时：{}".format(max(num_list), num_list.index(max(num_list))+2, time.clock() - t1))
import time
import math
import functools
def test1():
max_len = 0
i = 1000001
while i > 1:
num = i
count = 1
while num != 1:
if num%2 == 0:
num = num//2
else:
num = 3*num + 1
count += 1
if max_len < count:
max_len = count
max_num = i
i -= 2
return max_len,max_num
start = time.perf_counter()
print(test1())
end = time.perf_counter()
print(end-start)
本帖最后由 永恒的蓝色梦想 于 2021-2-18 11:51 编辑
C++ 12ms#include<iostream>
constexpr unsigned int MAX = 1000000;
unsigned short cache = { 0, 1 };
unsigned short Collatz(unsigned int num)noexcept {
if (num < MAX) {
if (cache) {
return cache;
}
if (num & 1) {
return cache = Collatz((num >> 1) + num + 1) + 2;
}
return cache = Collatz(num >> 1) + 1;
}
if (num & 1) {
return Collatz((num >> 1) + num + 1) + 2;
}
return Collatz(num >> 1) + 1;
}
int main() {
using namespace std;
ios::sync_with_stdio(false);
unsigned int num, max_num = 0;
unsigned short len, max_len = 0;
for (num = 1; num < MAX; num++) {
if (!cache) {
if (num & 1) {
len = Collatz((num >> 1) + num + 1) + 2;
}
else {
len = Collatz(num >> 1) + 1;
}
if (len > max_len) {
max_len = len;
max_num = num;
}
}
}
cout << max_num << endl;
return 0;
}
525 837799
0.788s
#include <stdio.h>
#include <stdlib.h>
#define MAX 1000
#define NUM 1000000
long long odd(long long);
long long even(long long);
void init(long long *);
void Insert(long long *, long long);
void init(long long* array){
array = 0;
}
void Insert(long long* array, long long e){
if (array == MAX)
exit(EXIT_FAILURE);
array[++array] = e;
}
void execute(long long *array, long long e){
long long temp = e;
Insert(array, temp);
while (temp != 1) {
if (temp % 2 != 0) {
temp = odd(temp);
Insert(array, temp);
}
if (temp % 2 == 0) {
temp = even(temp);
Insert(array, temp);
}
}
}
long long odd(long long num){
return 3 * num + 1;
}
long long even(long long num){
return num / 2;
}
int main(void)
{
int max = 0;
int maxNum = 0;
int temp;
long long array = {0};
for (int i = NUM - 1; i > 1; i-=2) {
init(array);
execute(array, i);
temp = (int)array;
if (max < temp){
maxNum = i;
max = temp;
}
}
printf("最大链长: %d, 数字: %d\n", max, maxNum);
return 0;
}
本帖最后由 永恒的蓝色梦想 于 2020-6-30 18:00 编辑
#include<stdio.h>
#include<stdlib.h>
void main()
{
int i, k;//定义一个整数变量，从1遍历到一百万
int t;
int n = 1;
int max = 1;
for (i = 2; i <= 5; i++)
{
t = i;
n = 1;
while (t != 1)
{
if (t % 2 == 0)
{
t = t / 2;
n++;
}
else
{
t = (t * 3) + 1;
n++;
}
if (t == 1)
if (n > max)
{
max = n;
k = i;
}
}
}
printf("%d,%d\n", max, k);
system("pause");
}
'''以下迭代序列定义在整数集合上：
n → n/2 (当 n 是偶数时)
n → 3n + 1 (当 n 是奇数时)
应用以上规则，并且以数字 13 开始，我们得到以下序列：
13 → 40 → 20 → 10 → 5 → 16 → 8 → 4 → 2 → 1
可以看出这个以 13 开始以 1 结束的序列包含 10 个项。虽然还没有被证明（Collatz 问题），但是人们认为在这个规则下，以任何数字开始都会以 1 结束。
以哪个不超过 100 万的数字开始，能给得到最长的序列？
注意: 一旦序列开始之后，也就是从第二项开始，项是可以超过 100 万的。'''
def longestsequence(num_of_sequence):
number = 1
longest = 1
memory = {}
while number <= num_of_sequence:
#print("这是%d的序列:" %number)
temp = 1
lonumber = number
while True:
if lonumber == 1:
#print(lonumber)
break
elif lonumber % 2 == 0:
#print(lonumber)
lonumber = int(lonumber / 2)
temp += 1
if memory.__contains__(lonumber):
temp += memory - 1
break
elif lonumber % 2 == 1:
#print(lonumber)
lonumber = 3*lonumber + 1
temp += 1
if memory.__contains__(lonumber):
temp += memory - 1
break
if temp > longest:
longest = temp
longestnumber = number
memory = temp
number += 1
#print("--------")
print("在不超过%d的数字中，能得到最长序列的数字是%d" %(num_of_sequence,longestnumber))
print("该数字序列量为： %d" %longest)
#print(memory)
start_longestsequence = time.time()
longestsequence(1000000)
time_longestsequence = time.time() - start_longestsequence
print("%f秒" %time_longestsequence)
在不超过1000000的数字中，能得到最长序列的数字是837799
该数字序列量为： 525
2.077740秒
做一个字典去存储已经计算过的序列，之后再遇到那一段同样的序列就可以直接加上已储存的值，这个方法把整个程序从33秒提升到2秒
def f():
record = []
for n in range(13,14):
count = 1
while1 :
if n % 2 == 0:
n = n // 2
count += 1
if n % 2 != 0 and n > 1:
n = 3 * n + 1
count += 1
if n == 1:
count
#print (count)
break
record.append(count)
count = 1
return max(record)
print (f())
#include <stdio.h>
#include <math.h>
static int flag;//计数器
int Collatz2(long long int value){//2、非递归
int count = 0;
while(value > 1){
flag++;
value = (value%2)?value * 3 + 1: value / 2;
count += 1;
}
return count + 1;
}
int main(void)
{
int i;
int max_Collatz_num;
int max;
int temp;
for(i=1;i<1000000;i++){
temp = Collatz2(i);
if (temp > max){
max = temp;
max_Collatz_num = i;
}
}
printf("max_Collatz_num = %d, count = %d\n", max_Collatz_num, Collatz2(max_Collatz_num));
printf("flag = %d\n", flag);
return 0;
}
//max_Collatz_num = 837799, count = 525
//flag = 131434796
FlySelf 发表于 2017-2-7 11:24
执行结果：
程序执行了3.018928s。
棒
#include<stdio.h>
#define MAX1000000
typedef unsigned int UINT;
int len = 0;
int Odd_or_Even(UINT);
int main(void)
{
unsigned int Max_len = 0,Max_num = 0;
for(int i = 1;i < max;i++)
{
len = 0;
Odd_or_Even(i);
if(Max_len < len )
{
Max_len = len;
Max_num = i;
}
}
printf("%d,%d",Max_len,Max_num);
return 0;
}
int Odd_or_Even(UINT num)
{
len ++;
if(num == 1)
return 1;
else
{
if(num % 2 ==0)
Odd_or_Even((num / 2));
else
Odd_or_Even((num * 3 + 1));
}
return 0;
}
本帖最后由 guosl 于 2022-1-2 19:03 编辑
/*
答案：837799
耗时：0.411748秒（单核）
0.0373096秒（八核）
*/
#include <iostream>
#include <omp.h>
using namespace std;
const int N = 1000000;
int main(void)
{
volatile int nMaxLen = 0, nVal = 0;
#pragma omp parallel for shared(nMaxLen,nVal) schedule(dynamic,16)
for (int i = 1; i <= N; ++i)
{
int nStep = 1;
long long l = i;
while (l != 1LL)
{
if (l % 2LL == 0)
l = l >> 1;
else
l = 3LL * l + 1LL;
++nStep;
}
if (nStep > nMaxLen)
{
#pragma omp critical
{
nMaxLen = nStep;
nVal = i;
}
}
}
cout << nVal << endl;
return 0;
}
package main
import (
"fmt"
"time"
)
//题目14：
//
//以下迭代序列定义在整数集合上：
//
//n → n/2 (当 n 是偶数时)
//n → 3n + 1 (当 n 是奇数时)
//
//应用以上规则，并且以数字 13 开始，我们得到以下序列：
//
//13 → 40 → 20 → 10 → 5 → 16 → 8 → 4 → 2 → 1
//
//可以看出这个以 13 开始以 1 结束的序列包含 10 个项。虽然还没有被证明（Collatz 问题），但是人们认为在这个规则下，以任何数字开始都会以 1 结束。
//
//以哪个不超过 100 万的数字开始，能给得到最长的序列？
//
//注意: 一旦序列开始之后，也就是从第二项开始，项是可以超过 100 万的。
var n = mapint64{
1: 1,
2: 2,
}
func If(b bool, vt int64, vf int64) int64 {
if b == true {
return vt
} else {
return vf
}
}
func loop(a int64) int64 {
t := a
var c int64 = 0
for n == 0 {
t = If(t%2 == 0, t/2, t*3+1)
c++
}
n = n + c
t = If(a%2 == 0, a/2, a*3+1)
p := a
for n == 0 {
n = n - 1
p = t
t = If(a%2 == 0, a/2, a*3+1)
}
return n
}
func main() {
t := time.Now()
var i int64
for i = 3; i < 1000000; i++ {
_ = loop(i)
}
var max = mapint64{
"key": 1,
"value": 1,
}
for key, value := range n {
if value > max["value"] {
max["value"] = value
max["key"] = key
}
}
fmt.Println(max)
tt := time.Now()
fmt.Println("耗时：", (tt.Nanosecond()-t.Nanosecond())/1e6, "ms")
}
输出：
map
耗时： 309 ms