Форум программистов, компьютерный форум, киберфорум
C# для начинающих
Войти
Регистрация
Восстановить пароль
Блоги Сообщество Поиск Заказать работу  
 
Рейтинг 4.92/37: Рейтинг темы: голосов - 37, средняя оценка - 4.92
0 / 0 / 0
Регистрация: 03.10.2011
Сообщений: 26

Сумма элементов массива

03.10.2011, 22:19. Показов 6993. Ответов 18
Метки нет (Все метки)

Студворк — интернет-сервис помощи студентам
Нужно на C# разработать алгоритм нахождения наиболее близкой к заданному целому числу суммы элементов заданного массива. Я уже весь мозг сломал, но никак не могу придумать алгоритм...
0
Лучшие ответы (1)
Programming
Эксперт
39485 / 9562 / 3019
Регистрация: 12.04.2006
Сообщений: 41,671
Блог
03.10.2011, 22:19
Ответы с готовыми решениями:

Количество положительных элементов массива, сумма элементов массива после последнего элемента, равного нулю
В одномерном массиве, который состоит из n действительных элементов, рассчитать: а) количество положительных элементов массива; б) сумму...

Сумма элементов массива
using System; using System.Collections.Generic; using System.Linq; using System.Text; using System.Threading.Tasks; using...

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

18
Эксперт .NET
 Аватар для kolorotur
17823 / 12973 / 3382
Регистрация: 17.09.2011
Сообщений: 21,261
03.10.2011, 22:27
Первое, что пришло в голову:

1. Отсортировать массив по возрастанию
2. Начиная с первого, складывать элементы массива друг с другом до тех пор, пока сумма не будет больше указанного числа.
3. Добавляем предыдущую сумму в массив "близких решений".
4. Повторить до конца массива или пока сумма двух рядом стоящих элементов не будет выше указанной.
5. Сравнить разницу указанного числа и сумм из массива "близких решений". Число, которое на выходе даст наименьшее значение - наш ответ.
0
0 / 0 / 0
Регистрация: 03.10.2011
Сообщений: 26
03.10.2011, 22:31  [ТС]
А я вот надумал:

1) отсортировать массив по возрастанию;
2) и поделить его на два массива: в первом массиве будут находиться все числа меньше заданного, а во втором все числа больше заданного.
3) А дальше вот я потерял свою мысль
0
Эксперт .NET
 Аватар для kolorotur
17823 / 12973 / 3382
Регистрация: 17.09.2011
Сообщений: 21,261
03.10.2011, 22:48
Вот, накидал наспех.
Массив надвое не делил, просто шел до тех пор, пока сумма двух прилежащих не становится выше заданной:

C#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
static void Main(string[] args)
{
    int[] numbers = new int[200];
 
    Console.WriteLine("Initial array:");
    for (int i = 0; i < numbers.Length; i++) {
        numbers[i] = i + 1;
        Console.Write("{0} ", numbers[i]);
    }
 
    Array.Sort(numbers);
 
    List<int> candidates = new List<int>();
    int target = 120;
    Console.WriteLine("\r\nTarget number is {0}", target);
 
    for (int i = 0; i < numbers.Length-1 && numbers[i] + numbers[i+1] <= target; i++) {
        int sum = numbers[i];
        Console.Write(sum);
        for (int j = i + 1; j < numbers.Length && sum + numbers[j] <= target; j++) {
            Console.Write(" + {0}", numbers[j]);
            sum += numbers[j];
        }
        Console.WriteLine(" = {0}", sum);
        candidates.Add(sum);
    }
 
    int result = 0;
    int diff = target;
    for (int i = 0; i < candidates.Count; i++)
        if (target - candidates[i] < diff) {
            diff = target - candidates[i];
            result = i;
        }
 
    Console.WriteLine("The closest sum is {0}", candidates[result]);
}
0
0 / 0 / 0
Регистрация: 03.10.2011
Сообщений: 26
03.10.2011, 22:50  [ТС]
Цитата Сообщение от kolorotur Посмотреть сообщение
Первое, что пришло в голову:

