互联网笔试题:数字转换机

小Q从牛博士那里获得了一个数字转换机,这台数字转换机必须同时输入两个正数a和b,并且这台数字转换机有一个红色的按钮和一个蓝色的按钮:

当按下了红色按钮,两个数字同时加1。

当按下了蓝色按钮,两个数字同时乘2。

小Q现在手中有四个整数a,b,A,B,他希望将输入的两个整数a和b变成A,B(a对应A,b对应B)。因为牛博士允许小Q使用数字转换机的时间有限,所以小Q希望按动按钮的次数越少越好。请你帮帮小Q吧。

输入:

输入包括一行,一行中有四个正整数a,b,A,B,(1<=a,b,A,B<=10^9)。

输出:

如果小Q可以完成转换,输出最少需要按动按钮的次数,否则输出-1。

样例输入:100  1000  202  2002

样例输出:2

func Test6() {
	testCase := [][]uint32{
		{uint32(100), uint32(1000), uint32(202), uint32(2002)},
		{uint32(100), uint32(1000), uint32(202), uint32(2003)},
		{uint32(100), uint32(1000), uint32(203), uint32(2003)},
		{uint32(101), uint32(1000), uint32(202), uint32(2002)},
		{uint32(51), uint32(61), uint32(101), uint32(111)},
	}

	f := func(s1, s2, e1, e2 uint32) (int, []string) {
		stepCounter, ret := 0, []string{}
		for s1*2 <= e1 && s2*2 <= e2 {
			s1, s2 = s1*2, s2*2
			stepCounter, ret = stepCounter+1, append(ret, "*2")
		}
		if e2-s2 != e1-s1 {
			return -1, nil
		} else {
			stepCounter = stepCounter + int(e2-s2)
			for i := 0; i < int(e2-s2); i++ {
				ret = append(ret, "+1")
			}
		}
		return stepCounter, ret
	}
	for i := 0; i < len(testCase); i++ {
		stepCounter, path := f(testCase[i][0], testCase[i][1], testCase[i][2], testCase[i][3])
		if stepCounter > 0 {
			fmt.Printf("%d %d -->%d %d  use %d step,", testCase[i][0], testCase[i][1], testCase[i][2],
				testCase[i][3], stepCounter)
			for i := 0; i < len(path); i++ {
				fmt.Printf("%s \t", path[i])
			}
			fmt.Printf("\n")
		} else {
			fmt.Printf("no way %d %d -->%d %d\n", testCase[i][0], testCase[i][1], testCase[i][2], testCase[i][3])
		}
	}
}