淘宝笔试题 大家来看看啊

如果n为整数，则将它除以2
如果n为奇数，则将它加1或者减1
问对于一个给定的n，怎样才能用最少的步骤将它变到1
例如
n=61
n-- 60
n/2 30
n/2 15
n++ 16
n/2 8
n/2 4
n/2 2
n/2 1

编程用c/c++

65 个解决方案

#1

题目有问题

#2

引用 1 楼 ProgrammerNO1 的回复:

题目有问题

没问题 老题了 近4原则 即考虑二进制位最后两位
01 -1
11 +1

#3

有点像np问题，估计应该是尽量向2的n靠拢，那样步骤才少吧

#4

引用 2 楼 richbirdandy 的回复:

引用 1 楼 ProgrammerNO1 的回复:
题目有问题 
 
没问题 老题了 近4原则 即考虑二进制位最后两位 
01 -1 
11 +1

题目应该是　

是偶数就除２，奇数就加１或减１，

你的原则有问题还是没讲清，３应该加１还要快？

#5

睡觉了，感觉思路是：
    0 检查是否为1；
    1 检查是否为偶数；
    2 是，则／2；
    3 不是，则 (--x)/2;
    4 跳回0。
   

#6

#include<iostream>

using namespace std;

int main(){
    int num,count=0;
    cout<<"请输入一个正整数";
    cin>>num;
    while(num!=1){
          count++;   
          if(num%2!=0){
                       if(num&3==3) num++;
                       else num--;
                       }
          num/=2;
          }
    cout<<endl<<"总步数:"<<count; 
    
    return 0;
    
}
 

#7

按自己想法写的

#include<iostream>

using namespace std;

int main(){
    int num,count=0,bb=2;
    cout<<"请输入一个正整数:";
    cin>>num;
    while(bb<=num) bb*=2;
    while(num!=1){
          count++;   
          if(num%2!=0){
           if(bb-num>num-bb) {num--;count++;cout<<"-- "<<num<<endl;}
           else {num--;count++;cout<<"++ "<<num<<endl;}
                      }
          num/=2;cout<<"/2 "<<num<<endl;
          if (bb/2>num) bb/=2;       
          }
    cout<<endl<<"总步数:"<<count;    
    return 0;   
}          
                  

按2楼想法写的,上楼代码写反了一些,重发

#include<iostream>

using namespace std;

int main(){
    int num,count=0;
    cout<<"请输入一个正整数:";
    cin>>num;
    while(num!=1){
          count++;   
          if(num%2!=0){
                       if(num&3==3) {num--;count++;cout<<"-- "<<num<<endl;}
                       else {num--;count++;cout<<"++ "<<num<<endl;}
                       }
          num/=2;cout<<"/2 "<<num<<endl;
          }
    cout<<endl<<"总步数:"<<count; 
    
    return 0;   
}
 

#8

引用 3 楼 scu_hurricane 的回复:

有点像np问题，估计应该是尽量向2的n靠拢，那样步骤才少吧

跟我想的一样，哈哈。

#9

不改了,郁闷,怎么都有一处写错了,呵

不过好像都不咋正确,还是请高手来写了

例如:61  

++ 62
/2 31
++ 32
/2 16
/2 8
/2 4
/2 2
/2 1

这个只要8步

例如:5
-- 4
/2 2
/2 1

要是加的请
++ 6
/2 3
++ 4
/2 2
/2 1

#10

修正后的答案一:

#include<iostream>

using namespace std;

int main(){
    int num,count=0,bb=2;
    cout<<"请输入一个正整数:";
    cin>>num;
    while(bb<=num) bb*=2;
    while(num!=1){
          count++;   
          if(num%2!=0){
           if(bb-num>=num-bb/2) {num--;count++;cout<<"-- "<<num<<endl;}
           else {num++;count++;cout<<"++ "<<num<<endl;}
                      }
          num/=2;cout<<"/2 "<<num<<endl;
          if (bb/2>num) bb/=2;         
          }
    cout<<endl<<"总步数:"<<count;     
    return 0;    
}
           
  
                   
       [/code]