1. Отсортировать массив по возрастанию
2. Начиная с первого, складывать элементы массива друг с другом до тех пор, пока сумма не будет больше указанного числа.
3. Добавляем предыдущую сумму в массив "близких решений".
4. Повторить до конца массива или пока сумма двух рядом стоящих элементов не будет выше указанной.
5. Сравнить разницу указанного числа и сумм из массива "близких решений". Число, которое на выходе даст наименьшее значение - наш ответ.
Ну например, массив { 1, 8, 10, 11, 55, 60 } Заданное число 22. Этот алгоритм найдет только сумму 21 ( из 10 и 11), а правильная сумма будет : 1 + 10 + 11 = 22
0
Эксперт .NET
 Аватар для kolorotur
17823 / 12973 / 3382
Регистрация: 17.09.2011
Сообщений: 21,261
03.10.2011, 23:13
antojka, я там выше код привел - попробуйте его модифицировать под ваш массив и требуемое число. Если ответ будет неправильным - дайте знать.

Кстати, сейчас мысль пришла об оптимизации: разность ведь можно и сразу вычислять по ходу перебора, а не оставлять на потом. Если разность равна 0 - наилучший результат найден. Думаю, это сэкономит прилично итераций.
0
0 / 0 / 0
Регистрация: 03.10.2011
Сообщений: 26
03.10.2011, 23:17  [ТС]
Цитата Сообщение от kolorotur Посмотреть сообщение
antojka, я там выше код привел - попробуйте его модифицировать под ваш массив и требуемое число. Если ответ будет неправильным - дайте знать.

Кстати, сейчас мысль пришла об оптимизации: разность ведь можно и сразу вычислять по ходу перебора, а не оставлять на потом. Если разность равна 0 - наилучший результат найден. Думаю, это сэкономит прилично итераций.
Компилатор нашел там 10 ошибок, помогите их найти пожалуйста
0
Эксперт .NET
 Аватар для kolorotur
17823 / 12973 / 3382
Регистрация: 17.09.2011
Сообщений: 21,261
03.10.2011, 23:18
Я его из студии скопировал, сразу после тестирования, так что ошибок не должно быть.
Какие ошибки выдает?
0
0 / 0 / 0
Регистрация: 03.10.2011
Сообщений: 26
03.10.2011, 23:20  [ТС]
Error 1 Expected class, delegate, enum, interface, or struct c:\users\antojka\documents\visual studio 2010\Projects\Project3\Project3\CodeFile 1.cs 1 8 Project3
Error 2 Identifier expected c:\users\antojka\documents\visual studio 2010\Projects\Project3\Project3\CodeFile 1.cs 1 25 Project3
Error 3 Expected class, delegate, enum, interface, or struct c:\users\antojka\documents\visual studio 2010\Projects\Project3\Project3\CodeFile 1.cs 1 27 Project3
Error 4 Identifier expected c:\users\antojka\documents\visual studio 2010\Projects\Project3\Project3\CodeFile 1.cs 3 13 Project3
Error 5 Expected class, delegate, enum, interface, or struct c:\users\antojka\documents\visual studio 2010\Projects\Project3\Project3\CodeFile 1.cs 3 15 Project3
Error 6 Expected class, delegate, enum, interface, or struct c:\users\antojka\documents\visual studio 2010\Projects\Project3\Project3\CodeFile 1.cs 3 29 Project3
Error 7 Identifier expected c:\users\antojka\documents\visual studio 2010\Projects\Project3\Project3\CodeFile 1.cs 3 33 Project3
Error 8 Expected class, delegate, enum, interface, or struct c:\users\antojka\documents\visual studio 2010\Projects\Project3\Project3\CodeFile 1.cs 7 28 Project3
Error 9 Expected class, delegate, enum, interface, or struct c:\users\antojka\documents\visual studio 2010\Projects\Project3\Project3\CodeFile 1.cs 8 49 Project3
Error 10 Type or namespace definition, or end-of-file expected c:\users\antojka\documents\visual studio 2010\Projects\Project3\Project3\CodeFile 1.cs 9 9 Project3
0
 Аватар для WonderFlik
208 / 138 / 15
Регистрация: 28.04.2011
Сообщений: 389
03.10.2011, 23:24
Лучший ответ Сообщение было отмечено как решение

Решение

