Как найти произведение всех чисел последовательности

Разберём чуть более сложную задачу. Итак, вам дана последовательность неотрицательных целых чисел $a_1, dots, a_{n}$. Вычислите

$$
maxlimits_{1 le i neq j le n}a_i cdot a_j , .
$$

Обратите внимание, что $i$ и $j$ должны быть разными, хотя в каких-то случаях можно наблюдать, что $a_i=a_j$.

• Формат ввода: Первая строка содержит целое число $n$. Следующая строка содержит $n$ неотрицательных целых чисел $a_1, dotsc, a_{n}$ (разделены пробелами).
• Формат вывода: Максимальное попарное произведение.
• Ограничения: $2 le n le 2cdot10^5$; $0 le a_1, dots, a_{n} le 2cdot 10^5$.
• Примеры

Пример 1

Ввод	Вывод
3 1 2 3	6

Пример 2

Ввод	Вывод
10 7 5 14 2 8 8 10 1 2 3	140

Наивный подход

Наивный способ решить задачу Максимальное произведение — перебрать все возможные пары вводных элементов $A[1dotsc n]=[a_1,dotsc, a_n]$ и найти пару, которая даёт наибольшее произведение.

MaxPairwiseProductNaive(A[1..n]):
    product = 0
    for i from 1 to n
        for j from 1 to n
            if i != j
                if product < A[i] * A[j]
                    product = A[i] * A[j]
    return product

Этот код можно оптимизировать и сократить следующим образом.

MaxPairwiseProductNaive(A[1..n]):
    product = 0
    for i from 1 to n
        for j from i+1 to n
            product = max(product, A[i] * A[j])
    return product

Реализуйте этот алгоритм, используя ваш любимый язык программирования. Если вы используете C++, Java или Python3, вам могут пригодиться начальные заготовки (для всех задач из книги мы предлагаем стартовые заготовки с использованием этих трёх языков в интерфейсе тестирующей системы).
С другими языками вам понадобится сделать работу с нуля.

Стартовые заготовки решений для C++, Java и Python3 представлены ниже.

C++

#include <iostream>
#include <vector>
#include <algorithm>

int MaxPairwiseProduct(const std::vector<int>& numbers) {
    int max_product = 0;
    int n = numbers.size();

    for (int first = 0; first < n; ++first) {
        for (int second = first + 1; second < n; ++second) {
            max_product = std::max(max_product,
                numbers[first] * numbers[second]);
        }
    }

    return max_product;
}

int main() {
    int n;
    std::cin >> n;
    std::vector<int> numbers(n);
    for (int i = 0; i < n; ++i) {
        std::cin >> numbers[i];
    }

    std::cout << MaxPairwiseProduct(numbers) << "n";
    return 0;
}

Java

import java.util.*;
import java.io.*;

public class MaxPairwiseProduct {
    static int getMaxPairwiseProduct(int[] numbers) {
        int max_product = 0;
        int n = numbers.length;

        for (int first = 0; first < n; ++first) {
            for (int second = first + 1; second < n; ++second) {
                max_product = Math.max(max_product,
                    numbers[first] * numbers[second]);
            }
        }

        return max_product;
    }

    public static void main(String[] args) {
        FastScanner scanner = new FastScanner(System.in);
        int n = scanner.nextInt();
        int[] numbers = new int[n];
        for (int i = 0; i < n; i++) {
            numbers[i] = scanner.nextInt();
        }
        System.out.println(getMaxPairwiseProduct(numbers));
    }

    static class FastScanner {
        BufferedReader br;
        StringTokenizer st;

        FastScanner(InputStream stream) {
            try {
                br = new BufferedReader(new
                    InputStreamReader(stream));
            } catch (Exception e) {
                e.printStackTrace();
            }
        }

        String next() {
            while (st == null || !st.hasMoreTokens()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }

        int nextInt() {
            return Integer.parseInt(next());
        }
    }

}

Python

def max_pairwise_product(numbers):
    n = len(numbers)
    max_product = 0
    for first in range(n):
        for second in range(first + 1, n):
            max_product = max(max_product,
                numbers[first] * numbers[second])

