编程C,C ++,Java,PHP,Ruby,图灵,VB
计算机科学加拿大 
编程C,C ++,Java,PHP,Ruby,图灵,VB  

用户名:    Password: 
  登记 登记    
 2004年CCC S5解决方案与3d中奖规则麻烦
指数 -> 竞赛
转到页面 1, 2   下一个
查看上一个主题 可打印的版本下载主题订阅本主题私人信息刷新页面 查看下一个主题
作者 信息
Zylum.




 邮政 发布: 2004年8月12日星期六1:59  帖子主题:

我很无聊,所以我尝试解决S5使用Memoization,因为网格可以100到100到100,并且飞机旧递归将花太长而无法解决问题。所以我首先编写了我的递归解决方案,但是当我尝试实现它失败的3d中奖规则表....

没有核对:
代码:
S5类{
       静态字符串[]映射= { "      1",
                                                        "  5    ",
                                                        "  *    ",
                                                        "  7    ",
                                                        "       " };
       静态int宽度=映射[0] .Length();
       静态int height = map.length;
       公共静态空白主(String[] args) {
                       long time1 = system.currenttimemillis();
                        int ret = bestPath(1, 1, 0, 1);
                       long time2 = system.currenttimemillis();
                        System.out.println(ret + " TIME: " + (time2 - time1));
        }
        static int bestPath(int x,int y,int金额,int dir) {
                if (x < 1 || x > width || y < 1 || y >高度||地图[y-1] .charat(x-1) == '*')return-integer.max_value;
                if (map[y-1].charAt(x-1) - '0' >= 0 && map[y-1].charAt(x-1) - '0'<= 9)数量+ = MAP [Y-1] .Charat(x-1) - '0';
                if (x == width && y == 1) return amount;
                return Math.max(Math.max(bestPath(x+1, y, amount, 0),dir == 1? -integer.max_value.: bestPath(x, y-1, amount, -1)),dir == -1? -integer.max_value.: bestPath(x, y+1, amount, 1));
        }
}


用备忘:
代码:
S5类{
   静态字符串[]映射= {   "      1",
                     "  5    ",
                     "  *    ",
                     "  7    ",
                     "       " };
   静态int宽度=映射[0] .Length();
   静态int height = map.length;
   静态int [] [] [] []3d中奖规则= new int [width] [height] [3];
   公共静态空白主(String[] args) {
              //get initial time
         long time1 = system.currenttimemillis();
         //初始化3d中奖规则表
         for (int i = 0; i < width; i++) for (int j = 0; j < height; j++) for (int k = 0; k < 3; k++)3d中奖规则[i] [j] [k] = -integer.max_value;
         //find best path
         int ret = bestPath(1, 1, 0, 1);
         //get final time
         long time2 = system.currenttimemillis();
         //输出最佳路径和运行时间
         System.out.println(ret + " TIME: " + (time2 - time1));
   }
   static int bestPath(int x,int y,int金额,int dir) {
         //检查坐标是否在网格中
      if (x < 1 || x > width || y < 1 || y >高度||地图[y-1] .charat(x-1) == '*')return-integer.max_value;
     //检查3d中奖规则表是否有当前位置的答案
      if (3d中奖规则[x-1] [y-1] [dir + 1]> -Integer.MAX_VALUE)返回3d中奖规则[x-1] [y-1] [dir + 1];
     //如果当前位置是整数,请更新金额
      if (map[y-1].charAt(x-1) - '0' >= 0 && map[y-1].charAt(x-1) - '0'<= 9)数量+ = MAP [Y-1] .Charat(x-1) - '0';
     //如果当前位置是最终位置,返回金额
      if (x == width && y == 1) return amount;
     //检查您可以去哪个方向的同时更新3d中奖规则表(up/down)
     3d中奖规则[x-1] [y-1] [dir + 1] = math.max(Math.max(bestPath(x+1, y, amount, 0),dir == 1? -integer.max_value.: bestPath(x, y-1, amount, -1)),dir == -1? -integer.max_value.: bestPath(x, y+1, amount, 1));
      //return best path
     返回3d中奖规则[x-1] [y-1] [dir + 1];
   }
}

在我使用答案的情况下应该是8

任何帮助实现会很棒
赞助
赞助
 赞助
 赞助
WTD.




 邮政 发布: THU 8月12日,2004年7:20 PM  帖子主题:(没有主题)

感谢您证明可以写入混淆的Java。  眨眼

清理它,所以我可以弄清楚它实际上是什么。
Bugzpodder.




 邮政 发布: 星期四,2004年8月12日上午9:17  帖子主题:(没有主题)

在比赛中,我想用封面,但我最终使用DP,但我不记得原因。可能存在一些有缺陷的逻辑(虽然我现在无法想到任何问题)虽然在理论上,如果不是所有DP问题,可以使用备忘,反之亦然。

