各位如果看到博客内有广告,可以动手点一点,谢谢

MENU

第四届蓝桥杯决赛B组C/C++——填算式

April 13, 2018 • Read: 383 • 算法

猜灯谜

A 村的元宵节灯会上有一迷题:
请猜谜 * 请猜谜 = 请边赏灯边猜
小明想,一定是每个汉字代表一个数字,不同的汉字代表不同的数字。
请你用计算机按小明的思路算一下,然后提交 “请猜谜” 三个字所代表的整数即可。
请严格按照格式,通过浏览器提交答案。
注意:只提交一个 3 位的整数,不要写其它附加内容,比如:说明性的文字。

题解

  1. 暴力 6 个 for 循环,没什么技术,就不说了
  2. dfs,这题其实比较巧妙,因为和八皇后很类似,你在脑中想象有一个 6*10 的格子(6 行 10 列),每一列代表一个数字,10 列分别从 0-9;每一行分别代表一个汉字,只不过在搜索的时候要注意第 0 行第 0 列不能放(下标都从 0 开始),因为第 0 行代表的汉字是 “请”,“请” 不能是 0,要不然就 0 开头了

代码

#include<bits/stdc++.h>
using namespace std;
int res[6];//分别表示请,猜,迷,边,赏,灯
//请猜谜*请猜谜 = 请边赏灯边猜 
void dfs(int k)//搜索到了第k层
{
    int j;
    if(k == 7 && (res[0]*100+res[1]*10+res[2])*(res[0]*100+res[1]*10+res[2]) == 
              (res[0]*100000+res[3]*10000+res[4]*1000+res[5]*100+res[3]*10+res[1]))
    {
        for(int i = 0;i < 6;i++)
            cout<<res[i]; 
        cout<<endl;
        return;
    }
    for(int i = 0;i < 10;i++)//i表示可取的列,也就是可取的值
    {
        for(j = 0;j < k;j++)//j表示第k行之前的数取值 
        {
            if(i==res[j])
                break;
        }
        if(k == j)
        {
            res[j] = i;
            if(res[0] == 0)
                 continue;
            dfs(k+1);
        }
    } 
} 
int main()
{
    dfs(0);
    return 0;
}

答案:897

Archives Tip
QR Code for this page
Tipping QR Code