📣 黑五价提前开抢|VIP一年通行证5折,蓝莓、Offer多多同步特惠
楼主: PincessR
跳转到指定楼层
上一主题 下一主题
收起左侧

[入门|算法|数据结构] 算法可第三周的编程作业题讨论

🔗
麻倉枼 2014-5-24 23:24:20 | 只看该作者
全局:
breezet 发表于 2014-5-24 08:43
好吧,我那个所谓的equation大概只相当于对问题建模

这种技能我是很难驾驭啊
回复

使用道具 举报

🔗
breezet 2014-5-25 08:46:10 | 只看该作者
全局:
麻倉枼 发表于 2014-5-24 23:24
这种技能我是很难驾驭啊

感觉这个还是跟数学关系比较大。。。
回复

使用道具 举报

🔗
麻倉枼 2014-5-25 13:14:38 | 只看该作者
全局:
breezet 发表于 2014-5-24 19:46
感觉这个还是跟数学关系比较大。。。

是的,周一开始攻略程序,话说我已经忘记上这堂课的初衷了,记得一开始是为了以后工作面试而准备的。。可是现在不记得了
回复

使用道具 举报

🔗
zladfqrts 2014-5-26 11:54:27 | 只看该作者
全局:
我第一个版本也是20,看了半天不知道哪里错,一气之下换个思路从头写,得出正确答案,回头看第一个版本,至今不知道哪里错
回复

使用道具 举报

🔗
麻倉枼 2014-5-29 17:48:09 | 只看该作者
全局:
本帖最后由 麻倉枼 于 2014-5-29 05:23 编辑
breezet 发表于 2014-5-21 21:00
我感觉问题可能出在把其他点的连接也由node2改成node1的部分,如果其他点之前已经跟node1相连的话这样似乎 ...

关于编程题真心跪了,目前答案最少的可以得到1。。可是答案还是错呀。。我都不知道debug了多少次,请问你能给点建议吗?

目前状况是:0. randomly create mainVertex and subVertex; if they are not the same, proceed the following:

1. 把subVertex 的Edge 全加进mainVertex Edge List;

2. remove duplicate mainVertex from the mainVertex Edge List;

3. remove all subVertex from every Edge List in the graph;

4. validate if duplicate mainVertex is removed and all subVertecies are removed;

5. if yes, then count each subVertex from the mainVertex EdgeList and count the number of mainVertecies from each subVertex's Edge List, and then modify each subVertex Edge List until it got the same number of mainVertex as the number of subVertex in the mainVertex Edge List;

6. repeat until the graph contains only two Vertecies.
回复

使用道具 举报

🔗
breezet 2014-5-29 18:16:15 | 只看该作者
全局:
麻倉枼 发表于 2014-5-29 17:48
关于编程题真心跪了,目前答案最少的可以得到1。。可是答案还是错呀。。我都不知道debug了多少次,请问你 ...

I think your ideas are not so clear, maybe it should not be so complicated. I run it as follows.

0. Create a Vertex structure which contains vertex list and edge list, originally every Vertex contains 1 vertex and some edges
1. Randomly choose a vertex A to merge, and randomly choose a vertex B in its edge list
2. Merge the vertex B into A, so A's vertex list now contains A and B, and merge B's edge list into A's, delete B
3. Loop around A's new edge list, find the edge connected to A or B and delete
4. Repeat until the graph contains only 2 vertices
回复

使用道具 举报

🔗
麻倉枼 2014-5-29 18:25:51 | 只看该作者
全局:
breezet 发表于 2014-5-29 05:16
I think your ideas are not so clear, maybe it should not be so complicated. I run it as follows.
...

一个问题,刚刚看文档发现的,就是A这个点每一次loop都会换么?我意思说目前我的想法是每一次Loop
A和B都会randomized generated,而我看到的好像A is a pivot? only B will be randomized generated every loop?
回复

使用道具 举报

🔗
breezet 2014-5-29 20:45:43 | 只看该作者
全局:
麻倉枼 发表于 2014-5-29 18:25
一个问题,刚刚看文档发现的,就是A这个点每一次loop都会换么?我意思说目前我的想法是每一次Loop
A和B ...

是的,是每一次都会换的
回复

使用道具 举报

