100盏灯经过一系列操作后最后还有多少盏灯亮着（百度的一道笔试题）

谁践踏了优雅 2022-05-19 08:46 188阅读 0赞

今年百度的一道笔试题：有100盏灯（它们的位置编号为1， 2 .. 99，100），刚开始全都是灭着的。第一次把所有的灯都打开，第二次把偶数位置上的灯灭了，第三次把位置是3的倍数的灯原来灭的打开，原来打开着的，灭了。第N次把位置是N的倍数的灯原来灭的打开，原来打开着的，灭了。问第100次后还有多少盏灯灭着的？下面我用编程实现这道题在写代码之前我们先分析一下这道题。100盏灯一会儿灭，一会儿亮到底哟什么规律呢？规律就是第N次操作会把位置是N的倍数的灯原来灭着的，打开，原来打开的，灭了。打开，关闭两种状态，可以用一个变量或者一个二进制位来表示，100盏灯可以用一个大小为100的整型数组或者100个二进制位来表示状态。下面我就用100个二进制位来实现算法。 ps:带有注释的代码是同一个函数的不同实现

#include "iostream"
    using namespace std;
    #include "memory.h"
    #define BYTESIZE 8
    #define LAMPNUM 100
    
    void setBitsByRules(char* pBuffer, int rules, const int bufferlen){ // 宏不能作为形参
    	
    	for (int i = 1; i < bufferlen+1; i++){
    		if (i % rules == 0){
    		    // 按位取反
    			*pBuffer = *pBuffer ^ (0x01 <<((i-1)%8));
    		}
    		
    		if (i%8==0) {
    			pBuffer++;
    		}
    
    	}
    	
    }

int  checkBits(char* pBuffer, int n){
    	int count = 0; // 记录有多少个位的值是1
    	
    	for (int i = 0; i < 100; i++){
    	
    		// 判断某位是不是为1
    		if ((int)((  (*pBuffer) & ( (0x01) << (i%8)  ) )) != 0){
    			count++;
    			cout << (i+1) << "亮 ";
    		}else {
    			//	cout << (i+1) << "灭 "; // 测试语句
    		}
    		
    		// 注意应该是if ((i+1)%8 == 0) 而不是if (i%8 == 0)下标是从0开始的
    		// 所以当8的倍数减1就要使pBuffer的下表自增1
    		if ((i+1)%8 == 0) {
    			pBuffer++;
    		}
    	}
    	return count;
    }

void main(){

// N个二进制位共需要多少个个字节（必须是整数）
        int bufferlen = 0;
    	if (LAMPNUM%BYTESIZE == 0){
    		bufferlen = LAMPNUM/BYTESIZE;
    	} else {
    		bufferlen = LAMPNUM/BYTESIZE + 1;
    	}
        
        char* pBuffer = new char[bufferlen];
    	 
    	// 初始时让所有的位都置0
    	memset(pBuffer, 0, bufferlen);
    
    	for (int i = 1; i < LAMPNUM+1; i++){
    	    setBitsByRules(pBuffer, i,  LAMPNUM);		
    	}
    
    	int count = 0;
    	// 检查有多少位是1即有多少盏灯是亮着的
    	count = checkBits(pBuffer, LAMPNUM);
    	cout << "最终有" << count << "盏灯亮着！" << endl;
    
    	delete[] pBuffer;
     }

![1351258902_6579.jpg][]

[1351258902_6579.jpg]: https://img-my.csdn.net/uploads/201210/26/1351258902_6579.jpg