POJ 1207 The 3n + 1 problem

10875 ワード

タイトルリンク:http://poj.org/problem?id=1207
関数F(x),xが1ならF(x)=1,そうでなければxが偶数ならF(x)=F(x/2)、xが奇数F(x)=F(x)=F(3*x+1)与えられたxから1への変換のステップ数を計算します.
注意点:
1.提供される各グループの2つの数字は、必ずしも左が小さく右が大きいとは限らないので、両者の値を交換する場合があります.また、出力時には2つの数が現れる順に出力する必要があります.
あるいは、まず2つの数を出力し、最後にmaxlenの値を出力し、同じ行に保証すればよい.
2.直接列挙して比較してもいいです.表を打つのも同じです.データの範囲があまり大きくないからです.
3.他にも検索方法、記憶方法などがあります.参考URL:http://hi.baidu.com/wzyjerry/blog/item/f7c1e44481ced42586947347.html 深さ検索+記憶化
方法1:直接列挙
Memory: 3004KTime: 204MS

import java.util.Scanner;

public class Main{

    public static void main(String[] args) {
        Scanner sin=new Scanner(System.in);
        int start,end,len,maxlen,temp;
        while(sin.hasNext()){
            maxlen=0;
            temp=0;
            start=sin.nextInt();
            end=sin.nextInt();
            if(start>end){
                temp=end;
                end=start;
                start=temp;
            }
            for(int i=start;i<=end;i++){
                len=calculateLen(i);
                if(len>maxlen){
                    maxlen=len;
                }
            }
            if(temp==0){
                System.out.println(start+" "+end+" "+(maxlen));
            }else{
                System.out.println(end+" "+start+" "+(maxlen));
            }
        }
    }
    
    public static int calculateLen(int n){
        int len=1;
        while(n!=1){
            if(n%2==0){
                n=n/2;
            }else{
                n=3*n+1;
            }
            len++;
        }
        return len;
    }
}

.csharpcode, .csharpcode pre
{
font-size: small;
color: black;
font-family: consolas, "Courier New", courier, monospace;
background-color: #ffffff;
/*white-space: pre;*/
}
.csharpcode pre { margin: 0em; }
.csharpcode .rem { color: #008000; }
.csharpcode .kwrd { color: #0000ff; }
.csharpcode .str { color: #006080; }
.csharpcode .op { color: #0000c0; }
.csharpcode .preproc { color: #cc6633; }
.csharpcode .asp { background-color: #ffff00; }
.csharpcode .html { color: #800000; }
.csharpcode .attr { color: #ff0000; }
.csharpcode .alt
{
background-color: #f4f4f4;
width: 100%;
margin: 0em;
}
.csharpcode .lnum { color: #606060; }

方法2:時計を打つ
Memory: 3044KTime: 172MS

import java.util.Scanner;

public class Main{
    
    public static int[] lens=new int[10002];

    public static void main(String[] args) {
        Scanner sin=new Scanner(System.in);
        calculateLen();
        int start,end,maxlen,temp;
        while(sin.hasNext()){
            maxlen=0;
            temp=0;
            start=sin.nextInt();
            end=sin.nextInt();
            if(start>end){
                temp=end;
                end=start;
                start=temp;
            }
            for(int i=start;i<=end;i++){
                if(lens[i]>maxlen){
                    maxlen=lens[i];
                }
            }
            if(temp==0){
                System.out.println(start+" "+end+" "+(maxlen+1));//       ()，   ，       ， 1       
            }else{
                System.out.println(end+" "+start+" "+(maxlen+1));
            }
        }
    }
    
    public static void calculateLen(){
        int i,n;
        for(i=1;i<10002;i++){
            lens[i]=0;
            n=i;
            while(n!=1){
                if(n%2==0){
                    n=n/2;
                }else{
                    n=3*n+1;
                }
                lens[i]++;
            }
        }
    }
}

#include <iostream>
#include <string.h>
using namespace std;
int M[200001];
int Ans;
int dfs(int n)
{
    if(n==1)
        return 1;
    if(n>200000)
    {
        if(n%2==0)
            return dfs(n/2)+1;//      ，         ，     1
        else
            return dfs(n*3+1)+1;
    }
    if(!M[n])//        n   ，         ，            [  ]
    {
        if(n%2==0)
            return M[n]=dfs(n/2)+1;
        else
            return M[n]=dfs(n*3+1)+1;
    }
    else
        return M[n];
}
int main()
{
    int a,b;
    M[0]=1;
    for(int i=1; i<=10000; i++)
    {
        M[i]=dfs(i);//         ，                      
    }
    while(cin >> a >> b)
    {
        cout << a << ' ' << b << ' ';
        Ans=0;
        for(int i=min(a,b); i<=max(a,b); i++)
            Ans=max(Ans,M[i]);
        cout << Ans << endl;
    }
    return 0;
}

【Python】jepg形式の画像ファイルをppm形式へ変換する

フロントjs MD 5暗号化バックグラウンドjava MD 5復号