Таким образом, вы можете использовать сложение, вычитание, умножение и сравнение.Я также предполагаю, что вы можете определять функции, и ваша цель состоит в том, чтобы определить две функции:
- Функция
evenList принимает список чисел и возвращает true, если (если-и-только-если) список содержит только четные числа. - Функция
oddList принимает список чисел и возвращает значение true, если список содержит только нечетные числа.
Сначала давайте определим even функция, которая принимает одно число и возвращает истину, если ввод четен:
even(i) = if (i == 0) true
else if (i == 1) false
else if (i > 1) even(i - 2)
else /* i < 0 */ even(i + 2)
Мы можем определить odd функцию в терминах even:
odd(i) = even(i+1)
Мызатем можно просто определить evenList рекурсивно:
evenList(nil) = true
eventList(x : xs) = even(x) & evenList(xs)
(я использую x : xs для обозначения списка, первый элемент которого равен x, а остаток - xs. Я используюnil означает пустой список.)
Но, возможно, вам не разрешено использовать логический оператор &.Что мы можем сделать вместо этого?
Рассмотрим умножение двух чисел, i и j.Какой паритет является результатом, основанным на паритете i и j?(Четность означает странность или равномерность.)
even(i) & even(j) -> even(i*j)even(i) & odd(j) -> even(i*j)odd(i) & even(j) -> even(i*j)odd(i) & odd(j) -> odd(i*j)
(я использую -> для обозначения «подразумевает».) Другими словами, i * j нечетно, если i нечетно, а j нечетно.
Итак, если вы умножитевсе ваши входные числа вместе, и произведение нечетное, тогда все входные данные нечетные.Итак, мы определим функцию product:
product(nil) = 1
product(x : xs) = x * product(xs)
И затем мы можем определить oddList следующим образом:
oddList(xs) = odd(product(xs))
Но как узнать, все ли входычетное?Даже один четный вход делает продукт четным.
Хитрость заключается в том, чтобы реверсировать четность всех входов, а затем реверсировать четность результата.Вы можете изменить паритет, добавив или вычтя один.Пусть i1 = i + 1 и j1 = j + 1. Тогда:
even(i) & even(j) -> odd(i1) & odd(j1) -> odd(i1 * j1) -> even(i1 * j1 + 1)even(i) & odd(j) -> odd(i1) & even(j1) -> even(i1 * j1) -> odd(i1 * j1 + 1)odd(i) & even(j) -> even(i1) & odd(j1) -> even(i1 * j1) -> odd(i1 * j1 + 1)odd(i) & odd(j) -> even(i1) & even(j1) -> even(i1 * j1) -> odd(i1 * j1 + 1)
Другими словами, (i + 1) * (j + 1) + 1 является четным тогда и только тогда, когда i четное, а j четное.
Итак, давайте определим функцию product1, которая возвращает произведение всех своих входов, каждый из которых увеличивается на 1 вначале:
product1(nil) = 1
product1(x : xs) = (x + 1) * product1(xs)
Затем мы можем определить evenList следующим образом:
evenList(xs) = even(1 + product1(xs))