免费注册 查看新帖 |

Chinaunix

  平台 论坛 博客 文库
最近访问板块 发新帖
查看: 47586 | 回复: 4

[其他] Project Euler - 011 [复制链接]

论坛徽章:
4
白羊座
日期:2013-11-05 10:26:09冥斗士
日期:2015-11-17 14:19:55白银圣斗士
日期:2015-11-17 15:13:0815-16赛季CBA联赛之新疆
日期:2016-04-01 09:10:58
发表于 2015-09-29 11:16 |显示全部楼层
本帖最后由 icymirror 于 2015-09-29 11:18 编辑

Problem 011:
In the 20×20 grid below, four numbers along a diagonal line have been marked in red.

08 02 22 97 38 15 00 40 00 75 04 05 07 78 52 12 50 77 91 08
49 49 99 40 17 81 18 57 60 87 17 40 98 43 69 48 04 56 62 00
81 49 31 73 55 79 14 29 93 71 40 67 53 88 30 03 49 13 36 65
52 70 95 23 04 60 11 42 69 24 68 56 01 32 56 71 37 02 36 91
22 31 16 71 51 67 63 89 41 92 36 54 22 40 40 28 66 33 13 80
24 47 32 60 99 03 45 02 44 75 33 53 78 36 84 20 35 17 12 50
32 98 81 28 64 23 67 10 26 38 40 67 59 54 70 66 18 38 64 70
67 26 20 68 02 62 12 20 95 63 94 39 63 08 40 91 66 49 94 21
24 55 58 05 66 73 99 26 97 17 78 78 96 83 14 88 34 89 63 72
21 36 23 09 75 00 76 44 20 45 35 14 00 61 33 97 34 31 33 95
78 17 53 28 22 75 31 67 15 94 03 80 04 62 16 14 09 53 56 92
16 39 05 42 96 35 31 47 55 58 88 24 00 17 54 24 36 29 85 57
86 56 00 48 35 71 89 07 05 44 44 37 44 60 21 58 51 54 17 58
19 80 81 68 05 94 47 69 28 73 92 13 86 52 17 77 04 89 55 40
04 52 08 83 97 35 99 16 07 97 57 32 16 26 26 79 33 27 98 66
88 36 68 87 57 62 20 72 03 46 33 67 46 55 12 32 63 93 53 69
04 42 16 73 38 25 39 11 24 94 72 18 08 46 29 32 40 62 76 36
20 69 36 41 72 30 23 88 34 62 99 69 82 67 59 85 74 04 36 16
20 73 35 29 78 31 90 01 74 31 49 71 48 86 81 16 23 57 05 54
01 70 54 71 83 51 54 69 16 92 33 48 61 43 52 01 89 19 67 48

The product of these numbers is 26 × 63 × 78 × 14 = 1788696.
What is the greatest product of four adjacent numbers in the same direction (up, down, left, right, or diagonally) in the 20×20 grid?

问题11:
在下面的20*20的表格里,有四个对角线方向的标识成红色的数字。
(表格同上,略)
这四个数字的积是:26 * 63 * 78 * 14 = 1788686
试找出在这个20*20的表格中,在同一方向上(横、竖、斜)相邻的四个数字的乘积的最大值是多少。

