十六进制运算与纯粹素数算法的编程实践

天驰联盟

1. 从外星人算术到纯粹素数：三个算法问题的深度解析

最近在整理算法题库时，遇到三个非常有意思的编程题目，它们分别涉及十六进制运算、纯粹素数判断和简单投票统计。这三个问题看似简单，但每个都蕴含着值得深入探讨的编程技巧和算法思想。下面我将逐一解析这三个问题，分享我的解题思路和实现细节。

2. 十六进制加法计算器

2.1 问题背景与需求分析

题目描述了一个有趣的场景：小晨在路上遇到外星人，外星人用十六进制出加法题考验他。我们需要编写一个程序，能够读取多组十六进制数字符串，计算它们的和，并以小写十六进制形式输出结果。

这个问题的核心在于：

如何正确解析十六进制字符串为数值
如何处理大数相加避免溢出
如何按要求格式输出结果

2.2 关键技术实现

在C++中，我们可以利用stringstream配合hex操纵符来实现十六进制字符串到数值的转换。这里有几个关键点需要注意：

cpp复制#include<bits/stdc++.h>
using namespace std;

int main(){
    int n;
    cin>>n;
    for(int i=0;i<n;i++){
        string s1,s2;
        cin>>s1>>s2;
        unsigned long long num1,num2;
        stringstream ss1,ss2;
        ss1<<hex<<s1;  // 将字符串按十六进制解析
        ss2<<hex<<s2;
        ss1>>num1;     // 转换为数值
        ss2>>num2;
        unsigned long long res=num1+num2;
        cout<<nouppercase<<hex<<res<<endl; // 小写十六进制输出
    }
    return 0;
}

重要提示：必须使用unsigned long long类型存储结果，因为十六进制数可能很大，普通int类型容易溢出。例如，十六进制"ffffffff"转换为十进制是4294967295，已经超过了int的最大值。

2.3 常见问题与调试技巧

在实际编码过程中，可能会遇到以下问题：

大小写敏感问题：题目要求输出小写十六进制，必须使用nouppercase操纵符。我曾经忘记加这个，导致输出全是大写字母，调试了很久才发现。
前导零处理：输入可能有前导零，但stringstream的hex解析会自动忽略它们。例如"00a"和"a"会被解析为相同的数值。
边界测试：需要测试最大值的相加情况，如"ffffffff"+"1"应该等于"100000000"。

3. 纯粹素数查找算法

3.1 纯粹素数的定义与特性

纯粹素数是一个很有趣的数学概念。根据题目描述，纯粹素数是指：

本身是素数
每次去掉最高位后剩下的数仍然是素数
直到最后剩下个位数仍然是素数

例如1013：

1013是素数
去掉最高位1后得到013（实际为13），13是素数
再去掉最高位1得到3，3也是素数
因此1013是纯粹素数

3.2 算法设计与实现

解决这个问题的关键在于：

高效判断一个数是否为素数
递归或迭代地检查去掉最高位后的数是否仍为素数

我的实现分为两个主要函数：

cpp复制bool issu(int n){
    if(n<2) return false;
    if(n==2) return true;
    if(n%2==0) return false;
    for(int i=3;i<=sqrt(n);i+=2){
        if(n%i==0) return false;
    }
    return true;
}

bool ischuncui(int num){
    if(!issu(num)) return false;
    string s=to_string(num);
    while(s.size()>1){
        s=s.substr(1);  // 去掉最高位
        int a=stoi(s);
        if(!issu(a)) return false;
    }
    return issu(stoi(s)); // 最后检查个位数
}

关键细节：在ischuncui函数中，当字符串长度大于1时才进入循环，最后还需要单独检查剩下的个位数是否为素数。这是容易出错的地方。

3.3 性能优化与测试

查找纯粹素数是一个计算密集型任务，特别是当n较大时。我们可以进行以下优化：

素数判断优化：issu函数已经做了基本优化（只检查到sqrt(n)，跳过偶数），还可以考虑预先生成素数表。
跳过明显非素数：在查找过程中，可以跳过偶数（除了2），减少不必要的检查。
并行计算：对于大规模查找，可以考虑将任务分片并行处理。

测试案例：

第1个大于1000的纯粹素数是1013
第2个是1033
第3个是1103
第20个是1847

4. 简单投票统计系统

4.1 问题描述与设计

第三个题目要求实现一个简单的投票统计系统：

有3个候选人：zhang、li、wang（不区分大小写）
10个选民投票
统计每个候选人的得票数和废票数

虽然题目描述为"纯送分"，但实际实现中还是有一些细节需要注意。

4.2 代码实现与细节

cpp复制#include<bits/stdc++.h>
using namespace std;

int main(){
    string s;
    int numz=0,numl=0,numw=0,wrong=0;
    for(int i=0;i<10;i++){
        cin>>s;
        // 统一转换为小写比较，实现不区分大小写
        transform(s.begin(), s.end(), s.begin(), ::tolower);
        
        if(s=="zhang") numz++;
        else if(s=="li") numl++;
        else if(s=="wang") numw++;
        else wrong++;
    }
    cout<<"li:"<<numl<<endl
        <<"zhang:"<<numz<<endl
        <<"wang:"<<numw<<endl
        <<"Wrong election:"<<wrong;
    return 0;
}