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.
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".
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".
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面数字一样的小球，我们就也取出来。最后问，有多少张这样的卡片，能把袋子里的小球都取出来。
要解决这个问题，我们要需要建立一个数字当它A面相上时和B面向上时所表示的两个不同数字的映射关系。我们将这层关系叫做：数字映射。
同时，在卡片反转之后，每个数字的位置也发生了变化，我们为了方便记忆我们称之为：位置映射。
这样，经过数字映射和位置映射我们就能通过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;
}
运行结果
8824
以上内容由steemit作者 @breathewind 原创发布。
All the content above are published by Steemit author @breathewind.
转载请注明出处。
Please indicate the source when you reblog or reuse.
如果您对我的内容感兴趣，不妨试试这些文章：
If you like my post, the following posts may be interested for you as well:
唠唠嗑 - 从奢侈品的风格改变，谈谈在Steemit上的写作风格
唠唠嗑 - “泡沫”不一定是件坏事 顺便说说steemit的泡沫
猜想与验证 - 英语的月份与意大利语数字
谢谢阅读 !
Thanks for your reading !
欢迎您我对我点赞，评论或者订阅 @breathewind
Please feel free to upvote, comment and follow me @breathewind