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

本文主要是介绍100盏灯经过一系列操作后最后还有多少盏灯亮着（百度的一道笔试题），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

今年百度的一道笔试题：有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 100void 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; // 记录有多少个位的值是1for (int i = 0; i < 100; i++){// 判断某位是不是为1if ((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的下表自增1if ((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];// 初始时让所有的位都置0memset(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;}