Способы улучшить этот код
Первый легче, потому что при чтении его слева направо Вы добираетесь: "Если что-то И somethingelse И somethingelse ТОГДА", который является легким для понимания предложения. Второй пример читает, "Если что-то ТОГДА, если somethingelse ТОГДА, если что-то еще ТОГДА", которое неуклюже.
кроме того, рассмотрите, хотели ли Вы использовать некоторый ORs в своем пункте - как Вы сделали бы это во втором стиле?
4 ответа
Во-первых, я бы не стал изобретать велосипед ... метод max уже определен в RichInt , поэтому вы можете написать a max b , для целых чисел a и b .
ТАКЖЕ, вместо slice устарел, поэтому lst.slice (0 , num) Я бы использовал lst.take (num) . Устаревшие методы, вероятно, исчезнут с запуском Scala 2.8.
РЕДАКТИРОВАТЬ: Действительно, как указал Дэниел , slice (Int, Int) не является устаревшим. Я очень торопился, когда изначально писал это, и думал о slice (Int) , что эквивалентно drop (Int) . Я по-прежнему считаю, что lst.take (num) более понятен, чем lst.slice (0, num) :).
(придирки) Ваша последняя строка также не компилируется, поскольку вы забыли добавить Nil в конец вашей последовательности минусов. 1 :: 2 :: 3 :: 4 , в конечном итоге вызовет :: для Int , у которого нет этого метода. Вот почему вам нужно добавить Nil в конец (вызвать :: на Nil ).
Кроме того, алгоритм, который вы использовали, не очевиден на первый взгляд. Я бы написал это следующим образом:
val numbers = /*"--the string of numbers--"*/.map(_.asDigit).toList
def sliding[A](xs: List[A], w: Int): List[List[A]] = {
for(n <- List.range(0, xs.size - w))
yield xs drop n take w
}
def product(xs: List[Int]): Int = (1 /: xs) (_ * _)
sliding(numbers, 5).map(product).sort(_ > _).head
Я чувствую, что последняя строка довольно хорошо объясняет, что должен делать алгоритм - взять скользящее окно списка, вычислить продукт в этом скользящем окне, а затем получить максимум вычисленных продуктов (я реализовал функцию максимума как sort (_> _). head из-за лени, Я мог бы сделать что-то O (n), а не O (n log (n)), если бы производительность была критической ... хотя она все еще выполняется менее чем за секунду).
Обратите внимание, что скользящая функция будет в библиотеке Scala 2.8 (см. сообщение Дэниела , откуда я был вдохновлен при написании этого определения скольжения.)
РЕДАКТИРОВАТЬ: Упс ... извините за /: . Мне просто нравится его лаконичность и тот факт, что начальный элемент сгиба стоит перед списком. Вы могли бы эквивалентно написать product , чтобы быть более точным:
def product(xs: List[Int]): Int = xs.foldLeft(1)(_ * _)
- Flaviu Cipcigan
val bigNumber = """73167176531330624919225119674426574742355349194934
96983520312774506326239578318016984801869478851843
85861560789112949495459501737958331952853208805511
12540698747158523863050715693290963295227443043557
66896648950445244523161731856403098711121722383113
62229893423380308135336276614282806444486645238749
30358907296290491560440772390713810515859307960866
70172427121883998797908792274921901699720888093776
65727333001053367881220235421809751254540594752243
52584907711670556013604839586446706324415722155397
53697817977846174064955149290862569321978468622482
83972241375657056057490261407972968652414535100474
82166370484403199890008895243450658541227588666881
16427171479924442928230863465674813919123162824586
17866458359124566529476545682848912883142607690042
24219022671055626321111109370544217506941658960408
07198403850962455444362981230987879927244284909188
84580156166097919133875499200524063689912560717606
05886116467109405077541002256983155200055935729725
71636269561882670428252483600823257530420752963450""".replaceAll("\\s+","")
def getMax(m: Int, l:List[Seq[Int]]): Int =
if (l.head.isEmpty) m else
getMax(m max l.foldLeft(1) ((acc, l) => acc * l.head), l map (_ tail))
def numDigits(bigNum: String, count: Int) =
(1 until count).foldLeft(List(bigNumber map (_ asDigit))) ((l, _) => l.head.tail :: l)
def solve(bigNum: String, count: Int) = getMax(0, numDigits(bigNum, count))
solve(bigNumber, 5)
val str = ... // строка цифр
val nums = str.map {_.asDigit}
(От 0 до nums.size-5) .map {i => nums.slice (i, i + 5) .product} .max
и еще один, более эффективный:
(от 0 до nums.size- 5) .foldLeft (-1) {case (r, i) => r max nums.slice (i, i + 5) .product}
Кстати: работает с scala2.8
Я так и сделал. Ничего фантастического. В вашем коде вы определяли длину списка на каждой итерации, что довольно расточительно. Я просто добавляю некоторое количество единиц (такое же, как количество последовательных цифр) в конец списка, поэтому мне не нужно проверять длину списка, чтобы завершить цикл.
val s = ... // string of digits
val ds = s.map(_.asDigit).toList
def findMaxProduct(ds: List[Int], n: Int, max: Int): Int = ds match {
case Nil => max
case _ :: rest => findMaxProduct(rest, n, Math.max(max, ds.take(n).reduceLeft(_ * _)))
}
val n = 5 // number of consecutive digits
println(findMaxProduct(ds ::: List.make(n, 1), n, -1))