猫史档案馆

最近很无聊，就开一个讲题目的系列吧~

注：本系列中，OJ均指aes.codemao.cn

大家可以在下方留言想要听的题目~我可能会更新

 

====================================正文分割线==================================

我们先来看一看题目

 

进制游戏  

Description

我们将整数n的奇偶性定义为以2为模计算的二进制表示位的和。 例如，数字21 = 101012在其二进制表示中有三个1，因此它的奇偶校验为3(mod2)或1。

在这个问题中，你必须计算整数1≤I≤2147483喵7 的奇偶校验。

 

Input

输入的每一行都有一个整数I，输入的结束由一行I = 0表示，其中I不应该被处理。

 

Output

对于输入中的每个整数I，你应该打印一行“The parity of B is P (mod 2)”，其中B是I的二进制表示。

 

Sample Input 1                                                                             Sample Output 1

1                                                                                                     The parity of 1 is 1 (mod 2).

2                                                                                                     The parity of 10 is 1 (mod 2).  

10                                                                                                   The parity of 1010 is 2 (mod 2). 

21                                                                                                   The parity of 10101 is 3 (mod 2).

0

 

仔细分析一下题目，其实这题的主要工作就是将输入的整数转换成二进制再统计1的个数。

而我为了方便统计，我就选用了string来进行操作。

先写好基本框架~

#include <iostream>
using namespace std;

int main()
{

    return 0;
}

然后定义一些我们需要的数据

#include <iostream>
#include <string> //导入string头文件
using namespace std;

int main()
{
    int n; //用于存放每次输入的数据
    int count; //用于统计二进制中1的个数
    string binary; //用于存放输入数据的二进制
    return 0;
}

接着，我们来思考一下如何实现基本输入。

如题中所述，程序只要输入0便需要停止。

这里肯定有人会说： 哎呀作者那么简单的题，用个while(n!=0)不就行了吗！

首先，这样不对的。因为我们需要在输入完之后立刻输出，而while循环的退出条件是每次执行完一次循环才会执行，所以我们得将这个判断放在输入后面，如下：

#include <iostream>
#include <string> //导入string头文件
using namespace std;

int main()
{
    int n; //用于存放每次输入的数据
    int count; //用于统计二进制中1的个数
    string binary; //用于存放输入数据的二进制
    while(1) //无限循环
    {
        scanf("%d", &n); //格式化输入
        if(n==0) break; //判断是否为0
    }
    return 0;
}

接着，就是这一题的重磅难点：如何将数字转换成二进制。

众所周知，我们要想将十进制转换成二进制，得用短除法对吧？

 

 

那我们就可以用C++配合string来进行模拟。

这里我自定义了一个函数，toBinary，表示转换成二进制

string toBinary(int n)
{
    string binary="";
    while(n!=0){
        binary = to_string(n%2)+binary; //如上图，我们需要从下往上依次读取，所以我们得逆向存储
        n /= 2;
    }
    return binary;
}

好了，我们已经攻克了这座大山，接下来的路程就畅通无阻了。

我们先来完善一下输入。

#include <iostream>
#include <string> //导入string头文件
using namespace std;

int main()
{
    int n; //用于存放每次输入的数据
    int count; //用于统计二进制中1的个数
    string binary; //用于存放输入数据的二进制
    while(1) //无限循环
    {
        scanf("%d", &n); //格式化输入
        if(n==0) break; //判断是否为0
        binary = toBinary(n); //转换成二进制
        count = 0;//这是下一步的步骤，我们先写上去
        printf("The parity of %s is %d (mod 2).\n", binary.c_str(), count); //输出
    }
    return 0;
}

或许有些眼尖的小伙伴已经注意到了，为什么binary要用c_str呢？这是因为在格式化输出的时候，我们使用的%s占位符指的是C语言风格的字符串，也就是char字符数组。这个c_str()就是将string转换成字符数组。

 

接下来就是最后一步——统计1的个数

这一步很简单，其实只需要for循环遍历就行，代码如下，这里我也定义了一个函数：

int countOne(string str){
	int count=0;
	for(int i=0;i<str.length();i++){
		if(str[i]=='1') count++;
	}
	return count;
}

好了！这就是OJ3015的全部内容了，完整代码如下（这里我稍稍修改了一下，读得懂就行）：

#include <iostream>
#include <string>
using namespace std;

string toBinary(int n){
	string binary="";
	while(n!=0){
		binary = to_string(n%2)+binary;
		n /= 2;
	}
	return binary;
}

int countOne(string str){
	int count=0;
	for(int i=0;i<str.length();i++){
		if(str[i]=='1') count++;
	}
	return count;
}

void read(){
	int n=1, count=0;
	string binary;
	while(n!=0){	
		scanf("%d", &n);
		if(n==0) return;
		binary = toBinary(n);
		count = countOne(binary);
		printf("The parity of %s is %d (mod 2).\n", binary.c_str(), count);
	}
}

int main()
{
	read();	
	return 0;
}

 

#include<iostream>
#include<cmath>                 // 需要用到pow函数
using namespace std;

int toBinary(int oct);          // 将十进制转为二进制
int countOne(int input);        // 数出数字1的个数

int main(){
    long long input, output;
    while(true){                // 用死循环监听输入
        cin >> input;
        if(input == 0) break;
        output = toBinary(input);
        cout << "The parity of " << output;
        output = countOne(output);
        cout << " is " << output << " (mod 2).\n";
    }
    return 0;
}

int toBinary(int input){
    int output = 0, bit = 0;    // bit是位置
    int *numList = new int[70]; // 先定了70位(毕竟long long也只有64位)
    for(; input != 0; bit ++){  // 先分解
        numList[bit] = input % 2;
        input = input / 2;
    }
    for(; bit >= 0; bit --){    // 后合并
        output += pow(10, bit) * numList[bit];
    }
    delete[] numList;
    return output;
}

int countOne(int input){
    int output = 0;
    while(input != 0){          // 这里更简单,不断除10就行
        if(input % 2 == 1) output ++;
        input /= 10;
    }
    return output;
}