Depoly your flask app into Heroku Fix shit IE code manually ISBN to Book Category by Scraping DangDang A Generic Makefile for C/C++ Program Configure Raspberry pi Remove watermark with PyPDF2 tips for docker Anaconda+TensorFlow+CUDA Snippets Configure Remote Mathematica Kernel Build your own ngrok server Access Array SSL VPN 使用Rstudio制作html5幻灯片 tips for Mac OS X system Tips for ipython notebook 配置Ubuntu server + Openbox (Obuntu) tips for Vimperator tips for Vim 安装CUDA My First Jekyll Blog rsync常见选项 在Linux中读取Ipod touch的文件 tip for texmacs 在VPS上建站的一些tip Gnuplot绘图札记 Samba系统和autofs自动挂载 Linux中alsamixer声卡无法录音 搭建自己的RSS订阅器——Tiny Tiny RSS Grub2引导安装Ubuntu awk tips 将Ubuntu系统装入U盘 The Great Rtorrent 编译GCC 再这样剁手!!!该死的libgd 使用ulimit进行资源限制 使用SSH代理上IPV6 使用RCurl抓取网页数据 修复Ubuntu Grub记 openbox中的文件关联 在Ubuntu 12.04下编译qtiplot 处理BCM4312网卡驱动纪实 配置我的Ubuntu Server记 Cygwin杂记 Linux 使普通用户具有以超级权限执行脚本 让firefox自定义地处理文件类型 WordPress优秀主题及插件 在phpcloud上搭建wordpress UBUNTU下用pptpd做VPN server ubuntu升级内核过后的一些问题 安装telnet服务 kubuntu札记 64位kubuntu札记 统计软件R virtualbox stardict星际译王 Ubuntu重装windows系统后的grub引导修复 SSH服务及花生壳域名解析 采用cbp2make工具由code::blocks工程创建makefile文件 UBUNTU 札记

Project Euler Problem 14

2014年03月12日

Q:

The following iterative sequence is defined for the set of positive integers:
n → n/2 (n is even)
n → 3n + 1 (n is odd)

Using the rule above and starting with 13, we generate the following sequence:
   13 → 40 → 20 → 10 → 5 → 16 → 8 → 4 → 2 → 1

It can be seen that this sequence (starting at 13 and finishing at 1) contains 10 terms. Although it has not been proved yet (Collatz Problem), it is thought that all starting numbers finish at 1.

Which starting number, under one million, produces the longest chain?
NOTE: Once the chain starts the terms are allowed to go above one million.

R

1st Version

nums <- 1:1000000
Nums <- 1:1000000
i <- 1
while(!(is.na(i)))
{
  i <- which.max(Nums[Nums>0])
  nums[i] <- 1
  j <- i
  repeat
  {
    if(j==1) break
    if((j %% 2)==0) 
      {
        Nums[j/2] <-0
        j <- j/2
      }
    else if((3*j+1)<=1000000) 
      {
        Nums[3*j+1] <- 0
        j <- 3*j+1
      }
    nums[i] <- nums[i] + 1

  }
  Nums[i] <- -Nums[i]  
}
print(which.max(nums))

#999847

2nd version

len <- 1e6-1
from <- 1:len
seq.length <- c(-1,rep(0,len-1))

remain <- 2:len # 还未抵1
while(length(remain)!=0){
  from[remain] <- ifelse(from[remain]%%2==0,from[remain]/2,from[remain]*3+1)

  done <- from[remain]<=len & seq.length[from[remain]]<0 #下一步过后就重复计算了
  done.index <- remain[done]
  seq.length[done.index] <- seq.length[from[done.index]]-1-seq.length[done.index]

  remain <- remain[!done]
  seq.length[remain] <- seq.length[remain]+1
}

print(which.min(seq.length))

3rd version

which.max(unlist(llply(1:len,function(x){
  l <- 0
  while(x!=1){
    x <- ifelse(x%%2==0,x/2,x*3+1)
    l <- l+1
  }
  l
})))

C++

#include <iostream>
#include <vector>
using namespace std;

int main(int argc, const char *argv[])
{
    typedef long INT;

    const INT len=999999;
    INT v[len];
    for (INT i = 0; i < len; i++) {
        v[i]=i;
    }

    INT largest_remain=len-1;
    INT longest=largest_remain;
    INT llength=-0;

    vector<INT> index;
    while(largest_remain!=0){
        index.push_back(largest_remain);
        do{
            index.push_back(index.back()%2==1?(index.back()-1)/2:(index.back()*3+3));//C++从0开始算,为方便把题目做个转化
        }while(index.back()!=0 && (index.back()>=len || v[index.back()]>0));

        for (INT i = index.size()-2; i >= 0; i--) {
            if(index[i]<len){
                v[index[i]] = v[index.back()]-index.size()+i+1;
            }
        }
        index.clear();

        if(llength>v[largest_remain]){//存储的长度是负数
            llength=v[largest_remain];
            longest=largest_remain;
        }

        do{
            largest_remain--;
        }while(v[largest_remain]<0);
    }

    cout<<longest+1<<endl;
    return 0;
}