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
use std::collections::BTreeMap;
pub fn run() -> Result<(), Box<dyn std::error::Error>> {
let mut map = BTreeMap::new();
for mut x in 2..1000000u32 {
let (i, mut n) = (x, 0u32);
while x != 1 {
if x < i {
n += map.get(&x).unwrap();
break;
} else if x % 2 == 0 {
x /= 2;
n += 1
} else {
x = (3 * x + 1) / 2;
n += 2
}
}
map.insert(i, n);
}
let mut max = 0u32;
let mut num = 0u32;
for (k, v) in map {
if v > max {
max = v;
num = k;
}
}
println!("num = {num}, max = {max}");
Ok(())
}
num = 837799, max = 524
不知道链长为啥不一样……
python版本，通过字典进行加速。注意中间值也要写入字典
import time
tt=time.time()
data={}
maxnum=(1,1)
data=1
def getl(x):
if x in data:
return (data,x)
if x%2==0:
ans=getl(x//2)+1
else:
ans=getl(3*x+1)+1
data=ans
return (ans,x)
for i in range(1,10**6+1):
maxnum=max(maxnum,getl(i))
print(maxnum)
print(time.time()-tt)
(525, 837799)
1.4954357147216797s