代码:

  1. package main

  2. import (
  3.         "fmt"
  4. )

  5. func Problem011(data [][]int, count int) int {
  6.         var height int = len(data)
  7.         if height < 1 {
  8.                 return 0
  9.         }
  10.        
  11.         var width int = len(data[0])
  12.         if (height < count || width < count) {
  13.                 return 0
  14.         }

  15.         maxProduct := 0

  16.         // Check on horizental direction
  17.         for index := 0; index < height; index++ {
  18.                 for subIndex := 0; subIndex < width - count; subIndex++ {
  19.                         currentProduct := 1
  20.                         for offset := 0; offset < count; offset++{
  21.                                 currentProduct *= data[index][subIndex + offset]
  22.                         }
  23.                         if currentProduct > maxProduct {
  24.                                 maxProduct = currentProduct
  25.                         }
  26.                 }
  27.         }
  28.        
  29.         // Check on vertical direction
  30.         for index := 0; index < width; index++ {
  31.                 for subIndex := 0; subIndex < height - count; subIndex++ {
  32.                         currentProduct := 1
  33.                         for offset := 0; offset < count; offset++ {
  34.                                 currentProduct *= data[subIndex + offset][index]
  35.                         }
  36.                         if currentProduct > maxProduct {
  37.                                 maxProduct = currentProduct
  38.                         }
  39.                 }
  40.         }
  41.        
  42.         // Check on back slash direction
  43.         for index := 0; index < width - count; index++ {
  44.                 for subIndex := 0; subIndex < height - count; subIndex++ {
  45.                         currentProduct := 1
  46.                         for offset := 0; offset < count; offset++ {
  47.                                 currentProduct *= data[index + offset][subIndex + offset]
  48.                         }
  49.                         if currentProduct > maxProduct {
  50.                                 maxProduct = currentProduct
  51.                         }
  52.                 }
  53.         }
  54.        
  55.         // Check on slash direction
  56.         for index := count; index < width; index++ {
  57.                 for subIndex := 0; subIndex < height - count; subIndex++ {
  58.                         currentProduct := 1
  59.                         for offset := 0; offset < count; offset++ {
  60.                                 currentProduct *= data[subIndex + offset][index - offset]
  61.                         }
  62.                         if currentProduct > maxProduct {
  63.                                 maxProduct = currentProduct
  64.                         }
  65.                 }
  66.         }

  67.         return maxProduct
  68. }

  69. func main() {
  70.         data := [][] int {{8,2,22,97,38,15,0,40,0,75,4,5,7,78,52,12,50,77,91,8},
  71.                                           {49,49,99,40,17,81,18,57,60,87,17,40,98,43,69,48,4,56,62,0},
  72.                                           {81,49,31,73,55,79,14,29,93,71,40,67,53,88,30,3,49,13,36,65},
  73.                                           {52,70,95,23,4,60,11,42,69,24,68,56,1,32,56,71,37,2,36,91},
  74.                                           {22,31,16,71,51,67,63,89,41,92,36,54,22,40,40,28,66,33,13,80},
  75.                                           {24,47,32,60,99,3,45,2,44,75,33,53,78,36,84,20,35,17,12,50},
  76.                                           {32,98,81,28,64,23,67,10,26,38,40,67,59,54,70,66,18,38,64,70},
  77.                                           {67,26,20,68,2,62,12,20,95,63,94,39,63,8,40,91,66,49,94,21},
  78.                                           {24,55,58,5,66,73,99,26,97,17,78,78,96,83,14,88,34,89,63,72},
  79.                                           {21,36,23,9,75,0,76,44,20,45,35,14,0,61,33,97,34,31,33,95},
  80.                                           {78,17,53,28,22,75,31,67,15,94,3,80,4,62,16,14,9,53,56,92},
  81.                                           {16,39,5,42,96,35,31,47,55,58,88,24,0,17,54,24,36,29,85,57},
  82.                                           {86,56,0,48,35,71,89,7,5,44,44,37,44,60,21,58,51,54,17,58},
  83.                                           {19,80,81,68,5,94,47,69,28,73,92,13,86,52,17,77,4,89,55,40},
  84.                                           {4,52,8,83,97,35,99,16,7,97,57,32,16,26,26,79,33,27,98,66},
  85.                                           {88,36,68,87,57,62,20,72,3,46,33,67,46,55,12,32,63,93,53,69},
  86.                                           {4,42,16,73,38,25,39,11,24,94,72,18,8,46,29,32,40,62,76,36},
  87.                                           {20,69,36,41,72,30,23,88,34,62,99,69,82,67,59,85,74,4,36,16},
  88.                                           {20,73,35,29,78,31,90,1,74,31,49,71,48,86,81,16,23,57,5,54},
  89.                                           {1,70,54,71,83,51,54,69,16,92,33,48,61,43,52,1,89,19,67,48}}
  90.         fmt.Println("Problem 011 result: ", Problem011(data, 4))
  91. }
复制代码

论坛徽章:
0
发表于 2015-10-07 14:59 |显示全部楼层
本帖最后由 ba_du_co 于 2015-10-09 14:06 编辑

拿来练练手。

