Помогите с алгоритмом - Компьютерный форум OSzone.net

Компьютерный форум OSzone.net (http://forum.oszone.net/index.php)

- Программирование и базы данных (http://forum.oszone.net/forumdisplay.php?f=21)

- - Помогите с алгоритмом (http://forum.oszone.net/showthread.php?t=272787)

Помогите с алгоритмом

Нужно подсчитать сумму всех элементов остаток от деления которых равен 0.
Задача, оптимизировать, ускорить этот процесс, то есть избегая следующей конструкции (цикла):

Код:

...

for (int i = 0; i < arr.Length; i++)

{

     if (((arr[i] % 3) == 0) || ((arr[i] % 7) == 0))

     count += count + arr[i];

}

...

Цитата:

Цитата nastr

остаток от деления которых равен 0. »

обычно делят что-то на что-то. Что на что делить надо?

Я более точно сформулировал задачу:

Дано:
Отсортированный массив, от 0 до N.
Задание:
Найти оптимальный алгоритм подсчёта суммы значений элементов массива, которые делятся на 3 и на 7 без остатка.

Учитывая условие я не нашел более оптимального алгоритма нежели перебор всех элементов:

Код:

...

int[] arr = new int[2013];

int count = 0;

for (int i = 0; i < arr.Length; i++)

arr[i] = i;

for (int i = 0; i < arr.Length; i++)

{

if (((arr[i] % 3) == 0) || ((arr[i] % 7) == 0))

count += arr[i];

}

...

Можно без массива. Дано N. Найти сумму натуральный чисел, не превосходящих N, которые делятся на 3 и на 7 без остатка.
найти сумма всех чисел не превосходящих N, которые делятся на 3 без остатка.

nastr, выполняйте одну проверку вместо двух, делится ли элемент массива без остатка на 21. Больше тут нечего оптимизировать.

Цитата:

Цитата Leha Ares

nastr, выполняйте одну проверку вместо двух, делится ли элемент массива без остатка на 21. Больше тут нечего оптимизировать. »

Пардон, это далеко не выход. Если я правильно понял условие. Найдется куча чисел, вроде 3, 6, 7, 9, 12, 14, которые делятся то на 3, то на 7. Ну, может, я не так понял. А может, автор не вполне корректно сформулировал, оставив лазейку для побочных интерпретаций.

Leha Ares, 7 на 21 не делится

XPEHOMETP, всё корректно
nastr, у тебя идеальный алгоритм. Либо это олимпиадная задача и требуется хитрость

Хотя... Leha Ares прав:
"на 3 и на 7" проще понять как "и на 3, и на 7", чем "на 3 либо на 7"

Цитата:

Цитата nastr

Вооот, это уже другая задача. Массив-то, как я понимаю, оказывается не просто упорядоченным, а с шагом в 1 (т.к. последовательность натуральных чисел).
Тогда алгоритм весь строится на сумме арифметической прогрессии следующим образом:
Шаг 0. Пусть N = 500 (т.е. числа 1 2 3 4... 499 500)
Шаг 1. Первый член арифметической прогрессии с шагом в 3 [An=3d] - это 3. Последний член прогрессии = mod(500 / 3) * 3 = 166 * 3 = 498 (используем целочисленное деление). Заодно мы в курсе, что последний член прогрессии имеет номер 166.
Шаг 2. Считаем сумму арифметической прогрессии по формуле (в википедии есть) sum = (A1+An)*n/2 = (3 + 498) * 166 / 2 = 41583
Шаг 3. Теперь с семёркой. Тут немного сложнее, т.к. нам надо из суммы исключить числа, делящиеся на 3
Имеем такой ряд: 7 14 28 35 49 56... Т.е. просто An=7d нас не устраивает. Используем хитрость:
Шаг 4. Сначала считаем сумму для прогрессии An=7d. 71 член прогрессии равен 497. Сумма = (7 + 497) * 71 / 2 = 17892
Шаг 5. Теперь нужно исключить числа, делящиеся на 21. Считаем сумму прогрессии An = 21d. 23 член прогрессии равен 483. Сумма = (21 + 483) * 23 / 2 = 5796
Шаг 6. Итоговый результат = 41583 + 17892 - 5796 = 53697.

Для маленького N такой алгоритм не особо эффективен, но для большого - то, что надо. Для предела в 500 значений, в ассемблере получается 40 инструкций для этого алгоритма и около 6500 инструкций для цикла с делением.
Конечно, если у вас массив - это не последовательность натуральных чисел, а просто упорядоченные случайные целые числа больше нуля, то ничего не выйдет, используйте цикл.

Цитата:

Цитата pva

Хотя... Leha Ares прав:
"на 3 и на 7" проще понять как "и на 3, и на 7", чем "на 3 либо на 7" »

В программировании "и" - вполне конкретная логическая операция в противовес "или". В задаче "и", значит и решаем через "и".

Код:

// declaration 

            decimal N = numericUpDown1.Value, loopTotaSum = 0, loopAmount = 0,

                prog3Amount, prog3Sum, prog7Amount, prog7Sum, prog21Amount, prog21Sum;

            System.Diagnostics.Stopwatch st = new System.Diagnostics.Stopwatch();



            // Loop

            st.Start();

            for (int i = 1; i <= N; i++)

            {

                if (i % 3 == 0 || i % 7 == 0)

                {

                    loopTotaSum += i;

                    loopAmount++;

                }

            }

            loopTotaSum_textBox.Text = loopTotaSum.ToString();

            loopAmount_textBox.Text = loopAmount.ToString();

            st.Stop();

            loopStopwatch_textBox.Text = st.ElapsedMilliseconds.ToString();

            st.Reset();



            // Progression

            st.Start();

            prog7Amount = decimal.Truncate(N / 7);

            prog7Sum = (7 + prog7Amount * 7) * prog7Amount / 2; //Сначала считаем сумму для прогрессии An=7d

            prog3Amount = decimal.Truncate(N / 3);

            prog3Sum = (3 + prog3Amount * 3) * prog3Amount / 2; //Считаем сумму арифметической прогрессии An=3d

            prog21Amount = decimal.Truncate(N / 21);

            prog21Sum = (21 + prog21Amount * 21) * prog21Amount / 2; //Нужно исключить числа, делящиеся на 21. Считаем сумму прогрессии An = 21d

            progTotalSum_textBox.Text = Convert.ToString(prog3Sum + prog7Sum - prog21Sum); //Итоговый результат

            prog3Amount_textBox.Text = Convert.ToString(prog3Amount + prog7Amount - prog21Amount);

            st.Stop();

            progStopwatch_textBox.Text = st.ElapsedMilliseconds.ToString();