#11

修正答案二:

#include<iostream>

using namespace std;

int main(){
    int num,count=0;
    cout<<"请输入一个正整数:";
    cin>>num;
    while(num!=1){
          count++;   
          if(num%2!=0){
                       if(num&3==3) {num--;count++;cout<<"-- "<<num<<endl;}
                       else {num++;count++;cout<<"++ "<<num<<endl;}

                       }
          num/=2;cout<<"/2 "<<num<<endl;
          }
    cout<<endl<<"总步数:"<<count; 
    
    return 0;  
}
 

#12

引用 5 楼 puzzle1986 的回复:

睡觉了，感觉思路是： 
        0   检查是否为1； 
        1   检查是否为偶数； 
        2   是，则／2； 
        3   不是，则   (--x)/2; 
        4   跳回0。 
      

   3   不是，则   (--x)/2; 这个不是很多对  像他给你例子就可以说明这个不对了 不是-而是+才是

#13

f(n)表示n变到1的步数，则
f(1) = 0
f(2) = 1
f(2n) = f(n) + 1
f(2n+1) = min(f(n), f(n+1)) + 1

#14

引用 13 楼 luansxx 的回复:

f(n)表示n变到1的步数，则 
f(1) = 0 
f(2) = 1 
f(2n) = f(n) + 1 
f(2n+1) = min(f(n), f(n+1)) + 1 

修正一下
f(2n+1) = min(f(n), f(n+1)) + 2

#15

先Mark 再看

#16

引用 14 楼 luansxx 的回复:

引用 13 楼 luansxx 的回复:
f(n)表示n变到1的步数，则 
f(1) = 0 
f(2) = 1 
f(2n) = f(n) + 1 
f(2n+1) = min(f(n), f(n+1)) + 1 
 
修正一下 
f(2n+1) = min(f(n), f(n+1)) + 2 

按你想法写的,呵,我这脑袋咋想不到

#include<iostream>

int f(int n){
     if(n==1) return 0;
     if(n%2==0) return f(n/2)+1;
     return f(n/2)<f(n/2+1)?(f(n/2)+2):(f(n/2+1)+2);
     }

int main()
{ 
    int num;
    std::cin>>num;
    std::cout<<"Count = "<<f(num);
      
    return 0;
}

#17

收藏了，呵呵！

#18

n = 1

#19

引用 16 楼 xiao9900 的回复:

C/C++ code#include<iostream>

