[Solution in Qt] Mathematics × Programming Competition #8 [Qt解答] 數學 × 程式編寫比賽 (第八回)

breathewind (63)in #cn • 7 years ago (edited)

English version (Chinese version is in following part 中文版本在接下来的部分)

I attended the contest offered by @kenchung 的 Mathematics × Programming Competition #8. In the following part, I will share my solution using Qt.

Analysing Part

We simplify the question as:
In a bag, there are 10,000 balls on which are numbers from 0000 to 9999. Now, we are trying to make some cards on which are numbers from 0000. There are 2 sides on each card, Side A and Side B . What we will do is that we firstly put the card in a position which Side A is on the top and take the ball with the same number as shown on current card from the bag. Then we put the card in reverse position with Side B on the top. If there exists a ball with the same number as shown on the reversed card, we take it from the bag as well. Finally, we need to tell how many cards are needed in order to take all the balls from the bag.

^{This picture is produced by @breathewind}

To work out this question, we need to establish a relationship between the number when Side A is on the top and the number when Side B is on the top. We name this relationship "number mapping".

^{This picture is produced by @breathewind}

In the same time, when a card reverse its position between Side A and Side B, the position of each single number changes as well. We name this position change "position mapping".

^{This picture is produced by @breathewind}

By number mapping and position mapping, we are able to transform a number from Side A up to Side B up. Till now, the main algorithm is illustrated. The remaining issue to be handled is to take balls with corresponding numbers from the bag. Easy work.

Code Part

1). Number mapping

QChar Card::number_mapping(QChar ch)
{
    if(ch == '0'){
        return '0';
    }else if(ch == '1'){
        return '1';
    }else if(ch == '2'){
        return '2';
    }else if(ch == '3'){
        return 'X';
    }else if(ch == '4'){
        return 'X';
    }else if(ch == '5'){
        return '5';
    }else if(ch == '6'){
        return '9';
    }else if(ch == '7'){
        return 'X';
    }else if(ch == '8'){
        return '8';
    }else if(ch == '9'){
        return '6';
    }else{
        return 'X';
    }
}

2). Position mapping

QString Card::position_mapping(QString num)
{
    QChar res[4];
    
    res[0] = number_mapping(num.at(3));
    res[1] = number_mapping(num.at(2));
    res[2] = number_mapping(num.at(1));
    res[3] = number_mapping(num.at(0));
    
    return QString(res,4); // return a QString initialized by a 4-bit QChar array
}

3). Main processing function

void Card::main_processing()
{
// Use QStringList as that bag
    QStringList list;
// Put balls with number from 0000 to 9999 into the bag
    for(int i=0; i<10000; i++)
    {
        QString number = QString("%1").arg(i, 4, 10, QChar('0')); // “XXXX” format
        list << number;
    }
    
    int count = 0;
// Cards from 0000
    for(int i=0; i<10000; i++)
    {
        QString number = QString("%1").arg(i, 4, 10, QChar('0'));
        if(list.size()>0){
// If Side A up
            if(list.contains(number)){
                count++;
                list.takeAt(list.indexOf(number));
            }
// If Side B up
            if(list.contains(position_mapping(number))){
                list.takeAt(list.indexOf(position_mapping(number)));
            }
        }else{
// If the bag is empty, terminate the loop
            break;
        }
    }
// Print card count
    qDebug() << count;
}

Result

8824

中文版本

我参加了 @kenchung 的數學 × 程式編寫比賽接下就跟大家分享下我用Qt写的答案。

分析部分

这道题可以简化为一个这样的问题：
我们有1个袋子里面装着写有0000到9999的1万个小球。现在我们要制作一些片，上面写着从0000开始的数字，这些卡片有A，B两个面。我们把A面向上，从袋子中取出那个跟A面数字一样的小球；再把B面向上，如果有跟B面数字一样的小球，我们就也取出来。最后问，有多少张这样的卡片，能把袋子里的小球都取出来。

^{此图片由 @breathewind 绘制}

要解决这个问题，我们要需要建立一个数字当它A面相上时和B面向上时所表示的两个不同数字的映射关系。我们将这层关系叫做：数字映射。

^{此图片由 @breathewind 绘制}

同时，在卡片反转之后，每个数字的位置也发生了变化，我们为了方便记忆我们称之为：位置映射。

^{此图片由 @breathewind 绘制}

这样，经过数字映射和位置映射我们就能通过A面向上时卡片所表示的数字得到B面向上时卡片所表示的数字。到此为止，这个程序中的主要算法核心已经出来了。剩下要做的就是将这个两个数字分别从袋子中取出即可。

代码部分

1). 数字映射

QChar Card::number_mapping(QChar ch)
{
    if(ch == '0'){
        return '0';
    }else if(ch == '1'){
        return '1';
    }else if(ch == '2'){
        return '2';
    }else if(ch == '3'){
        return 'X';
    }else if(ch == '4'){
        return 'X';
    }else if(ch == '5'){
        return '5';
    }else if(ch == '6'){
        return '9';
    }else if(ch == '7'){
        return 'X';
    }else if(ch == '8'){
        return '8';
    }else if(ch == '9'){
        return '6';
    }else{
        return 'X';
    }
}

2). 位置映射

QString Card::position_mapping(QString num)
{
    QChar res[4];
    
    res[0] = number_mapping(num.at(3));
    res[1] = number_mapping(num.at(2));
    res[2] = number_mapping(num.at(1));
    res[3] = number_mapping(num.at(0));
    
    return QString(res,4); // 以4位QChar数组 res 建立一个 QString 作为返回类型
}

3). 主函数

void Card::main_processing()
{
// 用 QStringList 模拟袋子
    QStringList list;
// 向袋子中放入写有0000到9999的小球
    for(int i=0; i<10000; i++)
    {
        QString number = QString("%1").arg(i, 4, 10, QChar('0')); // 统一 “XXXX” 格式
        list << number;
    }
    
    int count = 0;
// 从0000开始写卡片
    for(int i=0; i<10000; i++)
    {
        QString number = QString("%1").arg(i, 4, 10, QChar('0'));
        if(list.size()>0){
// 如果卡片A面相上
            if(list.contains(number)){
                count++;
                list.takeAt(list.indexOf(number));
            }
// 如果卡片B面相上
            if(list.contains(position_mapping(number))){
                list.takeAt(list.indexOf(position_mapping(number)));
            }
        }else{
// 如果袋子空了，就退出循环
            break;
        }
    }
// 输出一共用了多少个卡片
    qDebug() << count;
}