贝壳笔试

贝壳的笔试题解：

one 计算器;
two 推牌子;
three 族谱关系;

一个一个来分析:
n 与 m :
首先是计算器的那个题：无论是递归还是循环做，无非是难在n < m 那一块;
如果是按照正常的递归思路大概是如下：
if(n == m) return ;
else if(n > m){
step++
backtrace(n-1, m, step);
else
step++;
backtrace(n-1, m, step) && backtrace(2n, m ,step)
}
最关键的是在n<m最后一步的分差计算上面只是伪代码大致的思路是这样，但是边界条件写的是有问题的；
而第二种循环的做法也是在n < m的时候划分需要反过来想;
我们假设n < m时候 n如果才能获得m呢; 如果按照上面的递归的话无非是分叉做，但是这样需要利用栈保存状态，很难写，其实可以反过来想, 根据m值判定n如何变为m，假设m为偶数的话我们在假定n < m， n为了直接得到m则一定是n2才可以获得m，反操作就是 m/2; 而m为奇数的话则一定是 n*2-1则m的反操作（m+1）/2;
你可以会疑惑为什么是这样，请注意我的假设前提是n < m 直接由n获得m，所以如此；
大致代码如下：

include<iostream>

using namespace std;
int main(){
int n;

int count = 0;

cin>>n>>m;

//4 5 3

if(n > m){
cout << m-n;
}
else{
while( n<m ){
if(m % 2 == 0){ // (如果是偶数肯定是n2上来的，因为n<m)
count += 1;
m = m/2; // n2 == m/2;
}
else{
count += 2; // (如果为奇数证明肯定是经过两步2与减1)
m = (m+1)/2; // n2-1 == (m+1)/2;
}
}
cout<<count+(m-n);
}

return 0;
}

题目解读：
接着跳过第二题，先说说第三个题目，个人觉得有点像小学生的找线索构建图谱的问题，假设你已经阅读过题目了，你需要注意两点问题，所有的关系同源也就是出自同一个家族，所以相互间总归有关系，不会突然莫名的出现两个与此家族毫不相干的人这是题目情景的设定不然的话，写起来就会更麻烦一点，麻烦在构建族谱时候循环的终止条件上。

我以下的思路与写法都是一般人可以想到的思路：
我们把所有关系放到map中<key,value> 其中key代表儿子，value代表爸爸; 
首先第一步：你需要找到老祖宗，然后依据老祖宗构建第一代族谱；
接着第二步：就是依据你所构建的第一代族谱来不断完善你的族谱，至于完善中需要注意的事情是，在循环过程中你需要做的判断就是当前插入的 a b是否key已经存在如果a存在则证明a有爸爸，a只能做儿子同理如此，但是有可能在一次循环中a bkey均不存在，没关系先保存起来由于构建的过程是循序渐进的，在下一轮到几轮循环中a b的key则一定会存在,因为一个家族不会莫名的冒出两个与父辈毫无关系的人;
第三步：查找

查找过程则是首先看当前的a b是否均在族谱中，如果均不在则不存在关系;
如果在则分别从 a为子往上找父亲，看b是否在找父亲的那条路径上;
b为子往上找父亲，看a是否在找父亲的那条路径上;

#include<iostream>
#include<vector>
#include<map>
using namespace std;
int Relationship(map<int,int> & map_, int a, int b){
  int tempa = a ,tempb = b;
  if(map_.count(a) != 1 && map_.count(b)!=1){
    return 0;
  }
  else{
    //查找关系;
    if(map_.count(a) == 1){
      //从a开始找;
      while(map_[a]!=b){
        a = map_[a];
        if(map_.count(a) == 0 ) break;
      }
      if(map_.count(a) == 1){
        if(map_[a] == b){
          return 2;
        }
      }
    }

    a = tempa;
    b = tempb;

    if(map_.count(b) == 1){
      //从a开始找;
      while(map_[b]!=a){
        b = map_[b];
        if(map_.count(b) == 0 ) break;
      }
      if(map_.count(b) == 1){
        if(map_[b] == a){
          cout<<map_[b]<<":"<<a<<endl;
          return 1;
        }
      }
    }
  }
  return 0;
}
int Count(vector<int>& input){
  int size = 0;

  for(int i=0; i<input.size(); i++){
    if(input[i] == -2) size++;
  }

  return size;
}
int main(){

   int a=0,b=0,n=0,index=0;
   int root = 0;
   int query = 0;

   vector<int> inputA;
   vector<int> inputB;
   vector<int> outputA;
   vector<int> outputB;
   map<int,int> map_;

   cin>>n;

   //step one:首先找到祖宗节点;
   for(int i=0; i<n; i++){
     cin>>a>>b;
     inputA.push_back(a);
     inputB.push_back(b);
     if(a == -1 || b == -1){
        index = i;  //线索下标;
     }
   }

   if(inputA[index] == -1){
     swap(inputA[index], inputB[index]);
   }

   cin>>query;

   //祖宗节点;

   for(int i=0; i<query; i++){
     cin>>a>>b;
       outputA.push_back(a);
       outputB.push_back(b);
   }

   root = inputA[index];

   map_.insert(pair<int,int>(inputA[index],inputB[index]));

   //由于已经插入到族谱中可以无效化输入的关系;
   inputA[index] = -2;

   inputB[index] = -2;

   //step two： 依照祖宗节点为依据拓展族谱;
   for(int i=0; i<inputA.size(); i++){
     if(inputA[i] == root || inputB[i] == root){
        if(inputA[i] == root){
          swap(inputA[i], inputB[i]);
        }
        //族谱中存放的关系;
        map_.insert(pair<int,int>(inputA[i],inputB[i]));
        //无效化输入的关系;
        inputA[i] = -2;
        inputB[i] = -2;
     }
   }
   //step three: 按照已经构造好的族谱树来进一步完善族谱树;

   while(Count(inputA) != inputA.size()){
     // 这里为什么这么写不怕出现死循环，因为题目限制，两两输入之间一定会有关系，都是一系所出，所以
     // 族谱树一定可以可以构建完毕;
     for(int i=0; i<inputA.size(); i++){
       if(map_.count(inputA[i]) == 1 || map_.count(inputB[i]) == 1){
         if(map_.count(inputA[i]) == 1){  //inputA[i] 只能做父亲;
           swap(inputA[i],inputB[i]);
         }
         map_.insert(pair<int,int>(inputA[i],inputB[i]));
         inputA[i] = -2;
         inputB[i] = -2;
       }
     }
   }

   for(int i=0; i<query; i++){
     cout<<Relationship(map_, outputA[i], outputB[i])<<endl;
   }

   return 0;
}
写的有点累，多米诺的ac下午更新

#贝壳找房##笔试题目##题解#