    return max_product


if __name__ == '__main__':
    _ = int(input())
    input_numbers = list(map(int, input().split()))
    print(max_pairwise_product(input_numbers))

После проверки вы можете увидеть такое сообщение:

Failed case #4/17: time limit exceeded

Дело в том, что мы проверяем ваше решение на тестовых примерах — это помогает убедиться, что программа работает быстро и без ошибок.
В результате мы, как правило, знаем, какие ошибки вы допустили.
Сообщение выше говорит о том, что предложенная программа превышает ограничение по времени в 4-м тестовом примере из 17.

💡 Остановитесь и подумайте:
Почему решение не укладывается в ограничение по времени?

MaxPairwiseProductNaive выполняет порядка $n^2$ шагов при последовательности длиной $n$.
При максимальном возможном значении $n=2cdot 10^5$ количество шагов будет порядка $4cdot 10^{10}$.
Так как большинство современных компьютеров выполняют около $10^8$–$10^9$ базовых операций в секунду (разумеется, это зависит от компьютера),
выполнение MaxPairwiseProductNaive может занять десятки секунд.
Это превысит временное ограничение задачи.

Нам нужен более быстрый алгоритм!

Быстрый алгоритм

А что если внимательнее рассмотреть более мелкие примеры— скажем, $[5,6,2,7,4]$? Эврика! Достаточно помножить два самых больших элемента массива — $7$ и $6$.

То есть нам достаточно просканировать последовательность лишь дважды. При первом сканировании мы найдем самый большой элемент, затем — второй по величине.

MaxPairwiseProductFast(A[1..n]):
    index_1 = 1
    for i from 2 to n
        if A[i] > A[index_1]
            index_1 = i
    index_2 = 1
    for i from 2 to n
        if A[i] != A[index_1] and A[i] > A[index_1]
            index_1 = i
    return A[index_1] * A[index_2]

Тестирование и отладка

Реализуйте этот алгоритм и протестируйте его на вводе $A=[1,2]$. Как и ожидалось, алгоритм выводит $2$.
Затем проверьте на вводе $A=[2,1]$. На удивление, алгоритм выводит $4$.
Изучив код, вы обнаружите, что после первого цикла $index_1=1$. Далее алгоритм инициализирует $index_2$ значением $1$, и цикл for не обновляет $index_2$.
В результате перед возвратом $index_1=index_2$. Чтобы этого избежать, необходимо изменить псевдокод следующим образом:

MaxPairwiseProductFast(A[1..n]):
    index_1 = 1
    for i from 2 to n
        if A[i] > A[index_1]:
            index_1 = i
    if index_1 = 1
        index_2 = 2
    else:
        index_2 = 1
    for i from 1 to n
        if A[i] != A[index_1] and A[i] > A[index_1]
            index1 = i
    return A[index_1] * A[index_2]

Опробуйте этот код на маленьких наборах данных $[7,4,5,6]$, чтобы убедиться, что он выдает правильные результаты. Затем попробуйте ввод.

2  
100000 90000  

Может оказаться, что программа выдает что-то вроде $410,065,408$ или даже отрицательное число вместо правильного результата — $9,000,000,000$.
Вероятнее всего, это вызвано целочисленным переполнением. Например, на языке C++ такое большое число, как $9,000,000,000$, не умещается в стандартный тип int, который занимает 4 байта на большинстве компьютеров и варьируется от $-2^{31}$ до $2^{31}-1$ при
$$
2^{31}=2,147,483,648 ,.
$$

Соответственно, вместо использования типа int в C++ при вычислении произведения и сохранении результата вам нужно использовать тип int64_t.
Это предотвратит целочисленное переполнение, так как тип int64_t занимает 8 байтов и хранимые значения варьируются от $-2^{63}$ до $2^{63}-1$ при

$$
2^{63}=9,223,372,036,854,775,808 , .
$$

Затем протестируйте вашу программу с большими наборами данных, например, с массивом $A[1 dotsc 2 cdot 10^5]$, где $A[i]=i$ для всех $1 le i le 2 cdot 10^5$.
Это можно сделать двумя способами:

• Создать массив в программе и передать его MaxPairwiseProductFast (чтобы не считывать его из стандартного ввода).
• Создать отдельную программу, которая запишет такой массив в файл dataset.txt. Затем передать этот набор данных вашей программе из консоли:

yourprogram < dataset.txt

Убедитесь, что при обработке данных ваша программа укладывается в ограничение по времени и выдаёт верный результат: $39,999,800,000$.
Теперь вы можете быть уверенным, что ваша программа работает!

Однако система оценки снова ругается:

Failed case #5/17: wrong answer

Но как создать такой тестовый сценарий, который приведет к сбою программы и поможет понять, что с ней не так?

А в чём ошибка?

Вероятно, вас интересует, почему мы не предоставили 5-й набор данных из 17 — тот, который привел к сбою программы?
Причина проста: в реальности вам не будут показывать тестовые примеры.

Даже опытные программисты при решении задач с алгоритмами часто совершают ошибки, которые трудно обнаружить.
Поэтому важно научиться находить баги как можно раньше.
Когда авторы этой книги только начинали программировать, они ошибочно полагали, что почти все их программы правильные.
Сейчас же мы знаем, что при первом запуске наши программы почти никогда не верны.

Когда разработчик уверен в работе своей программы, он зачастую использует всего лишь несколько примеров для тестирования.
Если результаты выглядят приемлемо, он считает свою работу законченной — но это путь к катастрофе.
Если вы хотите убедиться, что ваша программа работает всегда, то советуем тщательно подобрать примеры для тестирования.
Реализация алгоритмов, а также их тестирование и отладка будут бесценным навыком для вашей будущей карьеры программиста.

Стресс-тестирование

Представляем вам стресс-тестирование — технику, которая позволяет генерировать тысячи тестовых сценариев. С её помощью можно найти тот, из-за которого провалилось ваше решение.

Стресс-тестирование состоит из четырёх частей:

• Реализация алгоритма.
• Альтернативная, банальная и медленная, но правильная реализация алгоритма для той же самой задачи.
• Генератор случайных тестов.
• Бесконечный цикл, генерирующий тесты и передающий их обоим вариантам реализации для сравнения результатов. Если результаты разнятся, выводятся оба результата и пример для тестирования, а программа останавливается. В ином случае цикл повторяется.

Стресс-тестирование основано на идее, что две правильных реализации
с каждым тестом должны приводить к одному ответу (при условии, что ответ на задачу уникален).
Однако если одна из реализаций неправильна, должен существовать такой тест, который приводит к разным ответам.
Единственный случай, при котором это не так, — когда в обеих реализациях есть одна и та же ошибка.
Но это маловероятно — если ошибка не где-то в программе ввода/вывода, общей для обоих решений.
Действительно, если одно решение правильно, а другое — нет, то существует сценарий тестирования, при котором они различаются.
Если оба решения неверны, но баги отличаются — скорее всего, есть тест, при котором два решения дают разные результаты.

Продемонстрируем стресс-тестирование MaxPairwiseProductFast,
используя

MaxPairwiseProductNaive в качестве тривиальной реализации:

StressTest(N, M):
    while true:
        n = ... // случайное целое число между 2 и N
        // создать массив A[1..n]
        for i from 1 to n
            A[i] = ... // случайное целое число между 0 и M
        print(A[1..n])
        result_1 = MaxPairwiseProductNaive(A)
        result_2 = MaxPairwiseProductFast(A)
        if result_1 = result_2:
            print("OK")
        else:
            print("Wrong answer:", result_1, result_2)
            return

Представленный выше цикл while сначала генерирует длину вводной последовательности $n$, случайное число между $2$ и $N$.
Оно должно быть не менее $2$: формулировка задачи гласит, что $n ge 2$.
Параметр $N$ должен быть достаточно маленьким, чтобы позволить нам рассмотреть множество тестов, несмотря на то, что наши решения медленные.

Сгенерировав $n$, мы генерируем массив $A$ с $n$ целыми числами от $0$ до $M$ и выводим его, чтобы по ходу бесконечного цикла мы всегда знали,
какой тест проходит сейчас. Это упростит нахождение ошибок в коде для генерации теста. Затем мы вызываем два алгоритма для $A$ и сравниваем результаты.
Если результаты отличаются, мы их печатаем и останавливаемся. В ином случае мы продолжаем цикл while.

Давайте запустим StressTest(10, 100'000) и скрестим пальцы в надежде, что он выдаст Wrong answer.
Для нас это выглядит как-то так (результат может отличаться на вашем компьютере из-за другого генератора случайных чисел).

...  
OK  
67232 68874 69499  
OK  
6132 56210 45236 95361 68380 16906 80495 95298  
OK  
62180 1856 89047 14251 8362 34171 93584 87362 83341 8784  
OK  
21468 16859 82178 70496 82939 44491  
OK 
68165 87637 74297 2904 32873 86010 87637 66131 82858 82935  
Wrong answer: 7680243769 7537658370  

Ура! Мы нашли пример, в котором MaxPairwiseProductNaive и MaxPairwiseProductFast приводят к разным результатам, и теперь можем проверить, что именно пошло не так.
Затем мы отлаживаем это решение через этот пример, находим баг, исправляем его и повторяем стресс-тестирование.

💡 Остановитесь и подумайте:
Видите что-то подозрительное в найденном наборе данных?

Обратите внимание, что генерировать тесты автоматически и проводить стресс-тестирование легко, но находить и исправлять баги — сложно.
Прежде чем углубиться в отладку багов, давайте попробуем сгенерировать тестовый пример поменьше — это упростит нам работу.
Для этого мы поменяем $N$ с 10 на 5 и $M$ с $100,000$ на $9$.

💡 Остановитесь и подумайте:
Почему мы сначала запустили StressTest с большими параметрами $N$ и $M$, а теперь хотим запустить с маленькими?

Затем мы заново начинаем стресс-тестирование и получаем следующее:

...  
7 3 6  
OK  
2 9 3 1 9  
2 3  
Wrong answer: 81 27  

Медленный алгоритм MaxPairwiseProductNaive даёт верный ответ $81$ ( $9 cdot 9 = 81$ ), но быстрый MaxPairwiseProductFast — неверный ($27$).

💡 Остановитесь и подумайте:
Как может выйти, что MaxPairwiseProductFast выдаёт $27$?

Чтобы избавиться от багов в первом решении, давайте проверим, какие два числа он считает наибольшими.
Для этого мы добавим следующую строку перед return в функции MaxPairwiseProductFast:

print(index_1, index_2)

Когда мы снова начинаем стресс-тестирование, мы получаем следующее:

...  
7 3 6  
OK  
2 9 3 1 9  
2 3  
Wrong answer: 81 27  

Обратите внимание, что наши решения работали и давали сбой на одних и тех же примерах тестирования, так как мы ничего не меняли в генераторе тестов.
Он использует псевдослучайные числа при создании тестов вместо действительно случайных.
Это значит, что последовательность выглядит случайной, но она одинакова каждый раз, когда работает программа.
Такое свойство удобно и важно. Советуем вам использовать эту практику, потому что в детерминированных программах (тех, что всегда выдают одинаковый результат при одинаковых вводных данных) легче находить баги, чем в недетерминированных.

Давайте теперь рассмотрим $index_1=2$ и $index_2=3$. Если мы обратим внимание на код для определения второго максимального числа, то заметим неочевидный баг.
Когда мы использовали условие для $i$ (число не должно быть таким же, как предыдущее самое большое), вместо сравнения $i$ и $index_1$ мы сравнили $A[i]$ и $A[index_1]$.
Это означает, что второе максимальное число отличается от первого по значению, а не по индексу элемента, который мы выбрали для решения задачи.
Так, наше решение не работает при любом тесте, в котором второе самое большое число равно первому.
Теперь изменим условие: вместо

A[i] != A[index_1]

мы используем

i != index_1

Проведя стресс-тестирование еще раз, мы видим на экране шквал сообщений OK. Ждём минуту, пока нам не надоест, и заключаем, что MaxPairwiseProductFast наконец-то работает правильно!

Однако не стоит останавливаться на этом, так как вы сгенерировали только очень маленькие тесты с $N=5$ и $M=10$.
Теперь нужно проверить, работает ли наша программа при большем $n$ и бо́льших элементах массива.
Таким образом, мы меняем $N$ на $1,000$ (при большем $N$ примитивное решение будет довольно медленным из-за квадратичного времени выполнения).
Мы также меняем $M$ на $200,000$ и запускаем программу.
Ещё раз наблюдаем, как экран заполняется сообщениями OK. Затем ждём минуту, а потом решаем, что MaxPairwiseProductFast действительно работает верно.
После этого мы сдаём получившееся решение системе оценки и успешно проходим тест!

Как вы можете заметить, даже при решении такой простой задачи как Максимальное попарное произведение сложно избежать
труднораспознаваемых ошибок на этапе проектирования и реализации алгоритма. Приведённый ниже псевдокод — это пример более надежного способа реализации алгоритма.

MaxPairwiseProductFast(A[1..n]):
    index = 1
    for i from 2 to n
        if A[i] > A[index]:
            index = i
    swap(A[index], A[n]) // поставим наибольшее значение в конец массива
    index = 1:
    for i from 2 to n - 1
        if A[i] > A[index]:
            index = i
    swap(A[index], A[n - 1]) // поставим второй по величине элемент предпоследним
    return A[n - 1] * A[n]

В этой книге вы узнаете, как проектировать и реализовывать алгоритмы так, чтобы минимизировать вероятность ошибок. А заодно научитесь тестировать вашу реализацию.

Ещё более быстрый алгоритм

Алгоритм MaxPairwiseProductFast находит два самых больших числа примерно за $2n$ сравнений.

💡 Остановитесь и подумайте:
Найдите два самых больших элемента в массиве за $1.5n$ сравнений.

Когда вы решите эту задачу, вас ждет ещё более сложное упражнение. Попробуйте с ним справиться!

💡 Остановитесь и подумайте:
Найдите два самых наибольших элемента в массиве за $n + lceil log_2 n rceil — 2$ сравнений.

Если это упражнение показалось вам слишком простым, посмотрите задачи ниже. Они вполне могут оказаться на следующем собеседовании!

✒️ Упражнение:
Докажите, что не существует алгоритма, которому потребуется менее $n + lceil log_2 n rceil — 2$ сравнений, чтобы найти два самых больших элемента массива.

✒️ Упражнение:
Какой алгоритм найдёт три самых больших элемента быстрее всего?

Более компактный алгоритм

Задачу Максимальное попарное произведение можно решить с помощью следующего компактного алгоритма, который использует сортировку (в неубывающем порядке).

MaxPairwiseProductBySorting(A[1..n]):
    Sort(A)
    return A[n-1]*A[n]

Этот алгоритм делает даже больше, чем нам нужно: вместо того, чтобы найти два самых больших элемента, он сортирует весь массив.
Поэтому его время выполнения $O(nlog n)$, а не $O(n)$. Однако для таких ограничений ($2 le n le 2 cdot 10^5$) он достаточно быстрый, чтобы выполнить задачу за секунду и успешно пройти тесты в нашей систему оценки.

Время на прочтение
7 мин

Количество просмотров 7.9K

Постановка вопроса: как найти декартово произведение произвольного количества последовательностей с помощью LINQ?

Для начала, давайте убедимся, что мы знаем, о чем идет речь. Я буду обозначать последовательности как упорядоченные множества: {a, b, c, d...} Декартово произведение двух последовательностей S1 и S2 есть последовательность всех возможных упорядоченных пар таких, что их первый элемент из S1, а второй — из S2. Так, к примеру, если у вас есть две последовательности {a, b} и {x, y, z}, то их декартово произведение выглядит как {{a, x}, {a, y}, {a, z}, {b, x}, {b, y}, {b, z}}.

Для упрощения, предположим, что S1 и S2 состоят из элементов одного типа. Разумеется, мы можем определить декартово произведение последовательности строк с последовательностью чисел как последовательность кортежей (string, int), но впоследствии это окажется тяжело обобщать, потому что система типов C#, в частности, не лучшим образом работает с кортежами произвольной длины.

В LINQ есть оператор специально для вычисления декартовых произведений: в «синтаксисе методов» это SelectMany, в «синтаксисе запросов» это запрос с двумя выражениями «from»:

var s1 = new[] {a, b}; <br/>
var s2 = new[] {x, y, z}; <br/>
var product =  <br/>
    from first in s1 <br/>
    from second in s2 <br/>
    select new[] { first, second };

Конечно же, мы можем обобщить декартово произведение на более чем две последовательности. Декартово произведение n последовательностей {S1, S2, ... , Sn} есть последовательность всех возможных n-элементных последовательностей, у которых первый элемент из S1, второй из S2 и т.д.

В этом определении не хватает тривиального случая: что есть декартово произведение нуля последовательностей? Пускай в таком случае оно состоит из последовательности, содержащей единственный элемент: пустую последовательность, то есть { { } }.

Обратите внимание, что это дает логичное определение декартова произведения одной последовательности. Декартово произведение последовательности, содержащей одну-единственную последовательность (скажем, {{a, b}}) есть последовательность всех возможных одноэлементых последовательностей, где первый (и единственный) элемент из {a, b}. Таким образом, декартово произведение {{a, b}} есть {{a}, {b}}.

С помощью LINQ вы можете составить декартово произведение любого количества последовательностей достаточно просто, если вы изначально знаете, с каким количеством будете работать:

var product =  <br/>
    from first in s1 <br/>
    from second in s2 <br/>
    from third in s3 <br/>
    select new[] {first, second, third};

Но что делать, если вы не знаете на этапе написания кода, сколько у вас будет последовательностей? То есть, как написать тело функции:

public static IEnumerable<IEnumerable<T>> CartesianProduct<T>(this IEnumerable<IEnumerable<T>> sequences)

Что ж, есть причина использовать индукцию; эта идея практически никогда не подводит при работе с рекурсивно определенными структурами данных.

Если sequences содержит ноль последовательностей, дело сделано: мы просто возвращаем { { } }.

Как найти декартово произведение двух последовательностей, скажем, снова {a, b} и {x, y, z}? Начнем с подсчета декартова произведения первой последовательности. Пускай индуктивное предположение состоит в том, что мы каким-либо образом сделали это, так что мы знаем ответ: {{a}, {b}}. Как соединить {{a}, {b}} с {x, y, z}, чтобы получить общее произведение?

Давайте вернемся в поисках вдохновения к изначальному определению декартова произведения двух последовательностей. Декартово произведение {{a}, {b}} и {x, y, z} — беспорядочное {{{a}, x}, {{a}, y}, {{a}, z}, {{b}, x}, {{b}, y}, {{b},z}}, которое, тем не менее, соблазнительно близко к тому, что мы хотим получить. Мы не просто хотим найти декартово произведение {{a}, {b}} и {x, y, z}, создавая последовательность, содержащую {a} и x, но нет, вместо этого нам нужно вычислить декартово произведение, присоединяя x к {a}, чтобы получить {a, x}! Другими словами, конкатенируя {a} и {x}.

В терминах кода: пускай у нас есть старое декартово произведение, скажем {{a}, {b}}. Мы хотим соединить его с последовательностью {x, y, z}:

var newProduct =  <br/>
    from old in oldProduct <br/>
    from item in sequence <br/>
    select old.Concat(new[]{item}};

И теперь у нас есть благополучный индукционный переход. Если oldProduct — любое декартово произведение, то мы можем вычислить его комбинацию с другой последовательностью, чтобы получить новое декартово произведение.

На всякий пожарный: этот метод работает с основой индукции? Да. Если мы хотим скомбинировать декартово произведение { { } } с последовательностью {{a}, {b}}, мы склеиваем { } с {a} и { } с {b}, чтобы получить {{a}, {b}}.

Давайте соберем все это вместе:

static IEnumerable<IEnumerable<T>> CartesianProduct<T>(this IEnumerable<IEnumerable<T>> sequences) <br/>
{ <br/>
    // основа индукции: <br/>
    IEnumerable<IEnumerable<T>> result = new[] { Enumerable.Empty<T>() }; <br/>
    foreach(var sequence in sequences) <br/>
    { <br/>
        var s = sequence; // нельзя замыкаться на переменную цикла <br/>
        // индукционный переход: используем SelectMany, чтобы построить новое произведение из старого <br/>
        result =  <br/>
            from seq in result <br/>
            from item in s <br/>
            select seq.Concat(new[] {item}); <br/>
    } <br/>
    return result; <br/>
} 

Работает отлично, но при желании можно сделать чуточку красивее. По существу мы здесь используем аккумулятор. Рассмотрим пример проще, скажем, суммирование списка целых чисел. Один из способов сделать это — сказать «Пусть аккумулятор вначале равен нулю. Новый аккумулятор получается из старого путем добавления текущего элемента к старому аккумулятору». Если у нас есть стартовое значение аккумулятора и мы некоторым образом можем получить новое значение из старого и из текущего элемента последовательности, тогда можно использовать полезный метод Aggregate. Он принимает стартовое значение аккумулятора и функцию, которая принимает последнее значение и текущий элемент и возвращает новое значение аккумулятора. На выходе метода — итоговое значение аккумулятора.

В данном случае мы начнем с пустым произведением в качестве аккумулятора, и каждый раз мы будем «добавлять» к нему путем комбинирования текущей последовательности с произведением предыдущих. На каждом шаге алгоритма, аккумулятор равен декартовому произведению уже просмотренных последовательностей.

static IEnumerable<IEnumerable<T>> CartesianProduct<T>(this IEnumerable<IEnumerable<T>> sequences) <br/>
{ <br/>
    IEnumerable<IEnumerable<T>> emptyProduct = new[] { Enumerable.Empty<T>() }; <br/>
    return sequences.Aggregate( <br/>
        emptyProduct, <br/>
        (accumulator, sequence) =>  <br/>
            from accseq in accumulator  <br/>
            from item in sequence  <br/>
            select accseq.Concat(new[] {item}));                <br/>
}

И напоследок несколько слов для разбирающихся. Помните, результат LINQ-запроса есть запрос, который предоставит результаты по требованию, а не результаты непосредственно. Когда мы строим этот аккумулятор, мы вообще-то не вычисляем декартово произведение. Мы строим большой сложный запрос, который при запуске выдаст декартово произведение. Запрос строится энергично, но выполняться будет лениво.

От переводчика

Эрик обошел в своем посте конкретное название идиомы, которую он использовал, а именно свертки. Впрочем, на эту тему на Хабрахабре уже были посты. Интересующийся может найти отличный перевод «Катаморфизм в F#».

Ту же задачу, гораздо менее многословно, но с тем же алгоритмом, можно решить и на F#. Вместо LINQ в код хорошо впишутся списочные выражения (list comprehensions) — одна из замечательных фич, традиционно свойственных функциональным языкам. Для достижения большей производительности приклеивать элемент к списку стоит с головы, оператором (::). В таком случае для достижения классического вида декартова произведения исходную последовательность перед началом работы придется перевернуть.

В сумме свертка, пайплайны и списочные выражения дадут вот такой красивый код:

let product seqs =
    List.rev seqs
    |> List.fold
        (fun acc cur ->
            [for seq in acc do
                for item in cur do
                    yield item::seq]) [[]]

Доброй ночи.
Второй день пытаюсь решить поставленную задачу. Сам я новичок, практикуюсь ежедневно по несколько часов, но случилась какая-то напасть, не могу решить и все. Не сплю практически, все думаю над решением.
Прошу сердечно помочь, растолкуйте пожалуйста, я в тупике.

Задача:
Посчитайте произведение всех чисел последовательности, заканчивающейся нулем. Если чисел в последовательности нет – выведите нейтральное для произведения число – 1.

Ввод:

Последовательность чисел, каждое в новой строке

Вывод:

res – произведение всех чисел

Sample Input: 1 2 -1 0
Sample Output: -2

tasks = [1]
n = int(input())
while n:
    tasks.append(n)
    n = int(input())
if len(tasks) == 1:
    print(*tasks)
else:
    del tasks[0]
    print(abs(int(*tasks[:1])) - abs(int(*tasks[1:(len(tasks))-1])) - abs(int(*tasks[(len(tasks))-1:(len(tasks))])))

Неверное решение #806248107
Python 3.10
Failed test #2 of 3. Runtime error

Error:
Traceback (most recent call last):
File «/sandbox/main.py», line 10, in
print(abs(int(*tasks[:1])) — abs(int(*tasks[1:(len(tasks))-1])) — abs(int(*tasks[(len(tasks))-1:(len(tasks))])))
TypeError: int() takes at most 2 arguments (5 given)

ЦИКЛЫ(ЗАДАЧИ).

---

Пример один:

Один из друзей открыл свою смузишную. Как настоящий стартап на блокчейне, смузишная не может обойтись без автоматического приёма заказов. Иначе кастомеры получат неоптимальный экспириенс и оставят негативный фидбек. Короче, надо помочь другу.

Напишите программу, которая формирует заказ в виде строки.

• Массив с вариантами основы для смузи записан в переменную liquids.

• Массив с фруктами находится в переменной fruits.

• Массив с зеленью записан в переменную greens.

• Выбор посетителя записан в виде чисел в переменные chosenLiquid (номер выбранной основы для смузи), chosenFruit (выбранный фрукт), chosenGreen (выбранная зелень).

• Обрати внимание, что посетители выбирают пункты в электронном меню, где нумерация начинается с единицы, а не с нуля, как в массивах. Учти это при решении.

• Собери строку с заказом посетителя вида ‘Основа — ‘ + основа для смузи + ‘, фрукт — ‘ + выбранный фрукт + ‘, зелень — ‘ + выбранная зелень. Точка в конце строки не нужна.

• Запиши результат в переменную order.

// Состав смузи

var liquids = ['вода', 'молоко', 'сок', 'чай', 'йогурт'];
var fruits = ['киви', 'банан', 'персик', 'манго', 'груша', 'ананас'];
var greens = ['мята', 'шпинат', 'руккола', 'петрушка', 'базилик'];

// Выбор посетителя

var chosenLiquid = 1;
var chosenFruit = 3;
var chosenGreen = 2;

// Заказ

var order = 'Основа — '+ liquids[chosenLiquid-1] + ', фрукт — ' + fruits[chosenFruit-1] + ', зелень — '+ greens[chosenGreen-1];//вычитаем единицу,поскольку нумерация массивов начинается с нуля, а клиенты выбирают с единицы.

---

Пример два:

Геометрическая прогрессия — последовательность чисел, где каждое следующее число — это предыдущее, увеличенное на множитель.

Например, нужно написать геометрическую прогрессию из пяти чисел, начиная с единицы. Множитель — двойка. Тогда числа будут такими: 1, 2, 4, 8, 16. Здесь каждое следующее число — произведение предыдущего числа и множителя (двойки).

Напишите программу, которая последовательно выводит в консоль числа в геометрической прогрессии.

• Стартовое значение, с которого должна начаться последовательность, записано в переменную startNumber.

• Множитель записан в переменную multiplier.

• Количество чисел записано в переменную quantity.

var startNumber = 1;
var multiplier = 4;
var quantity = 7;

for(var i = 0; i < quantity; i++){
  console.log(startNumber);
/*
  Первое число прогрессии
  это стартовое значение переменной startNumber.
  Оно не вычисляется, а берется из условия задачи.
  Поэтому сперва console.log(startNumber);
  а уже потом производим вычисления в цикле.
*/
  startNumber *= multiplier;
}

---

Пример три:

Есть такая детская математическая головоломка, в которой нужно найти самый быстрый способ посчитать сумму чисел от 1 до 100. В наших руках не просто ручка и листочек, а JavaScript и циклы, поэтому мы можем написать универсальную программу, которая сможет находить суммы любых чисел.

Напишите универсальную программу, которая вычисляет сумму чисел от 1 до n.

• Число, до которого нужно складывать числа (включительно), указано в переменной lastNumber.

• Найдите сумму всех чисел и сохраните результат в переменную sum.

var lastNumber = 10;
var sum = 0;

for(var i = 0; i <= lastNumber; i++){
  sum += i;
  }

---

Пример четыре:

Кроме суммы чисел от 1 до n можно ещё найти их произведение. Но в этот раз задача усложнилась — нужно найти произведение не всех чисел из последовательности, а только чётных.

Напишите универсальную программу, которая находит произведение всех чётных чисел из последовательности от 1 до n.

• Число, до которого идёт последовательность (включительно), записано в переменную lastNumber

• Найдите произведение всех чисел и сохраните результат в переменную multiplicationResult.

var lastNumber = 5;
var multiplicationResult = 1;

for(var i = 1; i <= lastNumber; i++){
  if(i %2 === 0){
    multiplicationResult *= i;
  }
}
  console.log(multiplicationResult);

---

Пример пять:

Напишите программу, которая находит все делители числа, кроме единицы и самого числа.

Число, делители которого нужно найти, записано в переменную number.

Выводите делители в консоль последовательно, друг за другом.

Делитель — число, на которое другое число делится без остатка. Например, у числа 119 четыре делителя, на которые это число делится без остатка: 1, 7, 17, 119. Для нашей задачи единица и само число не подходят. Поэтому в результате остаётся два числа: 7, 17.

Чтобы узнать есть ли остаток от деления двух чисел, нужно использовать оператор «остаток от деления». Он обозначается знаком процента (%) и возвращает остаток от деления чисел. Если остатка от деления нет, вернётся 0. Выглядит это так:

12 % 5;  // Вернёт 2
27 % 3;  // Вернёт 0
13 % 3;  // Вернёт 1

Решение:

var number = 15;

for(var i = 0; i <= number; i++){
  if(number %i === 0 && i != number && i !=1){
    console.log(i);
    }
  }

---

Пример шесть:

Напишите программу, которая определяет сколько цифр в одном целом числе.

• Само число записано в переменную number.

• Найдите количество цифр в этом числе и запиши результат в переменную quantity.

var number = 123;
var quantity = 0;

quantity=(number.toString()).length;
console.log(quantity);

---

Пример семь:

Пришло время для собственной программы, которая поможет правильно запастись протеином на любой период, например, на 15 или на 25 дней.

Программа усложняется тем, что принимать протеин надо не каждый день, а раз в три дня, да ещё и разное количество в будние дни и в выходные. Впрочем, вот техническое задание:

Программа должна считать количество протеина необходимое на период.

• Во-первых, расчёт всегда начинается с понедельника. Это первый день.

• Во-вторых, я принимаю протеин каждый третий день:

  • 2 день, вторник — нет,
  • 23 день, среда — да,
  • 24 день, четверг — нет,
  • 25 день, пятница — нет,
  • 26 день, суббота — да,
  • 27 день, воскресенье — нет,
  • 28 день, понедельник — нет,
  • 29 день, вторник — да
    и так далее.

• В-третьих, известно, сколько протеина я съедаю в будние и сколько в выходные дни.

• В-четвёртых, период задаётся целым числом, от одного до бесконечности (хотя планы дальше чем на месяц я обычно не строю).

• Программа должна возвращать общее количество протеина за период, записанное в переменную total.

• Количество дней хранится в переменной days, количество протеина для буднего дня — в переменной workDayAmount, для выходного — в переменной weekendAmount, период получения протеина — в переменной period, а результат необходимо записать в переменную total.

Конечно, в этой программе будет удобно использовать цикл, в котором будет накапливаться количество протеина.

var total = 0;
var days = 9; // Дней в периоде
var period = 3; // Как часто я ем протеин (раз в три дня)
var workDayAmount = 200; // Количество протеина в будние
var weekendAmount = 100; // Количество протеина в выходные

for(var i = period ; i <= days; i += period){
  if( (i % 7) == 6 || (i % 7) == 0){
    total += weekendAmount;
    }
    else{
      total +=  workDayAmount
    }
    }

---

Пример восемь:

Палиндромы — это слова или фразы, которые одинаково читаются слева направо и справа налево. Среди чисел тоже есть палиндромы. Например, 3223 или 1001.

В этом задании вам нужно написать программу, которая будет определять является ли число палиндромом.

Алгоритм такой: нужно записать изначальное число задом наперёд и сравнить этот вариант с изначальным. Если оба числа равны — перед нами палиндром.

Напишите программу, которая проверяет, является ли число палиндромом.

• Число записано в переменную poly.

• Переменная, куда нужно записать «перевёрнутую» версию числа, называется ylop.

• Выясни, является ли число из переменной poly палиндромом. Если да, значение флага isPalindrome должно быть true, если число не палиндром, то false.

Это решение самое простое, поскольку все числа палендромы при делении на 11 дают остаток 0.

var poly = 1221;
var ylop = 0;
var isPalindrome = false;

if(poly %11 == 0){
  isPalindrome = true;
  }
else{
  isPalindrome= false;
  }