🔗
麻倉枼 2014-5-30 00:15:44 | 只看该作者
全局:
本帖最后由 麻倉枼 于 2014-5-29 20:57 编辑
breezet 发表于 2014-5-29 07:45
是的,是每一次都会换的

我的程序好像跪了,一个小graph的话还是OK的,但是要运行很多遍才能找到min cut (在知道真正答案的情况下),

但是作业上面那个真心各种不解。。现在一个很大的bug实在找不出原因来。。while loop 和 for loop各种测试了都还是不行,这个bug是这样的:

在程序某部分我要把mainVertex的edge list整理一下,整理的内容为查看里面是否存在self loop,意思说list里面会有mainVertex出现,如果出现的话就把它删掉。。

然后bug就是如果我运行作业的文件的话,最后的两个vertex 的size不一致,原因就是self loop出现了。。

于是我干脆就写了一个Loop,把graph里面每一个edge list和每一个vertex分别检查一遍,反正无伤大雅。。
实在不知道怎么查bug了,其中最有可能出现问题是这部分可以看看吗?逻辑上的问题。。

前提:
1. graph是用 hashMap的;
2. Long currentVertex = 0L;
3. ArrayList<Long> currentEdgeList = null;

// remove every duplicate vertex from this current vertex edge list;
                                while(i < graph.size()){
                                       
                                        currentVertex = keyList.get(i);
                                        currentEdgeList = graph.get(currentVertex);

                                        int w = 0;
                                        while(w < currentEdgeList.size()){      //这里进去后      *** 有时候这里连进去都没进去,但出来后能查到size的确存在的,list还是有内容
                                                if(currentEdgeList.get(w) == currentVertex){    //这里压根没检查     ***然后这里压根没跑
                                                        graph.get(currentVertex).remove(w);
                                                        
                                                        System.out.println("CurrentVertex = " + currentVertex);
                                                        System.out.println("CurrentVertex Edge List = " + graph.get(currentVertex) + "\n");
                                                        
                                                        w = 0;
                                                        currentEdgeList = graph.get(currentVertex);
                                                }
                                                else{
                                                        w++;                    ***  这里却一直有Loop
                                                }
                                        }
                                       
                                        //System.out.println("In duplicte vertex while loop!!!! "  + "\n");
                                        i++;                 ***这里也有loop,最终数字和graph.size()一致
                                }


真心被压倒了,两天没睡觉了。。今天无论如何都睡一下,反正您都给了答案了。。


/***********************  更新 ***************************/
终于找到这个逆天的bug了!!
低级错误但是很有杀伤力,基础不好的人基本上就是要像我一样熬夜去吧。。。
答案就是Long, 不是long。。。。@~@
然后。。。让有缘人去解读这个bug。。。
回复

使用道具 举报

🔗
breezet 2014-5-30 09:21:01 | 只看该作者
全局:
麻倉枼 发表于 2014-5-30 00:15
我的程序好像跪了,一个小graph的话还是OK的,但是要运行很多遍才能找到min cut (在知道真正答案的情况 ...

其实我觉得你在15楼提到的整体思路不是很清楚,容易带来问题。。。如果单纯的看这一部分,倒没有什么问题。运行很多遍才找到也是正常的,我的一般运行40遍。

我觉得你的思路问题出在3和5上,先删掉了所有subVertex后面又modify each subVertex Edge List,虽然我不能很清楚的假设一种情况,但是直观上看这样会改变graph的结构,而且这种方法有点不“美”,我还是建议你不要删掉subVertex再modify而是直接用我提到的merge的办法,这样不需要改其他vertex的Edge
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 注册账号
隐私提醒:
  • ☑ 禁止发布广告,拉群,贴个人联系方式:找人请去🔗同学同事飞友,拉群请去🔗拉群结伴,广告请去🔗跳蚤市场,和 🔗租房广告|找室友
  • ☑ 论坛内容在发帖 30 分钟内可以编辑,过后则不能删帖。为防止被骚扰甚至人肉,不要公开留微信等联系方式,如有需求请以论坛私信方式发送。
  • ☑ 干货版块可免费使用 🔗超级匿名:面经(美国面经、中国面经、数科面经、PM面经),抖包袱(美国、中国)和录取汇报、定位选校版
  • ☑ 查阅全站 🔗各种匿名方法

本版积分规则

>
快速回复 返回顶部 返回列表