Значит, друг задал задачу. С клавиатуры вводится некоторая последовательность чисел, которые загоняются в массив. Потом все числа в этом массиве складываются сначала попарно, потом по три, потом по четыре и так далее.
После этого массив получившихся чисел сортируется по возрастанию и выводится на экран.
Длинна массива и числа для массива вводятся с клавиатуры.
У меня есть как бы пару идей. Как сортировать и выводить я знаю А вот ввод и нахождение сумм — . Вернее, как минимум сегодня, нет времени над этим подумать А решить хочется сегодня
Здравствуйте, Mamut, Вы писали:
M>Значит, друг задал задачу. С клавиатуры вводится некоторая последовательность чисел, которые загоняются в массив. Потом все числа в этом массиве складываются сначала попарно, потом по три, потом по четыре и так далее.
M>То есть получается что-то вроде M>
M>После этого массив получившихся чисел сортируется по возрастанию и выводится на экран.
M>Длинна массива и числа для массива вводятся с клавиатуры.
M>У меня есть как бы пару идей. Как сортировать и выводить я знаю А вот ввод и нахождение сумм — . Вернее, как минимум сегодня, нет времени над этим подумать А решить хочется сегодня
M>Не швырнете в меня кодом? Или кусками кода
Чтобы не усложнять, можно(?) изменить формат вводимых данных на что-то вроде
[1,2,15,20]
и тогда весь список читается одним вызовом read. Вот для затравки код ввода/вывода, а определение yourFunc за тобой
yourFunc :: [Int]->[Int]
yourFunc x = x
main = getLine >>= putStrLn.show.yourFunc.read
Оператор "точка" — это композиция функций, т.е. вместо sin(cos x) позволяет писать (sin.cos) x
КЕ>Чтобы не усложнять, можно(?) изменить формат вводимых данных на что-то вроде
[1,2,15,20]
и тогда весь список читается одним вызовом read.
О! Не знал. Думаю, это обсуждаемо.
КЕ>Вот для затравки код ввода/вывода, а определение yourFunc за тобой КЕ>
КЕ>yourFunc :: [Int]->[Int]
КЕ>yourFunc x = x
КЕ>main = getLine >>= putStrLn.show.yourFunc.read
КЕ>
КЕ>Оператор "точка" — это композиция функций, т.е. вместо sin(cos x) позволяет писать (sin.cos) x
Ага. getLine передается в read, результат которого в yourFunc и так далее. Так, надо почитать документацию в области >>= повнимательнее (вернее, по монадам вообще — все не дойду )
Здравствуйте, Mamut, Вы писали:
M>Значит, друг задал задачу. С клавиатуры вводится некоторая последовательность чисел, которые загоняются в массив. Потом все числа в этом массиве складываются сначала попарно, потом по три, потом по четыре и так далее.
Получаем список списков, да? Суммы смежных пар, суммы смежных троек, и т.д.?
plus_elts :: (Num elt)
=> [elt] -- суммы с прошлого раза
-> [elt] -- данные из исходного массива
-> [elt] -- новые суммы
plus_elts [_] [] = 0 -- ниже дадим гарантию, что списки отличаются на 1 элемент
plus_elts (x:xs) (y:ys) = (x+y):(plus_elts xs ys)
list2sums :: (Num elt)
=> [elt] -- исходный массив
-> [[elt]] -- массив сумм, начиная с суммы пар
list2sums [] = [] -- два дефолтных случая, когда просто нечего делать
list2sums [_] = [] -- впрочем, этот случай является завершением рекурсии ниже
list2sums d = list2sums' d (tail d) -- складываем со сдвигом: [1,2,3,...] + [2,3,4,...]
where
-- вход: список сумм с прошлого раза (s) и хвост массива исходных данных (d)
-- выход: список списков сумм n-ок, начиная со следующей
-- предусловие: (length s) == (length d)+1
-- постусловие: голова результата (передаваемая дальше) s', (length s')==(length d)==(length s)-1
list2sums' s [] = [] -- нечего больше складывать (кстати, можно проверить, что s содержит ровно один элемент)
list2sums' s d =
let s' = (plus_elts s d) -- length s' == length d
in s' : (list2sums' s' (tail d))
-- первый раз мы вызвали list2sums' где s - входные данные, т.е. суммы групп по одному :)
Далее тебе нужно отсортировать этот список. Поскольку его элементы — списки, то требуется лексикографическая сортировка.
Надо поискать в библиотеках — наверняка есть и лексикографическое сравнение, и сортировка.
Или самому руками написать.
Здравствуйте, Кодт, Вы писали:
К>Здравствуйте, Mamut, Вы писали:
M>>Значит, друг задал задачу. С клавиатуры вводится некоторая последовательность чисел, которые загоняются в массив. Потом все числа в этом массиве складываются сначала попарно, потом по три, потом по четыре и так далее.
К>Получаем список списков, да? Суммы смежных пар, суммы смежных троек, и т.д.?
Возможно, я неправильно понял условие.
Если первый список — это x1+x2:x1+x2+x3:..., второй x2+x3:x2+x3+x4 и т.д., то алгоритм чуть-чуть отличается.
То есть, индукция налицо.
Причём можно выделить паттерн этой индукции.
integrator f x0 [] = []
integrator f x0 (x1:xs) = x0' : integrator x0' xs
where x0'= x0 `f` x1
-- как-то можно выразить через foldr. как именно? лень думать, однако.
-- первая серия - это список частичных сумм
partialsums (x1:xs) = integrator (+) x1 xs
-- все серии
allsums [] = [] -- нет данных
allsums [x1] = [] -- недостаточно данных
allsums xs = s1 : integrator s1 iter xs
where
s1 = partialsums xs
-- и собственно операция скрещивания
sk `iter` xk = (tail sk) `decrement_by` xk
s `decrement_by` x = map (\si -> si-x) s
Здравствуйте, Mamut, Вы писали:
M>Значит, друг задал задачу. С клавиатуры вводится некоторая последовательность чисел, которые загоняются в массив. Потом все числа в этом массиве складываются сначала попарно, потом по три, потом по четыре и так далее. M>После этого массив получившихся чисел сортируется по возрастанию и выводится на экран.
В какой-то момент я подумал — а может быть, задача состоит в том, чтобы найти максимальную из сумм подряд идущих элементов (а выводить всё — это уже моцартом навеяно)?
В таком случае всё гораздо проще и делается за один пробег по списку.
Лень было думать, написал что написалось :
M>Значит, друг задал задачу. С клавиатуры вводится некоторая последовательность чисел, которые загоняются в массив. Потом все числа в этом массиве складываются сначала попарно, потом по три, потом по четыре и так далее.
M>То есть получается что-то вроде M>
M>После этого массив получившихся чисел сортируется по возрастанию и выводится на экран.
Если я ничего не путаю, то должен получиться список списков, нет?
Вот например (далеко не самый эффективный) код:
sumn [] _ = []
sumn xs n = sum head : sumn tail n
where (head, tail) = splitAt n xs
main = let num = 15
xs = [1,2,3,4,5,6,7,8,9,10,11,12,13,14,15]
in mapM_ (print . sumn xs) [2..num]
Или, видимо (скорее всего), я как-то не так понял задачу.
Функция сортировки так и называется — sort (см. модуль Data.List)
прочитать что-то с терминала — например, getChar или getLine
представить это как число — read c :: Integer
plus_elts :: (Num elt)
=> [elt] -- суммы с прошлого раза
->> [elt] -- данные из исходного массива
->> [elt] -- новые суммы
plus_elts [_] [] = 0 -- ниже дадим гарантию, что списки отличаются на 1 элемент
plus_elts (x:xs) (y:ys) = (x+y):(plus_elts xs ys)
В этом месте и GHC и Hugs ругаются следующим:
GHC
— Could not deduce (Num [elt]) from the context (Num elt) Main.hs ArraySort/src line 9 04 December 2005 10:18:06 13
— Probable fix: — add (Num [elt]) to the type signature(s) for `plus_elts' — or add an instance declaration for (Num [elt]) — In the definition of `plus_elts': plus_elts [_] [] = 0 Main.hs ArraySort/src line 9 04 December 2005 10:18:06 14
Hugs
ERROR "D:\Mamut\EclipseWorkspace\ArraySort\src\Main.hs":9 — Cannot justify constraints in explicitly typed binding
*** Expression : plus_elts
*** Type : Num a => [a] -> [a] -> [a]
*** Given context : Num a
*** Constraints : Num [a]
К>Далее тебе нужно отсортировать этот список. Поскольку его элементы — списки, то требуется лексикографическая сортировка. К>Надо поискать в библиотеках — наверняка есть и лексикографическое сравнение, и сортировка. К>Или самому руками написать.
Млин. Вернуть ны время вспять лет на десять, когда я жил и дышал математикой
Как оказалось, условие я и сам неправильно понял. Оказалось, что надо не просто суммы смежных двоек, троек и т.д., а все гораздо хуже Необходимо суммы всех возможных групп чисел вообще. Т.е. а1 + а2, а1 + а3, а1 + а4, ...., а1 + а2 + а3, а1 + а3 + а4, ..., а2 + а3, ..., а2 + а4 + а5, ...
И потом получившиеся суммы поставить в порядке возрастания. На вопрос "а нафига это надо", друг не ответил, сказал, что надо А я уже обещался помочь
Здравствуйте, Mamut, Вы писали:
M>Как оказалось, условие я и сам неправильно понял. Оказалось, что надо не просто суммы смежных двоек, троек и т.д., а все гораздо хуже Необходимо суммы всех возможных групп чисел вообще. Т.е. а1 + а2, а1 + а3, а1 + а4, ...., а1 + а2 + а3, а1 + а3 + а4, ..., а2 + а3, ..., а2 + а4 + а5, ...
Ну он злодей! Очевидно, что каждая такая сумма идентифицируется булевым вектором длины n и веса не менее 2 (указывающим вхождение элементов входных данных).
И какова же мощность множества таких векторов?
ОТВЕТ: (2^n)-(n+1)
где 2^n — мощность всего пространства, n — количество векторов с весом=1, 1 — количество векторов с весом=0
Ленивые вычисления здесь не пройдут, потому что сортировка. Либо придумать генератор сортированной последовательности (боюсь, что тогда вместо экспоненты в памяти мы получим экспоненту во времени).
К>ОТВЕТ: (2^n)-(n+1) К>где 2^n — мощность всего пространства, n — количество векторов с весом=1, 1 — количество векторов с весом=0
*задумчиво почесал в затылке*
К>Ленивые вычисления здесь не пройдут, потому что сортировка. Либо придумать генератор сортированной последовательности (боюсь, что тогда вместо экспоненты в памяти мы получим экспоненту во времени).
К>Тебе (и ему) оно надо?
он говорит, что ему надо. А вот надо ли мне
Итак. В Хаскеле эта задача трудновыполнимая из-за невозможности сохранить промежуточный результат, так получается (если не так, то примите во внимание, что Дима последние несколько дней немного тормоз )
Блин. А счастье было так возможно Придется качать CDT, писать на С++
Здравствуйте, Mamut, Вы писали:
M>Итак. В Хаскеле эта задача трудновыполнимая из-за невозможности сохранить промежуточный результат, так получается (если не так, то примите во внимание, что Дима последние несколько дней немного тормоз )
Почему трудновыполнимая? Не труднее, чем где-либо ещё. Просто она ЭКСПОНЕНЦИАЛЬНАЯ по своей природе
Но давай, однако, подумаем — а нельзя ли решить её алгоритмически?
Отсортируем входные данные.
Очевидно, что если две перестановки из n по k — назовём их I, J, упорядочены, I<J, то и соответствующие им суммы находятся в том же порядке. Проще говоря, I={i1,i2,...,ik} < J={j1,j2,...,jk} => x[i1]+...+x[im] < x[j1]+...+x[jm]
Перестановки можно перечислить. (Создание перестановки по индексу — дело неблагодарное, а вот получить следующую из текущей — легко и просто).
Отсюда:
1) делаем генератор сумм перестановок из n по k (для большого k, наверное, есть смысл вычислять очередную сумму инкрементно, а для маленького — можно и пересчитывать каждый раз заново)
2) делаем генератор, выполняющий сортировку слиянием — у него на входе n-1 генераторов сумм, для k=2..n
Затраты памяти — O(N^2). Затраты времени — O(N) на каждую итерацию.
Если бы мы умудрились нарожать массив сумм сразу — то на сортировку потратили бы O(S*log(S)) = O(N^2*N), где S=O(2^N) — размер массива.
То есть примерно столько же
Теперь осталось закодировать это на С, С++ или Хаскелле.
Конечно, там без монад не обойтись — но возможно (почти 100% уверен), что это всего лишь list comprehensions.
Если хочешь освоить Хаскелл — то вперёд, а если нужно по-быстрому за оставшийся день — то С++ в руки
M>>Итак. В Хаскеле эта задача трудновыполнимая из-за невозможности сохранить промежуточный результат, так получается (если не так, то примите во внимание, что Дима последние несколько дней немного тормоз )
К>Почему трудновыполнимая? Не труднее, чем где-либо ещё. Просто она ЭКСПОНЕНЦИАЛЬНАЯ по своей природе
К>Но давай, однако, подумаем — а нельзя ли решить её алгоритмически?
Ага, я так и думал, что где-то будет "the catch". Он состоит в том, что надо думать
К>Отсортируем входные данные.
[skip]
К>Теперь осталось закодировать это на С, С++ или Хаскелле. К>Конечно, там без монад не обойтись — но возможно (почти 100% уверен), что это всего лишь list comprehensions.
К>Если хочешь освоить Хаскелл — то вперёд, а если нужно по-быстрому за оставшийся день — то С++ в руки
Ну что ж. Буду думать, благо алгоритм уже разжеван и разве что в рот не положен Тем более, что время есть
Здравствуйте, Mamut, Вы писали:
К>>Если хочешь освоить Хаскелл — то вперёд, а если нужно по-быстрому за оставшийся день — то С++ в руки
M>Ну что ж. Буду думать, благо алгоритм уже разжеван и разве что в рот не положен Тем более, что время есть
-- тип "комбинация"...
type Combination = [Int] -- это упорядоченный список индексов комбинации
-- в принципе, мог быть и массив - но его порождать тяжелее
-- генератор комбинаций
combinations :: Int -> Int -> Int -> [Combination]
combinations n0 n1 k -- перебор k чисел из диапазона [n0..n1]
| k==0 = [ [] ] -- вырожденный случай
| k==1 = [ [x] | x <- [n0..n1] ] -- банальный случай
| otherwise = [ (x:xs) | x <- [n0..n1-(k-1)], -- первое число
xs <- combinations (x+1) n1 (k-1) -- и перебор всех остальных
]
-- сумма данной комбинации элементов массива
sum :: (Num a) => Array a -> Combination -> a
sum arr inds = foldr fn ids
where
{- по смыслу:
index `fn` total = (arr!index) + total
что равно
fn i t = (+) ((!) arr i) t
fn i = (+) ((!) arr i)
= (+)(((!) arr)i)
= (+)$((!) arr)i
fn = (+)$((!) arr)
-}
fn = (+)$((!)arr)
-- генератор сумм (до посинения)
gensums :: (Num a) => Array a -> Int -> [a]
gensums arr k = [ sum' comb | comb <- combinations n0 n1 k ] -- внёс поправку: combinations, а не permutations'
where
sum' = sum arr -- говорят, биндинг дешевле пассинга
(n0,n1) = bounds arr
-- список сумм
listsums :: (Num a) => Array a -> [[a]]
listsums arr = [ gensums' k | k <- [1..n] ]
where
gensums' = gensums arr
(n0,n1) = bounds arr
k = n1-n0+1
-- и вот теперь, над этим списком будем надругиваться...
mergesums :: (Num a) => [[a]] -> [a]
-- (фантазия временно иссякла)
-- финальная функция
allsums :: (Num a) => Array a -> [a]
allsums {-arr-} = mergesums.listsums {-arr-}
main = do
lst <- read <<= getStrLn -- через запятую, в квадратных скобках
let arr = arrayList (1,length lst) lst
print (allsums arr) -- тоже через запятую и в квадратных скобках
return ()
Меня вдруг посетила эврика, что задача-то уже почти решена.
Дано: список из n-1 упорядоченных списков (порождённое генератором — но это не имеет значения). Сами списки, правда, здоровенные (и порождаются генераторами).
Найти: их слияние.
Раз у нас список списков невелик, то рекурсивно применить попарное слияние — не страшно.
И, поскольку язык ленивый, то каждый merge2 будет вызван только тогда, когда в нём появится потребность.
Разумеется, выборка head output приведёт к тому, что все они по разу вздрогнут и предоставят первые элементы списков.
Но дальше этого не провалятся, и мы не выжрем вагон памяти.
Здравствуйте, Mamut, Вы писали:
M>Как оказалось, условие я и сам неправильно понял. Оказалось, что надо не просто суммы смежных двоек, троек и т.д., а все гораздо хуже Необходимо суммы всех возможных групп чисел вообще. Т.е. а1 + а2, а1 + а3, а1 + а4, ...., а1 + а2 + а3, а1 + а3 + а4, ..., а2 + а3, ..., а2 + а4 + а5, ...
M>И потом получившиеся суммы поставить в порядке возрастания. На вопрос "а нафига это надо", друг не ответил, сказал, что надо А я уже обещался помочь