Алгоритм поиска списка заданного точечного продукта и другого списка - PullRequest
Новая
       9

Алгоритм поиска списка заданного точечного продукта и другого списка

0 голосов
/ 17 октября 2018

Мне нужно написать функцию findL, которая принимает список L 1 целых чисел и желаемое скалярное произведение n и возвращает список L 2 неотрицательных целых чисел, таких что L 1 · L 2 = п .(Под «точечным произведением» я подразумеваю сумму попарных произведений; например, [1,2] · [3,4] = 1 · 3 + 2 · 4 = 11.)

Итак, дляНапример, findL(11, [1,2]) может вернуть SOME [3,4].Если возможного списка нет, я возвращаю NONE.

Я использую функциональный язык.(В частности, стандартный ML, но точный язык не так важен, я просто пытаюсь придумать алгоритм FP.) То, что я написал до сих пор:

Допустим, у меня есть findL (n, L1):

  1. , если L1 = [], я возвращаю NONE.
  2. , если L1 = [x] (список длиной 1)
    • , если (n> = 0 и x> 0 и n mod x = 0), вернуть SOME [n div x]
    • иначе вернуть NONE
  3. Если L1 имеет длину больше 1, я рекурсирую на findL (n, L [1:]).Если это возвращает список L2, я возвращаю [1] сцепленный с L2.Если рекурсивный вызов возвращает NONE, я сделал еще один рекурсивный вызов для findL (0, L [1:]) и добавил [n div x] к результату, если он не был NONE.Это работает на многих входах, но не на других.

Мне нужно изменить часть 3, но я не уверен, что у меня есть правильная идея.Буду признателен за любые советы!

1 Ответ

0 голосов
/ 17 октября 2018

Если вы не хотите сказать, что пустые списки на входе всегда плохие (даже n = 0 со списком []), я бы рекомендовал возвращать что-то другое для пустого списка, основываясь на том, достигли ли вы 0 наконец (все было вычтено) или нет, затем выполните рекурсию при получении любого непустого списка, а не специального списка из одного элемента.

Что касается третьего шага, вам нужно проверить каждые возможное положительное целое число, кратное первому элементу вашего списка ввода, пока они не превысят n, а не только первый и последний.Первое полученное значение, отличное от None, достаточно хорошо, поэтому вы просто добавляете множитель (не кратный) к списку возврата.Если все дает вам Nones, вы возвращаете None.

Я не знаю SML, но вот как я это сделаю в Haskell: 

import Data.Maybe (isJust, listToMaybe)

-- Find linear combinations of positive integers
solve :: Integer -> [Integer] -> Maybe [Integer]
-- If we've made it to the end with zero left, good!
solve 0 []     = Just []
-- Otherwise, this way isn't the way to go.
solve _ []     = Nothing
-- If one of the elements of the input list is zero, just multiply that element by one.
solve n (0:xs) = case solve n xs of
                      Nothing -> Nothing
                      Just ys -> Just (1:ys)
solve n (x:xs) =   listToMaybe                    -- take first solution if it exists
                 . map (\ (m, Just ys) -> m:ys)   -- put multiplier at front of list
                 . filter (isJust . snd)          -- remove nonsolutions
                 . zip [1 ..]                     -- tuple in the multiplier
                 . map (\ m -> solve (n - m) xs)  -- use each multiple
                 $ [x, x + x .. n]                -- the multiples of x up to n

Здесьон решает 11 с [1, 2] и 1 с [1, 2].

...