2 qq 26825135 qq_26825135 于 2016.09.16 16:31 提问

一道简单有趣的算法题,聪明人来

图片说明

10个回答

waterhexuan
waterhexuan   2016.09.17 11:48
已采纳

图片说明
嫌麻烦 输入部分 写死了 改成动态 就行了 核心算法 就是 findCount 函数

qq_26825135
qq_26825135 写在了楼下
大约一年之前 回复
qq_26825135
qq_26825135 我写全了,但那个cou好像传不出去呢
大约一年之前 回复
qq_29594393
qq_29594393   Ds   Rxr 2016.09.16 17:40

对于题给的示例有4种可以表示a的意思,是哪四种??
cab ccb eeb abb??如果是这样的话,倒是可以试着解决

qq_26825135
qq_26825135   2016.09.17 07:45

是的,我做的就是倒着的,但是有多层嵌套的循环和复杂的判定,最后失败了。我有写到简单的方法就是可以用两个string二维数组来存,把每次找到的单字母序数设为flag然后循环,很快就能找到一条路,然后得每次退出一步上限减还是利用原循环,再倒回来,应该是用到栈,不过这个判定不会写

qq_35553864
qq_35553864   2016.09.17 08:54

ccb为啥能表示a啊

qq_26825135
qq_26825135   2016.09.17 10:24

他写错了,是cca,eea,cab,abb

waterhexuan
waterhexuan   2016.09.17 10:35

这个得用递归来做....

qq_26825135
qq_26825135   2016.09.17 10:43

是啊,但是那个条件太难弄了

QiaXi
QiaXi   2016.09.17 15:23

我的理解是,假如n==6,那么开头两个字符替换成1个,长度变成5,然后开头两个又能替换,长度变成4,直到长度为1并且字符为'a', 代码如下

#include <iostream>
#include <map>
#include <string>
#include <vector>

int generateCode(std::string& code, const std::multimap<char, std::string>& codeBook, const std::string::size_type targetCodeLength)
{
    if (code.size() == targetCodeLength)
        return 1;

    int cnt = 0;
    for (std::multimap<char, std::string>::const_iterator itr = codeBook.lower_bound(code[0]); itr != codeBook.upper_bound(code[0]); ++itr)
    {
        std::string newCode(itr->second);
        newCode.append(code.begin() + 1, code.end());
        cnt += generateCode(newCode, codeBook, targetCodeLength);
    }

    return cnt;
}

int main()
{
    int n = 0;
    int q = 0;
    char value;
    std::string code;
    std::multimap<char, std::string> codeBook;

    std::cin >> n >> q;
    for (int i = 0; i != q; ++i)
    {
        std::cin >> code >> value;
        codeBook.insert(std::make_pair(value, code));
    }

    std::string targetCode = "a";
    std::cout << generateCode(targetCode, codeBook, n) << std::endl;
}
qq_26825135
qq_26825135   2016.09.17 19:01

#include
#include
#include
using namespace std;
int n = 0;
int q = 0;

string string_x[36];
string string_y[36];
int x = 0;
int y = 0;
void findCount(int depth, int *cou, char value)
{
for (int i = 0; i < q; i++)
{
if (string_y[i][0] == value)
{
if (depth == n)
{
++(*cou);
}
else
{
char val = string_x[i][0];
findCount(depth + 1, cou, val);
}
}
}
}
int main(){

//cout << string_x[0][0] << endl;
cin >> n >> q;
while (q > 0)
{
    cin >> string_x[x++];
    cin >> string_y[y++];
    q--;
}


int result_count = 0;
findCount(2, &result_count, 'a');
cout << result_count;
system("pause");
return 0;

}

qq_26825135
qq_26825135   2016.09.17 19:15

不好意思,一个很弱智的错误,我发现了,楼上两位代码都是对的

Csdn user default icon
上传中...
上传图片
插入图片
准确详细的回答,更有利于被提问者采纳,从而获得C币。复制、灌水、广告等回答会被删除,是时候展现真正的技术了!