在您的计划中,为什么在致电最佳路径后初始化3d中奖规则?
此外,由于3d中奖规则存储了最佳金额,那么您不应该将金额保持为变量右键?
Zylum.




 邮政 发布: THU 8月12日,2004年11:44 PM  帖子主题:(没有主题)

WTD. >代码在论坛视图中看起来很糟糕,请尝试将其复制到您编辑器。此外,如果您仍然不遵循,我也更新了“有3d中奖规则”版本以包括注释。

bug>哎呀,我没有注意到在调用函数后初始化3d中奖规则表。虽然Integer仍然大于未初始化的整数变量,但它并不重要。
WTD.




 邮政 发布: 星期五2004年8月13日12:33 AM  帖子主题:(没有主题)

您需要做的主要内容是将许多代码分解为方法。喜欢检查是否x和y在适当的范围内。

能够说:

代码:
if (xInBounds(x)) { ... }


而不是:

代码:
if (x < 1 || x > width) { ... }


会使你的代码更可读。
Bugzpodder.




 邮政 发布: 星期五2004年8月13日5:34 AM  帖子主题:(没有主题)

Zylum. ,我假设你已经修复了初始化错误,但它仍然没有工作(我不确定Java如何初始化,如果你说它不重要......)
我提到的第二个点怎么样......说你说你需要取出数量变量,但我不认为你没有正确更新。看上去
WTD.




 邮政 发布: 2004年8月16日12:28 AM  帖子主题:(没有主题)

您提到递归解决方案对于大型数据集是不切实际的......

您可以以任何语言实现,或者比赛是否将提交给Java?

我问,因为存在更多的语言,对递归更优化。如果您可以提供对问题的详细说明,我会在O'Caml中重新实现O'Caml。即使CCC示例也没有大部分解释实际所需的内容。
Bugzpodder.




 邮政 发布: 2004年8月16日7:11 AM  帖子主题:(没有主题)

您可以使用阶段1的任何内容......对于阶段2,您必须使用C / C ++ / Pascal,以及可能取决于年份的Java
赞助
赞助
 赞助
 赞助
WTD.




 邮政 发布: 2004年8月18日星期三下午2:20  帖子主题:(没有主题)

啊。这是一个耻辱,你必须使用其中一种语言。

使用功能语言,您可以获得令人难以置信的加速。例如,考虑这个特殊问题。功能语言可以自由地为您提供“Memoization”,而无需编写额外的代码。

疯了你说?

并不真地。

java. ,C ++等的原因不能给你这是存在副作用。不能保证使用这些语言中相同参数的函数具有相同的结果。在许多功能语言中,可以假设这一点。

如果我有一个名为my_map的地图,它占用了行号和列号...

代码:
best_path my_map 3 0


假设my_map保持不变,总是返回同样的事情。因此,编译器可以缓存该表达式的结果。任何未来的表达式都将简单地被恒定值替换。与您所写的忆解示例一样,即使我们使用递归解决方案,任何给定的起始点的最佳路径也只会计算一次。
WTD.




 邮政 发布: 2004年8月18日星期三:下午9:39  帖子主题:(没有主题)

毕竟这谈论O'Caml的解决方案有多伟大,我应该提供一个。  微笑

是的,语法突出显示,它看起来更好,特别是因为o'caml有...鲁棒...语法。突出显示可用于许多编辑器,包括Windows上的Vim和​​TextPad等流行的。

所有它需要的是一些逻辑,以便从文件中读取地图。

代码:
模块S5 =
        struct
               模块Stringutils =.
                        struct
                               让rec string_chars s =
                                        try (String.get s 0) :: string_chars (String.sub s 1 ((String.length s) - 1))
                                        with _ -> [];;
                        end
                               
                let map = ["   1";" 5  ";" *  ";" 7  "]
               
               让rec make_map =函数
                        [] -> []
                        | first_row::others -> (stringutils.string_chars first_row.) :: make_map others

               让get_map_height地图=
                        List.length map
                       
               让get_map_width映射=
                        try List.length (List.hd map)
                        with Failure "hd" -> 0

               out_of_grid
               exp_rof_run
               
               让get_map_cell映射行列=
                        try List.nth (List.nth map row) column
                        with _ -> raise Out_of_grid
                               
               让in_map映射行列=
                       尝试让临时= get_map_cell映射行列
                        with Out_of_grid -> false
                       
               让up_move_possible行=
                        row > 0
                       
                let right_move_possible地图列 =
                       让宽度= get_map_width映射
                                column < (width - 1)
                               
               让acceptable_int i =
                        i >= 0 && i <= 9
                       
               让filter_cell_char_to_int cell =
                        let cell_int = (int_of_char cell) - (int_of_char '0') in
                               如果可接受_int cell_int然后cell_int
                               否则如果cell ='*'则为-1
                                else 0
                               
               让rec best_path映射行列=
                       让current_cell = get_map_cell映射行列
                               让current_int_value = filter_cell_char_to_int current_cell
                                       如果current_cell ='*'那么
                                                0
                                        else if (up_move_possible row) && (right_move_possible地图列) then
                                               让up_cell = get_map_cell映射(row - 1) column and
                                               right_cell = get_map_cell映射行(column + 1) in
                                                       让up_cell_int_value = filter_cell_char_to_int up_cell和
                                                       right_cell_int_value = filter_cell_char_to_int right_cell
                                                               如果up_cell_int_value.>那么= right_cell_int_value
                                                                       current_int_value + best_path映射(row - 1) column                                               
                                                                else
                                                                       current_int_value + best_path映射row (column + 1)
                                       否则如果UP_MOVE_POSSIBLE行那么
                                               current_int_value + best_path映射(row - 1) column
                                        else if right_move_possible地图列 then
                                               current_int_value + best_path映射row (column + 1)
                                        else
                                                current_int_value
        end

