请教各位一道题，是关于非线性问题的回溯法(backtracking)

问题描述

这是我研究生课程的一道题，暂时还没有思路，请各位前辈集思广益，先谢过了。如果x,y属于{0,n}^n,thenrecallthatDist(x,y)denotestheHammingdistance（汉明距离）betweenxandy.Anon-linearcodeoflengthnandminimumdistancedisasubsetC{0,1}^nsuchthatDist(x,y)大于等于dforallx,yinC.DenotebyA(n,d)themaximumnumberofn-tuplesinalength-nnon-linearcodeofminimumdistanced.(a)给出一种回溯法来计算A(n,d)(写出伪码）ImplementyouralgorithmandcomputeA(n,4)for4<n<8.ThecorrectvaluesforA(n,d)forsmallvaluesofnanddcanbefoundonthefollowingwebpage:http://www.win.tue.nl/~aeb/codes/binary-1.htmlForeachofyourtests,reporttheinputvalues,thefinalanswer,thenumberofbacktrackingnodesvisitedandCPUtime.Efficiencyandclaritycount.(b)ShowapseudocodeandgiveaprogramforKnuth'sAlgorithmtoestimatethesizeofthebacktrackingtreeforyouralgorithm.Usethismethodtoestimatethesizeofthebacktrackingtreefor4<n<11.Foreachvalueofn,chooseasuitablylargenumberPofprobesandshowtheestimateforatleast5valuesofnumberofprobesequallyspacedwithin[10,P].Doesthisestimateapproximateswellthenumberofnodesyoufoundinthepreviousquestion?(Ifnot,youmayhavetocheckcorrectnessofthecomputationsthereoryourestimationhere).(c)ShowapseudocodeandgiveaprogramforKnuth'sgeneralizedmethodtoestimatethesizeofA(n,4)forn=4,...,16.Theexactvaluescanbefoundonthewebsitegiveninparta.

时间： 2024-12-09 20:05:45

请教各位一道题，是关于非线性问题的回溯法(backtracking)的相关文章

请高手请教下一道题， 截取字符串相关！

问题描述 在程序主界面中有一个信息输入框,在输入完成后按回车键进行逻辑判断判断输入内容的长度.固定字符是否匹配匹配成功后把当前这条数据的背景颜色更改为绿色,否则提示相应信息并清除输入框中的内容 解决方案 解决方案二:例子:输入内容为:XYZ12长度为5,符合要求从开始位置1到结束位置3的字符串为XYZ,和数据库中定义的固定字符匹配成功解决方案三:用正则运算,时间不着急的话,看一下正则法则,看完你就知道了解决方案四:if(Regex.IsMatch(strText,@"^(XYZ|ABC|这里填写

摄像头-南京理工大学在线oj-1014,请问这道题用C++该怎么写

问题描述 南京理工大学在线oj-1014,请问这道题用C++该怎么写 问题: 当下,全国各地安全事故时有发生.各大高校对此很是重视.于是,高校安全设施也相应的增加了.其中摄像头的安装对安全稳定的重要性不言而喻.简而言之,为了实时监控某个区域的状况,我们要在某些区域安装摄像头. 为了使问题简单化,将某个区域看成是有若干方格组成的正方形,每堵墙占一个方格,墙会阻碍摄像头的摄像.也许是各大高校过于紧张,他们觉得安装的摄像头越多越好,然而他们又不希望过于浪费(即不希望两个或多个摄像头出现在同一行或同一列

UVa 165：Stamps, 连续邮资问题

题目链接: http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=108 类型: 回溯 原题: The government of Nova Mareterrania requires that various legal documents have stamps attached to them so that the government can derive revenue fro

面试题

微软面试题:地球上有多少个满足这样条件的点 站在地球上的某一点,向南走一公里,然后向东走一公里,最后向北走一公里,回到了原点.地球上有多少个满足这样条件的点? 北极点满足这个条件. 距离南极点很近的一个圈上也满足这个条件.在这个圆圈上,向南走一公里,然后向东走一公里恰好绕南极点一圈,向北走一公里回到原点. 所以地球上总共有无数点满足这个条件. 谷歌面试题:判断一个自然数是否是某个数的平方 判断一个自然数是否是某个数的平方.当然不能使用开方运算. 假设待判断的数字是 N.   方法1: 遍历从1到

2013级C++第5周(春)项目——用构造函数初始化

课程主页在:http://blog.csdn.net/sxhelijian/article/details/11890759,由课程主页,可以看到完整教学方案,所有参考解答   有同学总结:老二说用数组法做给了我思路,真是有兄弟,不孤单.做了这道题才发现以前没用数组法做的那个判断第几天的程序结果存在错误. 我评论:每个人身边都有一帮子兄弟.靠兄弟,就不用靠老师.兄弟总在身边,弟兄们一起长大! 还有,实践中感受到的,就是真正学习到的.在学习中,只有将直接的体验与老师的讲解.看过的书交融起来,才能真

ZOJ 1002 - Fire Net 的答案（回溯法）

       ---------------------------------------------------------------------------------------------------------------------------        严格来讲,此题并不算我做出来的.因为我在WA后忍不住搜索了这道题的网上资料,并在参考了"洞庭散人"的代码后AC的.          ----------------------------------------

请教各位算法大神，acm一道题：赋权无向图的最小权值遍历用什么算法（存在负权值）？

问题描述 请教各位算法大神,acm一道题:赋权无向图的最小权值遍历用什么算法(存在负权值)? 1C 如题,问题是这样的:有一赋权无向连通图,可以从任意一结点出发,求遍历所有结点的最小权值路线.结束点也是任意的,每个节点也没有访问次数的限制,但必须每个节点都要被访问到.,想问一下用什么算法呢? 解决方案 可以参考djstera算法,求最短路径~借鉴其中的标记功能,只不过结束状态标志是所有节点均已遍历. 解决方案二: 可以参考djstera算法,求最短路径~借鉴其中的标记功能,只不过结束状态标志是所

请教一下 oc 这道题 第三问怎么做 求解题思路

问题描述 请教一下 oc 这道题 第三问怎么做 求解题思路 // 1.// - 使用可变数组管理所有书籍(定义Book类,包含书名和价格)// - 数组可以添加.删除书籍对象// - 可以从数组中 根据书名查找书籍,并修改书籍的价格// - 展示所有书籍清单(书名和价格) Book *str1 = [Book bookWithName:@""DuZhe"" price:32]; Book *str2 = [Book bookWithName:@""

c++基础-请教 mooc上的一道题。。。

问题描述 请教 mooc上的一道题... 写一个程序完成以下命令: new id --新建一个指定编号为id的序列(id<10000) add id num --向编号为id的序列加入整数num merge id1 id2 --合并序列id1和id2中的数,并将id2清空 unique id --去掉序列id中重复的元素 out id --从小到大输出编号为id的序列中的元素,以空格隔开 输入 第一行一个数n,表示有多少个命令( n<＝200000).以后n行每行一个命令. 输出 按题目要求输