| 网站首页 | 业界新闻 | 群组 | 交易 | 人才 | 下载频道 | 博客 | 代码贴 | 编程论坛
共有 503 人关注过本帖
标题:农夫过河问题。超时,有大神可以帮忙看一下吗?谢谢
只看楼主 加入收藏
Queenlight
Rank: 1
等 级:新手上路
帖 子:18
专家分:0
注 册:2017-3-14
结帖率:66.67%
  已结贴   问题点数:30  回复次数:3   
农夫过河问题。超时,有大神可以帮忙看一下吗?谢谢
#include <iostream>
#include <cstdlib>
#include <cstring>
using namespace std;

const int MAXQSIZE = 100;

template<class ElemType>
class SqQueue
{
private:
    ElemType *elem;
    int rear; //队尾指针
    int front; //队头指针
    int queueize;
    int count;
public:
    SqQueue(int ms = 0);
    ~SqQueue()
    {
        QueueDestroy();
    }
    bool QueueDestroy();
    bool QueueClear( );
    int StackLength() const
    {
        return (rear - front + queueize)%queueize;
    }
    bool QueueisEmpty() const
    {
        return count == 0;
    }
    bool GetHead(ElemType &e) const;
    bool EnQueue(ElemType &e);
    bool DeQueue(ElemType &e);
    void QueueTraverse() const;
};
//初始化
template<class ElemType>
SqQueue<ElemType>::SqQueue(int ms)
{
    if(ms == 0) ms = MAXQSIZE;
    elem = new ElemType[ms];
    if(!elem) exit(1);
    queueize = ms;
    count = 0;
    front = rear= 0;
}
//销毁
template<class ElemType>
bool SqQueue<ElemType>::QueueDestroy()
{
    if(!elem) return false;
    free(elem);
    front = rear = 0;
    queueize = 0;
    count = 0;
    return true;
}
//空表
template<class ElemType>
bool SqQueue<ElemType>::QueueClear( )
{
    if(!elem) return false;
    free(elem);
    front = 0;
    rear = 0;
    return true;
}
//返回队头元素
template<class ElemType>
bool SqQueue<ElemType>::GetHead(ElemType &e) const
{
    if(front == rear) return false;
    e = elem[front];
    return true;
}
//入队
template<class ElemType>
bool SqQueue<ElemType>::EnQueue(ElemType &e)
{
    if((rear+1)%queueize==front)
        return false;
    elem[rear] = e;
    rear = (rear+1)%queueize;
    count++;
    return true;
}
//出队
template<class ElemType>
bool SqQueue<ElemType>::DeQueue(ElemType &e)
{
    if(front == rear) return false;
    e = elem[front];
    front = (front+1) % queueize;
    count--;
    return true;
}
//遍历
template<class ElemType>
void SqQueue<ElemType>::QueueTraverse() const
{
    int i;
    int length = (rear - front + queueize)%queueize;
    for(i = front; i < length; i++)
        cout << elem[i];
    cout << endl;
}

int goat(int st)
{
    return (st&0x01)!=0;
}
int cabbage(int st)
{
    return (st&0x02)!=0;
}
int wolf(int st)
{
    return (st&0x04)!=0;
}
int farmer(int st)
{
    return (st&0x08)!=0;
}

int safe(int st)
{
    if((goat(st)==cabbage(st))&&(goat(st)!=farmer(st)))
        return 0;
    if((goat(st)==wolf(st))&&(goat(st)!=farmer(st)))
        return 0;
    return 1;
}

void print(char*str)
{
    int size = strlen(str);
    int k = 4-size;
    while(k)
    {
        cout << "0";
        k--;
    }
    cout << str << endl;
}

template<class ElemType>
void farmerProblem(SqQueue<ElemType> &S)
{
    int mover, i, st, st_new;
    int route[16];
    ElemType e0;
    e0 = 0x00;
    S.EnQueue(e0);
    for(i = 0; i < 16; i++)
    {
        route[i] = -1;
    }
    route[0] = 0;
    while(!S.QueueisEmpty()&&route[15]==-1)
    {
        S.GetHead(st);
        S.DeQueue(e0);
        for(mover = 1; mover <= 8; mover <<= 1)
        {
            if(farmer(st)==(0!=(st&mover)))
            {
                st_new = st^(0x08|mover);
            }
            if(route[st_new] == -1&&safe(st_new))
            {
                route[st_new] = st;
                S.EnQueue(st_new);
            }
        }
    }
    char*str;
    if(route[15] != -1)
        for(st = 15; st >= 0; st = route[st])
        {
            itoa(st, str, 2);
            print(str);
            if(st == 0) break;
        }
}

int main()
{
    SqQueue<int> S;
    farmerProblem(S);
    return 0;
}
2017-11-09 11:17
Queenlight
Rank: 1
等 级:新手上路
帖 子:18
专家分:0
注 册:2017-3-14
  得分:0 
好像是这个函数的问题itoa(st, str, 2);
我把这个直接换成自己转化就可以,请问为什么不能用这个函数?
2017-11-09 12:54
yuccn
Rank: 16Rank: 16Rank: 16Rank: 16
来 自:何方
等 级:版主
威 望:166
帖 子:6788
专家分:42352
注 册:2010-12-16
  得分:30 
你这是农夫过河问题的实现代码?看着有点绕,多写写注释好点

真巧前几天写过一遍,不过是python 写的
http://blog.yuccn.net/archives/211.html

希望对你有参考价值。



[此贴子已经被作者于2017-11-10 15:40编辑过]


我行我乐
我的博客:
http://blog.yuccn. net
2017-11-10 15:36
yuccn
Rank: 16Rank: 16Rank: 16Rank: 16
来 自:何方
等 级:版主
威 望:166
帖 子:6788
专家分:42352
注 册:2010-12-16
  得分:0 
回复 2楼 Queenlight
应该看看提示什么错误,原生提供itoa 应该能够满足了的

[此贴子已经被作者于2017-11-10 17:50编辑过]


我行我乐
我的博客:
http://blog.yuccn. net
2017-11-10 15:42







关于我们 | 广告合作 | 编程中国 | 清除Cookies | TOP | 手机版

编程中国 版权所有,并保留所有权利。
Powered by Discuz, Processed in 0.030495 second(s), 9 queries.
Copyright©2004-2018, BCCN.NET, All Rights Reserved