70600674
  1. #!perl6
  2. # g002edea

  3. my @grid =
  4.     <08 02 22 97 38 15 00 40 00 75 04 05 07 78 52 12 50 77 91 08>,
  5.     <49 49 99 40 17 81 18 57 60 87 17 40 98 43 69 48 04 56 62 00>,
  6.     <81 49 31 73 55 79 14 29 93 71 40 67 53 88 30 03 49 13 36 65>,
  7.     <52 70 95 23 04 60 11 42 69 24 68 56 01 32 56 71 37 02 36 91>,
  8.     <22 31 16 71 51 67 63 89 41 92 36 54 22 40 40 28 66 33 13 80>,
  9.     <24 47 32 60 99 03 45 02 44 75 33 53 78 36 84 20 35 17 12 50>,
  10.     <32 98 81 28 64 23 67 10 26 38 40 67 59 54 70 66 18 38 64 70>,
  11.     <67 26 20 68 02 62 12 20 95 63 94 39 63 08 40 91 66 49 94 21>,
  12.     <24 55 58 05 66 73 99 26 97 17 78 78 96 83 14 88 34 89 63 72>,
  13.     <21 36 23 09 75 00 76 44 20 45 35 14 00 61 33 97 34 31 33 95>,
  14.     <78 17 53 28 22 75 31 67 15 94 03 80 04 62 16 14 09 53 56 92>,
  15.     <16 39 05 42 96 35 31 47 55 58 88 24 00 17 54 24 36 29 85 57>,
  16.     <86 56 00 48 35 71 89 07 05 44 44 37 44 60 21 58 51 54 17 58>,
  17.     <19 80 81 68 05 94 47 69 28 73 92 13 86 52 17 77 04 89 55 40>,
  18.     <04 52 08 83 97 35 99 16 07 97 57 32 16 26 26 79 33 27 98 66>,
  19.     <88 36 68 87 57 62 20 72 03 46 33 67 46 55 12 32 63 93 53 69>,
  20.     <04 42 16 73 38 25 39 11 24 94 72 18 08 46 29 32 40 62 76 36>,
  21.     <20 69 36 41 72 30 23 88 34 62 99 69 82 67 59 85 74 04 36 16>,
  22.     <20 73 35 29 78 31 90 01 74 31 49 71 48 86 81 16 23 57 05 54>,
  23.     <01 70 54 71 83 51 54 69 16 92 33 48 61 43 52 01 89 19 67 48>;

  24. sub max-value {
  25.     my @direction =
  26.         0..19, 0..16,  0, -1, 0,  1,
  27.         0..16, 0..19, -1,  0, 1,  0,
  28.         0..16, 0..16, -1, -1, 1,  1,
  29.         0..16, 3..19, -1,  1, 1, -1;
  30.    
  31.     [max] @direction.map: -> $a, $b, $m, $n, $i, $j {
  32.         [max] $a.map: -> $x {
  33.              |$b.map: -> $y {
  34.                 my $X = $x + $m;
  35.                 my $Y = $y + $n;
  36.                 [*] (0 .. 3).map: { @grid[ $X += $i ][ $Y += $j ] }
  37.             }
  38.         }
  39.     }
  40. }

  41. say max-value; # 70600674
复制代码

求职 : 机器学习
论坛徽章:
79
2015年亚洲杯纪念徽章
日期:2015-05-06 19:18:572015七夕节徽章
日期:2015-08-21 11:06:172015亚冠之阿尔纳斯尔
日期:2015-09-07 09:30:232015亚冠之萨济拖拉机
日期:2015-10-21 08:26:3915-16赛季CBA联赛之浙江
日期:2015-12-30 09:59:1815-16赛季CBA联赛之浙江
日期:2016-01-10 12:35:21技术图书徽章
日期:2016-01-15 11:07:2015-16赛季CBA联赛之新疆
日期:2016-02-24 13:46:0215-16赛季CBA联赛之吉林
日期:2016-06-26 01:07:172015-2016NBA季后赛纪念章
日期:2016-06-28 17:44:45黑曼巴
日期:2016-06-28 17:44:4515-16赛季CBA联赛之浙江
日期:2017-07-18 13:41:54
发表于 2016-08-17 17:10 |显示全部楼层
Project 是否有什么比较快的算法啊  ?回复 1# icymirror


   

论坛徽章:
6
数据库技术版块每日发帖之星
日期:2015-11-27 06:20:00程序设计版块每日发帖之星
日期:2015-12-01 06:20:00每日论坛发贴之星
日期:2015-12-01 06:20:0015-16赛季CBA联赛之佛山
日期:2017-03-26 23:38:0315-16赛季CBA联赛之江苏
日期:2017-07-17 10:08:4415-16赛季CBA联赛之北京
日期:2018-03-04 17:01:50
发表于 2017-03-31 09:14 |显示全部楼层
问题,看似很简单,可还真写不好哦
这个司机不简单,今天算是见识了。
是否有更好的思路。
您需要登录后才可以回帖 登录 | 注册

本版积分规则 发表回复

  

北京盛拓优讯信息技术有限公司. 版权所有 京ICP备16024965号-6 北京市公安局海淀分局网监中心备案编号:11010802020122 niuxiaotong@pcpop.com 17352615567
未成年举报专区
中国互联网协会会员  联系我们:huangweiwei@itpub.net
感谢所有关心和支持过ChinaUnix的朋友们 转载本站内容请注明原作者名及出处

清除 Cookies - ChinaUnix - Archiver - WAP - TOP