###### tags: `UVa`
- [ ] uncheck
# UVa d712. The 3n + 1 problem
### 1st Ideas of solving a problem
> 1. Input data( a and b) in main function, and use another function 'test' in order to check the answer of each input data in this 3n+1 algo.
> 2. In 'test' function, use a for loop and while to check each cycle length in the scope of a and b.
> 3. In 'test' function, use a array to save each cycle length.
> 4. In 'test' function, use if and else to find out the biggest integer in array.
> Bug: TLE. If input datas are too large (maybe 1000000 and one integer is 4 byte= 4MB).
> Please compare to c039.

#include<stdio.h>
#define MAX_LEN 10000000
void threen(int,int);
void segment_tree(int*,int*,int,int,int);
void Find_max(int*,int,int,int);
int tree[MAX_LEN]={0};//建立待會要用的線段樹陣列存在tree陣列中並且初始化
int main(){
    int input1,input2;
    scanf("%d%d",&input1,&input2);
    printf("%d %d",input1,input2);
    if(input1>input2){
        int temp=input1;
        input1=input2;
        input2=temp;
    }
    threen(input1,input2);//把起始值和終點值傳入做計算
    printf(" ");
    printf("%d\n",tree[0]);
    return 0;
}
void threen(int input1,int input2){//先求出題目給區間的3n+1值然後再用線段樹去求出最大值 時間才會是O(logn)
    int size=(input2-input1+1);//先計算要宣告的陣列大小，arr存3n+1結果
    int arr[size];
    for(int i=input1,j=0;i<=input2,j<size;i++,j++){
        int ans=1;
        int temp=i;
        while(temp!=1){
            if(temp%2==1){
                temp=3*temp+1;
                ans++;
            }
            else if(temp%2==0){
                temp=temp/2;
                ans++;
            }
        }
        arr[j]=ans;//將最大值length存入arr[]陣列中
    }
    int father_INDEX=0;//root編號從0開始
    int arr_start=0;//原本陣列arr的起始index
    int arr_end=size-1;//原本陣列arr的終止index
    void segment_tree(int*arr,int*tree,int father_INDEX ,int arr_start,int arr_end);//(原資料的陣列指標,新建立的樹陣列指標,樹的根節點,原本數組陣列的起始,原本數組陣列的終點)
   
}

void segment_tree(int*arr,int*tree,int father_INDEX ,int arr_start,int arr_end){
    if(arr_start==arr_end){//如果資料只有一個
        tree[father_INDEX]=arr[arr_start];//把資料丟入父點
    }
    else{//資料不只一個 使用divide and conquer中的divide往下切割
        int mid=(arr_start+arr_end)/2;//求出資料中間index
        int left_INDEX=2*father_INDEX+1;//求出左子點的index
        int right_INDEX=2*father_INDEX+2;//求出右子點的index
        segment_tree(arr,tree,left_INDEX ,arr_start,mid);//遞回往下作父點變成左子點
        segment_tree(arr,tree,right_INDEX ,mid+1,arr_end);//遞回往下作父點變成右子點
        Find_max(tree,father_INDEX,left_INDEX,right_INDEX );//直到做到leave的編號後 去做比較找最大值，並將最大值往上存回父點
    }
}

void Find_max(int*tree,int father_INDEX,int left_INDEX,int right_INDEX){
    if(tree[left_INDEX]>=tree[right_INDEX]){
        tree[father_INDEX]=tree[left_INDEX];
    }
    else{
        tree[father_INDEX]=tree[right_INDEX];
    }
}