今天笔试了华为的提前批，爆炸，三道题最后就拿了200分，各种输入输出问题。。。醉了啊，题都不是很难，但输入输出折腾了半天T  T。。。第三题是和尚挑水的问题，

第二题就是找出数组中只能被自己整除的数，思路也很简单，最水的方法就是对每一个数，与数组中的其他数字进行除法运算，时间复杂度是O(n²)就不写代码了，也可以用通过维护一个除数的数组，具体时间复杂度有点难算，应该是2nk，k是这个数组的长度。代码我稍微写了一下。

#include 
     
      #include 
      
       using namespace std;int main() {	vector
       
         nums{ 4,5};	//即剔除只能本自己整除的数	vector
        
          temp{ 4 };	int flag = true;	for (int i = 0; i < nums.size(); i++) {		for (auto iter = temp.begin(); iter != temp.end(); iter++) {			if (*iter%nums[i] == 0) {				*iter = nums[i];				flag = false;				break;			}			else if (nums[i] % (*iter) == 0) {				flag = false;				break;			}		}		if (flag) {			temp.push_back(nums[i]);		}		else {			flag = true;		}	}	for (auto m : temp) {		cout << m << " ";	}}
        
       
      
     

　　

一、问题

某寺庙里7个和尚:轮流挑水，为了和其他任务不能冲突，各人将有空天数列出如下表：

和尚1: 星期二,四;

和尚2: 星期一,六;

和尚3: 星期三,日;

和尚4: 星期五;

和尚5: 星期一,四,六;

和尚6: 星期二,五;

和尚7: 星期三,六,日;

请将所有合理的挑水时间安排表

其实思路很简单，就是使用回溯算法，但是我自己太坑了啊，当时看到八皇后的题时候，知道用回溯算法，但是就看了一眼，没自己动手实现，结果今天不会写回溯。。。哈哈哈哈哈，最后用了非常傻逼的方法，就是全排列以后然后再选择符合的答案输出，但是格式有问题。。。最后300就拿了100分  _(:з」∠)____ 23333，对了，第二题我更加傻逼，200分一分没拿，哈哈哈哈哈气哭了，还是因为输入问题。。。。。感觉要好好练一下输入输出啊。。。

今天通过这题把回溯算法总结一下吧。

 这边先上我用非回溯写的算法，首先全排列，然后判断即可。

代码

#include 
     
      #include 
      
       using namespace std;void allCombination( vector
       
         &nums, vector
        
         
          > &res, int start){	if( start == 7 ){		res.push_back(nums);		return;	}	for( int i = start; i < 7; i++ ){		swap(nums[i],nums[start]);		allCombination(nums,res,start+1);		swap(nums[i],nums[start]);	}}int main(){//	vector
          
           
            > source(7,vector
            
             (7,0));// for( int i = 0; i < 7; i++ ){// for( int j = 0; j < 7; j++ ){// cin>>source[i][j];// }// } vector
             
              
               > source{ {0,1,0,1,0,0,0},{1,0,0,0,0,1,0},{0,0,1,0,0,0,1},{0,0,0,0,1,0,0},{1,0,0,1,0,1,0},{0,1,0,0,1,0,0,},{0,0,1,0,0,1,1}}; int count = 0; vector
               
                 nums{1,2,3,4,5,6,7}; vector
                
                 
                  > res; allCombination(nums, res, 0); vector
                  
                   
                    > resoult; bool flag = true; for( int i = 0; i < res.size(); i++ ){ for( int j = 0; j < 7; j++ ){ if(source[res[i][j]-1][j] == 0 ){ flag = false; break; } } if( flag ){ resoult.push_back(res[i]); count++; } else{ flag = true; } } cout<
                    
                     <
                    
                   
                  
                 
                
               
              
             
            
           
          
         
        
       
      
     

那全排列的问题是什么？其实就是减枝的问题，在排列的时候没有直接将不可能的结果去掉，比如1,X,X,X,X,X,X这样的排列组合，如果第一个和尚规定第一天就不能抬水，那么所有1开头的组合方式都是没有必要去验证的。所以回溯算法的本质其实是在可能的解空间进行搜索，这样相对于枚举的优势就是能够更快的找到解。

如果有了这样的的思路，那我们就可以这样判断从第一天开始判断，往后进行判断，如果当天某一个和尚能够挑水，则放入解向量中，并把这个和尚的标志设为已经挑水，如果往下搜索以后，发现所有情况都不能满足了，则回退到上一步，换其他的和尚挑水，反复进行，直到所有可能情况都遍历。

这边需要注意的一个是截止条件，比如对于和尚挑水这一题，

1.截止条件应该就是第一天挑水的和尚为不存在的第八个和尚，即<8。

2.是一个成功解的判定条件是解向量的长度为7，即每一天都有和尚挑水。

3.如果当前这一天成功，则搜寻下一天，如果当天失败，则回退到上一天。对3过程进行迭代

#include 
     
      #include 
      
       using namespace std;void allPossibleResult( vector
       
         &isSelected, int day, vector
        
         
          > &source, vector
          
            res ){ if( day == 7 ){ for( int i = 0 ; i < 7; i++ ){ cout<
           
            <<" "; } cout<
            

> source(7,vector

(7,0));// for( int i = 0; i < 7; i++ ){// for( int j = 0; j < 7; j++ ){// cin>>source[i][j];// }// } vector

> source{ {0,1,0,1,0,0,0},{1,0,0,0,0,1,0},{0,0,1,0,0,0,1},{0,0,0,0,1,0,0},{1,0,0,1,0,1,0},{0,1,0,0,1,0,0,},{0,0,1,0,0,1,1}}; vector

isSelected(7,0); vector

res(7,0); int num = 0; int day = 0; allPossibleResult(isSelected, day, source, res); }