мне кажется в задании речь идет о паре элементов) хотя хз
C#
1
2
3
4
5
6
7
8
9
            double[] arr = { 1, 8, 10, 11, 55, 60 };
            double number = 22;
            var min = arr.
                SelectMany((x, y) => arr.
                    Where((i, j) => y != j).
                Select(q => new { first = x, second = q, sum = x + q })).ToList()
                  .OrderBy(z => (number - z.sum) >= 0 ? (number - z.sum) : z.sum - number).First();
            Console.WriteLine("Ближе всего к {0} суммa элементов {1} и {2} равная {3}", number, min.first, min.second, min.sum);
            Console.ReadKey();
0
0 / 0 / 0
Регистрация: 03.10.2011
Сообщений: 26
03.10.2011, 23:25  [ТС]
Цитата Сообщение от WonderFlik Посмотреть сообщение
мне кажется в задании речь идет о паре элементов) хотя хз
C#
1
2
3
4
5
6
7
8
9
            double[] arr = { 1, 8, 10, 11, 55, 60 };
            double number = 22;
            var min = arr.
                SelectMany((x, y) => arr.
                    Where((i, j) => y != j).
                Select(q => new { first = x, second = q, sum = x + q })).ToList()
                  .OrderBy(z => (number - z.sum) >= 0 ? (number - z.sum) : z.sum - number).First();
            Console.WriteLine("Ближе всего к {0} суммa элементов {1} и {2} равная {3}", number, min.first, min.second, min.sum);
            Console.ReadKey();
Нет не о паре, а о лучшей сумме элементов, я уточнял у препода
0
Эксперт .NET
 Аватар для kolorotur
17823 / 12973 / 3382
Регистрация: 17.09.2011
Сообщений: 21,261
03.10.2011, 23:29
antojka, похоже у вас где-то скобочка фигурная не закрыта.
А вообще похоже вы правы, в вашем примере 22 не найдется по моему алгоритму. Щас подумаем
0
0 / 0 / 0
Регистрация: 03.10.2011
Сообщений: 26
03.10.2011, 23:37  [ТС]
Цитата Сообщение от WonderFlik Посмотреть сообщение
мне кажется в задании речь идет о паре элементов) хотя хз
C#
1
2
3
4
5
6
7
8
9
            double[] arr = { 1, 8, 10, 11, 55, 60 };
            double number = 22;
            var min = arr.
                SelectMany((x, y) => arr.
                    Where((i, j) => y != j).
                Select(q => new { first = x, second = q, sum = x + q })).ToList()
                  .OrderBy(z => (number - z.sum) >= 0 ? (number - z.sum) : z.sum - number).First();
            Console.WriteLine("Ближе всего к {0} суммa элементов {1} и {2} равная {3}", number, min.first, min.second, min.sum);
            Console.ReadKey();
Ну я вообще не понял что тут написано=) я просто еще нуб в синтаксисе СИ#

Добавлено через 33 секунды
Цитата Сообщение от kolorotur Посмотреть сообщение
antojka, похоже у вас где-то скобочка фигурная не закрыта.
А вообще похоже вы правы, в вашем примере 22 не найдется по моему алгоритму. Щас подумаем
Да, интересная задача...

Добавлено через 2 минуты
А что если:

1) отсортировать массив по возрастанию;
2) и поделить его на два массива: в первом массиве будут находиться все числа меньше заданного, а во втором все числа больше заданного.
3) Складывать последний элемент первого массива с первым, вторым, третьим...элементом
0
236 / 173 / 25
Регистрация: 13.11.2010
Сообщений: 425
03.10.2011, 23:40
Цитата Сообщение от antojka Посмотреть сообщение
Складывать последний элемент первого массива с первым, вторым, третьим...элементом
и что это даст? по-моему ничего.
Вообще задача нетривиальная. В лоб не решить. Наверно, есть методы поиска состава суммы. Вам насчет них препод ничего не говорил?
0
 Аватар для Unril
826 / 717 / 110
Регистрация: 06.10.2010
Сообщений: 825
Записей в блоге: 1
03.10.2011, 23:42
C#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
using System;
using System.Collections.Generic;
 
