新手perl问题求助

xiaoshengcaicai

楼主能不能把题目说得清楚一点，我比较有兴趣
@ARRAY 里面原来存的是什么...

[ 本帖最后由 xiaoshengcaicai 于 2007-2-8 21:08 编辑 ]

xiaoshengcaicai

原帖由 福瑞哈哥 于 2007-2-8 18:33 发表
不用语言如何描述算法？ 管他是真语言假语言总得有一种吧，perl还不错，语法简单，千万别用C玩算法。你可以去下载一本《Mastering Algorithms with Perl》，以前翻了一遍，还不错。

我认为大多数算法不用C的话，性能不高，算法效率狠低。。。

xiaoshengcaicai

现在有数组里的@array,经过如下转换:

$num=0;
while($num<=(@array/2)){
push @two_array, [@array[$num],@array[$num+1]];
     $num+=2;
}

里面的数据应该是：
a,b;
a,c;
b,e;
b,f;
c,e;
c,f;
b,c;
e,f;

@ARRAY里面是什么值？
$num=0;
while($num<=(@array/2)){
push @two_array, [@array[$num],@array[$num+1]];
     $num+=2;
}
这段算法是你写的？

xiaoshengcaicai

a,b;
a,c;
b,e;
b,f;
c,e;
c,f;
b,c;
e,f;

我对楼主题目的理解是：

有a,b,c,d,e,f 这些字母， a 到b， a到c有通路， b到e,b到f有通路，.....
现在要求任意2个字母之间的最短路径，并需要求出路径经过的字母

xiaoshengcaicai

任意两个字母之间一共有多少个不同的路线，每条路线经过了多少个字母：

最简单的方法就是先构造一个图， 用hash实现就可以，然后对所有的字母使用广度优先遍历

构造hash+ array ref的数据结构，用来存储路径

xiaoshengcaicai

哦。我有个问题
两个字母之间的通路， 中间的字母是不是不允许经过2次或以上

如果是这样的话，不需要用广度优先遍历，我刚才想到一个更好一点的算法

PS， 我也是菜鸟

[ 本帖最后由 xiaoshengcaicai 于 2007-2-8 22:08 编辑 ]

xiaoshengcaicai

1. 
   
2. 
   
3. #!perl
   
4. use strict;
   
5. 
   
6. use Data::Dumper;
   
7. use constant MAX_DEPTH => 100;
   
8. 
   
9. my @array = (
   
10.     ['a','b'],
    
11.     ['a','c'],
    
12.     ['b','e'],
    
13.     ['b','f'],
    
14.     ['c','e'],
    
15.     ['c','f'],
    
16.     ['b','c'],
    
17.     ['e','f'],
    
18. );
    
19. 
    
20. #make graph map
    
21. my $map = {};
    
22. for (@array) {
    
23.     push @{ $map->{$_->[0]} }, $_->[1];
    
24. }
    
25. 
    
26. #print Dumper($map);
    
27. 
    
28. #start
    
29. my @result = ();
    
30. my $depth = 1;
    
31. my @start_array = ();
    
32. 
    
33. for (keys %$map) {
    
34.     push @start_array, { start => $_, end => $_, visited => { $_ => 1} };
    
35. }
    
36. 
    
37. while ( $depth <= MAX_DEPTH  and @start_array > 0) {
    
38.     my @new_start_array = ();
    
39.     for my $to_expand (@start_array) {
    
40.         my $ra_can_expand = $map->{ $to_expand->{end} };
    
41.         for my $can_expand (@$ra_can_expand) {
    
42.             if (not $to_expand->{visited}->{$can_expand}) {
    
43.                 my %tmp_visited = %{ $to_expand->{visited} };
    
44.                 $tmp_visited{$can_expand} = 1;
    
45.                 my $new = {
    
46.                     start => $to_expand->{start},
    
47.                     end => $can_expand,
    
48.                     visited => \%tmp_visited,
    
49.                 };
    
50.                 push @new_start_array, $new;
    
51.                 push @result, $new;
    
52.             }
    
53.         }
    
54.     }
    
55.    
    
56.    
    
57.     @start_array = @new_start_array;
    
58.     $depth++;
    
59. }
    
60. 
    
61. print "the all result is \n";
    
62. for my $one (@result) {
    
63.     my $cost = ( keys %{ $one->{visited} } ) - 1;
    
64.     print $one->{start} . '-' . $one->{end} . " cost $cost\n";
    
65. }
    

复制代码

[ 本帖最后由 xiaoshengcaicai 于 2007-2-8 22:46 编辑 ]

xiaoshengcaicai

TO 楼上,可以放BLOG里面提供下载

PS,你觉得我的算法是否可行?有什么问题吗,昨天随手写的, 没细想

xiaoshengcaicai

刚上传了一把
http://blog.chinaunix.net/u/26905/showart_245044.html

这本书我没看过 >_<

不能保证链接一直有效,因为这本书大了点.以后没空间我会删掉它