int f(int n){
     if(n==1) return 0;
     if(n%2==0) return f(n/2)+1;
     return f(n/2)<f(n/2+1)?(f(n/2)+2):(f(…

有没有有高手将执行的步骤写出来,

#20

mark

#21

引用 19 楼 xiao9900 的回复:

引用 16 楼 xiao9900 的回复:


C/C++ code#include <iostream> 

int f(int n){ 
    if(n==1) return 0; 
    if(n%2==0) return f(n/2)+1; 
    return f(n/2) <f(n/2+1)?(f(n/2)+2):(f(… 
 

有没有有高手将执行的步骤写出来,

需要仔细看下了。。

#22

今天无聊写了一个，供大家参考

#include "stdafx.h"
#include <iostream.h>
#include <process.h>
#include <string.h>
#include <stdlib.h>

#define BIT_GET(var, bit) ((var >> bit) & 0x01)

void main(int argc, char* argv[])
{
	while ( true )
	{
		char cInChar[20] = {0};
		cout<<"input number or exit:";
		cin>>cInChar;
		if ( strstr( cInChar, "end" ) || strstr( cInChar, "exit" ) )
			break;
		//-------------------------------
		cout<<endl<<"==========================================="<<endl;
		long lInNumber = atol( cInChar );
		long lTemp = lInNumber;
		cout<<"the input number is: "<<lInNumber<<endl;
		int nTime = 0;
		char chOp[3] = {0};
		while ( lTemp != 1 )
		{
			memset( chOp, 0, 3 );
			if ( BIT_GET(lTemp, 0) )  // 奇数
			{
				if ( BIT_GET(lTemp, 1) ) // 倒数第二位还是1的话，+1
				{
					lTemp++;
					strcpy( chOp, "+1" );
				}
				else
				{
					lTemp--;
					strcpy( chOp, "-1" );
				}
			}
			else  // 偶数
			{
				lTemp /= 2;
				strcpy( chOp, "/2" );
			}
			nTime++;
			cout<<"step "<<nTime<<" : op is:"<<chOp<<" after op the number is:"<<lTemp<<endl;
		}

		cout<<endl<<"the number ( "<<lInNumber<<" ) take "<<nTime<<" step to 1";
		cout<<endl<<"==========================================="<<endl<<endl;
	}

	system( "pause" );
}

测试了几个：
===========================================
the input number is: 5
step 1 : op is:-1 after op the number is:4
step 2 : op is:/2 after op the number is:2
step 3 : op is:/2 after op the number is:1

the number ( 5 ) take 3 step to 1
===========================================
===========================================
the input number is: 61
step 1 : op is:-1 after op the number is:60
step 2 : op is:/2 after op the number is:30
step 3 : op is:/2 after op the number is:15
step 4 : op is:+1 after op the number is:16
step 5 : op is:/2 after op the number is:8
step 6 : op is:/2 after op the number is:4
step 7 : op is:/2 after op the number is:2
step 8 : op is:/2 after op the number is:1

the number ( 61 ) take 8 step to 1
===========================================
===========================================
the input number is: 40
step 1 : op is:/2 after op the number is:20
step 2 : op is:/2 after op the number is:10
step 3 : op is:/2 after op the number is:5
step 4 : op is:-1 after op the number is:4
step 5 : op is:/2 after op the number is:2
step 6 : op is:/2 after op the number is:1

the number ( 40 ) take 6 step to 1
===========================================
===========================================
the input number is: 56
step 1 : op is:/2 after op the number is:28
step 2 : op is:/2 after op the number is:14
step 3 : op is:/2 after op the number is:7
step 4 : op is:+1 after op the number is:8
step 5 : op is:/2 after op the number is:4
step 6 : op is:/2 after op the number is:2
step 7 : op is:/2 after op the number is:1

the number ( 56 ) take 7 step to 1
===========================================

#23

那为什么不是近8，近16原则？！

#24

mark~

#25

学习了

#26

学习了

#27

引用 4 楼 xiao9900 的回复:

引用 2 楼 richbirdandy 的回复:
引用 1 楼 ProgrammerNO1 的回复: 
题目有问题 

没问题 老题了 近4原则 即考虑二进制位最后两位 
01 -1 
11 +1 
 

题目应该是　 

是偶数就除２，奇数就加１或减１， 

你的原则有问题还是没讲清，３应该加１还要快？

近4原则应该是对的，但是在数字小于4的时候就需要特殊处理，至于说为什么不是近8，16原则，个人觉得近8，16最终回归到近4了

#28

谢谢大家这么踊跃答题 昨晚的笔试过了 下午要参加淘宝的面试了 祝我好运

#29

谢谢大家这么踊跃答题 昨晚的笔试过了 下午要参加淘宝的面试了 祝我好运

#30

谢谢大家这么踊跃答题 昨晚的笔试过了 下午要参加淘宝的面试了 祝我好运

#31

good luck！！！

#32

引用 16 楼 xiao9900 的回复:

引用 14 楼 luansxx 的回复:
引用 13 楼 luansxx 的回复: 
f(n)表示n变到1的步数，则 
f(1) = 0 
f(2) = 1 
f(2n) = f(n) + 1 
f(2n+1) = min(f(n), f(n+1)) + 1 

修正一下 
f(2n+1) = min(f(n), f(n+1)) + 2 
 

按你想法写的,呵,我这脑袋咋想不到 


C/C++ code#include<iostream>

int f(int n){
     if(n==1) return 0;
     if(n%2==0) return f(n/2)+1;
     return f(n/2)<f(n/2+1)?(f(n/2)+2):(f(…

效率差了点.

#33

近4原则

#34

最少的步骤：len-1 + 1的个数-1；
len和1的个数指的是n化为2进制时的长度和1的个数；

#35

总之一句，靠近2^n就对了，近4的话，还是特殊了点，比如 n=3

#36

引用 16 楼 xiao9900 的回复:

int f(int n){
     if(n==1) return 0;
     if(n%2==0) return f(n/2)+1;
     return f(n/2)<f(n/2+1)?(f(n/2)+2):(f(n/2+1)+2);
     }

这个实现不太好，有重复计算，可以通过一个数组记录已经计算的f(n)，下次遇到就不要再算了

#37

引用 34 楼 giftfish 的回复:

最少的步骤：len-1 + 1的个数-1； 
len和1的个数指的是n化为2进制时的长度和1的个数；

你的意思就是偶数除以2，奇数减1了，减一次刚好消除二进制中的一个1

#38

楼主中南大学的吧，昨天淘宝中南专场招聘会

#39

记号

#40

向4靠拢是有道理的，把数字用二进制表示，通过右移一位、加一、减一，让他最终变成0（注意，看成变成0的更好理解一些，其实1变成0只是一个“减一”操作，就相差一步），就需要把所有的1消除掉。
怎么去掉1呢，右移不能消除一，只有加减一能够，所以奇数时要考虑加还是减。
对于...01（2进制）这样的情形，减一能够消除1，加一不能，所以要减一；
对于...11，加一能够至少消除一个1（比如...0111就是消除两个1），减一只能消除一个1，那么对于...011的情形，应该加一还是减一呢？
答案应该是加一，因为向高位进的1可能会与更高位的1合并为1个连续的1串，使以后加一能够一下子消除更多的1；
这里有一个例外，就是3（二进制11），因为更高位没有1了，所以不能加一。

本人比较懒，具体的算法就不总结了

#41

MARK

#42

#include <iostream>
#include <stdlib.h>

using namespace std;

int main()
{
	int number;
	int totle_count = 0;
	std::cout << "please input a number: ";
	std::cin >> number;
	std::cout << std::endl;

	while ( number != 1)
	{
		if( number % 2 == 1)
		{
			number--;
			if(((number/2)%2 != 0) && (number != 2))
			{
				number += 2;
				std::cout << "now number is:" << number << "\t"
					          << "the operation is: number++" << std::endl;
			}
			else{
				std::cout << "now number is:" << number << "\t"
				              << "the operation is: number--" << std::endl;
			}
		}
		else{
			number /= 2;
			std::cout << "now number is:" << number << "\t"
				          << "the operation is: number / 2" << std::endl;
		}
		totle_count++;
	}
	std::cout << std::endl;
	std::cout << "now number is: " << number << std::endl;
	std::cout << "totle operation is : " << totle_count << std::endl;
}

#43

闪过~

#44

大哥们 比4小的就三个数 处理一下不就完了

4楼和23楼的兄台 希望你们不是像我一样正在找工作 不然比我还凄惨。。。

#45

用13楼的方法可以 但效率不高
35楼的让人很无语啊 您会编程么。。。

算了 我太焦躁了。。

#46

mark..

#47

广度优先

#48

mark

#49

应该是近2的n次方原则(n越大越好),不能近则奇数-1,偶数直接无视/2,这个前提下应该好写了。

#50

管他是什么不停的除2，奇数刚好1，偶数加161/2=30/2=15/2=7/2=3/2=1-1=0