namespace ConsoleApplicationTest {
    public static class Program {
        private static void Main() {
            var input = new[] { 8, 1, 11, 10, 60, 50 };
            const int value = 11;
 
            // Отбираем кандидатов.
            var challengers = new List<int>();
            foreach ( var i in input ) {
                if ( i <= value ) {
                    challengers.Add( i );
                }
            }
 
            // Перебираем все сочетания.
            int count = challengers.Count;
            var mask = new int[count];
            for ( int n = 0; n <= Math.Pow( 2, count ); n++ ) {
                // Вычисляем сумму.
                int sum = 0;
                for ( int i = 0; i < count; i++ ) {
                    sum += mask[ i ]*challengers[ i ];
                }
 
                // Проверяем соответствие.
                if ( sum == value ) {
                    Console.WriteLine( "Найдено решение: " );
                    for ( int i = 0; i < count; i++ ) {
                        if ( mask[ i ] == 1 ) {
                            Console.Write( challengers[ i ] + "  " );
                        }
                    }
                    Console.WriteLine();
                    Console.WriteLine( " ---- " );
                }
 
                // Получаем следующее сочетание.
                for ( int i = 0; i < count; i++ ) {
                    if ( i > 0 ) {
                        mask[ i - 1 ] = 0;
                    }
                    if ( mask[ i ] == 0 ) {
                        mask[ i ] = 1;
                        break;
                    }
                }
            }
 
            Console.ReadKey();
        }
    }
}
2
0 / 0 / 0
Регистрация: 03.10.2011
Сообщений: 26
03.10.2011, 23:47  [ТС]
Цитата Сообщение от Unril Посмотреть сообщение
C#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
using System;
using System.Collections.Generic;
 
namespace ConsoleApplicationTest {
    public static class Program {
        private static void Main() {
            var input = new[] { 8, 1, 11, 10, 60, 50 };
            const int value = 11;
 
            // Отбираем кандидатов.
            var challengers = new List<int>();
            foreach ( var i in input ) {
                if ( i <= value ) {
                    challengers.Add( i );
                }
            }
 
            // Перебираем все сочетания.
            int count = challengers.Count;
            var mask = new int[count];
            for ( int n = 0; n <= Math.Pow( 2, count ); n++ ) {
                // Вычисляем сумму.
                int sum = 0;
                for ( int i = 0; i < count; i++ ) {
                    sum += mask[ i ]*challengers[ i ];
                }
 
                // Проверяем соответствие.
                if ( sum == value ) {
                    Console.WriteLine( "Найдено решение: " );
                    for ( int i = 0; i < count; i++ ) {
                        if ( mask[ i ] == 1 ) {
                            Console.Write( challengers[ i ] + "  " );
                        }
                    }
                    Console.WriteLine();
                    Console.WriteLine( " ---- " );
                }
 
                // Получаем следующее сочетание.
                for ( int i = 0; i < count; i++ ) {
                    if ( i > 0 ) {
                        mask[ i - 1 ] = 0;
                    }
                    if ( mask[ i ] == 0 ) {
                        mask[ i ] = 1;
                        break;
                    }
                }
            }
 
            Console.ReadKey();
        }
    }
}
Вау, классно, спасибо огромное!!
0
 Аватар для WonderFlik
208 / 138 / 15
Регистрация: 28.04.2011
Сообщений: 389
03.10.2011, 23:53
чо то я кроме 11 не нашел цифры при которой ответ был бы правильным)
тестил с value = 8 10 40 -8 25 может у меня одного так
0
0 / 0 / 0
Регистрация: 03.10.2011
Сообщений: 26
04.10.2011, 00:24  [ТС]
Цитата Сообщение от WonderFlik Посмотреть сообщение
чо то я кроме 11 не нашел цифры при которой ответ был бы правильным)
тестил с value = 8 10 40 -8 25 может у меня одного так
Не знаю, но вот этот проканал массив { 1, 8, 10, 11, 55, 60 } Заданное число 22

Добавлено через 2 минуты
Ну с отрицательными он не выдает результата. Но это можно подправить!

Добавлено через 1 минуту
И не выдает результата, когда заданное число больше суммы всех элементов массива(((

Добавлено через 7 минут
1) отсортировать массив по возрастанию;
2) и поделить его на два массива: в первом массиве будут находиться все числа меньше заданного, а во втором все числа больше заданного;
3) Складывать последний элемент первого массива с первым, вторым, третьим...элементом, до тех пор пока не превысит заданного (записываем, пока что, эту сумму в лучшую);
4) Далее складываем, опять, последний элемент, но уже со вторым и проверяем ближе эта сумма или нет ( Если нет то суммировать дальше нет смысла );
5) Берем следующий элемент с конца и проделываем 3-й и 4-й пункты с ним;

