package codetest1;

import java.util.*;

public class Test2 {
    static class Node {
        int m;
        int s;
        int count;
        
        public Node(){
            this.m=0;
            this.s=0;
            this.count=0;
        }
    }
    
    public static int findMin(Node start,int n){
        
        Queue<Node> queue = new LinkedList<Node>();
        queue.add(start);
        while(!queue.isEmpty()){
            Node node = queue.poll();
            if(node.s == n){
                return node.count;
            }else if(node.s<n){
                Node node1 = new Node();
                Node node2 = new Node();
                int count = ++node.count;
                node1.m = node.s; node1.s = node.s*2; node1.count=count;
                node2.m = node.m; node2.s = node.s+node.m; node2.count=count;
                queue.add(node1);
                queue.add(node2);
            }
        }
        return -1;
        
    }


    public static void main(String[] args){
        Node start = new Node();
        start.s=1;start.m=1;start.count=0;
        long time = System.currentTimeMillis();
        int result = findMin(start, 9999);
        System.out.println("\r<br>执行耗时 : "+(System.currentTimeMillis()-time)/1000f+" 秒 ");
        System.out.println(result);
    }
    
    
}

#include<iostream>
#include<queue>
#include<time.h>
using namespace std;

class Node {
public:
        int m;
        int s;
        int count;
        Node(){
            this->m = 0;
            this->s = 0;
            this->count = 0;
        }
        Node(int m, int s, int count){
            this->m = m;
            this->s = s;
            this->count = count;
        }
};

int findMin(Node* start, int n){
    queue<Node*> q;
    q.push(start);
    while (!q.empty()){
            Node* node = q.front();
            q.pop();
            if (node->s == n){
                return node->count;
            }
            else if (node->s<n){
                int count = ++node->count;
                q.push(new Node(node->s,node->s*2,count));
                q.push(new Node(node->m,node->s+node->m,count));
            }
            delete node;
        }
        return -1;
    }


    int main(){
        clock_t starttime, finishtime;
        Node* start = new Node(1,1,0);
        starttime = clock();
        int result = findMin(start,9999);
        finishtime = clock();
        cout <<"时间："<<(double)(finishtime-starttime)/CLOCKS_PER_SEC<<" "<< result << endl;
        //System.out.println("\r<br>执行耗时 : " + (System.currentTimeMillis() - time) / 1000f + " 秒 ");
        system("pause");
        //.out.println(result);
    }