首页 新闻 论坛 群组 Blog 文档 下载 读书 Tag 网摘 搜索 .NET Java 游戏 视频 人才 外包 培训 数据库 书店 程序员
中国软件网
欢迎您:游客 | 登录 注册 帮助
  • 将程序代码中的goto全部优化为while等循环是NP完全性问题么? [已结贴,结贴人:DarknessTM]
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    发表于:2008-06-10 14:50:27 楼主
    如题。
    20  修改 删除 举报 引用 回复
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    发表于:2008-06-10 18:18:401楼 得分:10
    不是!
    证明:
    首先你要了解goto和while在计算机里面是用什么指令。goto是用非条件跳转指令实现的,而while是用条件跳转指令实现的。他们的区别就在这里。接下来就要看while的结构,在c++里面,while(){},或者是do{}while();这样子就说明了,我们可以通过设定真值条件来用while实现goto。也就是说,我们可以在多项式时间里面把实现goto的算法转变成while的算法。根据算法理论的定义,这个问题不是NP问题,而是P问题。
    证毕。

    如果您有兴趣了解算法理论,可以上我的blog。我最近在连载算法理论的笔记。把手上的笔记都翻译成中文。
    修改 删除 举报 引用 回复
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    发表于:2008-06-10 20:47:492楼 得分:0
    C/C++ code
    lable: for (int i = 0;i < 10;i++) { for(int j = 0;j < 10;j++) { ... if (...) goto lable; // 这个你怎么转化成while循环? ... } } int i = 0,j = 0; while(i < 10) { lable2: do { .... goto lable: // 转化? } while (j < 20) } goto lable3; // 转化? lable: i++,j++; goto lable2; // 转化? lable3:



    进一步说,就是在 单源有向有回路图中,分解所有存在回路的问题,让回路不交叉
    修改 删除 举报 引用 回复
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    发表于:2008-06-11 01:03:523楼 得分:0
    按照您所说的,如果有回路那么就是死循环了。
    修改 删除 举报 引用 回复
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    发表于:2008-06-11 01:09:184楼 得分:0
    那么请您画出,您所指的图的节点的定义是什么,边的定义是什么?
    修改 删除 举报 引用 回复
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    发表于:2008-06-11 01:12:225楼 得分:0
    如果你要反证明,请不要用代码,而是用自动机语言来描述。
    修改 删除 举报 引用 回复
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    发表于:2008-06-11 11:00:346楼 得分:5
    引用 2 楼 DarknessTM 的回复:
    进一步说,就是在 单源有向有回路图中,分解所有存在回路的问题,让回路不交叉

    这是求连通分支问题,是线性算法时间复杂度问题。
    当然你可能得出的部分回路不是单入口单出口的,甚至可以有多个入口和多个出口
    修改 删除 举报 引用 回复
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    发表于:2008-06-11 14:14:177楼 得分:0
    可以说就是一个程序流程图,用线和框表示的

    每个节点的目标节点最多为2个,最少为0个

    循环就是一个回路

    我不认为 goto 和while能简单的替换等价

    goto 可能是 while的循环体的最后一个节点,也可能是 do-while循环的while节点的一部分,也可能是 break,或者是 continue,或者不是直观的某种语句

    自动机语言 不懂- -
    修改 删除 举报 引用 回复
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    发表于:2008-06-11 14:59:368楼 得分:5
    感觉goto好像没法全变为while,或说是不可计算的,属于可计算性理论,不属于计算复杂性理论
    修改 删除 举报 引用 回复
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    发表于:2008-06-11 16:41:189楼 得分:0
    那如果goto不可被全部转化,哪么应该存在一个算法,在不支持goto的编程语言中无法使用?
    修改 删除 举报 引用 回复
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    发表于:2008-06-13 16:58:3810楼 得分:0
    顶一下
    修改 删除 举报 引用 回复

    网站简介广告服务网站地图帮助联系方式诚聘英才English 问题报告
    北京创新乐知广告有限公司 版权所有 京 ICP 证 070598 号
    世纪乐知(北京)网络技术有限公司 提供技术支持
    Copyright © 2000-2008, CSDN.NET, All Rights Reserved