编程算法案例1

抓交通肇事犯

1．问题描述

一辆卡车违反交通规则，撞人后逃跑。现场有三人目击该事件，但都没有记住车号，只记下了车号的一些特征。甲说：牌照的前两位数字是相同的；乙说：牌照的后两位数字是相同的，但与前两位不同；丙是数学家，他说：4位的车号刚好是一个整数的平方。请根据以上线索求出车号。

2．问题分析

• 将所有可能的4位整数进行筛选，保留前两位相同、后两位不同的数；
• 对剩下的数，逐个进行平方根计算并判断是否为整数；
• 如果是整数，说明该数是一个符合条件的车号。

3.算法设计：

当卡车车牌号码是一个4位整数时，根据3个目击者的描述，可以具体实现以下算法：

1. 1. 循环遍历所有的4位数，从1000到9999；
   2. 对于每个4位数，将它的千、百、十、个位分别计算出来。
   3. 根据甲、乙两位目击者的描述，筛选出可能的车牌号码：
   4. 对于满足条件的车牌号码，利用数学库中的平方根函数求出平方根，并判断平方根是否是整数。
   5. 输出符合条件的车牌号码。

Python语言实现

import math

for num in range(1000, 10000):
    a = num // 1000   # 取千位
    b = num // 100 % 10   # 取百位
    c = num // 10 % 10   # 取十位
    d = num % 10   # 取个位

    if a == b and c != d:   # 满足甲说的条件
        if c == d and a != c:   # 满足乙说的条件
            square = int(math.sqrt(num))   # 计算平方根，转换为整数
            if square * square == num:   # 满足丙说的条件
                print('车号是：', num)

代码中使用range函数对所有可能的4位整数进行遍历，然后根据题目所给的三个线索依次进行筛选，最后得到符合条件的车号。

执行结果为：

车号是： 7744

故该卡车的车牌号码是7744。

C语言实现

#include <stdio.h>
#include <math.h>

int main() {
    int a, b, c, d, num, square;

    for (num = 1000; num < 10000; num++) {
        a = num / 1000;   // 取千位
        b = num / 100 % 10;   // 取百位
        c = num / 10 % 10;   // 取十位
        d = num % 10;   // 取个位
        
        if (a == b && c != d) {   // 满足甲说的条件
            if (c == d && a != c) {   // 满足乙说的条件
                square = sqrt(num);
                if (square * square == num) {   // 满足丙说的条件
                    printf("车号是：%d\n", num);
                }
            }
        }
    }

    return 0;
}

这段 C 代码与 Python 版本类似，区别在于：

• C中 sqrt 函数存在于 math.h 头文件中。
• C中判断整数的方式与Python中略微不同。C语言中直接用 sqrt(num) * sqrt(num) == num 进行判断，Python中使用 int(sqrt(num))**2 == num。当然，由于C语言的运行速度比Python更快，对于这个数字计算的速度更快些。

执行结果：

车号是：7744

JAVA语言实现

public class Main {
    public static void main(String[] args) {
        int a, b, c, d, num, square;

        for (num = 1000; num < 10000; num++) {
            a = num / 1000;   // 取千位
            b = num / 100 % 10;   // 取百位
            c = num / 10 % 10;   // 取十位
            d = num % 10;   // 取个位
            
            if (a == b && c != d) {   // 满足甲说的条件
                if (c == d && a != c) {   // 满足乙说的条件
                    square = (int) Math.sqrt(num);
                    if (square * square == num) {   // 满足丙说的条件
                        System.out.println("车号是：" + num);
                    }
                }
            }
        }
    }
}

与前面两个版本类似，这个版本的 Java 代码实现了完全相同的算法。唯一的区别就是使用了 Java 语言的语法和库函数。与 C 语言不同的是，在 Java 中我们需要显式地将 Math.sqrt 的返回值转换为整数，否则将显示一个编译器错误。

执行结果：

车号是：7744