打开S5

让_ =
       让std_map = s5.make_map s5.map和
       start_row = 3和start_column = 0
               让这个_best_path = s5.best_path std_map start_row start_column
                       print_int this_best_path;
                        print_newline ()
WTD.




 邮政 发布: 2004年8月18日星期三10:28 PM  帖子主题:(没有主题)

附加是我写的解决方案允许输入文件。我向源文件添加了一个.txt扩展,以便在此发布,因为“.ml”似乎被阻止。

使用相同的简单测试:

代码:
   1
 5 
 * 
 7 


它给出了8件的预期答案。

使用更复杂的示例:

代码:
       8                  9
      *5                4 
      3            2     7
 1         9               
              **  *       
              9           
         5  6       3 2   
1   4  98                 
 1                         
                     9     
                  5****   
     **    4 5 67         
     *                     

   3 *       9 1 2 3     


它给了我19.我没有工作参考实施来比较这一点,所以我会问有人是否可以测试它。

然而,我注意到的第一件事是,即使第二个例子中的递归程度远远大,也似乎都采取了几乎相同的时间,即使是限制潜在路径的所有星号。



s5.ml.txt.
 Description:

下载
 Filename:  s5.ml.txt
 Filesize:  3.65 KB
 Downloaded:  229 Time(s)

WTD.




 邮政 发布: 2004年8月18日星期三晚10:49下午  帖子主题:(没有主题)

为了有趣,我刚刚在文件990线上播放它,长达592个字符,由这个小红宝石程序随机生成:

代码:
科尔斯 = rand 1000
行 = rand 1000

def rand_line.(len)
        Array.new(len) {
                case rand(10)
                        when 5, 6 then rand(9) + 1
                        when 0 then "*"
                        else " "
                end
        }.join
结尾

放大array.new.(rows) { rand_line(cols) }.join("\n")


它必须考虑这一个,但计算答案(无论是正确的吗,我不知道,虽然它应该是)一两分之一(我没有能够正确的基准测试)。

该大小的文件将占用Java示例多久了? (我不是流行的。如果标准的Java对这种递归足够强大,我真的很好奇。)
Bugzpodder.




 邮政 发布: 2004年8月18日星期三11:03 PM  帖子主题:(没有主题)

附上您在此处使用的文件,我将乐意使用Java编译我的解决方案,并使用我的PIII 660MHz蜗牛掌握XP的执行时间
WTD.




 邮政 发布: 2004年8月18日星期三11:11下午  帖子主题:(没有主题)

见附件。

哦,我用O'Caml 3.07 + 2在AMD Athlon XP 1800+上运行了这个例子,拥有256MB的RAM,80GB HD和Windows 2000 Professional。考虑到计算能力的差异,我会给你的一些余地。



Input4.txt.
 Description:

下载
 Filename:  input4.txt
 Filesize:  573.31 KB
 Downloaded:  226 Time(s)

WTD.




 邮政 发布: 2004年8月19日星期二2:44  帖子主题:(没有主题)

你知道,我很确定我的算法有一个错误。努力纠正它。

编辑:包含正确的版本,以及sys.time,它输出进程以秒为单位运行的时间。我在A. 非常 慢速机器,所以我明天会对这一巨大的文件进行测试。

可能还鞭打一个C版本以进行比较。



s5.ml.txt.
 Description:

下载
 Filename:  s5.ml.txt
 Filesize:  3.31 KB
 Downloaded:  235 Time(s)

从上一个显示帖子:   
    指数 -> 竞赛
查看上一个主题 告诉一个朋友可打印的版本下载主题订阅本主题私人信息刷新页面 查看下一个主题

12  [ 18 Posts ]
转到页面 1, 2   下一个
跳到:    


Style:  
搜索: