由买买提看人间百态

boards

本页内容为未名空间相应帖子的节选和存档,一周内的贴子最多显示50字,超过一周显示500字 访问原贴
Programming版 - 在写一个java小程序,求算法,10个包子答谢
相关主题
algorithm problemgoogle map 的问题
一个哈希表问题算法问题。
Check if the sum of two integers in an integer array eqauls to the given number 求助:多边形与锥体的相交问题 (转载)
面试题 -算法?请有图形编程经验的大牛给看看
两道M软件大公司的最新面世算法题 (转载)座位优化有多难?难于上青天?
哪种open source software 可以画这种地理分布图重新贴一次goodbug的要求
matlab 画图如何避免round off error
[合集] 怎样判断一条线段和一个园是否相交?我老再来出到题
相关话题的讨论汇总
话题: integer话题: curpath话题: list话题: 线段话题: graph
进入Programming版参与讨论
1 (共1页)
r*****e
发帖数: 4611
1
俺不是程序员,不过因为一些需要自己得写这个程序。现在遇到点困难,求帮忙。
问题是这样的,我有一系列的点。假设1000个吧。就称为点0,点1,。。。,点999
定义线段,连接某两个点,比如说某线段连接点20和点33.(线段是不碰中间那些点的
,就是说不经过21到32的点的)
连续的线段就形成通路,比如说线段a连接3到6,线段b连接6到9,线段c连接9到15,那
么abc就形成一个通路
现在我有一些线段,已经能够保证现存的每一个线段的前后都是存在连续的线段的,也
就是说不存在断线
现在我需要做的是列出所有从0点出发的10个线段以内的可能路径(就是说只需要列到
第10个线段即可)
谢谢
对了,补充一点,通路是不逆向走的,就是不会3到6,6到9,9又回到4什么的。只能向
数字更大的点走
S**I
发帖数: 15689
2
BFS

【在 r*****e 的大作中提到】
: 俺不是程序员,不过因为一些需要自己得写这个程序。现在遇到点困难,求帮忙。
: 问题是这样的,我有一系列的点。假设1000个吧。就称为点0,点1,。。。,点999
: 定义线段,连接某两个点,比如说某线段连接点20和点33.(线段是不碰中间那些点的
: ,就是说不经过21到32的点的)
: 连续的线段就形成通路,比如说线段a连接3到6,线段b连接6到9,线段c连接9到15,那
: 么abc就形成一个通路
: 现在我有一些线段,已经能够保证现存的每一个线段的前后都是存在连续的线段的,也
: 就是说不存在断线
: 现在我需要做的是列出所有从0点出发的10个线段以内的可能路径(就是说只需要列到
: 第10个线段即可)

l*****9
发帖数: 9501
3
数学版去
n*****t
发帖数: 22014
4
线段是已知的还是要计算?如果要计算怎么计算?线段 ab,a 是不是永远不大于 b?
这属于图的计算,是 CS 的基本功之一 ,数学问不着吧 。。。

【在 r*****e 的大作中提到】
: 俺不是程序员,不过因为一些需要自己得写这个程序。现在遇到点困难,求帮忙。
: 问题是这样的,我有一系列的点。假设1000个吧。就称为点0,点1,。。。,点999
: 定义线段,连接某两个点,比如说某线段连接点20和点33.(线段是不碰中间那些点的
: ,就是说不经过21到32的点的)
: 连续的线段就形成通路,比如说线段a连接3到6,线段b连接6到9,线段c连接9到15,那
: 么abc就形成一个通路
: 现在我有一些线段,已经能够保证现存的每一个线段的前后都是存在连续的线段的,也
: 就是说不存在断线
: 现在我需要做的是列出所有从0点出发的10个线段以内的可能路径(就是说只需要列到
: 第10个线段即可)

r*****e
发帖数: 4611
5
线段是已知的,线段包含的信息就是start和end,start永远小于end
这个程序输入就是一个线段的数组
输出的话应该是一个线段的数组的数组

【在 n*****t 的大作中提到】
: 线段是已知的还是要计算?如果要计算怎么计算?线段 ab,a 是不是永远不大于 b?
: 这属于图的计算,是 CS 的基本功之一 ,数学问不着吧 。。。

b*******s
发帖数: 5216
6
最简单的就是bfs

