数码管编程题-编程练习题（100）

问题：

7.	【问题描述】液晶数码管用七笔阿拉数字表示的十个数字，把横和竖的一个短划都称为一笔，即７有３笔，８有７笔等。对于十个数字一种排列，要做到两相邻数字都可以由另一个数字加上几笔或减去几笔组成，但不能又加又减。比如７→３是允许的，７→２不允许。任意输入一组数，判断是否符合上述规则，注意，1在右边。【输入形式】每行输入一个0~9的排列，数字之间用空格分隔，以-1作为输入结束【输出形式】输出YES或NO 【样例输入】 `4 1 0 7 3 9 5 6 8 2 3 5 1 6 2 7 9 0 4 8 -1` 【样例输出】 `YES NO`

分析：

方法1：可以把数码管的七笔进行编号，然后使用二维数字存储0-9十个数字所使用的数码管编号，如果两个数字编号交集等于其中一个数字的编号，则可以增几笔或减几笔变换，例如数字A用了编号1、3、5、7，数字B用了编号3、5，则 $Acap B$ =B：{3、5}。所以这个变换是允许的。

方法2：方法1理论上可以实现，但是会比较麻烦，每两个相邻的数都要进行对比，也就是要循环7*(n-1)次，其中n为0-9一个排列中所含数的个数。所以我又想到了一个方法，将允许进行转换的数字存入一个key-value对中，如果可以通过key找到对应的value（相邻的数），则表示允许转换，但是这个怎么存储呢？在map中key是不允许有重复的，但是我们可以使用multimap，这个函数操作就不细说了。这里我使用另一种简单的方法，使用一个二维数组map_array[10][10]，能相互转换的数字对应位置存1，不允许相互转换的存0。这样就可以在O(1)的时间内查看两个数字是否允许转换，相对于multimap来说就是造成了空间的浪费，但是相对于multimap来说数组的速度是要快的。

C++AC代码：

#include <iostream>

using namespace std;

int main()
{                         //0 1 2 3 4 5 6 7 8 9  数字0-9互相转换映射表，正好是对称矩阵
    int map_array[10][10]={{1,1,0,0,0,0,0,1,1,0},  //0
                           {1,1,0,1,1,0,0,1,1,1},  //1
                           {0,0,1,0,0,0,0,0,1,0},  //2
                           {0,1,0,1,0,0,0,1,1,1},  //3
                           {0,1,0,0,1,0,0,0,1,1},  //4
                           {0,0,0,0,0,1,1,0,1,1},  //5
                           {0,0,0,0,0,1,1,0,1,0},  //6
                           {1,1,0,1,0,0,0,1,1,1},  //7
                           {1,1,1,1,1,1,1,1,1,1},  //8
                           {0,1,0,1,1,1,0,1,1,1}   //9
                          };
    int number[10];
    bool flag = true;

    while(1)
    {
        flag = true;
        cin >> number[0];
        if(-1 == number[0] )
        {
            break;
        }
        for(int i=1; i<10; i++)
        {
            cin >> number[i];                              //获取数字存入number[]
            if(1 != map_array[ number[i-1] ][ number[i] ]) //判断是否允许转换
            {
                flag = false;
            }
        }
        if(false == flag)
        {
            cout << "NO" <<endl;
        }else{
            cout << "YES" <<endl;
        }
    }
    return 0;
}

总结：

这道题不难，就是将映射表做出来花了点时间。仔细想想这道题也挺有意思。