На бумаге прокручивал этот алгоритм, вроде работает!

Добавлено через 14 минут
Это если заданное число меньше самого большого значения в массиве... А если больше то хз, надо доработать
0
98 / 81 / 16
Регистрация: 14.01.2011
Сообщений: 438
05.10.2011, 00:40
Кстати в этом алгоритме есть недостаток.Если у нас отобранный массив состоит из 4 элементов(как в примере),то он повторяет проверять сочетания дважды 4 элемента и сочетания 1 и 4 элементов.Таким образом если поменять местами вначале массив хотя бы так:
C#
1
2
var input = new[] { 8, 1, 10, 11, 60, 50 };
const int value = 11;
то будет 2 раза выдавать число 11. Это происходит в двух последних итерациях главного цикла,но если изменить длину,уменьшив на 2,то всё будет ок,правда не тестил ещё для более длинных массивов,но я думаю,что после определённого числа он будет повторять сочетания. Вот если сделать так,то всё ок:
C#
1
for ( int n = 0; n <= Math.Pow( 2, count )-2; n++ ) {
Но алгоритм классный бесспорно!
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
inter-admin
Эксперт
29715 / 6470 / 2152
Регистрация: 06.03.2009
Сообщений: 28,500
Блог
05.10.2011, 00:40
Помогаю со студенческими работами здесь

Сумма элементов массива
Здравствуйте! Задание было: Дан одномерный массив, состоящий из n вещественных элементов. Найти сумму элементов массива, находящихся между...

Сумма элементов массива
Определить сумму всех элементов массива

Сумма элементов массива
День добрый! Не могу решить задачу, помогите пожалуйста Условие: Дан одномерный массив. Подсчитать сумму элементов массива,...

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

Сумма элементов массива
Вот задание:Сумму элементов массива, расположенных между первым и последним положительными элементами. Это пример,на одномерный массив. ...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
19
Ответ Создать тему
Новые блоги и статьи
[Owen Logic] Поддержание уровня воды в резервуаре количеством включённых насосов: моделирование и выбор регулятора
ФедосеевПавел 14.03.2026
Поддержание уровня воды в резервуаре количеством включённых насосов: моделирование и выбор регулятора ВВЕДЕНИЕ Выполняя задание на управление насосной группой заполнения резервуара,. . .
делаю науч статью по влиянию грибов на сукцессию
anaschu 13.03.2026
прикрепляю статью
SDL3 для Desktop (MinGW): Создаём пустое окно с нуля для 2D-графики на SDL3, Си и C++
8Observer8 10.03.2026
Содержание блога Финальные проекты на Си и на C++: hello-sdl3-c. zip hello-sdl3-cpp. zip Результат:
Установка CMake и MinGW 13.1 для сборки С и C++ приложений из консоли и из Qt Creator в EXE
8Observer8 10.03.2026
Содержание блога MinGW - это коллекция инструментов для сборки приложений в EXE. CMake - это система сборки приложений. Здесь описаны базовые шаги для старта программирования с помощью CMake и. . .
Как дизайн сайта влияет на конверсию: 7 решений, которые реально повышают заявки
Neotwalker 08.03.2026
Многие до сих пор воспринимают дизайн сайта как “красивую оболочку”. На практике всё иначе: дизайн напрямую влияет на то, оставит человек заявку или уйдёт через несколько секунд. Даже если у вас. . .
Модульная разработка через nuget packages
DevAlt 07.03.2026
Сложившийся в . Net-среде способ разработки чаще всего предполагает монорепозиторий в котором находятся все исходники. При создании нового решения, мы просто добавляем нужные проекты и имеем. . .
Модульный подход на примере F#
DevAlt 06.03.2026
В блоге дяди Боба наткнулся на такое определение: В этой книге («Подход, основанный на вариантах использования») Ивар утверждает, что архитектура программного обеспечения — это структуры,. . .
Управление камерой с помощью скрипта OrbitControls.js на Three.js: Вращение, зум и панорамирование
8Observer8 05.03.2026
Содержание блога Финальная демка в браузере работает на Desktop и мобильных браузерах. Итоговый код: orbit-controls-threejs-js. zip. Сканируйте QR-код на мобильном. Вращайте камеру одним пальцем,. . .
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2026, CyberForum.ru