【在 r*****e 的大作中提到】
: 俺不是程序员,不过因为一些需要自己得写这个程序。现在遇到点困难,求帮忙。
: 问题是这样的,我有一系列的点。假设1000个吧。就称为点0,点1,。。。,点999
: 定义线段,连接某两个点,比如说某线段连接点20和点33.(线段是不碰中间那些点的
: ,就是说不经过21到32的点的)
: 连续的线段就形成通路,比如说线段a连接3到6,线段b连接6到9,线段c连接9到15,那
: 么abc就形成一个通路
: 现在我有一些线段,已经能够保证现存的每一个线段的前后都是存在连续的线段的,也
: 就是说不存在断线
: 现在我需要做的是列出所有从0点出发的10个线段以内的可能路径(就是说只需要列到
: 第10个线段即可)

n*****t
发帖数: 22014
7
多叉树的遍历,俺不会 java,你看看这个有没有用
http://blog.csdn.net/shanzhizi/article/details/13022749

【在 r*****e 的大作中提到】
: 线段是已知的,线段包含的信息就是start和end,start永远小于end
: 这个程序输入就是一个线段的数组
: 输出的话应该是一个线段的数组的数组

r*****e
发帖数: 4611
8
有一点点区别,因为多叉树好像每个节点只有一个parent节点。我的情况是允许多个
parent节点的。
说错了莫怪
iteration的话记录数组有点麻烦,我最后自己想出了个办法。
就是建立个通路的数组。先记录0点出发所有线段,每段建一个通路存入数组。
然后就用一个while循环不断遍历这个数组,根据数组最后一个节点的连接段情况增长
和添加新通路,如果某通路有10段或者连到999了就标记为完成。这样直到数组中所有
的通路都是完成了的才停止循环。这样最后就是所有通路的列表了。

【在 n*****t 的大作中提到】
: 多叉树的遍历,俺不会 java,你看看这个有没有用
: http://blog.csdn.net/shanzhizi/article/details/13022749

n*****t
发帖数: 22014
9
你这个树不关心父节点,而且不会形成回路死循环,每个父节点用数组记录子节点就行
了,遍历子节点算法上递归很简单。
你的算法我没太明白 。。。会不会漏掉?

【在 r*****e 的大作中提到】
: 有一点点区别,因为多叉树好像每个节点只有一个parent节点。我的情况是允许多个
: parent节点的。
: 说错了莫怪
: iteration的话记录数组有点麻烦,我最后自己想出了个办法。
: 就是建立个通路的数组。先记录0点出发所有线段,每段建一个通路存入数组。
: 然后就用一个while循环不断遍历这个数组,根据数组最后一个节点的连接段情况增长
: 和添加新通路,如果某通路有10段或者连到999了就标记为完成。这样直到数组中所有
: 的通路都是完成了的才停止循环。这样最后就是所有通路的列表了。

r*****e
发帖数: 4611
10
我想过一下,遍历一遍也许不难,但是我想不明白怎样能把通路经过全部分别保存下来。
我说的那种办法我觉得应该不会漏吧。说白了就是遇到岔路就把岔路保存下来。

【在 n*****t 的大作中提到】
: 你这个树不关心父节点,而且不会形成回路死循环,每个父节点用数组记录子节点就行
: 了,遍历子节点算法上递归很简单。
: 你的算法我没太明白 。。。会不会漏掉?

相关主题
哪种open source software 可以画这种地理分布图google map 的问题
matlab 画图算法问题。
[合集] 怎样判断一条线段和一个园是否相交?求助:多边形与锥体的相交问题 (转载)
进入Programming版参与讨论
n*****t
发帖数: 22014
11
最脑残的办法,所有路径用 4 位数字打印每个节点编号,然后把长度超过 40 的行都
删了,哈哈

来。

【在 r*****e 的大作中提到】
: 我想过一下,遍历一遍也许不难,但是我想不明白怎样能把通路经过全部分别保存下来。
: 我说的那种办法我觉得应该不会漏吧。说白了就是遇到岔路就把岔路保存下来。

m**********e
发帖数: 12525
12
这个模型数学上叫random walk:
http://en.wikipedia.org/wiki/Random_walk
可以假设0,1,...10000是一个往下的台阶的编号,0台阶最高,势能最大,10000最低,
势能最低,一个球从0往下滚,可以滚0-1-3-7-....,也可以滚0-3-9-100-....,但是由
于能量守恒的原因,球不可能往上滚,这样的模型便符合你的要求
所以要穷尽10步就变得很简单的事情了,0取定后,产生随机数,根据运到方程随机选取
势能小的下一个台阶,滚下去.滚完后记录结果.然后再次循环
这个程序很简单,不要担心会产生遗漏,因为根据各态历经性,数学上遗漏可能是0.

