腾讯测试与开发工程师—数字转换机

问题描述

小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

问题分析

从样例我们可以看出,当小Q按下红色按钮一次,按下蓝色按钮一次后,100和1000变成了202和2002。小Q每一次对数字进行操作都有两种操作可以选,也就是数字可能有两种结果。我们用 完全二叉树 来存储每一次操作可能出现的结果。如图:

完全二叉树

完全二叉树很有规律,可以用一个数组进行存储,不需要指针。对于数组中任意位置 i 上的元素,其左儿子在位置 2i 上,右儿子在左儿子后的单元(2i + 1)中,它的父亲则在位置(i/2)(向下取整)上。

算法实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
#include <stdio.h>
#include <math.h>

#define N 200

struct demo{ //存储a,b元素
int a;
int b;
};

int main(){

int a;
int b;
int A;
int B;
scanf("%d%d%d%d",&a,&b,&A,&B);

struct demo num[N] = {0};
num[1].a = a;
num[1].b = b;

int i = 1;
for(i = 2; i <= N; i++){
if(i%2 ==0){
num[i].a = num[i/2].a + 1;
num[i].b = num[i/2].b + 1;
}else{
num[i].a = num[i/2].a*2;
num[i].b = num[i/2].b*2;
}

if(num[i].a == A && num[i].b == B){ //找到第一组符合的数据,就返回
printf("%d",(int)log2(i));
return 0;
}
}

printf("-1");
return 0;

}

算法测试

第一组测试数据: 2 6 20 36
(2+1+1+1)22 = 20 —— 进行了3次加法,2次乘法,一共5次
(6+1+1+1)22 = 36 —— 进行了3次加法,2次乘法,一共5次
符合,返回5
第一组测试数组

第二组测试数据: 100 1000 204 2004
(100+1+1)2 = 204 —— 进行了2次加法,1次乘法,一共3次
(1000+1+1)
2 = 2004 —— 进行了2此加法,1次乘法,一共3次
符合,返回 3
第二组测试数组

第三组测试数据: 100 1000 202 2002
(100+1)2 = 202 —— 进行了1次加法,1次乘法,一共2次
(1000+1)
2 = 2002 —— 进行了1次加法,1次乘法,一共2次
符合,返回 2
第三组测试数组

第四组测试数据: 100 1000 202 2004
(100+1)2 = 202 —— 进行了1次加法,1次乘法,一共2次
(1000+1+1)
2 = 2004 —— 进行了2此加法,1次乘法,一共3次
不符合,返回 -1
第四组测试数组


网易编程题—魔法币

问题描述

时间限制:1秒
空间限制:32768K

小易准备去魔法王国采购魔法神器,购买魔法神器需要使用魔法币,但是小易现在一枚魔法币都没有,但是小易有两台魔法机器可以通过投入x(x可以为0)个魔法币产生更多的魔法币。

魔法机器1:如果投入x个魔法币,魔法机器会将其变为2x+1个魔法币
魔法机器2:如果投入x个魔法币,魔法机器会将其变为2x+2个魔法币

小易采购魔法神器总共需要n个魔法币,所以小易只能通过两台魔法机器产生恰好n个魔法币,小易需要你帮他设计一个投入方案使他最后恰好拥有n个魔法币。

输入描述:
输入包括一行,包括一个正整数n(1 ≤ n ≤ 10^9 ), 表示小易需要的魔法币数量。

输出描述:
输出一个字符串,每个字符表示该次小易选取投入的魔法机器。其中只包含字符’1’和’2’。

输入例子1:
10

输出例子1:
122

问题分析

此题和上一题一样,同样生成一颗完全二叉树,只是此题的二叉树比较特殊,其层次遍历是一个自然数序列,所以不需要用数组进行存储。

算法实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include<stdio.h>

void func(int i){

if(i%2 == 0 && i != 1) {
func(i/2);
printf("1");
}else if(i%2 == 1 && i != 1){
func(i/2);
printf("2");
}
}

int main(){

long need;

scanf("%d",&need);

func(need + 1);

}

算法测试

第二道编程题运行结果