【在 r*****e 的大作中提到】
: 俺不是程序员,不过因为一些需要自己得写这个程序。现在遇到点困难,求帮忙。
: 问题是这样的,我有一系列的点。假设1000个吧。就称为点0,点1,。。。,点999
: 定义线段,连接某两个点,比如说某线段连接点20和点33.(线段是不碰中间那些点的
: ,就是说不经过21到32的点的)
: 连续的线段就形成通路,比如说线段a连接3到6,线段b连接6到9,线段c连接9到15,那
: 么abc就形成一个通路
: 现在我有一些线段,已经能够保证现存的每一个线段的前后都是存在连续的线段的,也
: 就是说不存在断线
: 现在我需要做的是列出所有从0点出发的10个线段以内的可能路径(就是说只需要列到
: 第10个线段即可)

k********e
发帖数: 702
13
这个题很简单。矩阵运算就可以出来。图论基本知识。矩阵好处是可以无限scale。任
你数亿个路线,我map redunce在数万个机器上跑 一圈,就解决了。
解题要注意多用当前流行的术语唬人。不要抱着几十年前的技术不放。虽然好,但是不
唬人也没用。
m*******t
发帖数: 1060
14
A simple solution as shown below.
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
public class PathFinder {
private static void printPath(List path) {
for (int i = 0; i < path.size(); i++) {
System.out.format("%2d", path.get(i));
if (i != path.size() - 1)
System.out.print("->");
else
System.out.println();
}
}
private boolean shouldSkip(List curPath, Integer pos) {
if (curPath == null)
return false;

for (Integer i : curPath) {
if (pos <= i) {
return true;
}
}

return false;
}

public void findPaths(Map> graph, int curPos,
List curPath, int expectedPathLen) {
curPath.add(curPos);
if (curPath.size() == expectedPathLen) {
printPath(curPath);
} else {
List children = graph.get(curPos);
if (children != null) {
for (Integer i : children) {
if (this.shouldSkip(curPath, i))
continue;
findPaths(graph, i, curPath, expectedPathLen);
}
}
}
curPath.remove(curPath.size() - 1);
}
public static void main(String[] args) {
Map> graph = new HashMap Integer>>();
// construct a graph
// 0 -> 1 -> 2 -> 3 ->4 ->5 ->6 ->7 ->8 -> 9 ->10 ->11
// 0 -> 2
// 1 -> 5
// 4 -> 6
// 7 -> 6 (a backward path)
for (int i = 0; i <= 10; i++) {
graph.put(i, new ArrayList());
graph.get(i).add(i + 1);
}
graph.get(0).add(2);
graph.get(1).add(5);
graph.get(4).add(6);
graph.get(7).add(6);
// a variable used to record current path
List curPath = new ArrayList();
new PathFinder().findPaths(graph, 0, curPath, 10);
// output
// 0-> 1-> 2-> 3-> 4-> 5-> 6-> 7-> 8-> 9
// 0-> 1-> 2-> 3-> 4-> 6-> 7-> 8-> 9->10
// 0-> 2-> 3-> 4-> 5-> 6-> 7-> 8-> 9->10
// 0-> 2-> 3-> 4-> 6-> 7-> 8-> 9->10->11
}
}
b***i
发帖数: 3043
15
维持一个广度优先的对列,保持头,尾,和当前层次.
从头开始到尾,把队列中每个点的下一个点输入新的尾,这样增加下一个层次的所有点.
重复即可.第一次只有一个点.

【在 r*****e 的大作中提到】
: 俺不是程序员,不过因为一些需要自己得写这个程序。现在遇到点困难,求帮忙。
: 问题是这样的,我有一系列的点。假设1000个吧。就称为点0,点1,。。。,点999
: 定义线段,连接某两个点,比如说某线段连接点20和点33.(线段是不碰中间那些点的
: ,就是说不经过21到32的点的)
: 连续的线段就形成通路,比如说线段a连接3到6,线段b连接6到9,线段c连接9到15,那
: 么abc就形成一个通路
: 现在我有一些线段,已经能够保证现存的每一个线段的前后都是存在连续的线段的,也
: 就是说不存在断线
: 现在我需要做的是列出所有从0点出发的10个线段以内的可能路径(就是说只需要列到
: 第10个线段即可)

1 (共1页)
进入Programming版参与讨论
相关主题
我老再来出到题两道M软件大公司的最新面世算法题 (转载)
关于数组动态分配的疑问???哪种open source software 可以画这种地理分布图
Re: 定义数组上限matlab 画图
[转载] CS Algorithm Interview question[合集] 怎样判断一条线段和一个园是否相交?
algorithm problemgoogle map 的问题
一个哈希表问题算法问题。
Check if the sum of two integers in an integer array eqauls to the given number 求助:多边形与锥体的相交问题 (转载)
面试题 -算法?请有图形编程经验的大牛给看看
相关话题的讨论汇总
话题: integer话题: curpath话题: list话题: 线段话题: graph